WIAS Preprint No. 2694, (2020)

Near-optimal tensor methods for minimizing gradient norm


Authors

  • Dvurechensky, Pavel
    ORCID: 0000-0003-1201-2343
  • Gasnikov, Alexander
    ORCID: 0000-0003-1201-2343
  • Ostroukhov, Petr
  • Uribe, A. Cesar
  • Ivanova, Anastasiya

2010 Mathematics Subject Classification

  • 90C30 90C25 68Q25

Keywords

  • Convex optimization, tensor methods, gradient norm, nearly optimal methods

DOI

10.20347/WIAS.PREPRINT.2694

Abstract

Motivated by convex problems with linear constraints and, in particular, by entropy-regularized optimal transport, we consider the problem of finding approximate stationary points, i.e. points with the norm of the objective gradient less than small error, of convex functions with Lipschitz p-th order derivatives. Lower complexity bounds for this problem were recently proposed in [Grapiglia and Nesterov, arXiv:1907.07053]. However, the methods presented in the same paper do not have optimal complexity bounds. We propose two optimal up to logarithmic factors methods with complexity bounds with respect to the initial objective residual and the distance between the starting point and solution respectively

Download Documents