Cyclic Gradient Under Interpolation
Descriptions may be stale. Consult the linked Lean sources.
Cyclic Gradient Under Interpolation
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity and smoothness).
Each
Assumption 2 (Interpolation and initial distance).
There exists
The oracle accepts any component index and any point in
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CyclicGradientInterpolation (Ours) (review) | |||
| (2) FISTA on |
Finite-dimensional specialization; |
(1): No established improvement in optimization complexity. | (1): Larger bound by
order |
| (3) Cyclic IGD (Cai and Diakonikolas 2024, Thm. 2.3) | Derived bound: finite dimension, interpolation; step |
(1): Removes |
(1): Requires
interpolation, unlike the general theorem. On the common class, worse
accuracy term when |
| (4) Cyclic projections
(Evron et al. 2023,
Prop. 4.13), |
Derived bound: |
(1): On this subclass,
|
(1): Certifies average loss, not maximum distance. Projection specialization is not formalized. |
| (5) Cyclic subspace projections (Swartworth et al. 2023, Thm. 1, Lem. 2) | Derived bound: |
(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 |
| (6) Cyclic projections
(Evron et al. 2023,
Prop. 4.13), |
Derived bound: |
(1): Matches known rate
for |
(1): Average loss instead of maximum-distance guarantee; projection specialization is not formalized. |
Abbr: