Convex Minimization with Polynomially Mixing Subgradients
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Polynomially Mixing Subgradients
We minimize a function
With
Our assumptions:
Assumption 1 (Convexity and attainment). For all
Assumption 2 (Polynomial absolute regularity). Let
Assumption 3 (Stationary subgradients and moments).
At query
After the allotted oracle calls, the algorithm must return a
measurable
Results
- Polynomial Mixing Confidence Lower Bound · Lean proof
- Polynomial Mixing Confidence Upper Bound · Lean proof
On the closed radius-
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) PolynomialMixingConfidenceUpperBound
(Ours) |
Upper bound (sufficient calls) |
||
| (2) PolynomialMixingConfidenceLowerBound
(Ours) |
Lower bound (necessary calls) |
||
| (3) Derived bound: Berbee blocking and clipped SGD (Liu and Zhou 2023, Thm. 3) | Sufficient calls, including skipped samples |
(1): Accuracy and
confidence costs add. At |
(1): The certified
accuracy factor |
| (4) Online projected gradient descent (Agarwal and Duchi 2013, Thm. 3) | Sufficient calls |
(1): Allows unbounded
replies. On the bounded convex Lipschitz sample-loss overlap at |
(1): Requires past–future
mixing where (4) needs single-time mixing against the
past. At fixed confidence and |
| (5) Ergodic mirror descent (Duchi et al. 2012, Thm. 2) | Sufficient calls |
(1): Allows heavy-tailed replies and dispenses with uniform conditional mixing. (5) assumes convex Lipschitz sample losses and a uniform conditional total-variation envelope. | (1): On the bounded,
uniformly mixing overlap at |
Abbr:
Table 1, continued.
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (6) Expected-gap lower bound (LongTails 2026) | Necessary calls |
(2): The same accuracy
exponent now carries |
(2), (6): Rates are not directly comparable. (6) targets expected error for smooth unconstrained objectives, centered moments and stationary average-TV mixing Markov chains. |
| (7) Quadratic lower bound (Sarkar et al. 2026, Thm. 4) | Necessary transitions at constant confidence |
(2): Quantifies
polynomial confidence dependence for every admissible |
(2), (7): Rates are not directly comparable. (7) starts the chain at a fixed state and measures quadratic objective error. |
Abbr: