Tight analyses for subgradient descent I: Lower bounds
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 $\Omega (\log (T)/\sqrt{T})$. This matches a known upper bound of $O(\log (T)/\sqrt{T})$...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2024-07-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.31/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825205177153486848 |
|---|---|
| author | Harvey, Nicholas J. A. Liaw, Chris Randhawa, Sikander |
| author_facet | Harvey, Nicholas J. A. Liaw, Chris Randhawa, Sikander |
| author_sort | Harvey, Nicholas J. A. |
| collection | DOAJ |
| description | 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 $\Omega (\log (T)/\sqrt{T})$. This matches a known upper bound of $O(\log (T)/\sqrt{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 $\Omega (\log (T)/T)$, matching a known upper bound of $O(\log (T)/T)$. These results resolve a question posed by Shamir (2012). |
| format | Article |
| id | doaj-art-cee8a4a556b344b2a67fb81b0a9fa7d3 |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2024-07-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-cee8a4a556b344b2a67fb81b0a9fa7d32025-02-07T14:01:17ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602024-07-01511710.5802/ojmo.3110.5802/ojmo.31Tight analyses for subgradient descent I: Lower boundsHarvey, Nicholas J. A.0Liaw, Chris1Randhawa, Sikander2University of British ColumbiaGoogle ResearchUniversity of British ColumbiaConsider 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 $\Omega (\log (T)/\sqrt{T})$. This matches a known upper bound of $O(\log (T)/\sqrt{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 $\Omega (\log (T)/T)$, matching a known upper bound of $O(\log (T)/T)$. These results resolve a question posed by Shamir (2012).https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.31/Gradient descentFirst-order methodsLower bounds |
| spellingShingle | Harvey, Nicholas J. A. Liaw, Chris Randhawa, Sikander Tight analyses for subgradient descent I: Lower bounds Open Journal of Mathematical Optimization Gradient descent First-order methods Lower bounds |
| title | Tight analyses for subgradient descent I: Lower bounds |
| title_full | Tight analyses for subgradient descent I: Lower bounds |
| title_fullStr | Tight analyses for subgradient descent I: Lower bounds |
| title_full_unstemmed | Tight analyses for subgradient descent I: Lower bounds |
| title_short | Tight analyses for subgradient descent I: Lower bounds |
| title_sort | tight analyses for subgradient descent i lower bounds |
| topic | Gradient descent First-order methods Lower bounds |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.31/ |
| work_keys_str_mv | AT harveynicholasja tightanalysesforsubgradientdescentilowerbounds AT liawchris tightanalysesforsubgradientdescentilowerbounds AT randhawasikander tightanalysesforsubgradientdescentilowerbounds |