← All setups

Self-Concordant Minimization with BFGS

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On an open convex D⊆Rd, f has three derivatives, positive-definite Hessian, closed sublevel sets, and a minimizer x⋆∈D, with |D3f(x)[h,v,v]|≤2D2f(x)[h,h]D2f(x)[v,v]. Assume x0∈D, B0≻0, initial gap at most Δ, mismatch at most Φ0, and 0<c1<c2<1. The setup requires unmodified BFGS; each oracle call returns an admissible weak-Wolfe step and exact gradient. Target: f(xT)−f(x⋆)≤ε for every admissible oracle realization.

Comparison for SelfConcordantBFGS.
Result Oracle complexity Novelty Limitations
(1) SelfConcordantBFGS (Ours) (⋆⋆⋆) (review) O((d+1)(Δ+1)2c13m2+(d+1)2(Δ+1)c1m4+Φ0m2+log⁡(2+1/ε)m) Wolfe calls, including initialization.
(2) BFGS (Jin and Mokhtari 2025), Thms. 3.1, 3.3, 4.3; App. D O(1+min{Ψ(B¯)+(1+D0)2ℓ,Ω+ℓ,Ω+ℓlog⁡(2+ℓ/Ω)}) Wolfe calls; fixed c1,c2, c1<1/2. Restricted to strongly self-concordant objectives on Rd.

(1): Scope extends to standard self-concordance, including barriers. For B0=aH⋆, a≫1, mismatch dependence becomes dlog⁡a instead of linear in a (other parameters fixed). Allows c1≥1/2.

For B0≈H⋆, 1≤d≪Δ, log⁡(1/ε)≲dΔ2: O(dΔ2) versus the O(Δ3+log⁡(1/ε)) bound (93); not dominance over the displayed minimum.

(1): No superlinear phase; extra d2(1+Δ) can hurt when d≳Δ. Larger constants. Internal line-search evaluations unbounded here; (2) bounds them.

Abbr: m=min{c1,1−c2}; Δ≥f(x0)−f(x⋆); Φ0≥2log⁡det(B0+H0)−log⁡detB0−log⁡detH0−2dlog⁡2, H0=∇2f(x0). For (2), normalize an M-strongly self-concordant objective by M2/4, including its gap and accuracy. D0=2ω−1(Δ), ω(s)=s−log⁡(1+s); H⋆=∇2f(x⋆), B~=H⋆−1/2B0H⋆−1/2, B¯=B~/(1+D0), Ψ(A)=trA−d−log⁡detA, Ω=Ψ(B~)+[Ψ(B¯)+(1+D0)2]D0, ℓ=1+log+⁡(Δ/ε), log+⁡s=max{0,log⁡s}. Quotients at Ω=0 use their limiting value.

Jin, Qiujiang, and Aryan Mokhtari. 2025. Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS Under Self-Concordance. https://doi.org/10.48550/arXiv.2507.00361.

Lean setup