Finite-Sum Minimization on an \(\ell_1\) Ball
Descriptions may be stale. Consult the linked Lean sources.
Finite-Sum Minimization on
an Ball
We consider minimizing over ,
where are positive integers and
. Each component is convex
and differentiable, with an -Lipschitz gradient in the Euclidean
norm, where . The oracle
returns at a queried
component and feasible point
. For , the goal is a
measurable output with
integrable objective gap satisfying ,
where minimizes on and is the law of the algorithm’s
randomness.
The constraint uses , while denotes the Euclidean norm.
The optimization problem is The algorithm receives , and .
Our assumptions:
Assumption 1 (Component convexity). For every , every , and every ,
Assumption 2 (Component smoothness). Each is differentiable everywhere on , and
Oracle queries consist of a chosen index and a point . The smoothness and convexity
conditions hold on the entire ambient space, although queries are
restricted to .
Continuity of and compactness
of ensure that a constrained
minimizer exists. Fix
satisfying After the allotted oracle
calls, the output must be a measurable -valued random variable. Its objective
gap must satisfy
Results
Lean setup