PaperlayerView exact revision on arXiv

Source-linked AI summary

A quasi-Newton proximal splitting method

Stephen Becker, M. Jalal Fadili

arXiv:1206.1156v2math.OCmath.NA

TL;DR

The paper addresses efficient optimization of convex objectives with smooth and non-smooth components, especially when constraints make standard quasi-Newton methods difficult to use. It develops proximity operators for selected scaled norms and applies them in a zero-memory SR1 forward-backward method. The resulting approach performs near the best tested solver across two LASSO examples while avoiding active-set parameters and inner-tolerance tuning.

  • Problem

    The paper addresses efficient optimization of convex problems with non-smooth terms or constraints, where adapting quasi-Newton methods is difficult.

  • Method

    The paper develops proximity operators for diagonal-plus-rank-one scaled norms and uses them in a variable-metric zero-memory SR1 forward-backward splitting algorithm.

  • Results

    In two LASSO examples, the proposed SR1 method is near the best algorithm, while the non-diagonal term provides significant acceleration over diagonal matrices.

  • Takeaways & Limitations

    The approach extends quasi-Newton optimization to a broad class of non-smooth convex problems without relying on active-set strategies.

  • Takeaways & Limitations

    Extending the approach to primal-dual settings makes updating B_k non-obvious, and rank-r proximity calculations generally require an r-dimensional inner problem.

Abstract

from arXiv · show

A new result in convex analysis on the calculation of proximity operators in certain scaled norms is derived. We describe efficient implementations of the proximity calculation for a useful class of functions; the implementations exploit the piece-wise linear nature of the dual problem. The second part of the paper applies the previous result to acceleration of convex minimization problems, and leads to an elegant quasi-Newton method. The optimization method compares favorably against state-of-the-art alternatives. The algorithm has extensive applications including signal processing, sparse recovery and machine learning and classification.

1 Introduction

The paper targets large-scale convex problems with non-smooth terms or constraints, where adapting quasi-Newton methods is difficult and existing active-set approaches require costly, heuristic subproblems. It introduces scaled-norm proximity calculations and a quasi-Newton framework intended for broader non-smooth functionals without active-set identification.

  • Motivation: Large datasets increase the need for efficient convex optimization methods.Limited-memory quasi-Newton and nonlinear conjugate-gradient methods generally outperform gradient descent on large-scale unconstrained smooth problems.
  • Existing methods: Proximal gradient descent extends gradient descent to problems with non-smooth terms or constraints.It is presented as an application of the forward-backward algorithm and includes projected gradient descent as a special case.
  • Problem: Quasi-Newton and conjugate-gradient methods are harder to adapt because active-set approaches require solving and tuning an inner subproblem.Their behavior approaches that of unconstrained methods only when the active set is correctly identified.
  • Problem formulation: The paper considers minimizing a sum of two proper lower-semicontinuous convex functions, with a smooth Lipschitz-gradient term and a separable non-smooth term.The minimizer set is assumed nonempty and a standard domain qualification is imposed.
  • Applications: The proposed framework targets non-smooth convex problems including convex constraints, regression, machine learning, and classification.Examples include non-negative least squares and sparse support vector machines.
  • Contributions: The contribution introduces computable scaled norms and a quasi-Newton approach that applies beyond box constraints without an active-set strategy.The paper emphasizes diagonal-plus-rank-one scaling and proximity operators for a wide variety of non-smooth functionals.

2 Quasi-Newton forward-backward splitting

The method replaces the fixed diagonal metric in forward-backward splitting with a diagonal-plus-rank-one Hessian approximation and computes the resulting proximity step efficiently. Its zero-memory SR1 design builds on proximal methods while avoiding active-set subproblems and supports line search or unit steps.

  • Forward-backward splitting: Forward-backward splitting updates each iterate using a quadratic approximation and a proximity step for the non-smooth term.The standard method is also called proximal or projected gradient descent.
  • The algorithm: The algorithm chooses B_k as a diagonal-plus-rank-one Hessian approximation instead of the usually poor fixed metric B = LI_H.The step-size satisfies t_k ∈ ]0, 2/L[, typically t_k = 1/L unless line search is used.
  • The algorithm: Zero-memory SR1 forms a new diagonal-plus-rank-one matrix at every iteration.The method computes a rank-one proximity operator, then may use line search along the resulting direction or choose t = 1.
  • Related methods: The method is positioned among proximal descent, spectral projected-gradient, FISTA, diagonal quasi-Newton, active-set, interior-point, and non-smooth quasi-Newton approaches.These alternatives differ in acceleration, metric choice, active-set handling, inner solves, or treatment of the non-smooth term.
  • Relation to alternatives: Unlike active-set methods, the approach does not require identifying active variables or tuning inner-iteration tolerances.This distinguishes it from methods such as L-BFGS-B, ASA, and projected quasi-Newton approaches that rely on active variables or subproblem solves.

3 Proximity operators and proximal calculus

The paper develops proximity operators for diagonal-plus-rank-1 scaled norms by reducing their computation to scalar problems, with efficient exact or iterative solutions for important function classes.

  • Diagonal+rank-1 proximity operators: Theorem 7 reduces a diagonal-plus-rank-1 scaled proximity operator to a scalar optimization involving a diagonally scaled proximity operator.The resulting scalar mapping is Lipschitz continuous and strictly increasing.
  • Separable case: For piecewise-affine component proximity operators, the scalar dual problem is piecewise affine and can be solved by sorting transition points.Sorting the transition values has average complexity O(k log k).
  • Examples: The framework applies to functions including the ℓ1-norm, the ℓ∞-ball indicator, the positive orthant, and block-separable cases.Table 1 summarizes functions with efficiently computable rank-1 proximity operators.
  • Semi-smooth Newton method: When the scalar root has no closed form, semi-smooth Newton methods solve it using a generalized derivative of the scalar mapping.The generalized derivative is nonsingular with a uniformly bounded inverse.
  • Semi-smooth Newton method: The semi-smooth Newton iteration converges superlinearly to the unique root because the scalar mapping has a suitable generalized derivative.Strict monotonicity supplies uniqueness of the root.
  • Examples: For positivity constraints, knowing the scalar α makes the primal and dual variables separable, and the required root can be located by binary search over sorted breakpoints.The relevant scalar function is linear between sorted transition values and monotonic.

4 A primal rank 1 SR1 algorithm

The paper extends SR1 into a zero-memory proximal quasi-Newton method that uses diagonal-plus-rank-1 inverse-Hessian approximations while retaining nonsmooth terms explicitly.

  • Algorithmic design: The algorithm uses zero-memory SR1, forming a new diagonal-plus-rank-1 inverse-Hessian approximation at every iteration.SR1 uses a rank-1 update rather than the rank-2 update used by BFGS.
  • Algorithmic design: The method extends SR1 from smooth optimization to minimizing f+h, where f is smooth and h may be nonsmooth or an indicator function.Each step replaces f with a quadratic approximation while leaving h unchanged.
  • Algorithmic design: The method incorporates the subgradient of h implicitly rather than taking an explicit subgradient step.This follows from keeping h unchanged in the quadratic approximation.
  • Scaling and safeguards: The initial inverse-Hessian approximation is scaled with the Barzilai-Borwein spectral step length τBB2 and a factor γ between 0 and 1.The scaling is chosen to support a well-defined SR1 update under the curvature condition.
  • Scaling and safeguards: Updates are skipped when the curvature quantity cannot be guaranteed nonzero at standard floating-point precision.The curvature condition is guaranteed for strictly convex objectives.
  • Scaling and safeguards: The authors report that γ = 0.8 works well in most situations, while adaptive γ and non-constant diagonal choices showed no consistent improvements.This is an empirical design choice rather than a stated universal optimum.

5 Numerical experiments and comparisons

The numerical experiments compare the proposed approach with established solvers on two LASSO problems, including compressed sensing and a discretized PDE. Performance varies across tests, while the SR1 method remains close to the best algorithm in both cases.

  • Figure 1 presents the first and second LASSO tests in panels (a) and (b), respectively.
  • The LASSO formulation using positive and negative parts doubles the number of variables and introduces degenerate zero eigenvalues into the Hessian.
  • The first LASSO test uses an iid Gaussian operator with m = 1500, n = 3000, and λ = 0.1.
  • L-BFGS-B performs very well on the first test, followed closely by the proposed SR1 algorithm and PSSas.
  • The second LASSO test uses a 3D discrete differential operator with n = 133 = 2197 and λ = 1.
  • On the second test, L-BFGS-B is very slow, FPC-AS is fastest, and SR1 is nearly as good as the best algorithm.

6 Conclusions

The paper proposes a variable-metric quasi-Newton forward-backward method for non-smooth convex problems and develops proximity operators for diagonal-plus-rank-1 metrics. Experiments provide evidence that the non-diagonal term accelerates the method, while several extensions remain technically challenging.

  • The paper proposes a variable-metric quasi-Newton forward-backward splitting algorithm for problems combining smooth and non-smooth convex terms.
  • The authors introduce weighted norms induced by diagonal+rank 1 symmetric positive definite matrices and a framework for computing proximity operators in those norms.
  • The paper reports clear evidence that the non-diagonal term provides significant acceleration over diagonal matrices.
  • Extending the approach to primal-dual settings is non-obvious because updating Bk is difficult.
  • Rank-2 proximity terms could enable a 0-memory BFGS method, but general rank-r extensions require an r-dimensional semismooth Newton inner problem.
  • Diagonal-plus-rank-1 blocks remain an extension whose robust quasi-Newton update is challenging.

A Elements from convex analysis

This appendix section gathers convex-analysis results used in the paper’s proof, while noting that some lemmas are standard or stated without proof.

  • The section collects convex-analysis results that are key for the paper’s proof.
  • Some lemmas are listed without proof because they are easily proved or available in standard references.

A.1 Background

The background defines the convex-analysis objects used throughout the paper, including indicators, infimal convolution, conjugates, subdifferentials, duality, Moreau envelopes, and separability. It also records their metric and calculus properties.

  • The appendix defines indicator functions and infimal convolution for convex functions.
  • The appendix introduces conjugates, including calculus rules for scaling, invertible linear operators, sums, and degenerate quadratic functions.
  • It defines subdifferentials and states that differentiable functions have their gradient as the only subgradient.
  • For V in the symmetric positive-definite cone, V∂h is the subdifferential of h in the metric space HV.
  • Fenchel-Rockafellar duality relates primal and dual solutions under a relative-interior qualification condition.
  • The Moreau envelope is defined through infimal convolution with a quadratic function and is convex with a 1/ρ-Lipschitz gradient.
  • The background also states separability for sums of functions and notes that the paper’s class includes non-smooth convex optimization with convex constraints.

B.1 Proof of Lemma 5

The proof expresses x through a scaled proximal-operator relation involving p, ρ, V, and the inverse of a shifted subdifferential operator.

  • The proof derives x from a scaled proximal expression involving p, ρ, V, and the operator (I_HV + V ∂(h/ρ))^-1.

B.2 Proof of Theorem 7

The proof reduces the dual problem to a one-dimensional strongly convex smooth optimization problem. It establishes uniqueness and analyzes the resulting scalar function using proximal-mapping regularity and firm non-expansiveness.

  • Dual reduction: The dual solution v⋆ is unique, and the proximity-related expression is represented through a scaled residual involving proxh∗◦D1/2.The displayed identity connects the conjugate proximal mapping with the scaled operator expression used in the proof.
  • Dual reduction: The dual problem minimizes a proper convex continuously differentiable objective with Lipschitz gradient over a linear set.The linear set is parametrized by v = αq = αD^-1/2u.
  • Dual reduction: Parametrizing the linear set by the scalar α yields an equivalent strongly convex smooth optimization problem with a unique solution α⋆.The proof also characterizes α⋆ as the unique root of p(α).
  • Properties of p: Lipschitz continuity of p(α) follows from non-expansiveness of the proximal mapping, together with triangle and Cauchy–Schwarz inequalities.These properties provide the regularity needed for the scalar characterization.
  • Properties of p: The proof establishes strict increasing monotonicity of p using firm non-expansiveness of the proximal mapping.The argument introduces P = proxh◦D^-1/2 and considers β > α.
Loading 1206.1156v2…