High-Dimensional Constrained Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Constrained Quasar Minimization
We minimize a possibly nonconvex function
The optimization problem is
The parameters satisfy
Our assumptions:
Assumption 1 (Feasible set and minimizer). The set
Assumption 2 (Smoothness and quasar convexity). The
function
Assumption 3 (Stochastic gradient oracle). There is
a probability distribution
Assumption 4 (Projection oracle). The projection
oracle returns
Both oracles accept queries anywhere in
Results
- High Dimensional Constrained Quasar Lower Bound · Lean proof
- High Dimensional Constrained Quasar Upper Bound · Lean proof
Compact convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) HighDimensionalConstrainedQuasarLowerBound
(Ours) |
|||
| (2) HighDimensionalConstrainedQuasarUpperBound (Ours) (review) | |||
| (3) (Hinder et al. 2020), Theorem 3 | (1): Same
deterministic-term order for every randomized algorithm. The additional
|
(1): Needs polynomially large dimension; allows uninformative exterior replies and establishes no randomized lower bound for the unconstrained oracle model. |
Abbr:
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (4) (Saad et al. 2025), Theorem 3.4 | (1): High-probability
noise term has an algebraic factor |
(1): Much larger
dimension; excludes |
|
| (5) (LongTails 2026), StochasticConstrainedQuasarHighProbability | (2): Matches known rate, oracle access and probability guarantee; obtained by restricting (5). | (2): Boolean seeds,
dimension floor, excluded small-noise band and |
|
| (6) (Martínez-Rubio
2026), Theorem 5; |
(2):
Gradient-and-projection access suffices without values; extends to
finite-variance noise. At |
(2): Extra |
|
| (7) QASGD (Fu et al. 2023),
Corollary 3.3, |
(2): Scope includes
constrained boundary minimizers. On common unconstrained instances with
|
(2): Needs compact |
Abbr: