Descriptions may be stale. Consult the linked Lean sources.
Self-Concordant Minimization
with BFGS
We consider minimizing over an open
convex set ,
where is an integer. On
, the function is self-concordant
with positive definite Hessian, has closed sublevel sets, and attains
its minimum at . BFGS
starts from a given and
positive definite matrix , with
bounded initial objective gap and Hessian mismatch. The oracle returns a
feasible Armijo–Wolfe step and its endpoint gradient. For , the goal is a last
iterate satisfying
almost surely under , the law of
the oracle randomness.
The optimization problem is We use the coordinate space with its supremum norm and
the pairing . The gradient denotes the coordinate representation of the
derivative, so . Write for the Hessian matrix. The algorithm receives only , , and ; the parameters , , , and may enter the call
budget, with also
specifying the oracle conditions.
Our assumptions:
Assumption 1 (Domain and self-concordance). The set
is open and convex. The function
is three times Fréchet
differentiable on . For every
, every nonzero , and every , For every , the set is closed in .
Assumption 2 (Minimizer and initialization). The
given point satisfies , and
is
symmetric positive definite. There exists such that For positive definite matrices , define The initial Hessian mismatch satisfies
Assumption 3 (Armijo–Wolfe oracle). A query consists
of a point and a direction
satisfying . The reply
satisfies If , it also
satisfies These conditions hold for every query history and
every realization of the oracle randomness. Replies may depend on that
history, and randomness across calls may be dependent. For a direction
with zero directional derivative, only endpoint feasibility and the
exact endpoint gradient are required.
Our result is algorithm-specific: we analyze BFGS with the given
initial matrix . The first
oracle call queries to
obtain , leaving
and unchanged. Thereafter, for , the method queries and receives , with The Hessian approximation is updated by Each scalar reciprocal
in this formula is defined to be zero when its denominator is zero; the
matrix inverse is likewise defined to be the zero matrix when singular.
Thus the recurrence also specifies the update at a stationary point.
Each oracle call returns the step and endpoint gradient together.
After calls, including the
initialization call, the output is the last iterate ; with zero calls it is
. The required accuracy
is