← All setups

Cyclic Gradient Under Interpolation

Descriptions may be stale. Consult the linked Lean sources.

Cyclic Gradient Under Interpolation

We consider minimizing F(x)=m−1∑i=0m−1fi(x) on a real Hilbert space E, where m≥1 is an integer. Each component fi:E→R is convex and differentiable with an L-Lipschitz gradient, where L>0. The components share a global minimizer x⋆, and the given starting point x0∈E satisfies ∥x0−x⋆∥≤R for R≥0. The oracle returns ∇fi(x) at a queried pair (i,x). Cyclic gradient descent with step size 1/L must return its last iterate x¯ with F(x¯)−F(x⋆)≤ε almost surely under the output law P, for ε>0.

The optimization problem is minx∈EF(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives only E, m, L, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Component convexity and smoothness). Each fi is Fréchet differentiable everywhere on E. For every i∈{0,…,m−1}, x,y∈E, and t∈[0,1], fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y),∥∇fi(x)−∇fi(y)∥≤L∥x−y∥.

Assumption 2 (Interpolation and initial distance). There exists x⋆∈E such that fi(x⋆)≤fi(x)for every i∈{0,…,m−1}, x∈E,∥x0−x⋆∥≤R.

The oracle accepts any component index and any point in E and returns the exact component gradient. Our formulation is algorithm-specific: we analyze cyclic gradient descent, initialized at the given point x0. Its updates are ik=kmodm,xk+1=xk−1L∇fik(xk),k=0,1,…. Each update uses one component-gradient call. After an allotted budget of K≥0 calls, with K an integer, the output is the last iterate x¯=xK. The required accuracy is F(x¯)−F(x⋆)=1m∑i=0m−1(fi(x¯)−fi(x⋆))≤εP-a.s. The common minimizer in this requirement is fixed independently of the output; all common minimizers have the same component objective values.

Results

On a real Hilbert space, m≥1 differentiable convex components have L-Lipschitz gradients, L>0, and a common minimizer x⋆ with ∥x0−x⋆∥≤R, R≥0. The oracle returns exact component gradients. The setup fixes cyclic gradient steps of size 1/L; the target is F(xout)−F(x⋆)≤ε, ε>0, almost surely, for the last complete-pass iterate. The guarantee holds for every outcome. Updates use m,L,x0; stopping additionally uses R,ε.

Comparison for InterpolatedFiniteSum.
Result Oracle complexity Novelty Limitations
(1) CyclicGradientInterpolation (Ours) (review) O(m+m4LR2ε)
(2) FISTA on F (Beck and Teboulle 2009, Thm. 4.4) O(m+mLR2ε)
Finite-dimensional specialization; m component calls per accelerated step.
(1): No established improvement in optimization complexity. (1): Larger bound by order m3T for T≥2; additionally requires interpolation.
(3) Cyclic IGD (Cai and Diakonikolas 2024, Thm. 2.3) O(m+mLR2εlog⁡(2+T))
Derived bound: finite dimension, interpolation; step η=[mLβ]−1, β=4max{1,log⁡K}.
(1): Removes log⁡(2+T) but adds m3; lower total order only when log⁡(2+T)≫m6. Scope: Hilbert spaces. Full-step analysis; horizon-independent updates, parameter-dependent stopping. (1): Requires interpolation, unlike the general theorem. On the common class, worse accuracy term when log⁡(2+T)≪m6.
(4) Cyclic projections (Evron et al. 2023, Prop. 4.13), m≥3 O(m+m4L2R4ε2)
Derived bound: fi=L2d(⋅,Ci)2, closed convex Ci⊂Rd with nonempty intersection; converted from maximum distance.
(1): On this subclass, ε−1 instead of ε−2, saving factor T for T≫1. Scope: arbitrary smooth interpolating losses; full-step cyclic analysis. (1): Certifies average loss, not maximum distance. Projection specialization is not formalized.
(5) Cyclic subspace projections (Swartworth et al. 2023, Thm. 1, Lem. 2) O(m+m3LR2ε)
Derived bound: fi=L2d(⋅,Ci)2 for linear subspaces Ci⊂Rd; one component call per projection.
(1): Scope extends from subspace squared distances to nonlinear convex sets and arbitrary smooth interpolating losses, retaining full-step cyclic updates. (1): Accuracy term is larger by factor m on the subspace subclass.
(6) Cyclic projections (Evron et al. 2023, Prop. 4.13), m=2 O(1+LR2ε)
Derived bound: fi=L2d(⋅,Ci)2, closed convex Ci⊂Rd with nonempty intersection.
(1): Matches known rate for m=2; extends squared-distance losses to arbitrary smooth interpolating losses. (1): Average loss instead of maximum-distance guarantee; projection specialization is not formalized.

Abbr: F=m−1∑i=1mfi; T=LR2/ε; K is the number of complete passes; d(x,C)=infy∈C∥x−y∥. Costs count individual component-gradient calls; on squared-distance losses, one call implements one exact projection. O suppresses universal constants.

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.
Cai, Xufeng, and Jelena Diakonikolas. 2024. Last Iterate Convergence of Incremental Methods and Applications in Continual Learning. https://doi.org/10.48550/arXiv.2403.06873.
Evron, Itay, Edward Moroshko, Gon Buzaglo, et al. 2023. “Continual Learning in Linear Classification on Separable Data.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 9440–84. https://proceedings.mlr.press/v202/evron23a.html.
Swartworth, William, Deanna Needell, Rachel Ward, Mark Kong, and Halyun Jeong. 2023. “Nearly Optimal Bounds for Cyclic Forgetting.” Advances in Neural Information Processing Systems 36: 68197–206. https://doi.org/10.52202/075280-2982.

Lean setup