Zeroth Order Matrix Generalized Accelerated — Zeroth-Order Matrix-Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Zeroth-Order Matrix-Smooth Convex Minimization · Lean proof
Zeroth-Order
Matrix-Smooth Convex Minimization
We consider minimizing a twice differentiable convex function , where . The function is matrix -smooth, with and , relative to an unknown positive
definite matrix bounded above by
the identity and satisfying , where . A given point satisfies and for a global
minimizer , with . The oracle returns the
scalar at . For and , the goal is a measurable
output satisfying with
probability at least over
the algorithm’s randomness.
The optimization problem is We use the
Euclidean inner product and its induced
norm . The algorithm
receives ,
and ; the matrix and the minimizer are not supplied.
Our assumptions:
Assumption 1 (Convexity and differentiability). The
function is differentiable
everywhere, its gradient is differentiable everywhere, and
Assumption 2 (Matrix generalized smoothness). There
exists a symmetric matrix and a constant
such that Write and
. The Hessian, viewed as a linear operator on
, satisfies
Assumption 3 (Initial distance and objective gap).
There exists a global minimizer such that
Function-value queries may be made at any point of . After the allotted calls,
the output
must be measurable and satisfy
where is the law of the
algorithm’s randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.ZerothOrderMatrixGeneralizedSmooth.spec
OracleTemplate.MatrixGeneralizedZO.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.