2013

Non-Asymptotic Convergence Analysis of Inexact Gradient Methods for Machine Learning Without Strong Convexity

So, Anthony Man-Cho

Understand

Many recent applications in machine learning and data fitting call for the algorithmic solution of structured smooth convex optimization problems.

Although the gradient descent method is a natural choice for this task, it requires exact gradient computations and hence can be inefficient when the problem size is large or the gradient is difficult to evaluate.
Therefore, there has been much interest in inexact gradient methods (IGMs), in which an efficiently computable approximate gradient is used to perform the update in each iteration.
Currently, non-asymptotic linear convergence results for IGMs are typically established under the assumption that the objective function is strongly convex, which is not satisfied in many applications of interest; while linear convergence results that do not require the strong convexity assumption are usually asymptotic in nature.

On Approximate Solutions of Systems of Linear Inequalities
A. J. Hoffman · 1952
Earlier work this paper cites.
Constrained Minimization Methods
E. S. Levitin and B. T. Polyak · 1966
Earlier work this paper cites.
Descent Methods for Convex Essentially Smooth Minimization
P. Tseng · 1991
Earlier work this paper cites.
On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
Z.-Q. Luo and P. Tseng · 1992
Earlier work this paper cites.
Remarks on Convergence of the Matrix Splitting Algorithm for the Symmetric Linear Complementarity Problem
W. Li · 1993
Earlier work this paper cites.
Error Bounds and Convergence Analysis of Feasible Descent Methods: A General Approach
Z.-Q. Luo and P. Tseng · 1993
Earlier work this paper cites.
Nonlinear Programming
D. P. Bertsekas · 1999
Earlier work this paper cites.

Introductory Lectures on Convex Optimization: A Basic Course
Yu. Nesterov · 2004
Cited alongside, same era.
A Convergent Incremental Gradient Method with a Constant Step Size
D. Blatt, A. O. Hero, and H. Gauchman · 2007
Cited alongside, same era.
The Tradeoffs of Large Scale Learning
L. Bottou and O. Bousquet · 2007
Cited alongside, same era.
Robust Stochastic Approximation Approach to Stochastic Programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2009
Cited alongside, same era.
Non–Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
F. Bach and E. Moulines · 2011
Cited alongside, same era.
Convergence Rates of Inexact Proximal–Gradient Methods for Convex Optimization
M. Schmidt, N. Le Roux, and F. Bach · 2011
Cited alongside, same era.
Information–Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
A. Agarwal, P. L. Barlett, P. Ravikumar, and M. J. Wainwright · 2012
Cited alongside, same era.

Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization
D. P. Bertsekas · 2012
Later among the works it cites.
Sample Size Selection in Optimization Models for Machine Learning
R. H. Byrd, G. M. Chin, J. Nocedal, and Y. Wu · 2012
Later among the works it cites.
Hybrid Deterministic–Stochastic Methods for Data Fitting
M. P. Friedlander and M. Schmidt · 2012
Later among the works it cites.
A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
N. Le Roux, M. Schmidt, and F. Bach · 2012
Later among the works it cites.
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
A. Rakhlin, O. Shamir, and K. Sridharan · 2012
Later among the works it cites.
Iteration Complexity of Feasible Descent Methods for Convex Optimization
P.-W. Wang and C.-J. Lin · 2013
Closest in time.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…