PaperlayerView exact revision on arXiv

Source-linked AI summary

First-order optimization algorithms via inertial systems with Hessian driven damping

Hedy Attouch, Zaki Chbani, Jalal Fadili, Hassan Riahi

arXiv:1907.10536v2math.OC

TL;DR

The paper addresses convergence of inertial first-order methods for convex optimization, including their gradient behavior and extensions beyond smooth settings. It derives algorithms by discretizing dynamics with viscous and Hessian-driven damping, using gradient differences and regularization, and reports fast objective convergence, gradient decay, nonsmooth applicability, and time-scaling acceleration. A key scope boundary is that preserving acceleration requires a constraint on the Hessian-damping parameter whose fundamental status remains open.

  • Problem

    The paper studies how inertial first-order optimization methods can combine accelerated objective convergence with rapid gradient decay while extending to nonsmooth convex functions.

  • Method

    It discretizes inertial dynamics with viscous and Hessian-driven damping, treats the Hessian term through gradient differences, and uses regularization for nonsmooth functions.

  • Results

    The resulting methods retain fast objective convergence, show rapid or exponential gradient convergence in the stated settings, extend to nonsmooth problems, and support time-scaling acceleration.

  • Takeaways & Limitations

    Hessian-driven inertial dynamics provide a first-order algorithmic framework combining accelerated values with fast gradients, global iterate convergence, nonsmooth extensions, and time scaling.

  • Takeaways & Limitations

    Preserving acceleration requires β < 2√s, and whether this constraint is technical or fundamental remains an open question.

Abstract

from arXiv · show

In a Hilbert space setting, for convex optimization, we analyze the convergence rate of a class of first-order algorithms involving inertial features. They can be interpreted as discrete time versions of inertial dynamics involving both viscous and Hessian-driven dampings. The geometrical damping driven by the Hessian intervenes in the dynamics in the form $\nabla^2 f (x(t)) \dot{x} (t)$. By treating this term as the time derivative of $ \nabla f (x (t)) $, this gives, in discretized form, first-order algorithms in time and space. In addition to the convergence properties attached to Nesterov-type accelerated gradient methods, the algorithms thus obtained are new and show a rapid convergence towards zero of the gradients. On the basis of a regularization technique using the Moreau envelope, we extend these methods to non-smooth convex functions with extended real values. The introduction of time scale factors makes it possible to further accelerate these algorithms. We also report numerical results on structured problems to support our theoretical findings.

1 Introduction

The paper develops first-order optimization algorithms from inertial dynamics combining viscous and Hessian-driven damping, retaining accelerated objective convergence while targeting rapid gradient decay. The framework covers convex and strongly convex settings, extends to nonsmooth functions, and uses time scaling for acceleration.

  • 1 Introduction: The Hessian-driven term ∇^2f(x(t)) ˙x(t) is the time derivative of ∇f(x(t)), enabling first-order discretizations that modify Nesterov extrapolation with gradient differences.The resulting dynamics generate first-order methods involving gradients or proximal operators rather than explicit Hessian computations.
  • 1 Introduction: For general convex objectives, the β ≡ 0, α = 3, b(t) ≡ 1 case recovers a continuous Nesterov accelerated gradient method with O(1/t^2) objective convergence.
  • 1 Introduction: The nonsmooth extension uses a regularized function and discretized dynamics requiring continuous differentiability of the regularization, rather than C2 smoothness of the original function.
  • 1 Introduction: On an ill-conditioned quadratic problem, Hessian damping neutralizes the wild oscillations observed with the viscous-damping dynamics.The comparison uses α = 3.1 and β = 1 in R2.
  • 1 Introduction: For strongly convex objectives, autonomous Hessian-driven dynamics and their discretizations yield linear convergence for objective values, iterates, and gradients.The analysis uses γ = 2√µ and parameter conditions including sufficiently small Lipschitz step scaling and β ≤ 1/√µ.

2 Inertial dynamics for general convex functions

The paper studies inertial dynamics with viscous and Hessian-driven damping for general convex optimization, allowing variable damping and time-scale parameters. Lyapunov analysis yields convergence guarantees, while time rescaling and parameter choices can reduce oscillations and accelerate convergence.

  • General framework: The framework analyzes inertial systems with Hessian-driven damping under general conditions on the parameter functions β(t) and b(t).The analysis uses a Lyapunov function to establish monotonicity and convergence properties.
  • Particular cases: For constant Hessian-damping and unit time scale, the dynamics recover previously studied inertial systems under suitable conditions such as α > 3.These specializations include the system with β(t) ≡ β and b(t) ≡ 1.
  • Time rescaling: The case β(t) ≡ 0 connects the dynamics to time-scaled accelerated viscous-damping systems, with b(t) controlling the time rescaling.The resulting conditions depend directly on the positivity and growth of b(t).
  • Time rescaling: For choices β(t) = t^β and b(t) = ct^b, the admissible parameters satisfy explicit inequalities relating c, b, β, and α.When b = β − 1, these conditions reduce to β < c − 1 and β ≤ α − 2.
  • Numerical illustration: In a convex quadratic example, flexible parameter choices reduce oscillations in both trajectories and objective values, beyond what the upper-bound rates alone reveal.Figure 2 compares objective convergence profiles and trajectories for different β(t) and b(t) choices.

3 Inertial algorithms for general convex functions

The paper discretizes Hessian-driven inertial dynamics into first-order gradient and proximal algorithms by replacing the Hessian term with a time difference of gradients. It establishes convergence for smooth and nonsmooth convex problems, including accelerated rates and gradient decay.

  • Discretization: Writing ∇²f(x(t))ẋ(t) as the time derivative of ∇f(x(t)) enables first-order discretizations using gradient differences.The resulting schemes modify Nesterov extrapolation without requiring explicit Hessian computations.
  • Smooth case: IPAHD is an inertial proximal algorithm with Hessian damping for convex C1 functions under growth conditions on the discrete parameters.Its proof uses a non-increasing discrete Lyapunov sequence.
  • Smooth case: The objective convergence rate is O(1/((k + 1)k)) under fairly general growth assumptions on βk and bk.When infk βk > 0, the analysis also gives a weighted summability property for gradient norms.
  • Non-smooth case: The Moreau envelope extends the proximal method to proper lower semicontinuous convex functions with extended real values.Because the envelope preserves minimizers and has a Lipschitz gradient, the smooth analysis can be applied and translated back through proximal calculus.
  • Gradient algorithms: IGAHD is an inertial gradient algorithm with Hessian damping whose energy is non-increasing for α ≥ 3, 0 ≤ β < 2√s, and s ≤ 1/L.The restriction β < 2√s limits geometric damping when preserving viscous-damping acceleration.

4 Inertial dynamics for strongly convex functions

For strongly convex functions, the Hessian-driven inertial system admits exponential convergence of objective values, trajectories, and gradient terms. The analysis uses Lyapunov functions and extends to nonsmooth convex functions through subdifferential dynamics.

  • Smooth strongly convex case: Suitable parameters yield exponential decay of the value function, trajectory, and gradients for strongly convex objectives.The analysis uses γ = 2√µ and bounds β within a specified range.
  • Smooth strongly convex case: For β > 0, the gradient estimate is presented as new relative to the cited literature.The β = 0 case recovers an earlier result, while the related β > 0 rate is reported as slightly worse.
  • Smooth strongly convex case: The Lyapunov analysis shows that gradient norms tend to zero exponentially in an averaged sense.The stated estimate concerns gradient terms in average, not pointwise.
  • Nonsmooth extension: Replacing gradients with subdifferentials extends the inertial dynamics to proper lower semicontinuous convex functions with extended real values.Most properties remain valid for the generalized nonsmooth version, including the strongly convex convergence result.

5 Inertial algorithms for strongly convex functions

Time discretization converts the strongly convex inertial dynamics into proximal and gradient algorithms with linear convergence. Under suitable step-size and damping conditions, the gradients also converge exponentially fast to zero, including in the nonsmooth proximal setting.

  • Algorithmic discretization: Proper discretization transfers the continuous system’s exponential convergence into linear convergence for inertial algorithms.The paper derives both proximal and explicit gradient schemes from the strongly convex dynamics.
  • Proximal algorithm: The inertial proximal algorithm with Hessian damping uses a positive step size h and imposes conditions on β and √s for geometric decay.The analysis obtains E_k ≤ qE_{k−1} with 0 < q < 1 under the stated parameter restrictions.
  • Proximal algorithm: The proximal algorithm’s gradients converge exponentially fast to zero, a result the paper identifies as unavailable for such a proximal scheme.The gradient rate uses θ = 1/(1+√µs), with 0 < θ < 1.
  • Nonsmooth algorithm: Moreau-Yosida regularization preserves strong convexity with modulus µ/(1+λµ), enabling nonsmooth strongly convex extensions.The resulting relaxed inertial proximal algorithm has constant coefficients and computational burden equivalent to twice that of the classical proximal algorithm.
  • Gradient algorithm: Explicit centered finite-difference discretization yields an inertial gradient algorithm with Hessian damping and linear convergence under smooth strong-convexity assumptions.The result includes linear convergence of the iterates and exponential convergence of gradients to zero.

6 Numerical results

The numerical study applies the inertial gradient method and FISTA to structured composite problems after reformulating the objective in a suitable metric. Across several regularizers, the observed profiles agree with the predicted rates, with the Hessian-damped method showing fewer oscillations and eventual faster convergence.

  • Problem formulation: The Moreau envelope f_M is continuously differentiable and has a Lipschitz-continuous gradient in the metric M.This places the nonsmooth composite problem within the smooth framework used by the inertial gradient method.
  • Numerical comparison: IGAHD and FISTA are evaluated with ℓ1, ℓ1−ℓ2, total-variation, and nuclear-norm regularizers.The experiments use four structured instances of the regularizer g.
  • Numerical comparison: The observed convergence profiles agree with the predicted rate, while IGAHD exhibits fewer oscillations and eventually converges faster than FISTA.The comparison is reported for the structured composite experiments shown in Figure 3.

7 Conclusion, Perspectives

The paper concludes that Hessian-driven inertial dynamics produce first-order methods that retain fast objective-value convergence while adding fast gradient convergence, global iterate convergence, nonsmooth extensions, and time-scaling acceleration.

  • Conclusion: Hessian-driven inertial dynamics generate a new class of first-order algorithms for convex optimization.The algorithms retain function-value convergence associated with Nesterov acceleration.
  • Conclusion: The principal additional properties are fast gradient convergence, global convergence of iterates, nonsmooth extensions, and acceleration through time-scaling factors.These properties summarize the paper’s stated contributions.
  • Perspectives: The authors identify future work on structured composite splitting, restart methods, and links with Newton, Levenberg–Marquardt, and Ravine methods.These directions are presented as research avenues rather than established results.

A.1 Extended descent lemma

The section develops descent and duality arguments for smooth convex functions, then analyzes inertial dynamics on quadratic objectives through decoupled eigenmodes. It also derives explicit special-case solutions and asymptotic behavior, while extending the framework toward nonsmooth objectives via Moreau envelopes.

  • Extended descent lemma: For an L-smooth convex function and step size s ≤ 1/L, the proof applies the standard descent lemma to y − s∇f(y).The resulting inequality is used as a basic estimate in the analysis.
  • Extended descent lemma: L-Lipschitz continuity of ∇f is linked by Fenchel duality to 1/L-strong convexity of the conjugate f∗.The argument also uses (∇f)^−1 = ∂f∗ before inserting the resulting inequality into the Fenchel identity.
  • Quadratic dynamics: For quadratic objectives with symmetric positive definite A, projection onto A’s eigenspaces reduces the dynamics to n independent one-dimensional ODEs.Each mode is associated with an eigenvalue λ_i > 0.
  • Quadratic dynamics: With constant β > 0, the Hessian-driven term forces exponential decrease in the quadratic dynamics.The asymptotic analysis uses special-function expansions for M, U, Jν, and Yν.
  • Time-scaled damping: Time-varying damping schedules are transformed into a special case of the earlier ODE, yielding corresponding asymptotic estimates.For β(t) = t^β and b(t) = ct^(β−1), the transformed variable satisfies a first-order linear ODE before parameter substitution.
Loading 1907.10536v2…