Descriptions may be stale. Consult the linked Lean sources.
BFGS for Linear
Predictors
We consider BFGS for minimizing on , where is linear
and is
convex with Lipschitz gradient. A given starting point lies within distance of a global minimizer , and the objective gap controls
squared prediction distance on the initial sublevel set. The oracle
returns a step length and the exact gradient at the resulting point,
satisfying Armijo–Wolfe conditions for descent directions. For , the goal is a last
iterate satisfying
almost surely under , the law of
the oracle’s randomness.
The optimization problem is Here , both spaces carry
their Euclidean inner products and norms, and denotes the induced
operator norm. The parameters satisfy The
algorithm receives only ;
the parameters may enter
the oracle-call budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is differentiable
everywhere, and for every and , The linear map satisfies
Assumption 2 (Initial distance and prediction
growth). There exists such that For every with ,
Assumption 3 (Armijo–Wolfe oracle). A query is any
pair .
The oracle returns
with
Whenever , the reply also satisfies These conditions hold for every query, every
prior query–reply history, and every realization of the oracle
randomness. Replies may depend on the history and may be dependent
across calls.
The task is algorithm-specific: we analyze BFGS with a scalar initial
Hessian approximation. The algorithm chooses using only its available inputs
and initializes at the
given point . One initial query
supplies ; its step-length reply
is discarded. For , the
method queries , receives
, and updates
To define the recurrence also in singular cases,
a scalar reciprocal at zero is taken to be zero, and the inverse of a
singular matrix is the zero matrix.
After the initial query and updates, the output is
the last iterate , using
oracle calls in total. With
zero calls, the output is . The
required accuracy is