2020/09/08 by Nikita O. Pletnev, Pletnev, Nikita
Computer Science · Mathematics · Medicine · #Advanced Optimization Algorithms Research #Advanced Technologies in Various Fields #FOS: Mathematics #Optical Imaging and Spectroscopy Techniques #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2009.03971
openalex publication_date 2020/09/08 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The work is devoted to the construction of efficient and applicable to real\ntasks first-order methods of convex optimization, that is, using only values of\nthe target function and its derivatives. Construction uses OGM-G, fast gradient\nmethod which is optimal by complexity, but requires to know the Lipschitz\nconstant for gradient and the strong convexity constant to determine the number\nof steps and step length. This requirement makes practical usage impossible. An\nadaptive on the constant for strong convexity algorithm ACGM is proposed, based\non restarts of the OGM-G with update of the strong convexity constant estimate,\nand an adaptive on the Lipschitz constant for gradient ALGM, in which the use\nof OGM-G restarts is supplemented by the selection of the Lipschitz constant\nwith verification of the convexity conditions used in the universal gradient\ndescent method. This eliminates the disadvantages of the original method\nassociated with the need to know these constants, which makes practical usage\npossible. Optimality of estimates for the complexity of the constructed\nalgorithms is proved. To verify the results obtained, experiments on model\nfunctions and real tasks from machine learning are carried out.\n