Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Lojasiewicz condition

被引：8

作者：

Apidopoulos, Vassilis ^{[1
]}

Ginatta, Nicolo ^{[2
]}

Villa, Silvia ^{[2
]}

机构：

[1] Univ Genoa, DIBRIS, MaLGa, Via Dodecaneso 35, I-16146 Genoa, Italy

[2] Univ Genoa, DIMA, MaLGa, Via Dodecaneso 35, I-16146 Genoa, Italy

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2022年 / 84卷 / 03期

基金：

欧洲研究理事会; 欧盟地平线“2020”;

关键词：

Non-convex optimization; Smooth optimization; Inertial dynamics; Heavy-ball method; Polyak-Lojasiewicz condition; Rates of convergence; 2ND-ORDER; SYSTEM;

D O I：

10.1007/s10898-022-01164-w

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study convergence of the trajectories of the Heavy Ball dynamical system, with constant damping coefficient, in the framework of convex and non-convex smooth optimization. By using the Polyak-Lojasiewicz condition, we derive new linear convergence rates for the associated trajectory, in terms of objective function values, without assuming uniqueness of the minimizer.

引用

页码：563 / 589

页数：27

共 44 条

[1]

Allen-Zhu Z, 2019, PR MACH LEARN RES, V97

[2] On the minimizing property of a second order dissipative system in Hilbert spaces [J].

Alvarez, F .

SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2000, 38 (04) :1102-1119

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

Alvarez, F ;

Attouch, H ;

Bolte, J ;

Redont, P .

JOURNAL DE MATHEMATIQUES PURES ET APPLIQUEES, 2002, 81 (08) :747-779

[4] Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions [J].

Apidopoulos, Vassilis ;

Aujol, Jean-Francois ;

Dossal, Charles ;

Rondepierre, Aude .

MATHEMATICAL PROGRAMMING, 2021, 187 (1-2) :151-193

[5] Convergence rate of inertial Forward-Backward algorithm beyond Nesterov's rule [J].

Apidopoulos, Vassilis ;

Aujol, Jean-Francois ;

Dossal, Charles .

MATHEMATICAL PROGRAMMING, 2020, 180 (1-2) :137-156

[6] The heavy ball with friction method, I. The continuous dynamical system: Global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system [J].

Attouch, H ;

Goudou, X ;

Redont, P .

COMMUNICATIONS IN CONTEMPORARY MATHEMATICS, 2000, 2 (01) :1-34

[7]

Attouch H., 2020, ARXIV PREPRINT ARXIV

[8]

Attouch H., 2002, ADV MATH SCI APPL, V12, P273

[9] First-order optimization algorithms via inertial systems with Hessian driven damping [J].

Attouch, Hedy ;

Chbani, Zaki ;

Fadili, Jalal ;

Riahi, Hassan .

MATHEMATICAL PROGRAMMING, 2022, 193 (01) :113-155

[10]

Attouch H, 2019, ESAIM CONTR OPTIM CA, V25, DOI 10.1051/cocv/2017083

← 1 2 3 4 5 →