Descriptions may be stale. Consult the linked Lean sources.
Capped Hessian-Similar
Convex Minimization
We minimize on a finite-dimensional real inner product space , where is an integer. The components
are
differentiable and convex, is
-strongly convex for , and the centered gradients
are jointly
-Lipschitz in root mean
square, with . A given
has objective gap at most
from a minimizer . Each oracle call returns exact
component gradients or proximal points for at most selected components.
For , the goal is a
measurable output with
integrable gap and ,
where is the law of the
algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on , which is also equipped with a
measurable structure. The algorithm receives , , , , , , , and .
Our assumptions:
Assumption 1 (Component convexity and strong
convexity). Each is Fréchet
differentiable everywhere. For all , , and ,
Assumption 2 (Mean-square similarity). Define . For all
,
Assumption 3 (Initial objective gap). There exists
such that
Oracle access is organized into capped calls. A call selects a set
with . For each , it independently specifies a
query point and either a
gradient request or a proximal request with coefficient . The corresponding exact reply
is, respectively, where the proximal map
satisfies, for every , , and , The reply has one
entry per component, with zero entries outside . Gradient and proximal requests may be
combined within a single call; the budget counts these capped calls.
After the allotted calls, the output must be measurable and its
objective gap must be integrable under . The required accuracy is