Descriptions may be stale. Consult the linked Lean sources.
Generalized Smooth
Finite-Sum Minimization
We consider minimizing on a real
Hilbert space , where is an integer. Each component
is convex,
continuously differentiable, and -smooth, with and . A global minimizer satisfies bounds on its distance
from a given starting point , the initial objective gap, and the average
component-gradient norm at .
At a query , the oracle
returns . For
, the goal is a
measurable output with
integrable objective gap satisfying ,
where is the law of the
algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on , which is equipped with a
measurable structure. The algorithm receives , , , , , , , , and .
Our assumptions:
Assumption 1 (Component convexity). For every , , and ,
Assumption 2 (Generalized smoothness). Each is Fréchet differentiable everywhere,
and is
continuous. For every , , and satisfying we have
Assumption 3 (Minimizer and initial bounds). There
exists such that
The algorithm may query any component at any point in ; each query returns the exact component
value and gradient together. After the allotted oracle calls, its output
must be measurable, its
objective gap must be integrable under , and it must satisfy