The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models
Abstract
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, Hs≥ 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,ξ) satisfying 𝔼ξ|g(x,ξ)|2 ≤ 2Hs(F(x)−F(x*)), 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: R2min{L, Hs/KN, L/N2+Hs/mKN} and R2min{L, min{L,Hs/K}/N2+Hs/mKN}, 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.
Related
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
- Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
- Near-Optimal Higher-Order Oracle Complexity for Convex--Concave Minimax Optimization
- Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
BibTeX
@misc{novoselov2026minimax,
title = {{The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models}},
author = {Kirill Novoselov and Yuriy Dorn and Darina Dvinskikh and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38354},
eprint = {2610.38354},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38354},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models
AU - Kirill Novoselov
AU - Yuriy Dorn
AU - Darina Dvinskikh
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38354
UR - https://arxiv.org/abs/2610.38354
AB - 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≥ 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,ξ) satisfying 𝔼_ξ|g(x,ξ)|^2 ≤ 2H_s(F(x)−F(x^*)), 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^2min{L, H_s/KN, L/N^2+H_s/mKN} and R^2min{L, min{L,H_s/K}/N^2+H_s/mKN}, 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.
ER -