← All setups

BFGS for Linear Predictors

Descriptions may be stale. Consult the linked Lean sources.

BFGS for Linear Predictors

We consider BFGS for minimizing f(x)=h(Ax) on Rd, where A:Rd→Rm is linear and h:Rm→R is convex with Lipschitz gradient. A given starting point x0 lies within distance R≥0 of a global minimizer x⋆, 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 ε>0, the goal is a last iterate x¯ satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the oracle’s randomness.

The optimization problem is minx∈Rdf(x). Here d,m∈N0, both spaces carry their Euclidean inner products and norms, and ∥A∥op denotes the induced operator norm. The parameters satisfy 0<μ≤Lh,L>0,0<c1<c2<1,R≥0,ε>0. The algorithm receives only d,m,x0,L; the parameters Lh,μ,c1,c2,R,ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function h is differentiable everywhere, and for every z,w∈Rm and t∈[0,1], h((1−t)z+tw)≤(1−t)h(z)+th(w),∥∇h(z)−∇h(w)∥≤Lh∥z−w∥. The linear map satisfies Lh∥A∥op2≤L.

Assumption 2 (Initial distance and prediction growth). There exists x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R. For every x∈Rd with f(x)≤f(x0), μ2∥Ax−Ax⋆∥2≤f(x)−f(x⋆).

Assumption 3 (Armijo–Wolfe oracle). A query is any pair (x,v)∈Rd×Rd. The oracle returns (α,g)∈R×Rd with g=∇f(x+αv). Whenever ⟨∇f(x),v⟩<0, the reply also satisfies α>0,f(x+αv)≤f(x)+c1α⟨∇f(x),v⟩,⟨g,v⟩≥c2⟨∇f(x),v⟩. 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 c>0 using only its available inputs and initializes B0=cId at the given point x0. One initial query (x0,0) supplies g0=∇f(x0); its step-length reply is discarded. For k≥0, the method queries (xk,vk), receives (αk,gk+1), and updates vk=−Bk−1gk,sk=αkvk,xk+1=xk+sk,yk=gk+1−gk,Bk+1=Bk−(Bksk)(Bksk)TskTBksk+ykykTykTsk. 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 K∈N0 updates, the output is the last iterate x¯=xK, using K+1 oracle calls in total. With zero calls, the output is x0. The required accuracy is f(x¯)−f(x⋆)≤εP-a.s.

Results

f(x)=h(Ax) on Rd, with linear A:Rd→Rm, convex Lh-smooth h, L≥Lh∥A∥2, L>0, and 0<μ≤Lh. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and μ2∥A(x−x⋆)∥2≤f(x)−f(x⋆) whenever f(x)≤f(x0). The setup restricts algorithms to BFGS with positive scalar initialization; (1) uses B0=LI. The oracle returns an Armijo–weak-Wolfe step and its endpoint gradient, with 0<c1<c2<1. Target: f(xK)−f(x⋆)≤ε, ε>0, for every admissible oracle history. Bundled line-search calls include initialization; internal search trials have no stated gradient/value-call budget.

BFGS for linear-predictor objectives: LinearPredictorBFGS.
Result Oracle complexity Novelty Limitations
(1) LinearPredictorBFGS (Ours) (⋆⋆⋆) (review) O(1+κ3/2γ−3/2LR2/ε) line-search calls.
(2) BFGS (Ding et al. 2026, Thm. 3.1, Eq. (11)) O(1+LW02γε) line-search calls; B0=LI, W0<∞. (1): Distance-only BFGS bound, independent of design conditioning; ε−1/2 instead of ε−1. For W0≍R, total gain when LR2/ε≫κ3/γ. No uniform W0 bound in setup parameters: h(z)=∥z∥2/2, A=diag(1,δ), x0=(R,0) give W0≥R/(2δ). (1) needs composite growth; (2) covers general convex smooth objectives with finite W0. For W0≍R, (1) loses at coarse accuracy and has worse γ dependence.
(3) AGD/FISTA (Beck and Teboulle 2009, Thm. 4.4), fixed step, ψ=0 O(1+LR2/ε) gradient calls, available through v=0 queries; applies throughout the target objective class. (1) matches the ε−1/2 order for BFGS, with extra parameter factors; no problem-class complexity improvement. (1) pays κ3/2γ−3/2 and a larger leading constant; needs composite growth and line-search access instead of gradients alone.

Abbr: κ=Lh/μ; γ=c1(1−c2); f⋆=f(x⋆); X⋆=argminf; W0=supx∉X⋆,f(x)≤f(x0)(f(x)−f⋆)/∥∇f(x)∥; ψ is the FISTA nonsmooth term; δ>0 is a design singular value; ≍ means equality up to universal factors; ≫ means asymptotically larger.

Beck, Amir, and Marc Teboulle. 2009. “A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems.” SIAM Journal on Imaging Sciences 2 (1): 183–202. https://doi.org/10.1137/080716542.
Ding, Lijun, Jinwen Yang, and Baoyu Zhou. 2026. On the Complexity of BFGS Method for Smooth Convex Optimization. https://doi.org/10.48550/arXiv.2608.16009.

Lean setup