← All setups

Linear Predictor BFGS — BFGS for Linear Predictors

Descriptions may be stale. Consult the linked Lean sources.

BFGS for Linear Predictors · Lean proof

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.

Proved result

⌈35⋅Lhμ⋅c1⋅(1−c2)⋅Lh⋅L⋅R2μ⋅c1⋅(1−c2)⋅ε⌉++1

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

Relevant previous results