Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918048962707456 |
|---|---|
| author | Bai, Cedar Site Bullins, Brian |
| author_facet | Bai, Cedar Site Bullins, Brian |
| contents | In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order Hölder smooth and uniformly convex functions. Specifically, for a function whose $p^{th}$-order derivatives are Hölder continuous with degree $ν$ and parameter $H$, and that is uniformly convex with degree $q$ and parameter $σ$, we focus on two asymmetric cases: (1) $q > p + ν$, and (2) $q < p+ν$. Given up to $p^{th}$-order oracle access, we establish worst-case oracle complexities of $Ω\left( \left( \frac{H}σ\right)^\frac{2}{3(p+ν)-2}\left( \fracσε\right)^\frac{2(q-p-ν)}{q(3(p+ν)-2)}\right)$ in the first case with an $\ell_\infty$-ball-truncated-Gaussian smoothed hard function and $Ω\left(\left(\frac{H}σ\right)^\frac{2}{3(p+ν)-2}+ \log\log\left(\left(\frac{σ^{p+ν}}{H^q}\right)^\frac{1}{p+ν-q}\frac{1}ε\right)\right)$ in the second case, for reaching an $ε$-approximate solution in terms of the optimality gap. Our analysis generalizes previous lower bounds for functions under first- and second-order smoothness as well as those for uniformly convex functions, and furthermore our results match the corresponding upper bounds in this general setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10773 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity Bai, Cedar Site Bullins, Brian Optimization and Control Machine Learning In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order Hölder smooth and uniformly convex functions. Specifically, for a function whose $p^{th}$-order derivatives are Hölder continuous with degree $ν$ and parameter $H$, and that is uniformly convex with degree $q$ and parameter $σ$, we focus on two asymmetric cases: (1) $q > p + ν$, and (2) $q < p+ν$. Given up to $p^{th}$-order oracle access, we establish worst-case oracle complexities of $Ω\left( \left( \frac{H}σ\right)^\frac{2}{3(p+ν)-2}\left( \fracσε\right)^\frac{2(q-p-ν)}{q(3(p+ν)-2)}\right)$ in the first case with an $\ell_\infty$-ball-truncated-Gaussian smoothed hard function and $Ω\left(\left(\frac{H}σ\right)^\frac{2}{3(p+ν)-2}+ \log\log\left(\left(\frac{σ^{p+ν}}{H^q}\right)^\frac{1}{p+ν-q}\frac{1}ε\right)\right)$ in the second case, for reaching an $ε$-approximate solution in terms of the optimality gap. Our analysis generalizes previous lower bounds for functions under first- and second-order smoothness as well as those for uniformly convex functions, and furthermore our results match the corresponding upper bounds in this general setting. |
| title | Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2409.10773 |