Fast adaptive by constants of strong-convexity and Lipschitz for gradient first order methods

Pletnev N.V.
 pdf (11051K)

The work is devoted to the construction of efficient and applicable to real tasks first-order methods of convex optimization, that is, using only values of the target function and its derivatives. Construction uses OGMG, fast gradient method which is optimal by complexity, but requires to know the Lipschitz constant for gradient and the strong convexity constant to determine the number of steps and step length. This requirement makes practical usage very hard. An adaptive on the constant for strong convexity algorithm ACGM is proposed, based on restarts of the OGM-G with update of the strong convexity constant estimate, and an adaptive on the Lipschitz constant for gradient ALGM, in which the use of OGM-G restarts is supplemented by the selection of the Lipschitz constant with verification of the smoothness conditions used in the universal gradient descent method. This eliminates the disadvantages of the original method associated with the need to know these constants, which makes practical usage possible. Optimality of estimates for the complexity of the constructed algorithms is proved. To verify the results obtained, experiments on model functions and real tasks from machine learning are carried out.

Keywords: fast gradient method, adaptivity on the constant for strong convexity, adaptivity on the Lipschitz constant for gradient
Citation in English: Pletnev N.V. Fast adaptive by constants of strong-convexity and Lipschitz for gradient first order methods // Computer Research and Modeling, 2021, vol. 13, no. 5, pp. 947-963
Citation in English: Pletnev N.V. Fast adaptive by constants of strong-convexity and Lipschitz for gradient first order methods // Computer Research and Modeling, 2021, vol. 13, no. 5, pp. 947-963
DOI: 10.20537/2076-7633-2021-13-5-947-963
URL: http://crm-en.ics.org.ru/journal/article/3121/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science