Lipschitz minimization and the Goldstein modulus
<|reference_start|>Lipschitz minimization and the Goldstein modulus: 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.<|reference_end|>
@article{kong2024lipschitz,
    title={Lipschitz minimization and the Goldstein modulus},
    author={Siyu Kong and Adrian S. Lewis},
    journal={arXiv preprint arXiv:2405.12655},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.12655},
    primaryClass={math.OC cs.NA math.NA}
}