Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916850198118400 |
|---|---|
| author | Huang, Minhui Zhu, Weiming |
| author_facet | Huang, Minhui Zhu, Weiming |
| contents | We propose perturbed proximal algorithms that can provably escape strict saddles for nonsmooth weakly convex functions. The main results are based on a novel characterization of $ε$-approximate local minimum for nonsmooth functions, and recent developments on perturbed gradient methods for escaping saddle points for smooth problems. Specifically, we show that under standard assumptions, the perturbed proximal point, perturbed proximal gradient and perturbed proximal linear algorithms find $ε$-approximate local minimum for nonsmooth weakly convex functions in $O(ε^{-2}\log(d)^4)$ iterations, where $d$ is the dimension of the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_02837 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms Huang, Minhui Zhu, Weiming Machine Learning Optimization and Control We propose perturbed proximal algorithms that can provably escape strict saddles for nonsmooth weakly convex functions. The main results are based on a novel characterization of $ε$-approximate local minimum for nonsmooth functions, and recent developments on perturbed gradient methods for escaping saddle points for smooth problems. Specifically, we show that under standard assumptions, the perturbed proximal point, perturbed proximal gradient and perturbed proximal linear algorithms find $ε$-approximate local minimum for nonsmooth weakly convex functions in $O(ε^{-2}\log(d)^4)$ iterations, where $d$ is the dimension of the problem. |
| title | Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2102.02837 |