Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization

By Mark W. Schmidt, Nicolas Le Roux, Francis R. Bach. 2011

629 citations recorded by the source corpus.

We consider the problem of optimizing the sum of a smooth convex function and a non-smooth convex function using proximal-gradient methods, where an error is present in the calculation of the gradient of the smooth term or in the proximity operator with respect to the non-smooth term. We show that both the basic proximal-gradient method and the accelerated proximal-gradient method achieve the same convergence rate as in the error-free case, provided that the errors decrease at appropriate rates. Using these rates, we perform as well as or better than a carefully chosen fixed error level on a set of structured sparsity problems.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Hyperparameter optimization with approximate gradient (2016, methodology): “…cost per iteration, which results in faster convergence. gence result of Theorem 2, H OAG is not guaranteed to be monotonically decreasing, and in fact, some degree of oscillation is expected when the decrease in the tolerance does not match the convergence rate (see e.g. Schmidt et al. (2011)).”
A Universal Catalyst for First-Order Optimization (2015, methodology): “Another useful methodological contribution was the convergence analysis of inexact proximal gradient methods of [23].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “Another interesting direction of research would be to study the stability of our result to inexact minimization of surrogate functions following for instance the analysis of [49] for proximal gradient methods.”
Optimization with Sparsity-Inducing Penalties (2011, background): “Note, however, that fast convergence rates can also be achieved while solving approximately the proximal problem, as long as the precision of the approximation iteratively increases with an appropriate rate (see [122] for more details).”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, methodology): “In particular, it relies on similar ideas as in Proposition 4 of [21].”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, background): “To resolve the recursion, we need the following lemma by Schmidt et al. (2011).”
The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than 1/k2 (2015, positive): “Inexact FISTA-like algorithms have also been considered in [24, 25].”
Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3 (2017, positive): “icles have been devoted the study of perturbed versions of the FISTA algorithm, with various formulation for the perturbations or errors: to cite a few of them Aujol-Dossal [10], Schmidt-Le Roux-Bach [34], Solodov-Svaiter [35], Villa-Salzo-Baldassarres-Verri [37]. As far as we know, our results are ”
A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization (2018, background): “However, approximate solutions of (11) suffice to provide a convergence rate guarantee for solving (2) [6, 9, 18, 19].”
A Fast Proximal Point Method for Computing Exact Wasserstein Distance (2018, background): “Moreover, even if the proximal operator defined in (5) is not exactly evaluated in each iteration, giving rise to inexact proximal point methods, the global convergence of which with local linear rate is still guaranteed under certain conditions [34, 31].”
A regularization interpretation of the proximal point method for weakly convex functions (2020, methodology): “When the proximal point method parameter is tuned correctly, the proximal point method can converge faster than the corresponding stochastic gradient descent method [27] [26] [11].”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “Sohl-Dickstein et al. [2014] propose a quasi-Newton method in this class that shows impressive empirical results, although the iteration cost is much higher.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “In the area of deterministic algorithms, the inexact variant of the full gradient descent method, xk+1 = xk−ωk[∇f(xk)+ k], has received a lot of attention [49, 11, 51, 16, 32].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In the area of deterministic algorithms, the inexact variant of the full gradient descent method, x = x −ωk[∇f(x) + ], has received a lot of attention [174, 39, 180, 59, 128].”