Unbiased least squares regression via averaged stochastic gradient descent

2024/06/26 by Kahalé, Nabil
#62Jxx 65K05 65C05 #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Methodology (stat.ME)

paper · doi:10.48550/arxiv.2406.18623

Abstract

We consider an on-line least squares regression problem with optimal solution θ^* and Hessian matrix H, and study a time-average stochastic gradient descent estimator of θ^*. For k≥2, we provide an unbiased estimator of θ^* that is a modification of the time-average estimator, runs with an expected number of time-steps of order k, with O(1/k) expected excess risk. The constant behind the O notation depends on parameters of the regression and is a poly-logarithmic function of the smallest eigenvalue of H. We provide both a biased and unbiased estimator of the expected excess risk of the time-average estimator and of its unbiased counterpart, without requiring knowledge of either H or θ^*. We describe an "average-start" version of our estimators with similar properties. Our approach is based on randomized multilevel Monte Carlo. Our numerical experiments confirm our theoretical findings.

Related

• On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression
• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
• Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions
• Iterate averaging as regularization for stochastic gradient descent
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)