← All setups

Quadratic Minimization with Temporal Discrepancy

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a real Hilbert space, f(x)=12∥A(x−x∗)∥2 for bounded linear A, with μ∥v∥2≤∥Av∥2≤L∥v∥2, 0<μ≤L, and f(x0)≤Δ. Call k returns A∗A(x−x∗)+ek, where deterministic, query-independent errors satisfy supn∥∑k<nek∥≤D. Here D,Δ≥0 and ε>0. Target: f(xout)−f(x∗)≤ε for every seed. The setup imposes no algorithm restriction.

Temporal gradient discrepancy on quadratics: QuadraticTemporalDiscrepancy.
Result Oracle complexity Novelty Limitations
(1) TemporalAcceleratedQuadratic (Ours) (review) O(1+κℓ+Dμε)
(2) Derived bound: batching and dilation, (Schmidt et al. 2011, Prop. 4, v2); Hilbert-space extension O(1+κℓ+Dμε); includes initial batch and all dilated queries; smooth specialization. (1): Matches known rate. No precision-dependent dilation; updates need neither D nor ε. Stopping still needs D,Δ,ε; no adaptive stopping guarantee. (1): Tail average instead of the last iterate.
(3) Derived bound: batching without dilation, (Schmidt et al. 2011, Prop. 4, v2); Hilbert-space extension O(1+κℓ[1+κDμε]), Δ>ε; counts every batch sample; smooth specialization. (1): Noise term D/με instead of κℓD/με; gain for D≥με, κ≫1. Updates need neither D nor ε; stopping does. (2) already matches (1). (1): Tail average instead of the last iterate.
(4) Subsequent repository result (NonlinearTemporalAcceleration.lean, n.d.); finite-dimensional quadratic restriction O([1+κ+Dμε]log(2+Δε)), with M=0. (1): Removes log⁡(2+Δ/ε) from the noise term on the quadratic overlap; also permits infinite-dimensional Hilbert spaces. (1): Quadratics only; (4) also covers nonquadratic objectives with Lipschitz Hessian.

Abbr: κ=L/μ; ℓ=log⁡(1+Δ/ε); M is the Lipschitz constant of ∇2f. Costs count primitive gradient-oracle calls. The tail average in (1) averages iterates K+1,…,2K over 2K calls.

NonlinearTemporalAcceleration.lean. n.d. Lean theorem in the LongTails repository. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/NonlinearTemporalAcceleration.lean.
Schmidt, Mark, Nicolas Le Roux, and Francis Bach. 2011. Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization. https://doi.org/10.48550/arXiv.1109.2415.

Lean setup