Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization
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_ | 1866929760472399872 |
|---|---|
| author | Lei, Ming Pong, Ting Kei Sun, Shuqin Yue, Man-Chung |
| author_facet | Lei, Ming Pong, Ting Kei Sun, Shuqin Yue, Man-Chung |
| contents | We study the class of subdifferentially polynomially bounded (SPB) functions, which is a rich class of locally Lipschitz functions that encompasses all Lipschitz functions, all gradient- or Hessian-Lipschitz functions, and even some non-smooth locally Lipschitz functions. We show that SPB functions are compatible with Gaussian smoothing (GS), in the sense that the GS of any SPB function is well-defined and satisfies a descent lemma akin to gradient-Lipschitz functions, with the Lipschitz constant replaced by a polynomial function. Leveraging this descent lemma, we propose GS-based zeroth-order optimization algorithms with an adaptive stepsize strategy for minimizing SPB functions, and analyze their convergence rates with respect to both relative and absolute stationarity measures. Finally, we also establish the iteration complexity for achieving a $(δ, ε)$-approximate stationary point, based on a novel quantification of Goldstein stationarity via the GS gradient that could be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04150 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization Lei, Ming Pong, Ting Kei Sun, Shuqin Yue, Man-Chung Optimization and Control We study the class of subdifferentially polynomially bounded (SPB) functions, which is a rich class of locally Lipschitz functions that encompasses all Lipschitz functions, all gradient- or Hessian-Lipschitz functions, and even some non-smooth locally Lipschitz functions. We show that SPB functions are compatible with Gaussian smoothing (GS), in the sense that the GS of any SPB function is well-defined and satisfies a descent lemma akin to gradient-Lipschitz functions, with the Lipschitz constant replaced by a polynomial function. Leveraging this descent lemma, we propose GS-based zeroth-order optimization algorithms with an adaptive stepsize strategy for minimizing SPB functions, and analyze their convergence rates with respect to both relative and absolute stationarity measures. Finally, we also establish the iteration complexity for achieving a $(δ, ε)$-approximate stationary point, based on a novel quantification of Goldstein stationarity via the GS gradient that could be of independent interest. |
| title | Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2405.04150 |