# Stochastic Composite Least-Squares Regression with convergence rate O(1/n)

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2017.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Accelerated SGD for Non-Strongly-Convex Least Squares](https://mlsanity.com/paper/2203.01744/) (2022)
- [SGD with memory: fundamental properties and stochastic acceleration](https://mlsanity.com/paper/2410.04228/) (2024)
- [Learning Curves for SGD on Structured Features](https://mlsanity.com/paper/2106.02713/) (2021)
- [Federated Composite Saddle Point Optimization](https://mlsanity.com/paper/2305.15643/) (2023)

## Abstract (arXiv)

We consider the minimization of composite objective functions composed of the expectation of quadratic functions and an arbitrary convex function. We study the stochastic dual averaging algorithm with a constant step-size, showing that it leads to a convergence rate of O(1/n) without strong convexity assumptions. This thus extends earlier results on least-squares regression with the Euclidean geometry to (a) all convex regularizers and constraints, and (b) all geome-tries represented by a Bregman divergence. This is achieved by a new proof technique that relates stochastic and deterministic recursions.