4.6 Article

A control-theoretic perspective on optimal high-order optimization

Related references

Note: Only part of the references are listed.
Article Operations Research & Management Science

Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping

Hedy Attouch et al.

Summary: In this paper, we study the convergence of a class of accelerated first-order algorithms in the setting of Hilbert spaces for convex optimization. These algorithms can be seen as discrete temporal versions of an inertial dynamic involving both viscous damping and Hessian-driven damping, with the asymptotically vanishing viscous damping associated with Nesterov's accelerated gradient method and the Hessian-driven damping enabling significant attenuation of oscillations. By treating the Hessian-driven damping as the time derivative of the gradient term, we obtain first-order algorithms in discretized form.

OPTIMIZATION (2023)

Article Computer Science, Software Engineering

Tensor methods for finding approximate stationary points of convex functions

G. N. Grapiglia et al.

Summary: This paper investigates the problem of finding epsilon-approximate stationary points of convex functions that are p-times differentiable with nu-Holder continuous pth derivatives. Tensor methods with and without acceleration are proposed, and the corresponding complexity bounds are obtained.

OPTIMIZATION METHODS & SOFTWARE (2022)

Article Mathematics, Applied

FAST CONVEX OPTIMIZATION VIA INERTIAL DYNAMICS COMBINING VISCOUS AND HESSIAN-DRIVEN DAMPING WITH TIME RESCALING

Hedy Attouch et al.

Summary: This paper develops fast methods for convex unconstrained optimization in a Hilbert setting. It introduces an inertial system with geometric damping and temporal scaling, and analyzes its asymptotic behavior. The obtained results include existing research on the topic and provide convergence rate analysis under general conditions. The paper focuses on the case of asymptotically vanishing viscous damping and demonstrates exponential convergence rate. This work opens up new possibilities for the development of inertial optimization algorithms.

EVOLUTION EQUATIONS AND CONTROL THEORY (2022)

Article Operations Research & Management Science

Fast Convergence of Dynamical ADMM via Time Scaling of Damped Inertial Dynamics

Hedy Attouch et al.

Summary: In this paper, a second-order time-continuous dynamic system is proposed in a Hilbertian setting to solve structured convex minimization problems with an affine constraint. The system is associated with the augmented Lagrangian formulation of the minimization problem. By adjusting time-varying parameters, fast convergence properties of values and feasibility gap are achieved.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS (2022)

Article Computer Science, Software Engineering

Implementable tensor methods in unconstrained convex optimization

Yurii Nesterov

Summary: In this paper, new tensor methods are developed for unconstrained convex optimization. These methods solve an auxiliary problem of minimizing convex multivariate polynomial at each iteration. The simplest scheme and its accelerated version are analyzed, with comparison of convergence rates to lower complexity bounds for corresponding problem classes. Furthermore, an efficient technique based on the relative smoothness condition is suggested for solving the auxiliary problem in third-order methods, resulting in fast implementation and convergence rates close to the lower bound.

MATHEMATICAL PROGRAMMING (2021)

Article Computer Science, Software Engineering

Tikhonov regularization of a second order dynamical system with Hessian driven damping

Radu Ioan Bot et al.

Summary: We investigate the asymptotic properties of trajectories generated by a second-order dynamical system with Hessian driven damping and a Tikhonov regularization term, in connection with minimizing a smooth convex function in Hilbert spaces. Fast convergence results for function values along the trajectories are obtained, with the Tikhonov regularization term enabling strong convergence of the trajectory to the minimizer of the objective function with minimum norm.

MATHEMATICAL PROGRAMMING (2021)

Article Mathematics, Applied

Continuous Newton-like Inertial Dynamics for Monotone Inclusions

Hedy Attouch et al.

Summary: In this study, we investigate the convergence properties of a Newton-like inertial dynamical system in a Hilbert framework, where the oscillations are significantly attenuated by introducing Hessian-driven damping. By replacing the maximally monotone operator with its Yosida approximation and introducing a Newton-like correction term, we obtain a well-posed evolution system with weak convergence towards the zeroes of the operator. Specializing to the case where the operator is the subdifferential of a convex lower semicontinuous function results in fast optimization outcomes.

SET-VALUED AND VARIATIONAL ANALYSIS (2021)

Article Mechanics

On dissipative symplectic integration with applications to gradient-based optimization

Guilherme Franca et al.

Summary: This paper introduces a geometric framework for systematically discretizing continuous-time dynamical systems to preserve stability and rates of convergence without the need for discrete convergence analysis. By generalizing symplectic integrators to non-conservative and dissipative Hamiltonian systems, rates of convergence can be preserved up to a controlled error, extending key results of symplectic integrators to non-conservative cases.

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT (2021)

Article Mathematics, Applied

UNIFIED ACCELERATION OF HIGH-ORDER ALGORITHMS UNDER GENERAL HO\LDER CONTINUITY

Chaobing Song et al.

Summary: This paper presents a concise unified acceleration framework for minimizing a convex function with Ho\lder continuous derivatives. The framework reconciles two different high-order acceleration approaches and unifies them with only a few parameters. It is the first approach to make high-order methods applicable for high-order smoothness conditions with respect to non-Euclidean norms.

SIAM JOURNAL ON OPTIMIZATION (2021)

Article Mathematics, Applied

GENERALIZED MOMENTUM-BASED METHODS: A HAMILTONIAN PERSPECTIVE

Jelena Diakonikolas et al.

Summary: The study generalizes Nesterov's accelerated gradient descent and Polyak's heavy ball method to a broad class of momentum methods, providing a generic and unifying nonasymptotic analysis of convergence based on time-dependent Hamiltonian and conserved quantities.

SIAM JOURNAL ON OPTIMIZATION (2021)

Article Computer Science, Software Engineering

Convergence of a relaxed inertial proximal algorithm for maximally monotone operators

Hedy Attouch et al.

MATHEMATICAL PROGRAMMING (2020)

Article Mechanics

Conformal symplectic and relativistic optimization

Guilherme Franca et al.

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT (2020)

Article Mathematics, Applied

TENSOR METHODS FOR MINIMIZING CONVEX FUNCTIONS WITH HOLDER CONTINUOUS HIGHER-ORDER DERIVATIVES

G. N. Grapiglia et al.

SIAM JOURNAL ON OPTIMIZATION (2020)

Article Mathematics, Applied

A UNIFIED ADAPTIVE TENSOR APPROXIMATION SCHEME TO ACCELERATE COMPOSITE CONVEX OPTIMIZATION

Bo Jiang et al.

SIAM JOURNAL ON OPTIMIZATION (2020)

Article Mathematics, Applied

CONVERGENCE RATES OF DAMPED INERTIAL DYNAMICS UNDER GEOMETRIC CONDITIONS AND PERTURBATIONS

O. Sebbouh et al.

SIAM JOURNAL ON OPTIMIZATION (2020)

Article Mathematics, Applied

NEWTON-LIKE INERTIAL DYNAMICS AND PROXIMAL ALGORITHMS GOVERNED BY MAXIMALLY MONOTONE OPERATORS

Hedy Attouch et al.

SIAM JOURNAL ON OPTIMIZATION (2020)

Article Automation & Control Systems

RATE OF CONVERGENCE OF THE NESTEROV ACCELERATED GRADIENT METHOD IN THE SUBCRITICAL CASE α ≤ 3

Hedy Attouch et al.

ESAIM-CONTROL OPTIMISATION AND CALCULUS OF VARIATIONS (2019)

Article Automation & Control Systems

RATE OF CONVERGENCE OF THE NESTEROV ACCELERATED GRADIENT METHOD IN THE SUBCRITICAL CASE α ≤ 3

Hedy Attouch et al.

ESAIM-CONTROL OPTIMISATION AND CALCULUS OF VARIATIONS (2019)

Article Computer Science, Software Engineering

Oracle complexity of second-order methods for smooth convex optimization

Yossi Arjevani et al.

MATHEMATICAL PROGRAMMING (2019)

Article Mathematics, Applied

UNIVERSAL REGULARIZATION METHODS: VARYING THE POWER, THE SMOOTHNESS AND THE ACCURACY

Coralia Cartis et al.

SIAM JOURNAL ON OPTIMIZATION (2019)

Article Mathematics, Applied

THE APPROXIMATE DUALITY GAP TECHNIQUE: A UNIFIED THEORY OF FIRST-ORDER METHODS

Jelena Diakonikolas et al.

SIAM JOURNAL ON OPTIMIZATION (2019)

Article Mathematics, Applied

ACCELERATED REGULARIZED NEWTON METHODS FOR MINIMIZING COMPOSITE CONVEX FUNCTIONS

Geovani N. Grapiglia et al.

SIAM JOURNAL ON OPTIMIZATION (2019)

Article Mathematics, Applied

FAST PROXIMAL METHODS VIA TIME SCALING OF DAMPED INERTIAL DYNAMICS

Hedy Attouch et al.

SIAM JOURNAL ON OPTIMIZATION (2019)

Article Computer Science, Software Engineering

Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity

Hedy Attouch et al.

MATHEMATICAL PROGRAMMING (2018)

Article Computer Science, Theory & Methods

Second-Order Optimality and Beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

Coralia Cartis et al.

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS (2018)

Article Mathematics

Convergence of damped inertial dynamics governed by regularized maximally monotone operators

Hedy Attouch et al.

JOURNAL OF DIFFERENTIAL EQUATIONS (2018)

Article Mathematics, Applied

THE DIFFERENTIAL INCLUSION MODELING FISTA ALGORITHM AND OPTIMALITY OF CONVERGENCE RATE IN THE CASE b ≤ 3

Apidopoulos Vassilis et al.

SIAM JOURNAL ON OPTIMIZATION (2018)

Article Mathematics, Applied

ANALYSIS OF OPTIMIZATION ALGORITHMS VIA INTEGRAL QUADRATIC CONSTRAINTS: NONSTRONGLY CONVEX PROBLEMS

Mahyar Fazlyab et al.

SIAM JOURNAL ON OPTIMIZATION (2018)

Article Computer Science, Software Engineering

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

E. G. Birgin et al.

MATHEMATICAL PROGRAMMING (2017)

Article Mathematics

Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity

Hedy Attouch et al.

JOURNAL OF DIFFERENTIAL EQUATIONS (2017)

Article Mathematics, Applied

ON HIGH-ORDER MODEL REGULARIZATION FOR CONSTRAINED OPTIMIZATION

Jose Mario Martinez

SIAM JOURNAL ON OPTIMIZATION (2017)

Article Mathematics, Applied

REGULARIZED NEWTON METHODS FOR MINIMIZING FUNCTIONS WITH HOLDER CONTINUOUS HESSIANS

G. N. Grapiglia et al.

SIAM JOURNAL ON OPTIMIZATION (2017)

Article Mathematics

Fast convex optimization via inertial dynamics with Hessian driven damping

Hedy Attouch et al.

JOURNAL OF DIFFERENTIAL EQUATIONS (2016)

Article Mathematics

Convergence to equilibrium for solutions of an abstract wave equation with general damping function

Tomas Barta et al.

JOURNAL OF DIFFERENTIAL EQUATIONS (2016)

Article Multidisciplinary Sciences

A variational perspective on accelerated methods in optimization

Andre Wibisono et al.

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA (2016)

Article Automation & Control Systems

SECOND ORDER FORWARD-BACKWARD DYNAMICAL SYSTEMS FOR MONOTONE INCLUSION PROBLEMS

Radu Ioan Bot et al.

SIAM JOURNAL ON CONTROL AND OPTIMIZATION (2016)

Article Mathematics, Applied

ANALYSIS AND DESIGN OF OPTIMIZATION ALGORITHMS VIA INTEGRAL QUADRATIC CONSTRAINTS

Laurent Lessard et al.

SIAM JOURNAL ON OPTIMIZATION (2016)

Article Mathematics, Applied

THE RATE OF CONVERGENCE OF NESTEROV'S ACCELERATED FORWARD-BACKWARD METHOD IS ACTUALLY FASTER THAN 1/k(2)

Hedy Attouch et al.

SIAM JOURNAL ON OPTIMIZATION (2016)

Article Mathematics

On damped second-order gradient systems

Pascal Begout et al.

JOURNAL OF DIFFERENTIAL EQUATIONS (2015)

Article Operations Research & Management Science

Newton-Like Dynamics and Forward-Backward Methods for Structured Monotone Inclusions in Hilbert Spaces

B. Abbas et al.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS (2014)

Article Operations Research & Management Science

Global Convergence of a Closed-Loop Regularized Newton Method for Solving Monotone Inclusions in Hilbert Spaces

H. Attouch et al.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS (2013)

Article Computer Science, Software Engineering

Gradient methods for minimizing composite functions

Yu Nesterov

MATHEMATICAL PROGRAMMING (2013)

Article Automation & Control Systems

FIRST-ORDER CONTINUOUS NEWTON-LIKE SYSTEMS FOR MONOTONE INCLUSIONS

Paul-Emile Mainge

SIAM JOURNAL ON CONTROL AND OPTIMIZATION (2013)

Article Mathematics, Applied

AN ACCELERATED HYBRID PROXIMAL EXTRAGRADIENT METHOD FOR CONVEX OPTIMIZATION AND ITS IMPLICATIONS TO SECOND-ORDER METHODS

Renato D. C. Monteiro et al.

SIAM JOURNAL ON OPTIMIZATION (2013)

Article Mathematics

Every ordinary differential equation with a strict Lyapunov function is a gradient system

Tomas Barta et al.

MONATSHEFTE FUR MATHEMATIK (2012)

Article Automation & Control Systems

A CONTINUOUS DYNAMICAL NEWTON-LIKE APPROACH TO SOLVING MONOTONE INCLUSIONS

H. Attouch et al.

SIAM JOURNAL ON CONTROL AND OPTIMIZATION (2011)

Article Computer Science, Software Engineering

Approximation accuracy, gradient methods, and error bound for structured convex optimization

Paul Tseng

MATHEMATICAL PROGRAMMING (2010)

Article Mathematics, Applied

ON THE COMPLEXITY OF THE HYBRID PROXIMAL EXTRAGRADIENT METHOD FOR THE ITERATES AND THE ERGODIC MEAN

Renato D. C. Monteiro et al.

SIAM JOURNAL ON OPTIMIZATION (2010)

Article Mathematics

CHARACTERIZATIONS OF LOJASIEWICZ INEQUALITIES: SUBGRADIENT FLOWS, TALWEG, CONVEXITY

Jerome Bolte et al.

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY (2010)

Article Computer Science, Artificial Intelligence

A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

Amir Beck et al.

SIAM JOURNAL ON IMAGING SCIENCES (2009)

Article Computer Science, Software Engineering

Accelerating the cubic regularization of Newton's method on convex problems

Yu. Nesterov

MATHEMATICAL PROGRAMMING (2008)

Article Mathematics, Applied

A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics

F Alvarez et al.

JOURNAL DE MATHEMATIQUES PURES ET APPLIQUEES (2002)

Article Automation & Control Systems

On the minimizing property of a second order dissipative system in Hilbert spaces

F Alvarez

SIAM JOURNAL ON CONTROL AND OPTIMIZATION (2000)