Tight analyses for subgradient descent I: Lower bounds
Open Journal of Mathematical Optimization · 2024
DOI: 10.5802/ojmo.31 ↗Kurz gefasst
Fachartikel in der Zeitschrift Open Journal of Mathematical Optimization, 2024. Verfasst von Nicholas J. A. Harvey und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 17 Literaturangaben.
Abstract (Originalsprache)
Consider the problem of minimizing functions that are Lipschitz and convex, but not necessarily differentiable. We construct a function from this class for which the T þ iterate of subgradient descent has error Ω ( log ( T ) / T ) . This matches a known upper bound of O ( log ( T ) / T ) . We prove analogous results for functions that are additionally strongly convex. There exists such a function for which the error of the T þ iterate of subgradient descent has error Ω ( log ( T ) / T ) , matching a known upper bound of O ( log ( T ) / T ) . These results resolve a question posed by Shamir (2012).
Zitieren
APA
Harvey, N. J. A., Liaw, C., & Randhawa, S. (2024). Tight analyses for subgradient descent I: Lower bounds. Open Journal of Mathematical Optimization. https://doi.org/10.5802/ojmo.31
Vancouver
Harvey NJA, Liaw C, Randhawa S. Tight analyses for subgradient descent I: Lower bounds. Open Journal of Mathematical Optimization. 2024. doi:10.5802/ojmo.31
BibTeX
@article{Harvey2024,
author = {Harvey, Nicholas J. A. and Liaw, Chris and Randhawa, Sikander},
title = {Tight analyses for subgradient descent I: Lower bounds},
journal = {Open Journal of Mathematical Optimization},
year = {2024},
doi = {10.5802/ojmo.31}
}
EUVIMED