Affine Softmax Finite Maximum — Smooth Finite-Maximum Minimization
Descriptions may be stale. Consult the linked Lean sources.
Smooth Finite-Maximum Minimization · Lean proof
Smooth
Finite-Maximum Minimization
We minimize over , where is a finite-dimensional real
inner-product space, ,
, and is an integer. Each is convex on , differentiable at every point of , and has an -Lipschitz gradient bounded in norm by
, where and . The oracle returns at with . Given and , the goal is a measurable
output almost surely
satisfying with
probability at least ,
where minimizes on and probabilities follow the law of the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives , , , , , , , and ; the component functions and the
minimizer are accessed only through the specified oracle
information.
Our assumptions:
Assumption 1 (Component convexity). For every , , and ,
Assumption 2 (Component regularity). Each is Fréchet
differentiable at every . For
every and ,
Assumption 3 (Constrained minimizer). There exists
such that
Oracle access consists of component queries: choosing an index and a point returns the exact value and
gradient of that component. Each such pair is obtained in one oracle
call.
After the allotted calls, the output must be measurable and satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothFiniteMaximum.spec OracleTemplate.AffineSoftmaxFiniteMaximum.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.