Quadratic Minimization with Temporal Discrepancy
Descriptions may be stale. Consult the linked Lean sources.
Quadratic Minimization with Temporal Discrepancy
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Quadratic structure). The objective
and its gradient are
Assumption 2 (Initial objective bound). The given
starting point satisfies
Assumption 3 (Temporal discrepancy). There is a
fixed deterministic sequence
After the allotted oracle calls, the output must satisfy
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) TemporalAcceleratedQuadratic (Ours) (review) | |||
| (2) Derived bound: batching and dilation, (Schmidt et al. 2011, Prop. 4, v2); Hilbert-space extension | (1): Matches known rate.
No precision-dependent dilation; updates need neither |
(1): Tail average instead of the last iterate. | |
| (3) Derived bound: batching without dilation, (Schmidt et al. 2011, Prop. 4, v2); Hilbert-space extension | (1): Noise term |
(1): Tail average instead of the last iterate. | |
| (4) Subsequent repository result (NonlinearTemporalAcceleration.lean, n.d.); finite-dimensional quadratic restriction | (1): Removes |
(1): Quadratics only; (4) also covers nonquadratic objectives with Lipschitz Hessian. |
Abbr: