EUVIMEDEUVIMED entdecken
Crossref

Tight analyses for subgradient descent I: Lower bounds

Nicholas J. A. Harvey, Chris Liaw, Sikander Randhawa

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →