2024/05/29 by Clément Lezane, Lezane, Clement, Sophie Langer +3 · 2 citations
Physics and Astronomy · Engineering · #Adaptive optics and wavefront sensing #Spacecraft Dynamics and Control #Space Satellite Systems and Control
paper · pdf · doi:10.48550/arxiv.2405.18976
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