Near-optimal tensor methods for minimizing gradient norm
Loading...
Date
2020
Volume
2694
Issue
Journal
Series Titel
Book Title
Publisher
Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik
Link to publishers version
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
Description
Keywords
Convex optimization, tensor methods, gradient norm, nearly optimal methods
Citation
Dvurechensky, P., Gasnikov, A., Ostroukhov, P., Uribe, A. C., & Ivanova, A. (2020). Near-optimal tensor methods for minimizing gradient norm (Vol. 2694). Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik. https://doi.org//10.20347/WIAS.PREPRINT.2694
Collections
License
This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties.
Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.