Markov Quadratic Interpolation
Descriptions may be stale. Consult the linked Lean sources.
Markov Quadratic Interpolation
We consider minimizing a convex quadratic
The optimization problem is
Our assumptions:
Assumption 1 (Interpolating quadratic model). There
exist a finite index set
Assumption 2 (Markov sampling and refresh). Let
Queries may be made at any point of
After the allotted oracle calls, the output
Results
On a real separable Hilbert space with its Borel measurable
structure, let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) MarkovQuadraticLastIterate
(Ours) |
Last-iterate SGD, |
||
| (2) Derived bound: averaged SGD | (1): Matches known rate; last iterate instead of averaging. No problem-class complexity gain. | (1): Much larger proved
constant; needs |
|
| (3) Derived bound: thinned SGD using (Dereziński and Dong 2026), Thm. 3.1 | Finite-dimensional restriction; skipped transitions included. |
(1): Removes |
(1): Larger proved
constants; the reported cost crossover requires |
| (4) (Even 2023), Thm. 5.6, interpolation | Special case: |
(1): Scope includes
singular operators and infinite dimension. On overlap with |
(1): Requires refresh and
known |
Abbr: