← All setups

Self Concordant BFGS — Self-Concordant Minimization with BFGS

Descriptions may be stale. Consult the linked Lean sources.

Self-Concordant Minimization with BFGS · Lean proof

Self-Concordant Minimization with BFGS

We consider minimizing f:Rd→R over an open convex set D⊆Rd, where d≥0 is an integer. On D, the function is self-concordant with positive definite Hessian, has closed sublevel sets, and attains its minimum at x⋆∈D. BFGS starts from a given x0∈D and positive definite matrix B0, with bounded initial objective gap and Hessian mismatch. The oracle returns a feasible Armijo–Wolfe step and its endpoint gradient. For ε>0, the goal is a last iterate x¯∈D satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the oracle randomness.

The optimization problem is minx∈Df(x). We use the coordinate space Rd with its supremum norm and the pairing u⊤v=∑i=1duivi. The gradient denotes the coordinate representation of the derivative, so df(x)[v]=∇f(x)⊤v. Write H(x)=∇2f(x) for the Hessian matrix. The algorithm receives only d, x0, and B0; the parameters 0<c1<c2<1, Δ≥0, Φ0≥0, and ε>0 may enter the call budget, with c1,c2 also specifying the oracle conditions.

Our assumptions:

Assumption 1 (Domain and self-concordance). The set D is open and convex. The function f is three times Fréchet differentiable on D. For every x∈D, every nonzero v∈Rd, and every h∈Rd, v⊤H(x)v>0,|∇3f(x)[h,v,v]|≤2h⊤H(x)hv⊤H(x)v. For every a∈R, the set {x∈D:f(x)≤a} is closed in Rd.

Assumption 2 (Minimizer and initialization). The given point satisfies x0∈D, and B0∈Rd×d is symmetric positive definite. There exists x⋆∈D such that f(x⋆)≤f(x)for all x∈D,f(x0)−Δ≤f(x)for all x∈D. For positive definite matrices B,H, define Ψ(B,H)=2log⁡det(B+H)−log⁡detB−log⁡detH−2dlog⁡2. The initial Hessian mismatch satisfies Ψ(B0,H(x0))≤Φ0.

Assumption 3 (Armijo–Wolfe oracle). A query consists of a point x∈D and a direction v∈Rd satisfying ∇f(x)⊤v≤0. The reply (α,g+)∈R×Rd satisfies x+αv∈D,g+=∇f(x+αv). If ∇f(x)⊤v<0, it also satisfies α>0,f(x+αv)≤f(x)+c1α∇f(x)⊤v,c2∇f(x)⊤v≤(g+)⊤v. 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 B0. The first oracle call queries (x0,0) to obtain g0=∇f(x0), leaving x0 and B0 unchanged. Thereafter, for k≥0, the method queries (xk,vk) and receives (αk,gk+1), with vk=−(Bk)−1gk,sk=αkvk,xk+1=xk+sk,yk=gk+1−gk. The Hessian approximation is updated by Bk+1=Bk−(Bksk)(Bksk)⊤(sk)⊤Bksk+yk(yk)⊤(yk)⊤sk. 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 N≥1 calls, including the initialization call, the output is the last iterate x¯=xN−1; with zero calls it is x¯=x0. The required accuracy is x¯∈D,f(x¯)−f(x⋆)≤εP-a.s.

Proved result

⌈221⋅(d+1)⋅(Δ+1)⋅(Δ+1c13⋅(min{c1,1−c2})2+d+1c1⋅(min{c1,1−c2})4)+10⋅Φ0(min{c1,1−c2})2+4⋅log⁡(64+2ε)min{c1,1−c2}⌉++2

OracleTemplate.Convergence LongTails.Setups.SelfConcordantBFGS.spec LongTails.Theorems.SelfConcordantBFGS.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.