Black Box Diagonal Acceleration — Hidden Diagonal Curvature Minimization
Descriptions may be stale. Consult the linked Lean sources.
Hidden Diagonal Curvature Minimization · Lean proof
Hidden Diagonal Curvature
Minimization
We consider minimizing a differentiable function , where , with a given starting point . For hidden weights
, its
first-order remainder lies between and , where and
. A global minimizer
satisfies , with . The oracle returns at . For , the goal is
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The inner
product and gradient are Euclidean. The algorithm receives only and ; the weights , relative curvature
parameter , initial gap bound
, and tolerance may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Diagonal curvature bounds). The
function is differentiable
everywhere. For every ,
Assumption 2 (Initial objective gap). There exists
such that
Queries may be made at any point of , with each call returning
the exact function value and Euclidean gradient together. After the
allotted oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.DiagonalSmoothStronglyConvexBlackBox.spec
OracleTemplate.BlackBoxDiagonal.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.