Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.18976 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915144983904256 |
|---|---|
| author | Lezane, Clement Langer, Sophie Koolen, Wouter M |
| author_facet | Lezane, Clement Langer, Sophie Koolen, Wouter M |
| contents | Acceleration for non-convex functions is a fundamental challenge in optimisation. We revisit star-convex functions, which are strictly unimodal on all lines through a minimizer. [1] accelerate unconstrained star-convex minimization of functions that are smooth with respect to the Euclidean norm. To do so, they add a certain binary search step to gradient descent. In this paper, we accelerate unconstrained star-convex minimization of functions that are weakly smooth with respect to an arbitrary norm. We add a binary search step to mirror descent, generalize the approach and refine its complexity analysis. We prove that our algorithms have sharp convergence rates for star-convex functions with $α$-Holder continuous gradients and demonstrate that our rates are nearly optimal for $p$-norms.
[1] Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond, Hinder Oliver and Sidford Aaron and Sohoni Nimit |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18976 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Accelerated Mirror Descent for Non-Euclidean Star-convex Functions Lezane, Clement Langer, Sophie Koolen, Wouter M Optimization and Control Acceleration for non-convex functions is a fundamental challenge in optimisation. We revisit star-convex functions, which are strictly unimodal on all lines through a minimizer. [1] accelerate unconstrained star-convex minimization of functions that are smooth with respect to the Euclidean norm. To do so, they add a certain binary search step to gradient descent. In this paper, we accelerate unconstrained star-convex minimization of functions that are weakly smooth with respect to an arbitrary norm. We add a binary search step to mirror descent, generalize the approach and refine its complexity analysis. We prove that our algorithms have sharp convergence rates for star-convex functions with $α$-Holder continuous gradients and demonstrate that our rates are nearly optimal for $p$-norms. [1] Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond, Hinder Oliver and Sidford Aaron and Sohoni Nimit |
| title | Accelerated Mirror Descent for Non-Euclidean Star-convex Functions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2405.18976 |