Metraipolis › archive › dc_9df05faed1f2
The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models — arXiv:2610.38354
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.38354
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:32:05.506Z
- SHA-256 of the archived text
f1c2dbe586a80e96948e3f902fd4cc117c48bb0799204f72b32fb0cb2553ae61- Stable URL of this page
https://metraipolis.com/documento/dc_9df05faed1f2
How to cite
The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models — arXiv:2610.38354 — arXiv (en), https://arxiv.org/abs/2610.38354 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9df05faed1f2 (Metraipolis archive dc_9df05faed1f2, sha256 f1c2dbe586a80e96948e3f902fd4cc117c48bb0799204f72b32fb0cb2553ae61)
BibTeX
@misc{dc9df05faed1f2,
title = {The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models — arXiv:2610.38354},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.38354},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9df05faed1f2; sha256 f1c2dbe586a80e96948e3f902fd4cc117c48bb0799204f72b32fb0cb2553ae61},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38354. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the minimax complexity of smooth convex stochastic optimization with intermittent communication: $m$ workers run for $N$ rounds, and between consecutive communication rounds each worker makes $K$ sequential stochastic gradient queries. We focus on the interpolation regime, in which all sample losses share a common minimizer, so that the gradient noise vanishes at the solution. Let $L$ be the smoothness of the objective, $H_s\ge L$ the smoothness of the sample losses, and $R$ the distance from the initial point to a minimizer. We consider three oracle models that provide increasing information: an unbiased stochastic gradient oracle $g(x,\xi)$ satisfying $\mathbb{E}_{\xi}\|g(x,\xi)\|^2 \leq 2H_s\bigl(F(x)-F(x^*)\bigr)$, gradients of the sample losses at fresh samples, and repeated gradient queries to stored samples. Up to logarithmic factors, all our results are described by two rates: \[ R^2\min\left\{L,\;\frac{H_s}{KN},\; \frac{L}{N^2}+\frac{H_s}{mKN}\right\} \qquad\text{and}\qquad R^2\min\left\{L,\; \frac{\min\{L,H_s/K\}}{N^2}+\frac{H_s}{mKN}\right\}, \] Under the weak growth condition, the first rate is the minimax rate, attained by the best of three simple baselines, as in the classical bounded-variance setting. With repeated access to samples, the second rate becomes the minimax rate for general convex objectives. For general convex objectives with fresh sample gradients, the minimax rate lies between the two rates. Our lower bounds apply to arbitrary randomized intermittent-communication algorithms.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.38354 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:14:28.297Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).