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

2018/09/16 by Nesterov, Yurii, Gasnikov, Alexander, Guminov, Sergey +1 · 5 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1809.05895

Abstract

In this paper, a new variant of accelerated gradient descent is proposed. The pro-posed method does not require any information about the objective function, usesexact line search for the practical accelerations of convergence, converges accordingto 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. Asfar as we know this is the rst such method possessing all of the above properties atthe same time. We also present a universal version of the method which is applicableto non-smooth problems. We demonstrate how in practice one can efficiently use thecombination of line-search and primal-duality by considering a convex optimizationproblem with a simple structure (for example, linearly constrained).

Cited by

• Continuized Nesterov Acceleration for Non-Convex Optimization
• Smooth Quasar-Convex Optimization with Constraints
• Sparse Partial Optimal Transport via Quadratic Regularization
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L₀, L₁)-Smoothness
• Optimized methods for composite optimization: a reduction perspective

Related

• A universal accelerated primal-dual method for convex optimization problems
• Accelerated primal-dual methods for linearly constrained convex optimization problems
• Primal-dual fast gradient method with a model
• A Primal-Dual Type Algorithm with the O(1/t) Convergence Rate for Large Scale Constrained Convex Programs
• Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems