Variance Reduction in Stochastic Methods for Large-Scale Regularized Least-Squares Problems
Yusuf Yiğit Pılavci, Pierre‐Olivier Amblard, Simon Barthelmé, Nicolas Tremblay · 2022 30th European Signal Processing Conference (EUSIPCO) · 2022
Large dimensional least-squares and regularized least-squares problems are expensive to solve. There exist many approximate techniques, some deterministic (like conjugate gradient), some stochastic (like stochastic gradient descent). Among the latter, a new class of techniques uses Determinantal Point Processes (DPPs) to produce unbiased estimators of the solution. In particular, they can be used to perform Tikhonov regularization on graphs using random spanning forests, a specific DPP. While the unbiasedness of these algorithms is attractive, their variance can be high. We show here that variance can be reduced by combining the stochastic estimator with a deterministic gradient-descent step, while keeping the property of unbiasedness. We apply this technique to Tikhonov regularization on graphs, where the reduction in variance is found to be substantial at very small extra cost.