PaperlayerView exact revision on arXiv

Source-linked AI summary

Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms

Andreas Themelis, Lorenzo Stella, Panagiotis Patrinos

arXiv:1606.06256v2math.OC

TL;DR

The paper addresses fully nonconvex optimization of a smooth term plus a possibly nonsmooth term using only forward-backward splitting oracles. It develops ZeroFPR from forward-backward envelope properties, proving global convergence and superlinear local rates under Dennis-Moré directions, with numerical results showing strong performance against FBS and AFBS.

  • Problem

    Fully nonconvex sums of a smooth and a possibly nonsmooth function require methods that use only gradient and proximity evaluations while still achieving fast convergence.

  • Method

    ZeroFPR uses the forward-backward envelope and nonmonotone linesearch directions, including quasi-Newton updates, to optimize the original nonconvex sum through forward-backward splitting oracles.

  • Results

    ZeroFPR globally converges under the Kurdyka-Łojasiewicz property and achieves superlinear convergence at strong local minima when directions satisfy the Dennis-Moré condition; it greatly outperforms FBS and AFBS numerically.

  • Takeaways & Limitations

    The forward-backward envelope retains sufficient first- and second-order structure for fast convergence of ZeroFPR despite the fully nonconvex setting.

  • Takeaways & Limitations

    The first-order continuity and differentiability guarantees require γ < Γ(x⋆); at γ = Γ(x⋆), the forward-backward map may be multivalued and the envelope may fail to be differentiable.

Abstract

from arXiv · show

We propose ZeroFPR, a nonmonotone linesearch algorithm for minimizing the sum of two nonconvex functions, one of which is smooth and the other possibly nonsmooth. ZeroFPR is the first algorithm that, despite being fit for fully nonconvex problems and requiring only the black-box oracle of forward-backward splitting (FBS) --- namely evaluations of the gradient of the smooth term and of the proximity operator of the nonsmooth one --- achieves superlinear convergence rates under mild assumptions at the limit point when the linesearch directions satisfy a Dennis-Moré condition, and we show that this is the case for quasi-Newton directions. Our approach is based on the forward-backward envelope (FBE), an exact and strictly continuous penalty function for the original cost. Extending previous results we show that, despite being nonsmooth for fully nonconvex problems, the FBE still enjoys favorable first- and second-order properties which are key for the convergence results of ZeroFPR. Our theoretical results are backed up by promising numerical simulations. On large-scale problems, by computing linesearch directions using limited-memory quasi-Newton updates our algorithm greatly outperforms FBS and its accelerated variant (AFBS).

1. Introduction

The paper studies fully nonconvex composite optimization using forward-backward methods and develops ZeroFPR, an envelope-based line-search algorithm with strong convergence guarantees.

  • Problem setting: The problem allows both the smooth term f and nonsmooth term g to be nonconvex.The smooth term has Lipschitz-continuous gradient, while the nonsmooth term is proper, closed, and prox-bounded.
  • Background: Forward-backward splitting uses first-order information and can converge globally with accelerated variants achieving order o(1/k^2) objective-value rates in convex settings.FBS requires gradient and proximal evaluations, while accelerated FBS adds little per-iteration computation.
  • Forward-backward envelope: The forward-backward envelope is an exact penalty function whose value is defined by the minimization problem underlying the forward-backward step.This connects the envelope to both FBS and the Moreau envelope.
  • Contributions: The paper extends FBE regularity results to nonconvex f and g, establishing differentiability, strict twice differentiability at critical points, and equivalence of strong local minima.These properties support Newton-like optimization of the envelope beyond the convex nonsmooth setting.
  • Contributions: ZeroFPR converges globally under the Kurdyka-Łojasiewicz property and superlinearly with quasi-Newton Broyden directions under mild additional conditions.The algorithm is designed to retain the black-box FBS ingredients while exploiting envelope curvature.

2. Preliminaries

The preliminaries define the composite optimization notation, proximal ingredients, and forward-backward surrogate that underlie the paper’s algorithms and analysis.

  • Notation and assumptions: The smooth term belongs to C1,1(R^n), while the nonsmooth term is proper, closed, and prox-bounded.These assumptions provide Lipschitz gradient control and ensure proximal subproblems are well posed for suitable parameters.
  • Proximal mappings: The Moreau envelope and proximal mapping generalize projection operations for nonsmooth functions.For indicator functions, the proximal mapping coincides with projection onto the underlying set.
  • Forward-backward iterations: The quadratic surrogate ℓγ(z;x) majorizes the original objective and is exact at z=x.FBS minimizes this surrogate, making the method a majorization-minimization procedure.
  • Forward-backward iterations: The forward-backward operator and residual encode the proximal step and its displacement from the current point.The notation is simplified to Tγ and Rγ when the decomposition is clear.

3. Stationary and critical points

This section distinguishes stationarity, criticality, and optimality for nonconvex composite objectives, showing how criticality connects fixed points of FBS with meaningful suboptimal solutions.

  • Stationarity and criticality: For nonconvex objectives, stationarity is necessary for optimality but does not by itself imply that a point is optimal.The paper therefore introduces criticality as an intermediate notion between stationarity and optimality.
  • Definitions: A point is critical when it is a fixed point of the forward-backward operator for some admissible stepsize.The criticality threshold Γ records the largest stepsize range in which this property holds.
  • Properties: Every critical point is γ-critical for all γ below its threshold, and the forward-backward operator is single-valued there.At such points, the residual vanishes and the fixed-point characterization is well behaved.
  • Invariance: Criticality depends on the composite objective rather than on a particular decomposition into smooth and nonsmooth terms.The decomposition changes the threshold, but criticality can also be characterized through a proximal mapping of the full objective.
  • Optimality relations: Optimal points are critical under admissible stepsizes, but criticality and optimality are not equivalent in general.The examples show that stationary points may fail to be critical and that critical points need not be global optima.

4. Forward-backward envelope

The forward-backward envelope (FBE) extends Moreau-envelope ideas to the paper’s fully nonconvex setting while retaining exactness, strict continuity, and useful local regularity. These properties support ZeroFPR and connect critical points and strong local minima of the FBE with those of the original cost.

  • Motivation: The FBE may be nondifferentiable in fully nonconvex problems, so ZeroFPR uses its continuity and forward-backward oracle rather than requiring ∇²f.The oracle consists of operations associated with forward-backward iterations, while earlier FBE approaches required second derivatives.
  • Continuity: For γ ∈(0, γg), the FBE is real-valued and strictly continuous on Rn.This regularity follows from its connection with the Moreau envelope of g.
  • Exactness: For sufficiently small γ, minimizing the FBE is equivalent to minimizing the original function because their infima and argmin sets coincide.At fixed points of the forward-backward operator, the original function and FBE also have equal values.
  • First-order properties: Under prox-regularity at a critical point and suitable γ, the FBE is continuously differentiable nearby with gradient ∇ϕγ = QγRγ.Prox-regularity is required at critical points for the subgradient −∇f(x⋆).
  • Limitations: The bound γ < Γ(x⋆) is necessary for guaranteed continuity of the forward-backward map and continuous differentiability of the FBE around a critical point.At γ = Γ(x⋆), the map can become set-valued and the FBE can fail to be differentiable.
  • Second-order properties: At critical points satisfying the relevant second-order assumptions, the FBE is twice differentiable and its strong local minimality is equivalent to that of the original cost.The paper links strong local minimality to nonsingularity of the forward-backward residual Jacobian.

5. ZeroFPR algorithm

ZeroFPR solves the forward-backward residual inclusion with a nonmonotone linesearch that globalizes Newton-like directions while using only the forward-backward oracle. Its convergence analysis supports finite backtracking and superlinear rates for suitable quasi-Newton directions.

  • Algorithmic viewpoint: ZeroFPR targets zeros of the forward-backward residual, which is continuous and differentiable at critical points under mild assumptions.This locally converts the generalized equation into a well-behaved system of equations.
  • Algorithmic viewpoint: The method bypasses the lack of globally defined FBE descent directions by exploiting favorable FBE properties without requiring the FBE gradient.It therefore remains derivative-free and uses the same oracle as FBS.
  • Globalization strategy: A nominal forward-backward step decreases the FBE, after which a direction computed at the forward-backward point is globalized by backtracking.The update has the form x+ = ¯x + d rather than x + d.
  • Globalization strategy: Finite backtracking follows from the FBE decrease and continuity, regardless of the chosen direction.The nonmonotone condition compares the candidate FBE value with a reference parameter ¯Φk.
  • Quasi-Newton directions: BFGS uses rank-two updates and performs well in practice, although its Dennis-Moré guarantee requires a symmetric Jacobian that is absent here.The paper also considers modified Broyden rank-one updates for the theoretical superlinear result.

5.3. Main remarks.

The implementation remarks describe adaptive handling of unknown smoothness, support for locally Lipschitz gradients, evaluation costs, and the reduction to standard FBS.

  • Adaptive implementation: ZeroFPR can adapt to an unknown Lipschitz constant by increasing its estimate and decreasing γ when the quadratic bound fails.The linesearch is restarted, and the estimate is incremented only finitely many times.
  • Assumptions: If dom g is bounded and the selected directions remain bounded, the assumption on f can be relaxed to locally Lipschitz ∇f.The relevant Lipschitz constant is then taken on a compact domain containing the iterates.
  • Cost per iteration: Evaluating the FBE essentially requires one forward-backward operator evaluation, with one additional Tγ evaluation generally needed per backtracking step.The accepted candidate also supplies the forward-backward point required by the next iteration.
  • Relation to FBS: Setting all directions dk to zero reduces ZeroFPR to classical forward-backward splitting.In that case the unit stepsize is always accepted.

5.4. Convergence results.

The convergence analysis establishes criticality and objective convergence, then derives global, linear, and superlinear rates under progressively stronger assumptions. Dennis-Moré directions, including Broyden directions, provide the superlinear regime.

  • Criticality: The residuals converge to zero square-summably, and every cluster point of the iterates solves the forward-backward residual inclusion.The iterates and their forward-backward points have the same cluster-point set.
  • Criticality: The FBE values converge to a finite limit, and the original objective values at the forward-backward points converge under boundedness.The associated reference sequence is decreasing.
  • Global convergence: Under eventual monotonicity, boundedness, the KL property, and prox-regular cluster points, both iterate sequences converge to the same point and residuals are summable.The stated result additionally assumes f is C2 near the cluster set.
  • Linear convergence: When the KL function has the form ψ(s) = ρs^θ with θ ∈[1/2, 1], the convergent sequences are R-linearly convergent.This is the linear-rate specialization of the monotone-linesearch result.
  • Superlinear convergence: Under strict second-order assumptions at a strong local minimum, Dennis-Moré directions produce superlinear convergence and eventually force acceptance of unit stepsizes.The result applies to the iterates, forward-backward points, and residuals.
  • Superlinear convergence: Broyden directions satisfy the Dennis-Moré condition when the residual is Lipschitz-continuously semidifferentiable at the limit point.Consequently, the superlinear convergence theorem applies to the Broyden implementation.

6. Simulations

The simulations evaluate ZeroFPR with several quasi-Newton directions against FBS and accelerated variants on sparse approximation, dictionary learning, and matrix decomposition problems. Across these settings, L-BFGS and BFGS directions perform especially well, including on large-scale problems.

  • Experimental setup: Experiments compare ZeroFPR using Broyden, BFGS, and L-BFGS directions with FBS, IFBS, and AFBS.The methods are evaluated on nonconvex sparse approximation, dictionary learning, and matrix decomposition problems.
  • Search directions: BFGS and L-BFGS outperform Broyden in practice despite the Jacobian of the fixed-point residual generally being nonsymmetric at critical points.Full quasi-Newton updates are shown for one example, while L-BFGS is emphasized for large-scale experiments.
  • Nonconvex sparse approximation: 100 random sparse-approximation problems are evaluated by average and maximum CPU time to reach ∥Rγ(xk)∥≤10^-6.The experiments vary n and λ and use the same starting point x0 = 0 for all algorithms.
  • Dictionary learning: In dictionary learning, ZeroFPR(L-BFGS) reaches a critical point significantly faster than FBS in the great majority of 50 random problems.The algorithms stop when ∥Rγ(xk)∥≤10^-4; the problem instance has 26000 variables.
  • Matrix decomposition: On the ShoppingMall matrix-decomposition dataset with 8192000 variables, ZeroFPR(L-BFGS) exhibits fast asymptotic convergence compared with FBS and IFBS.The experiment uses n = 50 frames, rank bound r = 1, and λ = 3·10^-3.

7. Conclusions

The conclusions present the FBE as a merit function for nonconvex composite optimization and establish global convergence of ZeroFPR under a KL assumption. Under stronger local conditions, the method is superlinear, and simulations report strong performance from quasi-Newton directions.

  • Main conclusions: The FBE provides a merit function for linesearch methods solving the stationary-point system of nonsmooth nonconvex composite problems.It is used to derive efficient algorithms for functions ϕ = f + g.
  • Convergence guarantees: ZeroFPR globally converges to a stationary point when ϕγ has the Kurdyka-Łojasiewicz property.This conclusion applies to the proposed linesearch framework.
  • Convergence guarantees: At strong local minima, convergence is superlinear when the linesearch directions satisfy the Dennis-Moré condition.The paper gives Broyden directions as an example satisfying the required condition.
  • Empirical results: Numerical simulations on convex and nonconvex problems report that Broyden, BFGS, and L-BFGS directions greatly outperform FBS and its accelerated variant.BFGS is used for small-scale problems and L-BFGS for large-scale problems.

Proof of Theorem 4.10.

The proof establishes differentiability properties of the forward-backward residual and envelope near a critical point, then derives the envelope Hessian through the chain rule.

  • Residual differentiability: Differentiability of the proximal mapping yields strict differentiability of the forward-backward residual Rγ at the critical point.The Jacobian follows from the chain rule under the stated regularity assumptions.
  • Jacobian structure: The proximal Jacobian is symmetric positive semidefinite because it has the form ΠS[I + γM]^-1ΠS.Positive definiteness of I + γM ensures invertibility in the proof.
  • Envelope differentiability: Since Qγ is continuous and Rγ is strictly differentiable, the gradient of the FBE is strictly differentiable at the critical point.The result follows by applying the chain rule to ∇ϕγ = QγRγ.
  • Second-order properties: The FBE Hessian is expressed as γ^-1[Qγ − QγPγQγ] and is symmetric at the critical point.Symmetry follows because both Qγ and Pγ are symmetric.

Proof of Theorem 4.11.

The proof connects positive definiteness of the FBE Hessian, strong local minimality, and the spectral structure of the residual Jacobian. These conditions are shown equivalent under the theorem’s assumptions.

  • Equivalent conditions: A second-order condition is expressed as ⟨d,(∇2f(x⋆)+M)d⟩>0 for every d in S.M and S are the objects specified in Assumption II.
  • Local minimality: Positive definiteness of ∇2ϕγ(x⋆) implies strong local minimality of the FBE and invertibility of JRγ(x⋆).Conversely, local minimality together with invertibility yields a positive-definite FBE Hessian.
  • Jacobian structure: JRγ(x⋆) is similar to Qγ(x⋆)^-1/2∇2ϕγ(x⋆)Qγ(x⋆)^-1/2, linking its spectrum to the symmetric FBE Hessian.The similarity implies positive definiteness of one matrix exactly when it holds for the other.

Appendix B. Additional results for Section 5

Appendix B establishes additional convergence properties for ZeroFPR under direction and boundedness assumptions, including behavior of cluster-point sets. It also shows that the forward-backward envelope has the KL property near strong local minima.

  • Convergence properties: Under condition (5.13), Lemma B.1 derives properties of the iterates generated by ZeroFPR.Its proof uses τ_k ∈ (0, 1] and bounds the auxiliary-iterate differences by the primal differences and residuals.
  • Cluster-point structure: If (x_k) is bounded and (5.13) holds, the cluster-point sets of x_k and x̄_k are nonempty, compact, and connected.The sets coincide, and both ϕ and ϕ_γ are constant on them.
  • KL property: At a strong local minimum x⋆ of ϕ, the FBE ϕ_γ has the KL property for every γ ∈ (0, 1/L_f).The desingularizing function can be chosen as ψ(s) = ρs^(1/2) for some ρ > 0.
  • KL property: The KL result follows because ϕ_γ is twice differentiable at x⋆ with positive-definite Hessian H⋆ and zero gradient.Using the smallest and largest Hessian eigenvalues yields local quadratic and gradient bounds around x⋆.
Loading 1606.06256v2…