← All setups

Temporal Accelerated Quadratic — Quadratic Minimization with Temporal Discrepancy

Descriptions may be stale. Consult the linked Lean sources.

Quadratic Minimization with Temporal Discrepancy · Lean proof

Quadratic Minimization with Temporal Discrepancy

We consider minimizing f(x)=∥A(x−x⋆)∥2/2 on a real Hilbert space E, where A:E→E is bounded and linear and x⋆∈E. For constants 0<μ≤L, assume μ∥v∥2≤∥Av∥2≤L∥v∥2 for every v∈E. A given starting point x0∈E satisfies f(x0)≤Δ, where Δ≥0. At call k≥0, the oracle returns ∇f(x)+ek, with fixed errors ek∈E whose partial sums have norm at most D≥0. For ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm is induced by the inner product on E, and A∗ denotes the Hilbert-space adjoint of A. The algorithm receives only E, L, μ, and x0; the discrepancy bound D, initial objective bound Δ, and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Quadratic structure). The objective and its gradient are f(x)=12∥A(x−x⋆)∥2,∇f(x)=A∗A(x−x⋆),x∈E, where A:E→E is a bounded linear operator satisfying μ∥v∥2≤∥Av∥2≤L∥v∥2,v∈E. In particular, x⋆ is the unique minimizer and f(x⋆)=0.

Assumption 2 (Initial objective bound). The given starting point satisfies f(x0)≤Δ.

Assumption 3 (Temporal discrepancy). There is a fixed deterministic sequence (ek)k≥0 in E such that the oracle reply at call k, for any query x∈E, is gk(x)=A∗A(x−x⋆)+ek. Its cumulative error satisfies ‖∑k=0n−1ek‖≤D,n=0,1,2,…, with the empty sum equal to zero.

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Proved result

2⋅max{1,⌈Lμ⋅log⁡(1+8⋅Δε)+8⋅Dμ⋅ε⌉+}

OracleTemplate.Convergence LongTails.Setups.QuadraticTemporalDiscrepancy.spec OracleTemplate.TemporalDiscrepancy.budget

Relevant previous results

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