Tight analyses for subgradient descent I: Lower bounds
Open Journal of Mathematical Optimization · 2024
DOI: 10.5802/ojmo.31 ↗At a glance
Journal article in Open Journal of Mathematical Optimization, 2024. Written by Nicholas J. A. Harvey and 2 co-authors. Cited 1 times so far (Crossref); 17 references.
Abstract (original language)
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).
Cite
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