Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.12655 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911883265572864 |
|---|---|
| author | Kong, Siyu Lewis, Adrian S. |
| author_facet | Kong, Siyu Lewis, Adrian S. |
| contents | Goldstein's 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance - the step size - and relies on a certain approximate subgradient. That "Goldstein subgradient" is the shortest convex combination of objective gradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang et al. 2020), and a more sophisticated variant (Davis and Jiang, 2022) leverages typical objective geometry to force near-linear convergence. To explore such methods, we introduce a new modulus, based on Goldstein subgradients, that robustly measures the slope of a Lipschitz function. We relate near-linear convergence of Goldstein-style methods to linear growth of this modulus at minimizers. We illustrate the idea computationally with a simple heuristic for Lipschitz minimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12655 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lipschitz minimization and the Goldstein modulus Kong, Siyu Lewis, Adrian S. Optimization and Control Numerical Analysis 90C56, 49J52, 65Y20 G.1.6 Goldstein's 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance - the step size - and relies on a certain approximate subgradient. That "Goldstein subgradient" is the shortest convex combination of objective gradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang et al. 2020), and a more sophisticated variant (Davis and Jiang, 2022) leverages typical objective geometry to force near-linear convergence. To explore such methods, we introduce a new modulus, based on Goldstein subgradients, that robustly measures the slope of a Lipschitz function. We relate near-linear convergence of Goldstein-style methods to linear growth of this modulus at minimizers. We illustrate the idea computationally with a simple heuristic for Lipschitz minimization. |
| title | Lipschitz minimization and the Goldstein modulus |
| topic | Optimization and Control Numerical Analysis 90C56, 49J52, 65Y20 G.1.6 |
| url | https://arxiv.org/abs/2405.12655 |