Source-linked AI summary
A proximal method for composite minimization
A. S. Lewis, S. J. Wright
TL;DR
The paper addresses composite minimization with smooth inner functions and nonsmooth, possibly extended-valued or prox-regular outer functions. It proposes ProxDescent, based on a linearized proximal subproblem, and establishes convergence and active-manifold identification properties, with promising preliminary computational results.
Problem
Composite minimization must accommodate nonsmooth, extended-valued, and nonconvex outer functions while modeling constraints and varied applications.
Method
ProxDescent repeatedly solves a proximal linearized subproblem and uses properties of its local solutions to analyze convergence and active-manifold identification.
Results
The paper proves a global convergence result and reports promising preliminary experiments on convex and nonconvex regularized least-squares and nonlinear-programming examples.
Takeaways & Limitations
The framework applies across a wide variety of optimization problems, including constrained, sparse, and nonconvex models.
Takeaways & Limitations
The computational algorithm is bare-bones, and the reported experiments are preliminary.
Abstract
from arXiv · showhide
We consider minimization of functions that are compositions of convex or prox-regular functions (possibly extended-valued) with smooth vector functions. A wide variety of important optimization problems fall into this framework. We describe an algorithmic framework based on a subproblem constructed from a linearized approximation to the objective and a regularization term. Properties of local solutions of this subproblem underlie both a global convergence result and an identification property of the active manifold containing the solution of the original problem. Preliminary computational results on both convex and nonconvex examples are promising.
1. Introduction.
The paper studies composite minimization with a smooth inner map and a nonsmooth, possibly extended-valued or prox-regular outer function. It develops ProxDescent, whose proximal linearized subproblems support convergence analysis and active-manifold identification.
- Problem framework: The framework models objectives h∘c with smooth c and nonsmooth h, including convex, extended-valued, and prox-regular outer functions.Extended values allow constraints to be enforced within h.
- Algorithm: ProxDescent repeatedly solves a proximal linearized subproblem to obtain a trial step.For nonpolyhedral or nonconvex h, the subproblem solution can be a first approximation later enhanced using higher-order information.
- Active-manifold identification: Partial smoothness generalizes active-set structure and can enable identification of the active manifold containing the solution.The identification condition is that the transformed step lies on the active manifold.
- Local analysis: The analysis establishes local subproblem properties, including a nearby solution of size O(|x−x̄|) and, under prox-regularity, a unique local solution for sufficiently large µ.A projection step can then reduce the objective.
- Scope and results: The paper presents a global convergence result and preliminary computational experiments on convex and nonconvex regularized least-squares and nonlinear-programming applications.The computational study is explicitly preliminary, while the framework covers a wide variety of examples.
2. Examples.
The composite framework captures approximation, nonlinear-programming penalty, regularization, matrix-completion, and quadratic problems. These examples show how choices of h encode sparsity, rank, constraints, robustness, and nonconvex models.
- Approximation problems: Least-squares, ℓ1 approximation, and Huber losses fit the framework through suitable choices of the outer function h.The formulation also includes sums of Euclidean norms used in facility location and group-sparse regularization.
- Nonlinear programming penalty functions: Extended-valued polyhedral h represents nonlinear-programming penalty functions while incorporating constraints on x and residual quantities.The associated multiplier vector corresponds to a convex combination of active constraint normals.
- Finite polyhedral case: Finite polyhedral outer functions provide active-index representations whose subgradients are convex hulls of the active vectors.Their criticality conditions align with standard first-order conditions through Lagrange multipliers.
- Regularized minimization: Regularized minimization combines a smooth objective with a nonsmooth regularizer, trading accuracy for simplicity as the regularization parameter τ increases.The ℓ1 choice promotes sparse solutions, while nuclear and total-variation norms promote low rank and piecewise-constant images.
- Regularized minimization: The proximal subproblem yields efficient shrinkage operations for separable ℓ1 regularization and singular-value thresholding for matrix completion.For ℓ1 regularization, the cited subproblem can be solved in O(n) time; matrix completion applies shrinkage to singular values.
- Quadratic and nonconvex examples: The framework also covers quadratic, trust-region, and maximum-of-quadratics models, including nonconvex outer functions.For sufficiently large µ, quadratic examples lead to tractable subproblems such as linear systems, convex quadratic programs, or standard trust-region problems.
3. Related Work.
The paper situates its proximal linearized subproblem within work on composite optimization, trust-region and proximal methods, active-manifold identification, and curvature-enhanced local steps.
- Alternative subproblems: Related methods use linearized subproblems, trust regions, or proximal regularization to compute trial steps for composite optimization.These approaches cover polyhedral penalties, general convex outer functions, and nonlinear programming formulations.
- Manifold identification: Several algorithms estimate or identify the active constraint manifold before computing an enhanced step, often through quadratic or Lagrangian models.This pattern appears in methods based on ℓ∞ trust regions, equality-constrained quadratic programs, and manifold approximations.
- Regularization strategies: Prior convergence analyses sometimes require a sufficiently large regularization parameter to guarantee descent, contrasting with the adaptive strategy considered here.The contrast is stated for convex formulations using subproblems with parameter µ.
- Proximal methods: Proximal-point research establishes convergence for convex and nonconvex settings, while this work favors a more direct and self-contained analysis.The cited literature includes classical convex convergence results and later inexact or nonconvex variants.
- Manifold identification: The paper’s identification result is related to VU-theory results, but its subproblem differs and is generally easier when the composite map is nonlinear.The cited comparison concerns proximal points on a fast track and the relative difficulty of the alternative subproblem.
- Local acceleration: Curvature information on the active manifold can accelerate local convergence while preserving global convergence and manifold identification properties.Related examples include ℓ1-regularized logistic regression and least squares.
4. Properties of the Proximal Linearized Subproblem.
The proximal linearized subproblem can fail for extended-valued, nonsmooth compositions unless a transversality condition supports feasible, controlled steps. Under stronger regularity and partial smoothness assumptions, its local solutions become well behaved, unique, and capable of identifying the active manifold.
- Motivation: Curved constraints in the composition can make the linearized subproblem infeasible and invalidate the basic criticality condition.The example exhibits both an identically +∞ subproblem objective and no multiplier satisfying the criticality condition.
- Existence and control of steps: Under transversality, a local subproblem step exists with size O(|x−¯x|) and objective value near the critical value h(¯c).For nonconvex h, the proximal parameter µ must be sufficiently large.
- Restoring feasibility: The transversality framework guarantees that feasibility restoration is possible in theory, although computing the restoration may be difficult depending on h.The resulting restoration process is called an efficient projection.
- Uniqueness and multiplier convergence: With the stronger constraint qualification, sufficiently large-µ local minimizers and their multipliers converge, and the proximal step is eventually unique.For convex lower semicontinuous h, the required threshold is ¯µ = 0.
- Manifold identification: Under partial smoothness, constraint qualification, and strict criticality, the subproblem solution identifies the active manifold M; for convex lower semicontinuous h, ˆµ = 0.The result applies to sequences xr → ¯x and µr satisfying µr|xr −¯x| → 0.
- Algorithmic implications: ProxDescent adjusts the proximality parameter µ to obtain sufficient decrease and supports global convergence and manifold-identification results.The algorithm is developed after the subproblem properties and is accompanied by preliminary experiments on convex and nonconvex problems.
5. A Proximal Descent Algorithm.
ProxDescent repeatedly solves a proximal linearized subproblem, adjusts its regularization parameter to obtain sufficient decrease, and may improve the trial point by projection or higher-order steps. Under stated regularity, boundedness, and transversality assumptions, accumulation points are critical, while partial smoothness enables active-manifold identification.
- Algorithm: ProxDescent finds a local subproblem minimizer with strict improvement over the zero step, then derives the next iterate from the trial point using projection or other enhancements.The algorithm accepts a step only when the subproblem value decreases, and efficient projection can enforce the required acceptance conditions.
- Algorithm: Higher-order derivatives of c can further improve x+ by taking a step along the manifold identified by the subproblem.The framework permits resetting x+ when this additional step reduces h ◦ c.
- Global convergence: If h is not critical at an accumulation point, critical subproblem steps remain bounded away from zero after scaling by µ, contradicting the algorithm’s acceptance behavior.Lemma 5.1 supplies ϵ > 0 with lim inf µr|dr| ≥ ϵ, while the convergence proof uses this bound to rule out persistent parameter increases.
- Global convergence: Under C2 smoothness, subdifferential regularity, prox-boundedness, and transversality, every accumulation point generated by ProxDescent satisfies the composite criticality condition.The theorem assumes a global quadratic lower bound through prox-boundedness and concludes criticality at any accumulation point.
- Manifold identification: When h is convex, continuous, and partly smooth, and the constraint and strict criticality conditions hold, the algorithm eventually places the linearized image c(xr) + ∇c(xr)dr on the active manifold M.This is the paper’s identification property for the manifold associated with partial smoothness.
6. Computational Results.
Computational experiments apply ProxDescent to convex and nonconvex regularized least-squares problems and nonsmooth power-grid penalties. The reported results show accurate signal recovery, apparent linear convergence, and rapid convergence on two power-grid instances, while the authors characterize the implementation as preliminary and bare-bones.
- Scope and implementation: The authors emphasize that the framework is bare-bones and that efficiency could improve through adaptive µ updates and application-specific customization.The experiments are presented as preliminary evidence across diverse applications, including a nonconvex regularizer and a nonsmooth power-system penalty.
- Regularized least squares: The compressed-sensing experiment recovered 25 nonzero components and accurately captured all larger-magnitude components of the 51-component signal.ProxDescent ran for 92 iterations; the objective displayed apparent linear convergence, while µ_k decreased slowly and remained above µ_min.
- Regularized least squares: Replacing the ℓ1 penalty with MCP reduced apparent magnitude bias while retaining comparable convergence behavior despite nonconvexity.The recovered spikes lacked the slight downward bias seen with ℓ1, and convergence was clearly linear until high-accuracy identification around iteration 80.
- Power-grid penalties: The power-grid experiments model voltage phasors and slacks, with c(x) derived from the nonlinear AC power-flow model.The bounds encode acceptable voltage-magnitude deviations and other operational requirements.
- Power-grid penalties: The 57-bus instance converged in 26 iterations after 44 subproblems, with steady linear convergence of the objective components toward their optimal values.It had 143 variables and 143 active constraints; execution required less than one second, while a manually identified active-set variant used 21 iterations and about half the runtime.
- Power-grid penalties: The 118-bus instance converged in 21 iterations after 34 subproblems, with Q-linear constraint-violation convergence at an approximate rate of .5.It had 262 variables and 260 active constraints; runtime was about .6 seconds, compared with about .18 seconds for the active-set variant.