Primal–dual accelerated gradient methods with small-dimensional relaxation oracle

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).

Keywords:

• Accelerated gradient descent
• line-search
• primal–dual methods
• convex optimization
• nonconvex optimization

AMS Classifications:

• 90C25
• 68Q25

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The work in Section 2 was funded by Russian Science Foundation (project 18-71-10108). The work in Section 3 was supported by grant Russian Foundation for Basic Research (RFBR) 18-29-03071 mk. The work in Section 4 was supported by the Grant of the President of the Russian Federation MD-1320.2018.1 and RFBR 18-31-20005 mol_a_ved. The work of A. Gasnikov was partially supported by Yahoo Faculty Research and Engagement Program, 2019.