# Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2013.

## Built on by (most cited first, 30 of 32)

- [Sampling-based inference for large linear models, with application to linearised Laplace](https://mlsanity.com/paper/2210.04994/) (2022)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)
- [Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits](https://mlsanity.com/paper/2410.01112/) (2024)
- [Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications](https://mlsanity.com/paper/2303.01370/) (2023)
- [Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descent](https://mlsanity.com/paper/2305.12056/) (2023)
- [Blessing of Class Diversity in Pre-training](https://mlsanity.com/paper/2209.03447/) (2022)
- [Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition](https://mlsanity.com/paper/2310.02941/) (2023)
- [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)
- [Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping](https://mlsanity.com/paper/2403.02051/) (2024)
- [A General Framework for Estimating Preferences Using Response Time Data](https://mlsanity.com/paper/2507.20403/) (2025)
- [Stable Anderson Acceleration for Deep Learning](https://mlsanity.com/paper/2110.14813/) (2021)
- [Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods](https://mlsanity.com/paper/2602.10697/) (2026)
- [On Misspecification in Prediction Problems and Robustness via Improper Learning](https://mlsanity.com/paper/2101.05234/) (2021)
- [Low Complexity Approximate Bayesian Logistic Regression for Sparse Online Learning](https://mlsanity.com/paper/2101.12113/) (2021)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)
- [On the SAGA algorithm with decreasing step](https://mlsanity.com/paper/2410.03760/) (2024)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [Global Optimization via Softmin Energy Minimization](https://mlsanity.com/paper/2509.17815/) (2025)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Stochastic optimal transport in Banach Spaces for regularized estimation of multivariate quantiles](https://mlsanity.com/paper/2302.00982/) (2023)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)
- [Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization](https://mlsanity.com/paper/2405.14459/) (2024)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Quantile-Based Randomized Kaczmarz for Corrupted Tensor Linear Systems](https://mlsanity.com/paper/2503.18190/) (2025)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)
- [Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate](https://mlsanity.com/paper/2510.25287/) (2025)

## Abstract (arXiv)

In this paper, we consider supervised learning problems such as logistic regression and study the stochastic gradient method with averaging, in the usual stochastic approximation setting where observations are used only once. We show that after N iterations, with a constant step-size proportional to 1/R2 √N where N is the number of observations and R is the maximum norm of the observations, the convergence rate is always of order O(1/√N), and improves to O(R2 / μ N) where μ is the lowest eigenvalue of the Hessian at the global optimum (when this eigenvalue is greater than R2/√N). Since μ does not need to be known in advance, this shows that averaged stochastic gradient is adaptive to unknown local strong convexity of the objective function. Our proof relies on the generalized self-concordance properties of the logistic loss and thus extends to all generalized linear models with uniformly bounded features.