Primal–dual accelerated gradient methods with small-dimensional relaxation oracle. (4th July 2021)

• Record Type: Journal Article
• Authors: Nesterov, Yurii; Gasnikov, Alexander; Guminov, Sergey; Dvurechensky, Pavel
• Is Part Of: Optimization methods and software. Volume 36:Number 4(2021)
• Page Start: 773
• Page End: 810
• Publication Date: 2021-07-04
• Subjects: Accelerated gradient descent -- line-search -- primal–dual methods -- convex optimization -- nonconvex optimization; 90C25 -- 68Q25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1731747
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, a new variant of accelerated gradient descent is proposed. The proposed method does not require any information about the objective function, uses exact line search for the practical accelerations of convergence, converges according to the well-known lower bounds for both convex and non-convex objective functions, possesses primal–dual properties and can be applied in the non-euclidian set-up. As far as we know this is the first such method possessing all of the above properties at the same time. We also present a universal version of the method which is applicable to non-smooth problems. We demonstrate how in practice one can efficiently use the combination of line-search and primal-duality by considering a convex optimization problem with a simple structure (for example, linearly constrained).