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

2019/07/24 by Hédy Attouch, Zaki Chbani, Attouch, Hedy +5 · 9 citations
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Optimization and Variational Analysis #Advanced Optimization Algorithms Research

paper · pdf · doi:10.48550/arxiv.1907.10536

Abstract

In a Hilbert space setting, for convex optimization, we analyze the\nconvergence rate of a class of first-order algorithms involving inertial\nfeatures. They can be interpreted as discrete time versions of inertial\ndynamics involving both viscous and Hessian-driven dampings. The geometrical\ndamping driven by the Hessian intervenes in the dynamics in the form \∇²\nf (x(t)) \x (t). By treating this term as the time derivative of \∇\nf (x (t)) , this gives, in discretized form, first-order algorithms in time\nand space. In addition to the convergence properties attached to Nesterov-type\naccelerated gradient methods, the algorithms thus obtained are new and show a\nrapid convergence towards zero of the gradients. On the basis of a\nregularization technique using the Moreau envelope, we extend these methods to\nnon-smooth convex functions with extended real values. The introduction of time\nscale factors makes it possible to further accelerate these algorithms. We also\nreport numerical results on structured problems to support our theoretical\nfindings.\n

Cited by

• Essential Convergence Rates of Continuous-Time Models for Optimization Methods
• The Dynamical Anatomy of Anderson Acceleration:From Adaptive Momentum to Variable-Mass ODEs
• Continuized Nesterov Acceleration for Non-Convex Optimization
• Inertial Primal Dual Dynamics with Hessian-driven Damping for Saddle Point Problems
• HNAG++: A Super-Fast Accelerated Gradient Method for Strongly Convex Optimization
• Inexact and Stochastic Gradient Optimization Algorithms with Inertia and Hessian Driven Damping
• A √(2)-accelerated FISTA for composite strongly convex problems
• Towards understanding Accelerated Stein Variational Gradient Flow -- Analysis of Generalized Bilinear Kernels for Gaussian target distributions
• Multiobjective Accelerated Gradient-like Flow with Asymptotic Vanishing Normalized Gradient

Related

• Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping
• Fast convex optimization via inertial dynamics combining viscous and\n Hessian-driven damping with time rescaling
• On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping
• Inertial Methods with Viscous and Hessian driven Damping for Non-Convex Optimization
• Fast convex optimization via inertial dynamics with Hessian driven\n damping