PaperlayerView exact revision on arXiv

Source-linked AI summary

Forward-backward quasi-Newton methods for nonsmooth optimization problems

Lorenzo Stella, Andreas Themelis, Panagiotis Patrinos

arXiv:1604.08096v2math.OC

TL;DR

The paper addresses how to obtain faster convergence for nonsmooth composite optimization without making proximal computations substantially harder. It minimizes a smooth forward-backward envelope using line-search and quasi-Newton methods, retaining FBS operations and convergence properties while enabling superlinear convergence under suitable conditions.

  • Problem

    FBS is effective for nonsmooth composite problems but has sublinear convergence and can suffer from ill-conditioning, while Q-norm second-order variants may require difficult inner proximal solves.

  • Method

    The paper interprets FBS as variable-metric gradient descent on a continuously differentiable forward-backward envelope and applies line-search quasi-Newton methods using the same forward-backward oracle.

  • Results

    The proposed scheme has FBS-like global convergence under convexity or the Kurdyka-Łojasiewicz property and achieves superlinear convergence with suitable quasi-Newton directions and second-order conditions.

  • Takeaways & Limitations

    BFGS and L-BFGS fit the framework, providing a route to faster nonsmooth optimization without inner proximal subproblems and with limited-memory support for large-scale settings.

  • Takeaways & Limitations

    The superlinear-convergence analysis assumes differentiability and nonsingularity conditions for the FBE, ensured only under additional second-order assumptions on the original problem.

Abstract

from arXiv · show

The forward-backward splitting method (FBS) for minimizing a nonsmooth composite function can be interpreted as a (variable-metric) gradient method over a continuously differentiable function which we call forward-backward envelope (FBE). This allows to extend algorithms for smooth unconstrained optimization and apply them to nonsmooth (possibly constrained) problems. Since the FBE and its gradient can be computed by simply evaluating forward-backward steps, the resulting methods rely on the very same black-box oracle as FBS. We propose an algorithmic scheme that enjoys the same global convergence properties of FBS when the problem is convex, or when the objective function possesses the Kurdyka-Łojasiewicz property at its critical points. Moreover, when using quasi-Newton directions the proposed method achieves superlinear convergence provided that usual second-order sufficiency conditions on the FBE hold at the limit point of the generated sequence. Such conditions translate into milder requirements on the original function involving generalized second-order differentiability. We show that BFGS fits our framework and that the limited-memory variant L-BFGS is well suited for large-scale problems, greatly outperforming FBS or its accelerated version in practice. The analysis of superlinear convergence is based on an extension of the Dennis and Moré theorem for the proposed algorithmic scheme.

1. Introduction

The paper targets nonsmooth composite optimization, where FBS is broadly applicable but can be limited by sublinear convergence and ill-conditioning. It introduces the forward-backward envelope as a smooth surrogate enabling line-search and quasi-Newton methods while retaining FBS-based operations and convergence guarantees.

  • Motivation: FBS generalizes gradient descent to composite objectives with a smooth term and an additional nonsmooth convex term.The nonsmooth term is handled through a proximal mapping, and such problems arise in control, signal processing, machine learning, and statistics.
  • Motivation: In convex problems, FBS has sublinear objective convergence O(1/k), improved to O(1/k^2) by acceleration, but first-order methods suffer from ill-conditioning.The paper motivates second-order information to improve scaling and asymptotic convergence.
  • Contribution: The forward-backward envelope is a continuously differentiable exact penalty whose value and gradient require only a forward-backward step.FBS is interpreted as a variable-metric gradient method applied to this envelope, creating a smooth optimization problem associated with the original nonsmooth one.
  • Contribution: The proposed line-search scheme preserves FBS’s global convergence under convexity or the Kurdyka-Łojasiewicz property and proves O(1/k) objective convergence in the convex case.The analysis addresses convergence to critical points despite the FBE being generally nonconvex.
  • Contribution: Quasi-Newton directions yield superlinear convergence under appropriate nonsingularity and second-order conditions, with BFGS and L-BFGS included in the framework.The method uses the same forward-backward operations as FBS and avoids solving an inner problem required by Q-norm proximal approaches.

2. Forward-backward envelope

The forward-backward envelope (FBE) reformulates the nonsmooth composite problem as minimizing a continuously differentiable real-valued function while preserving key optimization properties under suitable step sizes. Its bounds, differentiability, and stationarity relationships justify using FBE-based smooth optimization methods.

  • Definition and interpretation: The FBE is a real-valued function obtained from the forward-backward subproblem and can be evaluated through the forward-backward mapping.It is defined as the value function of the partially linearized subproblem associated with forward-backward splitting.
  • Basic inequalities: For sufficiently small γ, the FBE is bounded above by ϕ and below by ϕ(Tγ(x)), with the bounds coinciding at critical points.These relationships are summarized by Proposition 2.2 and Proposition 2.3(i).
  • Optimization equivalence: When γ ∈ (0, 1/Lf], inf ϕ = inf ϕγ and argmin ϕ ⊆ argmin ϕγ; under the stated conditions, the minimizer sets coincide.The converse inclusion is established for minimizers of the FBE, yielding equality of minimizers and minimum values when attained.
  • Step-size scope: The step-size restriction is substantive: in the example, γ = 1 gives ϕγ ≡ 0, whereas γ > 1 makes the FBE unbounded below.The example shows that the bounds in Proposition 2.3 are tight.
  • Differentiability and stationarity: The FBE is continuously differentiable when f is twice continuously differentiable, and for γ ∈ (0, 1/Lf) its stationary points equal zer ∂ϕ.Thus, the nonsmooth problem is equivalent to unconstrained minimization of a continuously differentiable function, although the FBE may remain nonconvex.
  • Algorithmic interpretation: FBS can be interpreted as a variable-metric gradient method on the FBE, enabling line-search and quasi-Newton methods to operate using forward-backward evaluations.This reformulation avoids directly computing the generally difficult proximal mapping of ϕ = f + g.

3. Forward-backward line-search methods

The proposed forward-backward line-search method minimizes the FBE while retaining FBS-like global convergence guarantees and oracle information. It supports adaptive stepsizes, quasi-Newton directions, and convergence rates under convexity or KL assumptions.

  • Algorithmic scheme: The method applies line-search techniques to minimize the FBE while preserving the composite structure and FBS-level oracle information.The algorithm interleaves FBE descent steps with forward-backward steps.
  • Algorithmic scheme: Algorithm 1 adaptively decreases γ when its forward-backward condition fails and eventually keeps γ positive and constant.The parameter is reduced only finitely many times along the iterations.
  • Algorithmic scheme: The method reduces to classical forward-backward splitting when β=0, d_k=0, and τ_k=0, while replacing x_{k+1} with T_{γ_k}(w_k) generally performs better in practice.The latter choice usually requires fewer forward-backward steps than the classical line-search variant.
  • Global convergence: The algorithm descends both the FBE and the original objective, with square-summable residuals when the objective is lower bounded.If the objective instead tends to −∞, the corresponding residual or iterate conclusions change as stated in Proposition 3.3.
  • Global convergence: For convex objectives, the method achieves global O(1/k) objective convergence, and strong convexity yields global linear convergence.The convexity requirement concerns the original objective components, even though the FBE may be nonconvex.
  • Global convergence: Under the KL property, the iterates converge globally to a critical point, with local linear convergence available under the corresponding Łojasiewicz conditions.In the convex case, quasi-Newton directions do not affect the stated linear or sublinear convergence results even if their inverse matrices are unbounded.

4. Quasi-Newton methods

The paper applies quasi-Newton directions to forward-backward envelope minimization, preserving global convergence while enabling superlinear local convergence under second-order conditions. BFGS fits the framework, and L-BFGS reduces storage and computation for large-scale problems.

  • Quasi-Newton framework: Quasi-Newton directions are analyzed within the forward-backward envelope framework to retain global convergence and obtain superlinear asymptotic convergence under standard assumptions.The framework addresses restrictive convergence behavior of standalone quasi-Newton methods on nonconvex objectives.
  • Quasi-Newton framework: The proposed Dennis-Moré analysis accommodates an additional forward-backward step and does not require sufficient objective decrease or strict descent directions for the superlinear result.The theorem instead uses a line search that tries τk = 1 first and establishes eventual acceptance under its assumptions.
  • Quasi-Newton framework: Superlinear convergence requires nonsingularity or positive definiteness conditions on the FBE Hessian together with appropriate differentiability at the limiting critical point.The stated results use strict or calm semidifferentiability and ∇2ϕγ(x⋆) ≻ 0.
  • BFGS: BFGS updates produce nonsingular approximations to the FBE Hessian, while inverse updates compute directions without explicitly forming a matrix inverse.Starting from B0 ≻ 0 preserves positive definiteness and yields descent directions for the FBE.
  • BFGS: L-BFGS stores only a few recent vector pairs, uses two-loop recursion, requires no matrix storage, and needs O(n) operations per direction computation.The method is therefore suited to problems with many variables; the memory parameter is typically m ∈ {3, ..., 20}.

5. Simulations

The simulations compare the proposed FBE-based methods with FBS, Fast FBS, and classical quasi-Newton methods across sparse regression, group lasso, matrix completion, and image restoration. The experiments use problem-specific computational measures, including iterations, matrix-vector products, SVDs, operator calls, and fixed-point residuals.

  • Experimental setup: The experiments compare Algorithms 1 and 2, using BFGS or L-BFGS directions, with classical line-search methods, FBS, and Fast FBS.The convex experiments use β = 0.05 for Algorithm 1 and γ = 0.95/Lf for Algorithm 2 when Lf is known.
  • Lasso: The lasso experiments evaluate sparse-representation methods on SPEAR datasets, including high-dynamic-range instances that are difficult for algorithms to solve.Figure 4 uses spear_inst_1 with m = 512, n = 1024, and λ = 0.05λmax; Table 1 measures progress to ϕ(x) −ϕ⋆≤10−6|ϕ⋆|.
  • Lasso: Algorithm 2 requires much less iterations and operations than Fast FBS in the reported lasso comparison.The comparison uses BFGS directions on a small-dimensional instance and L-BFGS directions on the largest instances.
  • Group lasso: The group-lasso experiment tests FBS, L-BFGS, and Algorithm 1 with L-BFGS directions on a dense problem with 2 · 10^4 decision variables.The problem has m = 200 examples, 200 variable blocks, and a dense matrix with 4 million coefficients.
  • Matrix completion: The matrix-completion experiment compares Algorithm 2 with L-BFGS directions, classical L-BFGS, and FBS on MovieLens100k using relative error versus computed SVDs.The dataset contains 105 ratings of 1682 movies from 943 users, yielding approximately 1.6 million variables; partial SVDs approximate the proximal step.
  • Image restoration: The nonconvex image-restoration experiment compares Algorithm 1 with FBS using blur- and Haar-operator calls as the computational axis and fixed-point residual as the vertical measure.The test uses a 256 × 256 image with Gaussian blur and Gaussian noise, and recovered images are shown separately.

6. Conclusions

The paper reframes FBS as optimization of the continuously differentiable forward-backward envelope and builds line-search methods around that interpretation. The resulting scheme preserves FBS-style global convergence while supporting quasi-Newton and limited-memory directions.

  • Core framework: FBS is equivalent to a variable-metric gradient method on the continuously differentiable forward-backward envelope when f ∈ C2.The FBE and its gradient use the same forward-backward-step oracle as FBS.
  • Algorithm: The proposed algorithm alternates line-search steps over descent directions with forward-backward steps and does not require prior knowledge of Lf.It uses evaluations of f, its gradient, g, and the proximal mapping, while estimating information adaptively.
  • Convergence: Under convexity or the Kurdyka-Lojasiewicz property at critical points, the method has the same global convergence properties as FBS.The conclusion identifies this as a key property despite the FBE being nonconvex in general.
  • Quasi-Newton acceleration: Quasi-Newton directions can yield superlinear convergence, and L-BFGS is analyzed as a large-scale variant within the framework.The superlinear result requires the stated nonsingularity conditions at the limit point.

Appendix A. Definitions and known results

Appendix A introduces differentiability notions and records composition, product, and semidifferentiability results used in the paper’s analysis. These results formalize when generalized derivatives and strict differentiability are preserved.

  • Differentiability notions: Strict differentiability is introduced as a stronger differentiability property, and its Jacobian is uniquely determined.The appendix also relates strict differentiability to continuity of the semiderivative mapping.
  • Composition: Strict differentiability is preserved under composition when the component mappings are strictly differentiable at the relevant points.The result applies to a composition T = P ◦ F.
  • Products: Products remain differentiable under standard assumptions, with weaker requirements when one factor vanishes at the reference point.If R(¯x) = 0, continuity or Lipschitz continuity of Q can combine with differentiability or strict differentiability of R.
  • Semidifferentiability: For semidifferentiable mappings, continuity of the semiderivative in its first argument, strict semidifferentiability, and strict Fréchet differentiability are equivalent under the stated neighborhood assumption.The appendix also defines calmness as a local boundedness condition on the semiderivative.

Appendix B. Proofs of Section 2

Appendix B supplies differentiability and curvature facts for the proximal mapping, the forward-backward residual, and the FBE. It connects positive definiteness of the FBE Hessian with conditions on the original composite problem.

  • Proximal mapping: Differentiability of the proximal mapping composed with x − γ∇f(x) follows from differentiability assumptions on g and the C2 smoothness of f.The resulting formula is obtained by applying the composition rule.
  • Local matrices: The matrix Qγ(x) is symmetric and positive definite when γ < 1/Lf, while the relevant proximal Jacobian is symmetric positive semidefinite with norm at most one.These properties support the local curvature analysis of the FBE and residual.
  • FBE curvature: The Hessian of the FBE exists and is symmetric under the theorem’s assumptions.The proof relates its positive definiteness to the spectrum of the Jacobian of the fixed-point residual.
  • Second-order conditions: Positive definiteness of the FBE Hessian is equivalent to a second-order condition involving ∇2f(x) and the generalized curvature term on the active subspace.The proof also characterizes this through positivity of I + γM relative to Q.

Appendix C. Proofs of Section 3

Appendix C establishes the convergence properties used for Algorithm 1, including stepsize control, critical-point convergence, and linear-rate consequences under stronger conditions.

  • Stepsizes: The generated stepsizes remain bounded below by a positive constant and eventually become constant because the stepsize sequence is nonincreasing.The lower bound is obtained from the line-search contradiction argument.
  • Linear convergence: Under the stated convex error-bound condition, the iterates xk converge linearly to the unique critical point x⋆.The same argument gives linear convergence of the forward-backward points wk when the error bound also holds for the limiting envelope.
  • Convergence: The iterates converge to a critical point when the sequence is infinite and the relevant residuals are nonzero.The proof shows the iterates are Cauchy and then invokes the criticality result.
  • KL convergence: The Kurdyka-Łojasiewicz property yields Q-linear decay of an auxiliary sequence and therefore R-linear convergence of ∥xk −x⋆∥.The proof applies the uniformized KL property near the compact limit set.
  • KL convergence: The forward-backward points wk also converge R-linearly when the stepsizes are bounded below, using prox nonexpansiveness and Lipschitz continuity of ∇f.These properties transfer the rate from xk to wk.

Appendix D. Proofs of Section 4

Appendix D proves the local behavior of the quasi-Newton method, showing eventual unit steps and superlinear convergence under positive-definite envelope curvature and suitable inverse-Hessian conditions.

  • Superlinear convergence: Under the stated nonsingularity and Hessian-approximation conditions, xk converges Q-superlinearly and wk converges R-superlinearly to x⋆.The proof transfers the rate through the forward-backward mapping using prox nonexpansiveness and Lipschitz continuity of ∇f.
  • Unit steps: The line search eventually accepts unit steps, reducing Algorithm 1 to the iterations analyzed in the local quasi-Newton theorem.The proof verifies the non-increase condition with τk = 1 for sufficiently large k.
  • Local convergence: Positive-definite generalized Hessian conditions make x⋆ a strong local minimizer of the forward-backward envelope and imply linear convergence of xk and wk.The argument combines the envelope curvature condition with the earlier linear-convergence theorems.
  • Quasi-Newton updates: The quasi-Newton curvature pairs eventually satisfy ⟨sk, yk⟩>0, so the BFGS update condition holds after sufficiently many iterations.Linear convergence makes the relevant remainder summable, enabling the curvature condition.
Loading 1604.08096v2…