betaFeedback

WorksMathematics

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: mm workers run for NN rounds, and between consecutive communication rounds each worker makes KK 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 LL be the smoothness of the objective, Hs≥LH_s\ge L the smoothness of the sample losses, and RR 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,ξ)g(x,ξ) satisfying Eξ∥g(x,ξ)∥2≤2Hs(F(x)−F(x∗))\mathbb{E}_ξ\|g(x,ξ)\|^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: R2min⁡{L,  HsKN,  LN2+HsmKN}andR2min⁡{L,  min⁡{L,Hs/K}N2+HsmKN}, 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.

Introduction

Modern machine learning models are overparameterized and interpolate the training data: a single parameter vector minimizes the loss of every example. In this regime the noise of stochastic gradients vanishes at the solution, and stochastic methods attain faster rates than in the classical setting. SGD with a constant step size converges at the rate of gradient descent [9, 13, 17], momentum methods attain accelerated rates [7, 17], and minibatch accelerated methods achieve a linear speedup in the minibatch size [19]. These results concern a single machine.

A natural question is how interpolation affects distributed training, where communication between machines is the bottleneck, as in federated learning [4, 10]. The standard model of this regime is intermittent communication [20]: mm workers run for NN rounds, each worker makes KK sequential stochastic gradient queries in every round, and the workers communicate only at the end of rounds. For convex objectives with LL-Lipschitz gradients and stochastic gradients whose variance is uniformly bounded by σ2\sigma^2, Woodworth et al. [23] determined the minimax complexity of this model up to logarithmic factors: the optimal method is the better of minibatch accelerated SGD [6], with NN updates and batch size mKmK, and accelerated SGD on a single worker. Under interpolation, the noise vanishes at the solution and scales with the smoothness HsH_s of the individual losses, and the minimax complexity of intermittent communication in this regime has remained open.

Besides interpolation itself, the answer depends on what the oracle reveals. Discussing how their lower bound might be circumvented, Woodworth et al. [23, Sections 5.2 and 5.3] pointed to two features of statistical learning. First, stochastic gradients are usually gradients ∇f(x;z)\nabla f(x; z) of smooth convex losses at random examples zz. The hard oracle of their lower bound is not of this form, and they asked whether this structure yields better guarantees or whether the lower bound persists. Second, an algorithm can often evaluate the gradient of the same example at several points, as variance-reduced methods do, and distributed variants of SVRG improve on their lower bound. We study intermittent communication under interpolation in three oracle models that isolate these features, ordered by the information that a query provides.

  • Weak growth (Assumption 1): the oracle is unbiased, and its second moment is at most 2Hs2H_s times the suboptimality of the query. Nothing else is assumed. Interpolation implies this condition for sample gradients (Lemma 4.1). The upper bounds in Sections 3 and 4 rely only on this condition.

  • Fresh sample gradients (Assumption 2): the oracle returns the gradient of an HsH_s-smooth convex sample loss at a fresh example, and all sample losses are minimized at a common point. This is the setting of Woodworth et al. [23, Section 5.2] under interpolation.

  • Sample reuse (Assumption 3): the examples form a stored training set, and the gradient of the same example can be computed at several points. This is the setting of Woodworth et al. [23, Section 5.3] under interpolation.

Here L≤HsL \le H_s is the smoothness of the population objective. The resulting minimax bounds are summarized in Table 1.

Contributions

  • Weak growth (Section 3). We determine the minimax rate up to the factor log⁡2(em)\log^2(em), for general convex and for quadratic populations. For general convex populations, the lower bound extends the construction of Woodworth et al. [23] to relative noise, and the optimal method is the best of three baselines: returning x0x_0, serial SGD on one worker, and minibatch AC-SA. For quadratic populations, local SGD steps reduce the effective smoothness to min⁡{L,Hs/K}\min\{L, H_s/K\}, and an accelerated method on the resulting spectral surrogate is optimal.

  • Fresh sample gradients (Section 4). We prove a lower bound with a new hard instance, since the construction of Woodworth et al. [23] is not a sample-gradient oracle. This answers the question of Woodworth et al. [23, Section 5.2] for quadratic populations under interpolation: the structure of sample gradients gives the same minimax rate as the weak growth condition. For general convex populations a gap remains, and we show that closing it from above requires structure beyond the weak growth condition.

  • Sample reuse (Section 5). In the setting of Woodworth et al. [23, Section 5.3] under interpolation, we determine the minimax rate up to the factor Jlog⁡2(em)J\log^2(em) with J=O(log⁡(KN))J = O(\log(KN)). The upper bound is attained by an accelerated method on empirical objectives, which each worker computes by SVRG on its own batch. The lower bound holds for arbitrary reuse of samples, and for an infinite pool it coincides with the lower bound for fresh sample gradients.

All lower bounds hold for arbitrary randomized algorithms in finite dimension, without linear-span assumptions.

Related work

Intermittent communication and local updates. The intermittent communication model was studied by Woodworth et al. [20] within a graph-oracle framework for parallel stochastic optimization, together with lower bounds for it. Local SGD was analyzed by Stich [16] and compared with minibatch SGD by Woodworth et al. [22], who showed that local SGD strictly dominates minibatch SGD for quadratic objectives, that its accelerated variant is minimax optimal for quadratics, and that it does not dominate minibatch SGD for general convex objectives; heterogeneous objectives were studied by Woodworth et al. [21]. The min-max complexity under bounded variance was determined by Woodworth et al. [23]. We refer to Kairouz et al. [4] for a survey of federated learning. Our results show that the advantage of local updates on quadratics persists under weak growth, and that sample reuse extends it to general convex populations under interpolation.

Interpolation and growth conditions. Fast convergence of SGD under the strong growth condition, where the second moment of the stochastic gradient is bounded by a multiple of ∥∇F∥2\lVert\nabla F\rVert^2, was shown by Schmidt and Le Roux [13]. The benefits of interpolation for SGD and its minibatch speedup were explained by Ma et al. [9]. Vaswani et al. [17] introduced the weak growth condition, which interpolation implies for smooth finite sums, and showed that SGD with Nesterov acceleration attains the deterministic accelerated rate under strong growth. For least squares, Liu and Belkin [7] accelerated SGD in the interpolation regime. Rates that adapt to the minimal loss for smooth nonnegative losses go back to Srebro et al. [15], and accelerated minibatch methods with such rates were given by Cotter et al. [2] and, with the optimal dependence on the minibatch size, by Woodworth and Srebro [19]. We use the accelerated scheme of the latter in Appendix C. These works concern a single machine; we study the intermittent communication model.

OracleLower boundUpper boundReference
Bounded varianceLR2K2N2+min⁡{LR2,σRmKN}\frac{LR^2}{K^2N^2}+\min\left\{LR^2,\frac{\sigma R}{\sqrt{m}KN}\right\}LR2N2+min⁡{σRN2,σRKN}\frac{LR^2}{N^2}+\min\left\{\frac{\sigma R}{N^2},\frac{\sigma R}{KN}\right\}Woodworth et al. [23]
Weak growth, quadratic FFR2min⁡{L,min⁡{L,Hs/K}N2+HsmKN}R^2\min\left\{L,\frac{\min\{L,H_s/K\}}{N^2}+\frac{H_s}{mKN}\right\}This paper<br>Theorem 3.3
Weak growth, convex FFR2min⁡{L,HsKN,LN2+HsmKN}R^2\min\left\{L,\frac{H_s}{KN},\frac{L}{N^2}+\frac{H_s}{mKN}\right\}This paper<br>Theorem 3.2
Sample gradients, quadratic FFR2min⁡{L,min⁡{L,Hs/K}N2+HsmKN}R^2\min\left\{L,\frac{\min\{L,H_s/K\}}{N^2}+\frac{H_s}{mKN}\right\}This paper<br>Theorem 4.2
Sample gradients, convex FFR2min⁡{L,min⁡{L,Hs/K}N2+HsmKN}R^2\min\left\{L,\frac{\min\{L,H_s/K\}}{N^2}+\frac{H_s}{mKN}\right\}R2min⁡{L,HsKN,LN2+HsmKN}R^2\min\left\{L,\frac{H_s}{KN},\frac{L}{N^2}+\frac{H_s}{mKN}\right\}This paper<br>Theorem 4.3
Sample reuse, convex FFR2min⁡{L,min⁡{L,Hs/K}N2+Hsmin⁡{S,mKN}}R^2\min\left\{L,\frac{\min\{L,H_s/K\}}{N^2}+\frac{H_s}{\min\{S,mKN\}}\right\}This paper<br>Theorem 5.1

Table 1. Bounds on the minimax risk in the intermittent communication model with mm workers, NN rounds, and KK queries per worker per round, for convex objectives with LL-Lipschitz gradients and ∥x0−x∗∥≤R\lVert x_0-x^*\rVert\le R. Numerical constants are omitted. The result of Woodworth et al. [23] holds up to logarithmic factors. Here HsH_s is the constant of the weak growth condition (the smoothness of the sample functions), σ2\sigma^2 the variance, and SS the pool size.

Local subproblems. Solving a proximal subproblem on a minibatch is the idea of minibatch-prox [18]. Our method with sample reuse computes such proximal points locally by SVRG [3] and uses them as gradients of empirical Moreau envelopes inside an accelerated method; interpolation guarantees that the envelopes share the minimizer of the population.

Lower bounds. Our lower bounds use hidden chains, which go back to Nemirovsky and Yudin [11], combined with random rotations to avoid linear-span assumptions, as in Woodworth et al. [23]. For the weak growth condition, we extend the rare-progress oracle of Woodworth et al. [23] to relative noise.

For quadratic populations, we use a random-rotation representation of adaptive matrix-vector algorithms, building on techniques developed by Braverman et al. [1] and closely related to those recently employed by Shamir [14] in the centralized setting. Our analysis additionally accounts for the depth of batched adaptive queries and uses a Chebyshev-type certificate tailored to smooth convex quadratic objectives. We combine these techniques with Bernoulli masking of entire sample losses, an approach already used in our previous work on federated variational inequalities [12], to establish lower bounds for interpolating sample-gradient oracles under intermittent communication.

Setting

Throughout, 0<L≤Hs0<L\le H_s and R>0R>0 are constants, mm, KK, N≥1N\ge1 are integers, d≥1d\ge1 is the dimension, and x0∈Rdx_0\in\mathbb{R}^d is the initial point. All norms and inner products are Euclidean, and all logarithms are natural.

Intermittent communication.

Definition 2.1 (Intermittent communication). An algorithm in the class IC(m,K,N)\mathrm{IC}(m,K,N) runs mm workers for NN rounds. In every round, each worker makes at most KK sequential oracle queries. Each query of a worker is a measurable function of the public parameters, the random seed of the algorithm, all messages exchanged before the current round, and the queries and replies of this worker in the current round. At the end of every round the workers exchange arbitrary messages. The output x^∈Rd\hat{x}\in\mathbb{R}^d is a measurable function of the seed and of all messages. The seed is independent of the instance and of the oracle randomness. No restriction is imposed on memory, local computation, message size, or the norms of queries and outputs; in particular, queries need not lie in the span of previous replies. The public parameters are mm, KK, NN, LL, HsH_s, RR, dd, x0x_0, and the pool size SS in Assumption 3. The objective, its minimizer, and the oracle law are unknown to the algorithm.

Oracle assumptions. We consider three oracle models, ordered by the information that a query provides.

Assumption 1 (Weak growth condition). The objective F:Rd→RF : \mathbb{R}^d \to\mathbb{R} is convex, has an LL-Lipschitz gradient, and has a minimizer x∗x^* with ∥x0−x∗∥≤R\lVert x_0-x^*\rVert\le R. There are a probability distribution D\mathcal{D} on a measurable space Ξ\Xi and a jointly measurable map g:Rd×Ξ→Rdg : \mathbb{R}^d \times\Xi\to\mathbb{R}^d such that, for every x∈Rdx \in\mathbb{R}^d,

Eξ∼Dg(x,ξ)=∇F(x),Eξ∼D∥g(x,ξ)∥2≤2Hs(F(x)−F(x∗)).(1)\mathbb{E}_{\xi\sim\mathcal{D}} g(x,\xi)=\nabla F(x), \qquad\mathbb{E}_{\xi\sim\mathcal{D}}\lVert g(x,\xi)\rVert^2 \le2H_s\bigl(F(x)-F(x^*)\bigr). \tag*{(1)}

On a query xx, the oracle draws a fresh sample ξ∼D\xi\sim\mathcal{D} and returns only g(x,ξ)g(x,\xi).

The map g(⋅,ξ)g(\cdot,\xi) in Assumption 1 need not be a gradient field or continuous.

Assumption 2 (Sample gradients under interpolation). There are a probability distribution D\mathcal{D} on a measurable space Ξ\Xi and differentiable convex functions fξ:Rd→Rf_\xi: \mathbb{R}^d \to\mathbb{R}, ξ∈Ξ\xi\in\Xi, such that (x,ξ)↦fξ(x)(x,\xi) \mapsto f_\xi(x) and (x,ξ)↦∇fξ(x)(x,\xi) \mapsto\nabla f_\xi(x) are jointly measurable and, for some x∗∈Rdx^* \in\mathbb{R}^d with ∥x0−x∗∥≤R\lVert x_0-x^*\rVert\le R and D\mathcal{D}-almost every ξ\xi,

∥∇fξ(x)−∇fξ(y)∥≤Hs∥x−y∥for all x,y∈Rd,∇fξ(x∗)=0.(2)\lVert\nabla f_\xi(x)-\nabla f_\xi(y)\rVert\le H_s\lVert x-y\rVert\quad\text{for all }x,y\in\mathbb{R}^d,\qquad\nabla f_\xi(x^*)=0. \tag*{(2)}

The objective

F(x)=Eξ∼D[fξ(x)−fξ(x∗)]F(x)=\mathbb{E}_{\xi\sim\mathcal{D}}\bigl[f_\xi(x)-f_\xi(x^*)\bigr]

References

  1. [1]Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. The gradient complexity of linear regression. In Proceedings of the 33rd Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 627–647, 2020.arxiv.org/abs/1911.02212
  2. [2]Andrew Cotter, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. In Advances in Neural Information Processing Systems, volume 24, 2011.arxiv.org/abs/1106.4574
  3. [3]Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, 2013.
  4. [4]Peter Kairouz, H. Brendan McMahan, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1–2):1–210, 2021.arxiv.org/abs/1912.04977
  5. [5]Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the Polyak-lojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 795–811, 2016.DOI
  6. [6]Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1–2):365–397, 2012.
  7. [7]Chaoyue Liu and Mikhail Belkin. Accelerating SGD with momentum for over-parameterized learning. In International Conference on Learning Representations, 2020.
  8. [8]Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85–116, 2022.arxiv.org/abs/2003.00307
  9. [9]Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3325–3334, 2018.arxiv.org/abs/1712.06559
  10. [10]Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1273–1282, 2017.arxiv.org/abs/1602.05629
  11. [11]Arkadi S. Nemirovsky and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.DOI
  12. [12]Kirill Novoselov, Yuriy Dorn, Darina Dvinskikh, and Alexander Gasnikov. Optimal rates for federated variational inequalities under different relaxations of bounded variance assumption, 2026. URL https://arxiv.org/abs/2610.12641.
  13. [13]Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1308.6370, 2013.arxiv.org/abs/1308.6370
  14. [14]Ohad Shamir. A simple complexity lower bound for solving Ax = b, 2026.arxiv.org/abs/2609.10874
  15. [15]Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, volume 23, 2010.
  16. [16]Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.arxiv.org/abs/1805.09767
  17. [17]Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 1195–1204, 2019.arxiv.org/abs/1810.07288
  18. [18]Jialei Wang, Weiran Wang, and Nathan Srebro. Memory and communication efficient distributed stochastic optimization with minibatch prox. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1882–1919, 2017.arxiv.org/abs/1702.06269
  19. [19]Blake Woodworth and Nathan Srebro. An even more optimal stochastic optimization algorithm: Minibatching and interpolation learning. In Advances in Neural Information Processing Systems, volume 34, 2021.arxiv.org/abs/2106.02720
  20. [20]Blake Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nathan Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems, volume 31, 2018.arxiv.org/abs/1805.10222
  21. [21]Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local SGD for heterogeneous distributed learning. In Advances in Neural Information Processing Systems, volume 33, 2020.arxiv.org/abs/2006.04735
  22. [22]Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10334–10343, 2020.arxiv.org/abs/2002.07839
  23. [23]Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Proceedings of the 34th Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4386–4437, 2021.arxiv.org/abs/2102.01583

Paper details

vlnc:W_pzu282kt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents