Source-linked AI summary
Efficiency of minimizing compositions of convex functions and smooth maps
Dmitriy Drusvyatskiy, Courtney Paquette
TL;DR
The paper studies composite optimization and develops first-order algorithms based on prox-linearization, smoothing, and fast-gradient subproblem solves. It also extends acceleration and randomized incremental techniques to broader composite settings.
Problem
The paper considers the class of composite optimization problems and notes that prox-linear stationarity conclusions can fail for the general composite class.
Method
The approach combines an inexact prox-linear method on a smooth approximation with fast-gradient methods for approximately solving proximal subproblems.
Results
The resulting scheme is identified as having the best known complexity bound for this problem class among first-order methods, with logarithmic terms hidden by eO.
Takeaways & Limitations
The framework extends to randomized incremental subproblem methods and to an accelerated algorithm for the entire composite problem class with inexact subproblem solves.
Takeaways & Limitations
The general stationarity conclusion fails for the composite class, and eliminating logarithmic terms requires a good estimate of the initial objective gap.
Abstract
from arXiv · showhide
We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the subproblems are solved exactly, the method has efficiency $\mathcal{O}(\varepsilon^{-2})$, akin to gradient descent for smooth minimization. We show that when the subproblems can only be solved by first-order methods, a simple combination of smoothing, the prox-linear method, and a fast-gradient scheme yields an algorithm with complexity $\widetilde{\mathcal{O}}(\varepsilon^{-3})$. The technique readily extends to minimizing an average of $m$ composite functions, with complexity $\widetilde{\mathcal{O}}(m/\varepsilon^{2}+\sqrt{m}/\varepsilon^{3})$ in expectation. We round off the paper with an inertial prox-linear method that automatically accelerates in presence of convexity.
1 Introduction
The paper studies global efficiency for composite optimization and develops first-order, finite-sum, and convexity-adaptive extensions of the prox-linear method. It also clarifies what prox-gradient smallness does and does not imply for stationarity.
- Problem class: The problem class is F(x) = g(x) + h(c(x)), where g and h are convex and c is smooth.The setting includes additive composite minimization as a special case and covers nonlinear least squares, exact penalties, robust phase retrieval, and matrix factorization.
- Basic method: The prox-linear method extends prox-gradient by linearizing c and solving a regularized proximal subproblem at each iteration.The analysis assumes h is L-Lipschitz and ∇c is β-Lipschitz, with progress measured by scaled steps called prox-gradients.
- Stationarity: A small prox-gradient need not imply that the current iterate is nearly stationary for the general composite objective.The paper notes that gradients of differentiable iterates can remain bounded away from zero even while prox-gradient norms tend to zero.
- Stationarity: Theorem 4.5 shows that a small prox-gradient guarantees proximity to a point that is nearly stationary for the original objective.The result uses a smooth approximation of F with identical stationary points and relates the prox-gradient to the quality of a proximal point.
- First-order complexity: Õ(ε^-3) complexity is obtained for first-order solution of prox-linear subproblems by combining smoothing, inexact prox-linear iterations, and fast-gradient methods.The bound counts evaluations of c and Jacobian-vector products together with proximal operations, and is identified as the best known bound for this class among first-order methods.
- Acceleration: The paper extends an accelerated additive-composite scheme to the full composite class with inexact subproblem solves.Under finite diameter of dom g, the resulting inertial prox-linear method is designed to accelerate when convexity is present without worsening nonconvex performance relative to prox-gradient.
2 Notation
The paper establishes Euclidean-space notation, extended-real-valued convex-analysis definitions, and Moreau-envelope and proximal-mapping properties.
- The paper works in Euclidean spaces with inner products, induced norms, adjoints, Lipschitz maps, distances, and projections.
- A function’s domain and epigraph describe where it is finite and the set lying above its graph; functions are assumed proper and closed when stated.
- A subgradient satisfies the global affine-underestimator inequality f(y) ≥ f(x) + ⟨v, y − x⟩.
- Fenchel conjugacy recovers a closed convex function through f = f** and provides the usual subgradient equivalence.
- The Moreau envelope regularizes a function, while its proximal mapping identifies the corresponding regularized minimizer.
- For closed convex functions, the Moreau envelope is convex and C1-smooth; for L-Lipschitz functions, it remains L-Lipschitz.
3 The composite problem class
The paper studies minimizing a proper closed convex term plus a convex Lipschitz function composed with a smooth map, targeting first-order stationary points. It introduces the prox-linear method and motivating applications across nonlinear optimization, estimation, and large-scale computation.
- The composite objective consists of a proper closed convex function g, a convex L-Lipschitz function h, and a C1 map c with β-Lipschitz Jacobian.The constants combine as µ := Lβ.
- Motivating examples: The framework includes additive composite minimization, nonlinear least squares, exact penalty formulations, statistical estimation, and grey-box minimization.
- Motivating examples: Additive composite minimization specializes the framework to a real-valued smooth map c and identity h, covering applications in statistical learning and imaging.
- Motivating examples: Statistical estimation instances use convex structural surrogates such as l1 and squared l2 terms together with misfit functions including l2 and l1 norms.
- The optimization goal is a point satisfying 0 ∈ ∂F(x), equivalently a point whose directional derivative is nonnegative in every direction.
- Prox-linear method: The prox-linear method linearizes c at each iterate and solves a regularized proximal subproblem, extending proximal gradient beyond additive composites.For t ≤ µ^-1, the subproblem model is an upper model of F.
- Prox-linear method: With exact subproblem solutions and t ≤ µ^-1, the pure prox-linear method has a stated efficiency guarantee measured by the prox-gradient mapping.
4 Prox-gradient size ∥Gt∥and approximate stationarity
The prox-gradient reliably measures near-stationarity in additive composites but can fail for general nonsmooth compositions. Weak convexity instead connects the prox-gradient to a smooth Moreau envelope and a nearby nearly stationary point.
- Additive versus general composites: In additive composite problems, a small prox-gradient yields an iterate with nearly nonnegative directional derivatives and near-stationarity.
- Weak convexity and the Moreau envelope: The composition h ◦ c is weakly convex with a parameter ρ ∈ [0, µ], enabling Moreau-envelope regularization.
- Weak convexity and the Moreau envelope: For ν ∈ (0, 1/µ), the proximal map of F is single-valued, the Moreau envelope Fν is C1-smooth, and stationary points of Fν and F coincide.
- Weak convexity and the Moreau envelope: A small Moreau-envelope gradient produces a nearby point ˆx with no larger objective value and small subdifferential distance.
- Prox-gradient interpretation: Theorem 4.5 gives quantitative bounds relating the prox-gradient to the Moreau-envelope gradient and near-stationarity.At t = 1/µ, the resulting bounds specialize to explicit estimates involving ∥G1/µ(x)∥.
5 Inexact analysis of the prox-linear method
The paper analyzes inexact prox-linear updates under function-value and dual near-stationarity criteria. Dual formulations enable first-order solution of proximal subproblems and preserve convergence guarantees through primal recovery.
- Exact proximal subproblem solutions are often impossible, so the paper studies inexactness through near-optimality and near-stationarity.
- Near-optimality: Under near-optimality, an inexact prox-linear iterate is an εk+1-approximate minimizer of the regularized subproblem at xk.
- Near-optimality: The step size and subproblem accuracy jointly control the true prox-gradient, making observed step sizes usable as stationarity surrogates.
- Near-optimality: Theorem 5.2 provides convergence of the inexact prox-linear method under near-optimality when t ≤ µ^-1.
- Dual near-stationarity: For first-order subproblem solvers, the paper turns to the Fenchel dual because the direct near-stationarity criterion is generally unavailable unless h is smooth.
- Dual near-stationarity: Dual first-order methods can find approximately stationary dual points using smooth-gradient evaluations and the proximal map of h*.
- Dual near-stationarity: Primal recovery maps a dual approximately stationary point to a primal minimizer of a perturbed proximal subproblem, motivating the dual inexact algorithm.
- Dual near-stationarity: Theorem 5.6 gives convergence for the dual near-stationarity variant when t ≤ µ^-1, with step size and dual error controlling the stationarity measure.
6 Overall complexity for the composite problem class
The section develops first-order complexity guarantees for composite minimization by smoothing the nonsmooth term and approximately solving prox-linear subproblems with fast-gradient methods.
- Complexity framework: The target is a first-order operation bound for finding a point with small prox-gradient when proximal subproblems cannot be solved exactly.The analysis counts evaluations of c, Jacobian-vector products, and proximal operations under prox-friendly assumptions.
- Proposed strategy: Smoothing+prox-linear+fast-gradient replaces h by a Moreau-envelope approximation and uses fast-gradient methods for the resulting inexact prox-linear subproblems.The smoothing parameter is chosen carefully to balance the approximation and optimization costs.
- Complexity guarantees: The resulting estimates are described as the best-known efficiency guarantees of any first-order method for the composite problem class, up to logarithmic dependence on problem data.Two estimates are stated to be identical up to logarithmic dependence.
7 Finite sum problems
The finite-sum extension treats the number of component functions as an explicit problem parameter and improves baseline costs in expectation using accelerated incremental methods inside smoothed prox-linear subproblems.
- Finite-sum setting: Finite-sum problems minimize an average of m composite functions, with m representing the typically large number of recorded measurements.The framework uses individual component evaluations as basic operations and assumes smooth component maps with Lipschitz gradients.
- Finite-sum setting: The finite-sum formulation is an instance of the general composite problem class, allowing the preceding prox-linear and smoothing analysis to be reused.The paper makes an explicit identification between the finite-sum and composite formulations.
- Baseline efficiency: Baseline estimates are obtained by applying the earlier inexact prox-linear schemes directly, separately for smooth and nonsmooth component functions.These baselines target a point with small prox-gradient.
- Improved efficiency: The improved strategy smooths the component functions, applies inexact prox-linear iterations, and solves each proximal subproblem with accelerated incremental methods.The incremental solver is the principal novelty relative to the preceding finite-sum baseline.
- Incremental algorithms: Katyusha is highlighted as substantially better than Prox-SVRG when m ≪ κ, a regime relevant after smoothing because subproblem condition numbers can be huge.Both methods are used as linearly convergent subschemes for prox-linear subproblems.
8 An accelerated prox-linear algorithm
The paper proposes an accelerated prox-linear scheme adaptive to convexity properties of the composite problem, while requiring bounded dom g. Its convergence guarantees include exact and inexact subproblem settings, with O(1/N^2) functional error when r=0.
- Algorithm and assumptions: The proposed algorithm adapts to natural convexity constants of the composite function but requires the domain of g to be bounded.The paper identifies boundedness of dom g as a downside of the scheme's analysis.
- Algorithm and assumptions: The method emulates accelerated proximal-gradient steps while incorporating an additional scaling parameter α for the composite structure.Its construction is motivated by accelerated methods for additive composite problems.
- Convexity properties: The pair-convexity constant r implies r-weak convexity of the composition, but the converse is false.The paper gives an example where h∘c is identically zero and convex although the pair has a nonzero convexity constant.
- Convergence guarantees: Theorem 8.5 establishes efficiency estimates for the exact accelerated prox-linear method, including a special r=0 bound on function values.With ˜µ set to 2µ, the paper states a succinct version of the bound.
- Convergence guarantees: Inexact accelerated prox-linear methods preserve the exact method's rate when error sequences such as {√iδi}, {iδi}, and {i^2εi} are summable.It suffices to choose εi, δi proportional to 1/i^(3+q) for some q>0; when r=0, functional error is O(1/N^2).
B Backtracking
The backtracking variant removes the need to know L and β by using a line search, while retaining analogous convergence guarantees. A separate first-order strategy can remove logarithmic dependence when a good initial objective-gap estimate is available, but introduces scope and parameter-setting limitations.
- Backtracking method: Algorithms 11 and 12 use backtracking to handle unknown constants L and β in the accelerated prox-linear method.The backtracking loop terminates once t≤µ^-1 and requires only logarithmically many iterations.
- Backtracking method: Theorem B.2 provides convergence guarantees for the backtracking scheme, including a special r=0 function-value bound.The guarantee uses parameters t0, η, and α and defines ˜µmax and ˜µ0 from them.
- Removing logarithmic dependence: A first-order method can remove logarithmic dependence when a good estimate of F(x0)−inf F is available.The strategy combines a constant number of inexact prox-linear iterations with accelerated primal-dual iterations on each proximal subproblem.
- Removing logarithmic dependence: The no-logarithm strategy requires an initial objective-gap estimate and fixes the total inner-iteration budget using ∥∇c∥ rather than iterate-wise Jacobian norms.This contrasts with earlier algorithms whose dependence could use an upper bound along the generated iterates.
- Removing logarithmic dependence: The dual subproblem method exploits C1-smoothness of G⋆ and a domain diameter bounded by 2L for the relevant dual function.Algorithm 13 is identified with the optimal method of Auslender–Teboulle and Tseng.