← All setups

Minimization with Bounded Temporal Discrepancy

Descriptions may be stale. Consult the linked Lean sources.

Minimization with Bounded Temporal Discrepancy

We consider minimizing a twice continuously differentiable function f:E→R on a finite-dimensional real Hilbert space E. The function is μ-strongly convex with L-Lipschitz gradient and M-Lipschitz Hessian, where 0<μ≤L and M≥0. A given starting point x0∈E has objective gap at most Δ≥0 above a global minimizer x⋆. The oracle returns the gradient plus a fixed deterministic error sequence 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 ∥⋅∥op denotes the induced operator norm. The algorithm receives E, x0, μ, L, M, D, Δ, and ε.

Our assumptions:

Assumption 1 (Strong convexity and smoothness). The function f is twice continuously Fréchet differentiable. For every x,y∈E, f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥2,∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 2 (Lipschitz Hessian). The Hessian ∇2f(x):E→E satisfies ∥∇2f(x)−∇2f(y)∥op≤M∥x−y∥,x,y∈E.

Assumption 3 (Bounded temporal discrepancy). There is a fixed deterministic sequence (ek)k≥0 in E. At the kth call, indexed from zero, a query x∈E returns gk(x)=∇f(x)+ek. The cumulative errors satisfy ‖∑k=0n−1ek‖≤D,n=0,1,2,….

Assumption 4 (Initial objective gap). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,f(x0)−f(x⋆)≤Δ.

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

On a finite-dimensional real Hilbert space, f∈C2 is μ-strongly convex, L-smooth, and ∥∇2f(x)−∇2f(y)∥≤M∥x−y∥, with 0<μ≤L. A minimizer x∗ exists and f(x0)−f(x∗)≤Δ. Call k returns ∇f(x)+ek, with hidden, query- and seed-independent errors satisfying supn∥∑k<nek∥≤D. Here M,D,Δ≥0, ε>0; all parameters are supplied. The target is f(xout)−f(x∗)≤ε; (1) achieves it for every seed. Costs count all gradient replies, including batches and padding. The reviews identify no concrete application establishing this exact cancellation model.

Temporal-discrepancy acceleration under the HessianLipschitzTemporalDiscrepancy setup.
Result Oracle complexity Novelty Limitations
(1) NonlinearTemporalAcceleration (Ours) (⋆⋆⋆) (review) O([κ(1+MDμ2)+Dμε]ℓ)
(2) Restarted, batched AGD+ (Cohen et al. 2018); Derived bound from Lemma 3.2 and Eq. (3.2). O(κ[ℓ0+Dμε])

(1): noise cost Dℓ/με instead of κD/με. Total speedup ≍κ/ℓ when κ≥Cℓ, D≥Cℓμε, Mεℓ≤μ3/2/C.

For μ=M=D=Δ=1, L=ε−1, ε→0: O(ε−1/2log⁡(1/ε)) instead of O(ε−1).

(1) needs Lipschitz Hessian and known M; adds κMDℓ/μ2. Can lose for small noise or Mε≫μ3/2.
(3) Quadratic dilation reduction (Schmidt et al. 2011), Prop. 4; specialization to M=0. O(κℓ0+Dμε) (1): scope extends from quadratics to nonlinear Hessian-Lipschitz objectives. The dilation reduction requires affine gradients. Matches known acceleration when D=0. (1) at M=0: extra ℓ0 factor on the noise term.

Abbr: κ=L/μ; ℓ0=1+log⁡(1+Δ/ε); ℓ=1+log⁡(1+Δ/ε+M2Δ/μ3); C is a sufficiently large universal constant. ≍ denotes equality up to universal factors; log is natural.

Cohen, Michael B., Jelena Diakonikolas, and Lorenzo Orecchia. 2018. “On Acceleration with Noise-Corrupted Gradients.” In Proceedings of the 35th International Conference on Machine Learning, edited by Jennifer Dy and Andreas Krause, vol. 80. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v80/cohen18a.html.
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