Source-linked AI summary
Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
Mark Schmidt, Nicolas Le Roux, Francis Bach
TL;DR
The paper studies proximal-gradient optimization of a smooth convex term plus a non-smooth convex term when gradient or proximity-operator calculations are inexact. It analyzes decreasing error sequences for basic and accelerated methods and reports that appropriate control preserves error-free convergence rates, with experiments on structured sparsity. The discussion also identifies sensitivity to errors and assumptions left for future extension.
Problem
The paper addresses how errors in gradient and proximity-operator calculations affect convergence rates for proximal-gradient methods.
Method
The paper analyzes basic and accelerated inexact proximal-gradient methods as functions of gradient-error magnitudes and proximal-problem accuracies, then evaluates strategies on structured sparsity.
Results
With appropriately decreasing errors, both inexact proximal-gradient strategies achieve the convergence rates of their corresponding exact methods.
Takeaways & Limitations
The results provide theoretical justification and practical error-decay guidance for using inexact proximal-gradient methods in structured sparsity and other regularized applications.
Takeaways & Limitations
Accelerated methods are more sensitive to errors than basic methods, so acceleration may not outperform the basic method in the inexact setting.
Abstract
from arXiv · showhide
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.
1 Introduction
Proximal-gradient methods exploit structure in composite convex optimization and offer faster convergence than classical subgradient methods. The paper addresses how gradient and proximity-operator errors affect these methods and analyzes controlled inexact strategies.
- Composite problems combine a smooth convex function with a non-smooth convex function, including ℓ1-regularized least squares.
- Proximal-gradient methods achieve O(1/k) objective error, while accelerated variants achieve O(1/k^2).
- Exact proximity operators are unavailable or expensive for important regularizers, motivating efficient approximate calculations.
- The paper shows that controlled proximity-operator errors preserve the convergence rates of corresponding exact methods.
- The analysis covers inexact proximal-gradient and accelerated methods, including gradient-calculation errors, followed by structured-sparsity experiments.
2 Related Work
Related work established convergence under weak assumptions for inexact proximal-gradient methods but had not fully characterized how proximity-operator errors affect convergence rates. This paper analyzes decreasing, potentially deterministic or adversarial errors under weaker accuracy assumptions than some concurrent work.
- For exact proximity operators with independent, zero-mean random gradient errors, proximal-gradient methods achieve O(1/k).
- This paper instead studies errors converging to zero without assuming unbiasedness or independence, covering deterministic and adversarial errors.
- Unlike fixed-error analyses, decreasing errors can permit convergence to the optimal solution and larger errors during early iterations.
- Earlier work established convergence of approximate-proximity methods under weak mapping, descent, or error-norm assumptions.
- Concurrent accelerated-method analysis obtained weaker error dependence but assumed the inexact operator produced an εk-subdifferential, whereas this work assumes a specified proximal accuracy.
3 Notation and Assumptions
The analysis assumes a convex differentiable smooth term with Lipschitz-continuous gradient and a lower semi-continuous proper convex non-smooth term. It permits nonunique minimizers and models both gradient and proximal-objective errors.
- The smooth function g is convex, differentiable, and has an L-Lipschitz-continuous gradient.
- Strong convexity of g is additionally assumed only for the strongly convex propositions.
- The non-smooth function h is lower semi-continuous, proper, and convex, without differentiability or Lipschitz-continuity requirements.
- The framework allows h to be an extended-real-valued convex function, including a convex-set indicator whose proximity operator is projection.
- The notation permits a minimizer x∗ that need not be unique, while ek denotes gradient error and εk denotes proximal-objective error.
4 Convergence Rates of Inexact Proximal-Gradient Methods
The paper derives convergence rates for basic and accelerated proximal-gradient methods under gradient and proximity-operator errors, covering convex and strongly convex cases. Appropriate error decay preserves the error-free rates, while insufficiently controlled errors can degrade convergence, especially for acceleration.
- Convexity: Under assumptions (H), the basic proximal-gradient method retains the O(1/k) rate when ||e_k|| and √ε_k are summable.A sufficient condition is decay at O(1/k^(1+δ)) for any δ > 0; faster decay improves only the constant factor.
- Convexity: The accelerated method achieves the optimal O(1/k^2) rate when {k||e_k||} and {k√ε_k} are summable.A sufficient condition is ||e_k|| and √ε_k = O(1/k^(2+δ)); the bound applies to the last iterate x_k.
- Convexity: If accelerated errors decay only as O(1/k^2), accumulated error terms grow as O(log k), yielding a slower convergence rate.The accelerated method is more sensitive to computational errors than the basic method in this setting.
- Strong convexity: With strong convexity, the basic method has linear convergence when ||e_k|| and √ε_k decrease linearly to zero.The rate constant is max(1 − γ, Q′), with the error-free constant 1 − γ when Q′ < 1 − γ.
- Strong convexity: With strong convexity, the accelerated method converges linearly when ||e_k||^2 and ε_k decrease linearly, and can outperform the exact basic method under a stated error condition.Its rate depends on 1 − √γ and Q′, but it requires knowledge of µ and can slow if µ is misspecified.
5 Experiments
The experiments evaluate inexact proximal-gradient methods for structured sparsity, using approximate proximity computations terminated by decreasing tolerances, fixed tolerances, or fixed iteration counts. Decreasing tolerances selected according to the convergence analysis perform competitively, with εk = 1/k3 best for the basic method and εk = 1/k4 strongest on one accelerated-method data set.
- Experimental setup: The experiments test basic and accelerated inexact proximal-gradient methods on a CUR-like matrix-factorization problem for structured sparsity.The experiments use four data sets and focus on p = 2, where the proximity operator is approximated with block coordinate descent.
- Experimental setup: Three termination strategies use εk = 1/kα, εk = α, or n = α for the BCD approximation.These correspond respectively to decreasing tolerance, fixed tolerance, and a fixed number of inner iterations.
- Evaluation: The experiments measure objective value against BCD iterations because the sparse inner iterates make proximity calculations the main time cost.The three strategies can all yield global convergence for the basic method, but the theoretical guarantee for arbitrary tolerance is associated with sufficiently large α in the decreasing schedule.
- Basic method: εk = 1/k3 gives the best basic proximal-gradient performance across all four data sets.The paper identifies this schedule as achieving the fastest convergence rate according to its analysis.
- Accelerated method: For accelerated proximal-gradient methods, εk = 1/k3 no longer dominates the alternatives.On SRBCT, εk = 1/k4 performs better than εk = 1/k3, while εk = 1/k5 has reasonable but not best performance on any data set.
6 Discussion
The discussion contrasts inexact proximal-gradient methods with smoothing and alternating-direction alternatives, emphasizing sparse iterates and sensitivity to error schedules. It also identifies assumptions and extensions that remain open.
- Comparison: Inexact proximal-gradient methods tend to generate sparse iterates, unlike the smoothing and alternating-direction alternatives discussed.The comparison is made in the context of structured sparsity problems.
- Comparison: The accelerated smoothing method has convergence rate O(1/k), while alternating-direction performance is often sensitive to the penalty parameter.The discussion presents these as disadvantages relative to the proposed approach.
- Error schedules: Practical performance is sensitive to the exact choice of the error sequence, although the analysis suggests schedules like O(1/kα) for sufficiently large α.The theoretical schedule recommendation does not determine a universally best practical choice.
- Scope: The analysis supports applications beyond structured sparsity, including total-variation and nuclear-norm regularization, and accommodates gradient-calculation errors.The paper also cites examples involving graphical models, kernel methods, and semidefinite programming.
- Open issues: The analysis assumes known L, and accelerated strongly convex results also assume known µ.Extending inexact methods to estimate these constants is identified as an open direction.
Appendix: Proofs of the propositions
The appendix proves the convergence propositions by translating approximate proximal solutions into ε-subdifferential conditions, deriving recursive distance bounds, and then bounding objective errors. The proofs separately track proximal and gradient errors.
- Approximate proximal solutions: An ε-optimal proximal solution yields an ε-subdifferential relation that decomposes into a smooth-term component and an h-component.This relation introduces a vector f whose norm is controlled by the proximal accuracy.
- Proof strategy: The proofs first bound distances such as ∥xi − x∗∥ or ∥vi − x∗∥ recursively, then use those bounds to control function values.The resulting bounds depend on the initial distance and the gradient and proximal errors.
- Proof ingredients: Convexity, Lipschitz gradients, non-expansiveness, and strong convexity supply the inequalities used to derive the recursions.Strong convexity is invoked only in the propositions that assume it.
- Error accounting: The error terms are separated into proximal accuracy εk and gradient error ek, with auxiliary terms such as fk capturing the approximate proximal solution.The accelerated proof recursively propagates these error contributions through its estimate sequence.