High Dimensional Strong Quasar Upper Bound — High-Dimensional Strong Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Strong Quasar Minimization · Lean proof
High-Dimensional Strong Quasar Minimization
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Parameter and dimension regime). The
dimension
Assumption 2 (Smoothness). The function
Assumption 3 (Strong quasar convexity and initial
gap). There exists a global minimizer
Queries may be made at any point of
Proved result
OracleTemplate.Convergence LongTails.Setups.HighDimensionalStrongQuasar.spec
LongTails.Theorems.HighDimensionalStrongQuasarUpperBound.budgetRelevant previous results
- Jun-Kun Wang and Andre Wibisono. Continuized Acceleration for
Quasar Convex Functions in Non-Convex Optimization. 2023, ICLR;
preprint v1. Complexity:
expected exact-gradient oracle calls for , using continuized Nesterov acceleration stopped at a fixed continuous time. - Julien Hermant, Jean-François Aujol, Charles Dossal, and Aude
Rondepierre. Study of the
behaviour of Nesterov Accelerated Gradient in a non convex setting: the
strongly quasar convex case. 2024 preprint; version used: v2, 2025.
Complexity:
fixed exact-gradient oracle calls for , using Nesterov accelerated gradient, provided for all .