Zeroth-Order Matrix-Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Zeroth-Order Matrix-Smooth Convex Minimization
We consider minimizing a twice differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and differentiability). The
function
Assumption 2 (Matrix generalized smoothness). There
exists a symmetric matrix
Assumption 3 (Initial distance and objective gap).
There exists a global minimizer
Function-value queries may be made at any point of
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ZerothOrderMatrixGeneralizedAccelerated
(Ours) |
|||
| (2) RS-NAG (Omiya et al. 2026), Thm. 3.3, Prop. 5.2. Derived bound: independent runs, best-value selection. | (1): Scope extends to
|
(1): Adds |
|
| (3) AGD (Tyurin 2026), Thm. 4.3; Euclidean reduction. | (1): Values suffice; no
|
(1): Probabilistic
instead of deterministic accuracy; needs |
|
| (4) Uniform coordinate acceleration (Lobanov 2026), Thm. 6. | (1): Values replace
derivatives and exact segment solves; |
||
| (5) Importance-sampled coordinate acceleration (Lobanov 2026), Thm. 8. | (1): No
coordinate-curvature inputs; |
Abbr: