# Accelerated Mirror Descent for Non-Euclidean Star-convex Functions

arXiv: https://arxiv.org/abs/2405.18976 · HTML: https://mlsanity.com/paper/2405.18976/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2024.

## Built on by (most cited first, 1 of 1)

- [Smooth Quasar-Convex Optimization with Constraints](https://mlsanity.com/paper/2510.01943/) (2025)

## Abstract (arXiv)

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