Accelerated Mirror Descent for Non-Euclidean Star-convex Functions

Clement LEZANE, Sophie Langer, Wouter M Koolen
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-41, 2026.

Abstract

Acceleration for non-convex functions is a fundamental challenge in optimization. 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 $\alpha$-Holder continuous gradients and demonstrate that our rates are nearly optimal for $p$-norms. [1] Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-lezane26a, title = {Accelerated Mirror Descent for Non-Euclidean Star-convex Functions}, author = {LEZANE, Clement and Langer, Sophie and Koolen, Wouter M}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--41}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/lezane26a/lezane26a.pdf}, url = {https://proceedings.mlr.press/v313/lezane26a.html}, abstract = {Acceleration for non-convex functions is a fundamental challenge in optimization. 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 $\alpha$-Holder continuous gradients and demonstrate that our rates are nearly optimal for $p$-norms. [1] Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond} }
Endnote
%0 Conference Paper %T Accelerated Mirror Descent for Non-Euclidean Star-convex Functions %A Clement LEZANE %A Sophie Langer %A Wouter M Koolen %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-lezane26a %I PMLR %P 1--41 %U https://proceedings.mlr.press/v313/lezane26a.html %V 313 %X Acceleration for non-convex functions is a fundamental challenge in optimization. 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 $\alpha$-Holder continuous gradients and demonstrate that our rates are nearly optimal for $p$-norms. [1] Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond
APA
LEZANE, C., Langer, S. & Koolen, W.M.. (2026). Accelerated Mirror Descent for Non-Euclidean Star-convex Functions. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-41 Available from https://proceedings.mlr.press/v313/lezane26a.html.

Related Material