Efficiency of minimizing compositions of convex functions and smooth maps

Prox-gradient and the Moreau envelope

• A small prox-gradient need not make an iterate nearly stationary for the general composite problem, but it identifies a nearby proximal point that is nearly stationary for F.The argument uses a smooth approximation of F with the same stationary points.Source: §1 · pp. 2–3

Complexity of first-order methods through smoothing

• Smoothing the objective and approximately solving prox-linear subproblems with fast-gradient methods yields first-order efficiency bounds for the general composite class.The method assumes a finite upper bound on the operator norms of ∇c over the domain of g.Source: §1 · p. 3

Inexactness and first-order methods

• The inexact prox-linear analysis covers both near-optimality in function value and near-stationarity in the dual, while direct first-order subproblem methods yield unsatisfactory bounds or impractical algorithms.The paper therefore advocates running the inexact method on a smooth approximation.Source: §1 · p. 3

Complexity of finite-sum problems

• A randomized method using accelerated incremental methods for finite-sum subproblems improves the expected complexity, with the coefficient of 1/ε^3 scaling at worst as √m.The problem averages m composite functions, and the complexity is measured in individual function and derivative evaluations and proximal operations.Source: §1 · pp. 3–4

Acceleration

• The paper extends the accelerated algorithm of Ghadimi-Lan to the full composite class with inexact subproblem solves, with a guarantee conditioned on finite dom g diameter and convexity-like behavior.The analysis uses constants c1 and c2, with 0 ≤ c1 ≤ c2 ≤ 1, to quantify that behavior.Source: §1 · p. 4

• The setting is a Euclidean space R^d with an inner product and induced norm; linear-map adjoints satisfy ∥A∥op = ∥A*∥op.Source: §2 · p. 5
• Lipschitz continuity is expressed through lip(F) ≤ L, and the section introduces distance to and projection onto a set Q.Source: §2 · p. 5
• Functions use the extended real line, with dom f and epi f defined explicitly; encountered functions are assumed proper, and closedness means a closed epigraph.The indicator δQ is zero on Q and +∞ outside Q.Source: §2 · p. 5
• A subgradient v at x satisfies f(y) ≥ f(x) + ⟨v, y − x⟩ for all y, and the section defines ∂f(x) and the Fenchel conjugate.For closed convex f, f = f**.Source: §2 · pp. 5–6
• The Moreau envelope of a closed convex function is convex and C1-smooth; its gradient is 1/ν-Lipschitz, and for L-Lipschitz f the envelope is L-Lipschitz.The proximal mapping of an indicator δQ is projection onto Q, and its Moreau envelope is (1/(2ν)) dist²(x; Q).Source: §2 · p. 6

3 The composite problem class

• The composite components assume a proper, closed, convex R, a convex L-Lipschitz function h, and a C1 map c with β-Lipschitz Jacobian; μ is defined as Lβ.These conditions specify the functional assumptions used throughout the section.Source: §3 · pp. 6–7

3.1 Motivating examples

• Examples include additive composite problems in learning and imaging and bound-constrained nonlinear least squares, commonly addressed by proximal-gradient and Gauss-Newton methods [37,43,45].The section also identifies exact-penalty formulations of nonlinear optimization problems.Source: §3.1 · p. 7
• Statistical estimation minimizes a misfit between nonlinear process model G(x) and observed data b; in grey-box minimization, h is explicit while c(x) and Jacobian ∇c(x) may require simulation.The l2 norm appears in nonlinear least squares; the l1 norm is used in LAD regression, Kalman smoothing with impulsive disturbances [2], and robust phase retrieval [25].Source: §3.1 · pp. 7–8

3.2 First-order stationary points for composite problems

• For the nonconvex composite objective, the target is a stationary point satisfying 0 ∈ ∂F(x), equivalently one whose directional derivative is nonnegative in every direction.The Fréchet and limiting subdifferentials coincide for this problem class.Source: §3.2 · pp. 8–9

3.3 The prox-linear method

• The prox-linear method linearizes c and solves a proximal subproblem; for t ≤ μ^-1 its model upper-bounds F, and in the additive setting it reduces to proximal gradient.The section presents the pure prox-linear method's efficiency guarantee for t ≤ μ^-1, though the supplied passage omits its bound.Source: §3.3 · pp. 9–10

4 Prox-gradient size ∥Gt∥and approximate stationarity

• In the additive composite setting, prox-gradient size at most ε yields dist(0;∂F(x_{k+1}))≤ε and directional derivative F′(x;u)≥−ε in every unit direction.Source: §4 · p. 11
• For general composites with nonsmooth h, dist(0;∂F(x_{k+1})) typically need not tend to zero even when the prox-gradient size does.Source: §4 · p. 11

4.1 Weak convexity and the Moreau envelope of the composition

• For ν∈(0,1/μ), h∘c is ρ-weakly convex for some ρ∈[0,μ], and F_ν is C1-smooth with the same stationary points as F.Source: §4.1 · p. 12

4.2 Prox-gradient and the gradient of the Moreau envelope

• A small ∥G_1/μ(x)∥ certifies a point near x with no greater objective value and subgradient distance at most 4∥G_1/μ(x)∥, though that point is not computable.The certificate uses the point x̂ = prox_{F/2μ}(x); computing it is not required to certify approximate stationarity.Source: §4.2 · pp. 14–15

5.1 Near-optimality in the subproblems

• Near-optimality errors ε_k = O(1/k^(1+q)), for q > 0, suffice to maintain the exact prox-linear method’s rate, and step sizes with the error jointly control the prox-gradient measure.The method sets each next iterate to an ε_k-approximate minimizer of the current proximal subproblem; step sizes can serve as surrogates for the true stationarity measure.Source: §5.1 · pp. 16–17

5.2 Near-stationarity in the subproblems

• Dual near-stationarity enables first-order solution of the subproblems: proximal-gradient methods target the smooth-plus-nonsmooth dual, and dual iterates yield primal updates.Primal recovery maps a dual point to a minimizer of a perturbed proximal subproblem.Source: §5.2 · pp. 17–18
• Summable near-stationarity errors preserve the exact method’s rate in N; ε_k ∼ 1/k^(1+q), for q > 0, is one sufficient schedule.The step size and error jointly control the prox-gradient stationarity measure.Source: §5.2 · pp. 19–20

6 Overall complexity for the composite problem class

• Smoothing h with its Moreau envelope, then applying inexact prox-linear iterations with fast-gradient subproblem solves, is the proposed strategy for the composite problem.The analysis uses the envelope’s stated properties; the passages here do not give the smoothing strategy’s final complexity.Source: §6 · p. 21, §6.3 · p. 27

6.1 Interlude: fast gradient method for additive convex composite problems

• A prox-gradient step converts an objective gap of at most ε²/(8Lf) into a point with subgradient norm at most ε for a convex additive composite problem.The cited bound follows from a descent inequality and the fast-gradient method’s convergence guarantee.Source: §6.1 · p. 22

6.2 Total cost if h is smooth

• For smooth h, the section analyzes total cost with linearly convergent subproblem solvers and favors dual subproblems for global analysis because their domain is bounded.When h is L-Lipschitz, dom h⋆ is bounded in norm by L, so its diameter is at most 2L.Source: Total cost based on dual… · p. 23

Total cost based on dual near-stationarity in the subproblems

• For dual near-stationarity subsolves, each fast-gradient iteration with the extra prox-gradient step takes 9 basic operations, plus one proximal map of g to complete the step.The subproblem is solved until its subgradient distance is at most εk+1.Source: Total cost based on dual… · p. 23

Total cost based on approximate minimizers of the subproblems

• Direct primal fast-gradient solves lack a simple bound on each subproblem’s initial distance, so Algorithm 6 couples fixed inner runs to the outer prox-linear iterations using the solver’s linear rate.The coupling also supports stochastic subproblem solvers, with convergence analyzed in expectation; deterministic solvers retain deterministic rates.Source: Total cost based on approximate… · pp. 24–25

6.3 Total cost of the smoothing strategy

• The smoothing analysis replaces h with a smooth approximation and relies only on the Moreau envelope’s three stated properties, allowing other smoothings with analogous properties.This passage introduces the strategy but does not state its resulting complexity.Source: §6.3 · p. 27
• A prox-gradient comparison theorem motivates choosing the smoothing parameter ν to relate target-problem accuracy to the smoothed problem.The target accuracy is stated in terms of the norm of the target prox-gradient.Source: §6.3 · p. 28
• The two estimates (6.20) and (6.21) are identical up to a logarithmic dependence on problem data and are, to the authors’ knowledge, the best-known efficiency estimates of any first-order method for composite problem class (3.1).Algorithm 6 uses fast-gradient primal subsolves, as described in Section 6.2.Source: §6.3 · p. 29
• The logarithmic dependence can be removed if an accurate estimate of F(x0) − inf F and an a priori estimate of ∥∇c∥ are available, but the authors consider that scheme less practical.Its details are placed in Appendix C.Source: §6.3 · p. 29

7 Finite sum problems

• The section treats regularized empirical risk minimization as an average of m composite functions, with componentwise Lipschitz data and basic operations including individual component evaluations.The component maps are real-valued for notational convenience; analogous results hold for higher-dimensional outputs.Source: §7 · p. 30

Baseline efficiency when hi are smooth:

• For smooth hi, the baseline efficiency estimate from Section 6.2 is multiplied by m because each gradient evaluation requires m component-gradient evaluations.The section uses the substitutions in Remark 7.2 when transferring the previous estimate to the finite-sum setting.Source: Baseline efficiency when hi are smooth · p. 31, §7 · p. 31

Baseline efficiency when hi are nonsmooth:

• For nonsmooth hi, smoothing gives a baseline estimate for finding a point with small prox-gradient, which the section then improves in expectation using accelerated incremental subproblem solvers.The improvement changes the way proximal subproblems are approximately solved.Source: Baseline efficiency when hi are… · p. 31

7.1 An interlude: incremental algorithms

• Prox-SVRG [71] and Katyusha [1] serve as incremental subproblem solvers; Katyusha’s efficiency estimate is significantly better only when m ≪ κ, a relevant regime after smoothing.The section focuses on these methods among incremental algorithms for strongly convex finite-sum problems.Source: §7.1 · pp. 32–33

Improved efficiency estimates when hi are smooth:

• For smooth hi, modified Prox-SVRG+ and Katyusha+ yield total efficiency estimates for the inexact prox-linear method, with the better estimate depending on the subsolver.The modifications add an initial prox-gradient step to put the schemes in the required convergence form.Source: Improved efficiency estimates when hi… · pp. 33–34

Improved efficiency estimates when hi are nonsmooth:

• Smoothing with inexact prox-linear iterations and accelerated incremental subproblem solvers improves the expected finite-sum guarantee; its 1/ε^3 term scales as √m, unlike the deterministic baseline.The method chooses the more efficient of Prox-SVRG+ and Katyusha+ for each proximal subproblem.Source: Baseline efficiency when hi are… · p. 31, Improved efficiency estimates when hi… · p. 35

8 An accelerated prox-linear algorithm

• The proposed accelerated prox-linear method adapts to natural convexity constants, but its analysis requires dom g to be bounded.It is motivated by inertial steps used in accelerated methods for additive composite problems.Source: §8 · p. 36

Convergence guarantees

• Theorem 8.5 gives convergence guarantees that adapt to weak convexity ρ and pair convexity r of the composite problem.The theorem's efficiency estimate has terms associated with different levels of convexity.Source: §8.1 · p. 37, Convergence guarantees · p. 38

Weak convexity and convexity of the pair

• Convexity of the pair (h, c) with constant r implies that the composite Φ is r-weakly convex, but the converse does not hold.The paper illustrates the failure of the converse with a convex, identically zero composition whose pair has a nonzero convexity constant.Source: Weak convexity and convexity of the pair · p. 37

8.2 Inexact computation

• For the inexact dual-subproblem method, summable error sequences suffice to preserve the exact method’s rate in N.The method provides a near-stationarity guarantee; the passage states that the error sequences must be summable to retain the exact method's rate.Source: §8.2 · pp. 40–41
• When r = 0, the inexact near-optimality method gives functional error O(1/N^2).Sufficient error choices are ε_i, δ_i ∼ 1/i^(3+q) for some q > 0, which make the stated weighted error sequences summable.Source: §8.2 · pp. 41–42

B Backtracking

• Algorithm 12 replaces known L and β with a backtracking line search within the accelerated prox-linear method.At each step, it calls Backtracking to select a regularization parameter and step size.Source: B Backtracking · pp. 53–54
• The backtracking procedure terminates after logarithmically many iterations, with the loop ending once t ≤ μ^-1.The termination lemma bounds evaluations of S_{α·}(y), though the supplied passage omits the bound’s formula.Source: B Backtracking · pp. 53–54
• Theorem B.2 establishes convergence guarantees for Algorithm 12 using μ̃_max = max{(αt0)^-1, (αη)^-1μ} and μ̃_0 = (αt0)^-1.When r = 0, the second summand in the stated inequality is replaced by zero, even if M = ∞, and a function-value efficiency bound also holds; the supplied passages omit the bounds’ formulas.Source: B Backtracking · p. 54