Advanced Search
Article Contents
Article Contents

On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping

  • * Corresponding author: Hedy Attouch

    * Corresponding author: Hedy Attouch 

The last author is supported by the OP VVV project CZ.02.1.01/0.0/0.0/16_019/0000765 "Research Center for Informatics"

Abstract Full Text(HTML) Figure(2) Related Papers Cited by
  • Second-order continuous-time dissipative dynamical systems with viscous and Hessian driven damping have inspired effective first-order algorithms for solving convex optimization problems. While preserving the fast convergence properties of the Nesterov-type acceleration, the Hessian driven damping makes it possible to significantly attenuate the oscillations. To study the stability of these algorithms with respect to perturbations, we analyze the behaviour of the corresponding continuous systems when the gradient computation is subject to exogenous additive errors. We provide a quantitative analysis of the asymptotic behaviour of two types of systems, those with implicit and explicit Hessian driven damping. We consider convex, strongly convex, and non-smooth objective functions defined on a real Hilbert space and show that, depending on the formulation, different integrability conditions on the perturbations are sufficient to maintain the convergence rates of the systems. We highlight the differences between the implicit and explicit Hessian damping, and in particular point out that the assumptions on the objective and perturbations needed in the implicit case are more stringent than in the explicit case.

    Mathematics Subject Classification: 37N40, 46N10, 49M30, 65B99, 65K05, 65K10, 90B50, 90C25.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Example on a smooth function: Evolution of the objective error and distance to the minimizer as a function of $ t $ for different error decay exponents

    Figure 2.  Example on a non-smooth function: Evolution of the objective error and distance to the minimizer as a function of $ t $ for different error decay exponents

  • [1] S. Adly and H. Attouch, Finite convergence of proximal-gradient inertial algorithms combining dry friction with Hessian-driven damping, SIAM J. Optim., 30 (2020), 2134-2162.  doi: 10.1137/19M1307779.
    [2] S. Adly and H. Attouch, Finite time stabilization of continuous inertial dynamics combining dry friction with Hessian-driven damping, J. Conv. Analysis, 28 (2021), 281-310. 
    [3] C. D. Alecsa, S. László and T. Pinţa, An extension of the second order dynamical system that models Nesterov's convex gradient method, Appl. Math. Optim., 84 2020), 1687–1716. doi: 10.1007/s00245-020-09692-1.
    [4] F. AlvarezH. AttouchJ. Bolte and P. Redont, A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics, J. Math. Pures Appl., 81 (2002), 747-779.  doi: 10.1016/S0021-7824(01)01253-3.
    [5] V. ApidopoulosJ.-F. Aujol and C. Dossal, Convergence rate of inertial Forward-Backward algorithm beyond Nesterov's rule, Math. Program. Ser. A, 180 (2020), 137-156.  doi: 10.1007/s10107-018-1350-9.
    [6] H. Attouch, R. I. Boţ and E. R. Csetnek, Fast optimization via inertial dynamics with closed-loop damping, Journal of the European Mathematical Society (JEMS), (2021), arXiv: 2008.02261v2 [math. OC].
    [7] H. Attouch and A. Cabot, Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity, J. Differential Equations, 263 (2017), 5412-5458.  doi: 10.1016/j.jde.2017.06.024.
    [8] H. Attouch, A. Cabot, Z. Chbani and H. Riahi, Accelerated forward-backward algorithms with perturbations: Application to Tikhonov regularization, J. Optim. Theory Appl., 179 (2018), 1–36. doi: 10.1007/s10957-018-1369-3.
    [9] H. Attouch, Z. Chbani, J. Fadili and H. Riahi, First order optimization algorithms via inertial systems with Hessian driven damping, Math. Program., (2020). doi: 10.1007/s10107-020-01591-1.
    [10] H. Attouch, Z. Chbani, J. Fadili and H. Riahi, Convergence of iterates for first-order optimization algorithms with inertia and hessian driven damping, Optimization, (2021). doi: 10.1080/02331934.2021.2009828.
    [11] H. AttouchZ. ChbaniJ. Peypouquet and P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program. Ser. B, 168 (2018), 123-175.  doi: 10.1007/s10107-016-0992-8.
    [12] H. Attouch, Z. Chbani and H. Riahi, Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha \leq 3$, ESAIM Control Optim. Calc. Var., 25 (2019), Paper No. 2, 34 pp. doi: 10.1051/cocv/2017083.
    [13] H. AttouchZ. Chbani and H. Riahi, Fast proximal methods via time scaling of damped inertial dynamics, SIAM J. Optim., 29 (2019), 2227-2256.  doi: 10.1137/18M1230207.
    [14] H. Attouch and M.-O. Czarnecki, Asymptotic control and stabilization of nonlinear oscillators with non-isolated equilibria, J. Differential Equations, 179 (2002), 278-310.  doi: 10.1006/jdeq.2001.4034.
    [15] H. Attouch and A. Damlamian, Strong solutions for parabolic variational inequalities, Nonlinear Analysis, 2 (1978), 329-353.  doi: 10.1016/0362-546X(78)90021-4.
    [16] H. Attouch and S. C. László, Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators, SIAM J. Optim., 30 (2020), 3252-3283.  doi: 10.1137/20M1333316.
    [17] H. Attouch and S. C. László, Continuous Newton-like inertial dynamics for monotone inclusions, Set-Valued Var. Anal., 29 (2020), 555-581.  doi: 10.1007/s11228-020-00564-y.
    [18] H. AttouchP.-E. Maingé and P. Redont, A second-order differential system with Hessian-driven damping; Application to non-elastic shock laws, Differ. Equ. Appl., 4 (2012), 27-65.  doi: 10.7153/dea-04-04.
    [19] H. AttouchJ. Peypouquet and P. Redont, Fast convex minimization via inertial dynamics with Hessian driven damping, J. Differential Equations, 261 (2016), 5734-5783.  doi: 10.1016/j.jde.2016.08.020.
    [20] J.-F. Aujol and C. Dossal, Stability of over-relaxations for the forward-backward algorithm, application to FISTA, SIAM J. Optim., 25 (2015), 2408-2433.  doi: 10.1137/140994964.
    [21] J.-F. AujolC. Dossal and A. Rondepierre, Optimal convergence rates for Nesterov acceleration, SIAM J. Optim., 29 (2019), 3131-3153.  doi: 10.1137/18M1186757.
    [22] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202.  doi: 10.1137/080716542.
    [23] R. I. BotE. R. Csetnek and S. C. Laszlo, Tikhonov regularization of a second order dynamical system with Hessian damping, Math. Program. Ser. B, 189 (2021), 151-186.  doi: 10.1007/s10107-020-01528-8.
    [24] H. Brézis, Opérateurs Maximaux Monotones Dans Les Espaces de Hilbert et Équations D'évolution, Lecture Notes 5, North Holland, 1972.
    [25] C. Castera, J. Bolte, C. Févotte and E. Pauwels, An inertial newton algorithm for deep learning, J. Mach. Learn. Res., 22 (2021), Paper No. 134, 31 pp. doi: 10.22405/2226-8383-2021-22-2-121-134.
    [26] A. Chambolle and Ch. Dossal, On the convergence of the iterates of the "fast iterative shrinkage thresholding algorithm", J. Opt. Theory Appl., 166 (2015), 968-982.  doi: 10.1007/s10957-015-0746-4.
    [27] A. Haraux and M. A. Jendoubi, On a second order dissipative ode in Hilbert space with an integrable source term, Acta Math. Sci., 32 (2012), 155-163.  doi: 10.1016/S0252-9602(12)60009-5.
    [28] T. Lin and M. I. Jordan, A control-theoretic perspective on optimal high-order optimization, (2019), arXiv: 1912.07168v1 [math. OC].
    [29] M. Muehlebach and M. I. Jordan, A dynamical systems perspective on nesterov acceleration, (2019), arXiv: 1905.07436.
    [30] Y. Nesterov, A method of solving a convex programming problem with convergence rate $O(1/k^2)$, Dokl. Akad. Nauk SSSR, 269 (1983), 543-547. 
    [31] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization, 87. Kluwer Academic Publishers, Boston, MA, 2004. doi: 10.1007/978-1-4419-8853-9.
    [32] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc., 73 (1967), 591-597.  doi: 10.1090/S0002-9904-1967-11761-0.
    [33] B. T. Polyak, Introduction to Optimization, Optimization Software, Inc., Publications Division, New York, 1987.
    [34] M. Schmidt, N. Le Roux and F. Bach, Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization, NIPS'11 - 25 th Annual Conference on Neural Information Processing Systems, Dec 2011, Grenada, Spain, HAL inria-00618152v3.
    [35] B. Shi, S. S. Du, M. I. Jordan and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, Math. Program., (2021). doi: 10.1007/s10107-021-01681-8.
    [36] W. Su, S. Boyd and E. J. Candès, A differential equation for modeling nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 27 (2016), Paper No. 153, 43 pp.
    [37] S. VillaS. SalzoL. Baldassarres and A. Verri, Accelerated and inexact forward-backward, SIAM J. Optim., 23 (2013), 1607-1633.  doi: 10.1137/110844805.
  • 加载中



Article Metrics

HTML views(624) PDF downloads(328) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint