# On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression

arXiv: https://arxiv.org/abs/1606.03000 · HTML: https://mlsanity.com/paper/1606.03000/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2016.

## Built on by (most cited first, 9 of 9)

- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Federated Orthogonal Training: Mitigating Global Catastrophic Forgetting in Continual Federated Learning](https://mlsanity.com/paper/2309.01289/) (2023)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms](https://mlsanity.com/paper/2401.10923/) (2024)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization](https://mlsanity.com/paper/2405.14459/) (2024)
- [Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.27340/) (2025)

## Abstract (arXiv)

The problem of least squares regression of a d-dimensional unknown parameter is considered. A stochastic gradient descent based algorithm with weighted iterate-averaging that uses a single pass over the data is studied and its convergence rate is analyzed. We first consider a bounded constraint set of the unknown parameter. Under some standard regularity assumptions, we provide an explicit O(1/k) upper bound on the convergence rate, depending on the variance (due to the additive noise in the measurements) and the size of the constraint set. We show that the variance term dominates the error and decreases with rate 1/k, while the term which is related to the size of the constraint set decreases with rate log k/k2. We then compare the asymptotic ratio ρ between the convergence rate of the proposed scheme and the empirical risk minimizer (ERM) as the number of iterations approaches infinity. We show that ρ≤ 4 under some mild conditions for all d≥ 1. We further improve the upper bound by showing that ρ≤ 4/3 for the case of d=1 and unbounded parameter set. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with ρ≤ 4/3 even for large d in practice.