| | |
| | |
Stat |
Members: 3645 Articles: 2'506'133 Articles rated: 2609
27 April 2024 |
|
| | | |
|
Article overview
| |
|
Near-optimal tensor methods for minimizing the gradient norm of convex function | Pavel Dvurechensky
; Alexander Gasnikov
; Petr Ostroukhov
; César A. Uribe
; Anastasiya Ivanova
; | Date: |
7 Dec 2019 | Abstract: | Motivated by convex problems with linear constraints and, in particular, by
entropy-regularized optimal transport, we consider the problem of finding
$varepsilon$-approximate stationary points, i.e. points with the norm of the
objective gradient less than $varepsilon$, 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
$ ilde{O}(varepsilon^{-2(p+1)/(3p+1)})$ and
$ ilde{O}(varepsilon^{-2/(3p+1)})$ with respect to the initial objective
residual and the distance between the starting point and solution respectively. | Source: | arXiv, 1912.3381 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |