Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

Francis Bach, Éric Moulines

Type: Preprint

Publication Date: 2013-01-01

Citations: 226

DOI: https://doi.org/10.48550/arxiv.1306.2119

View Publication

Locations

arXiv (Cornell University) - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression	2014	Francis Bach
+	Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression	2013	Francis Bach
+	Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise.	2021	Eduard Gorbunov Marina Danilova Innokentiy Shibaev Pavel Dvurechensky Alexander Gasnikov
+	Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization	2014	Mehrdad Mahdavi
+ PDF Chat	An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes	2024	Antonio Orvieto Lin Xiao
+	Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimization	2019	Michael R. Metel Akiko Takeda
+	Variance Reduction for Faster Non-Convex Optimization	2016	Zeyuan Allen-Zhu Elad Hazan
+	Variance Reduction for Faster Non-Convex Optimization	2016	Zeyuan Allen-Zhu Elad Hazan
+	Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise	2021	Eduard Gorbunov М. А. Данилова Innokentiy Shibaev Pavel Dvurechensky Alexander Gasnikov
+	On the Local Minima of the Empirical Risk	2018	Chi Jin Lydia T. Liu Rong Ge Michael I. Jordan
+	The Landscape of Empirical Risk for Non-convex Losses	2016	Mei Song Yu Bai Andrea Montanari
+	Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds	2017	Lijun Zhang Tianbao Yang Rong Jin
+	Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds	2017	Lijun Zhang Tianbao Yang Rong Jin
+	Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions	2018	Mingrui Liu Xiaoxuan Zhang Lijun Zhang Rong Jin Tianbao Yang
+	Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions	2018	Mingrui Liu Xiaoxuan Zhang Lijun Zhang Rong Jin Tianbao Yang
+ PDF Chat	The Sample Complexity of Gradient Descent in Stochastic Convex Optimization	2024	Roi Livni
+	Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes	2012	Ohad Shamir Tong Zhang
+	Noisy Linear Convergence of Stochastic Gradient Descent for CV@R Statistical Learning under Polyak-Łojasiewicz Conditions	2020	Dionysios S. Kalogerias
+	Stochastic optimization and sparse statistical recovery: An optimal algorithm for high dimensions	2012	Alekh Agarwal Sahand Negahban Martin J. Wainwright
+	Stochastic optimization and sparse statistical recovery: An optimal algorithm for high dimensions	2012	Alekh Agarwal Sahand Negahban Martin J. Wainwright

Works That Cite This (175)

Action	Title	Year	Authors
+ PDF Chat	Online Covariance Matrix Estimation in Stochastic Gradient Descent	2021	Wanrong Zhu Xi Chen Wei Biao Wu
+	Some Limit Properties of Markov Chains Induced by Recursive Stochastic Algorithms	2020	Abhishek Gupta Chen Hao Jianzong Pi Gaurav Tendolkar
+	COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization	2021	M. Madeira Renato Negrinho João Xavier Pedro M. Q. Aguiar
+	How Data Augmentation affects Optimization for Linear Regression.	2020	Boris Hanin Yi Sun
+	Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence	2020	Abhishek Gupta William B. Haskell
+ PDF Chat	Minimizing finite sums with the stochastic average gradient	2016	Mark Schmidt Nicolas Le Roux Francis Bach
+	A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids	2022	Tianyu Zhang Noah Simon
+ PDF Chat	Making the Best of a Bad Situation: A Multiscale Approach to Free Energy Calculation	2019	Michele Invernizzi Michele Parrinello
+	Finite-time analysis of projected Langevin Monte Carlo	2015	Sébastien Bubeck Ronen Eldan Joseph Lehec
+ PDF Chat	An elementary analysis of ridge regression with random design	2022	Jaouad Mourtada Lorenzo Rosasco

Works Cited by This (13)

Action	Title	Year	Authors
+ PDF Chat	Smoothing Spline ANOVA Models	2013	Chong Gu
+	Convergence Rate of Incremental Subgradient Algorithms	2001	Angelia Nedić Dimitri P. Bertsekas
+	Optimal Rates of Aggregation	2003	Alexandre B. Tsybakov
+	Interior-Point Polynomial Algorithms in Convex Programming	1994	Yurii Nesterov Arkadi Nemirovski
+	Robust Stochastic Approximation Approach to Stochastic Programming	2009	Arkadi Nemirovski Anatoli Juditsky Guanghui Lan Alexander Shapiro
+ PDF Chat	Self-concordant analysis for logistic regression	2010	Francis Bach
+	On the Averaged Stochastic Approximation for Linear Regression	1996	László Györfi Harro Walk
+	Optimum Bounds for the Distributions of Martingales in Banach Spaces	1994	Iosif Pinelis
+	Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)	2013	Francis Bach Éric Moulines
+	Convex Optimization	2004	Stephen Boyd Lieven Vandenberghe