Stochastic Constrained Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Constrained Quasar Minimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Feasible geometry). The set
Assumption 2 (Smoothness and quasar convexity). The
function
Assumption 3 (Stochastic gradient oracle). There are
a probability measure
Assumption 4 (Exact projection oracle). The
projection oracle returns
Both oracles accept queries throughout
Results
A finite-dimensional real Hilbert space; compact convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticConstrainedQuasarHighProbability
(Ours) |
|||
| (2) (Martínez-Rubio 2026), Thm. 5 | (1): Scope:
finite-variance stochastic gradients. Oracle: removes function values.
Matches deterministic polynomial rate at |
(1): At |
|
| (3) QASGD (Fu et al. 2023), Cor. 3.3 | (1): Scope: constrained boundary minimizers; variance instead of gradient-second-moment bound. Oracle: no component values. High-confidence guarantee. | (1): Needs compact |
|
| (4) Derived bound: (Fu et al. 2023), Cor. 3.3 + Markov | (1): On overlap with
|
(1): Requires a known
compact feasible set containing a global minimizer; |
Abbr: