Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption
Abstract
We study how interpolation affects local steps and parallel sampling in monotone variational inequalities (VIs), with m workers, K oracle calls per worker per round, and N rounds. Under the strong growth condition (SGC), we determine the minimax rate for affine VIs, attained by local extragradient with worker averaging. For nonlinear monotone VIs and convex-concave saddle problems with Lipschitz operators satisfying SGC, we improve the stochastic terms of bounded-variance expected-gap guarantees from (KN)−1/2 to (KN)−1 with local steps and from (mKN)−1/2 to (mKN)−1 with minibatches. Under strong monotonicity, we improve the noise-dependent condition-number scaling of existing extragradient bounds from quadratic to linear. The resulting monotone-gap and strongly monotone accuracy bounds match lower bounds up to logarithmic factors in m. Under generalized smoothness and SGC, adaptive steps give polynomial dependence on the initial radius. For affine VIs with globally bounded oracle variance, we also attain the minimax rate: the deterministic rate over KN sequential calls plus the statistical rate over all mKN samples. For composite VIs with smooth convex sample interpolation and an exactly evaluated monotone Lipschitz component, accelerated mirror-prox sliding achieves an N−2 gradient term, a (KN)−1 monotone term, and a (mKN)−1 sampling term, without assuming SGC.
Related
- Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits
- Sharp logarithmic Sobolev inequalities on free groups by variational comparison
- Lp-Integral Affine Surface Area-Variational Capacity Inequalities
- Some Properties of Mordukhovich Derivatives with Applications to Locally Variational Inequalities in Banach Spaces
- Solving Quasi-Variational Inequalities Using the Progressive Decoupling of Linkages
BibTeX
@misc{novoselov2026optimal,
title = {{Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption}},
author = {Kirill Novoselov and Yuriy Dorn and Darina Dvinskikh and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12641},
eprint = {2610.12641},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12641},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption
AU - Kirill Novoselov
AU - Yuriy Dorn
AU - Darina Dvinskikh
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12641
UR - https://arxiv.org/abs/2610.12641
AB - We study how interpolation affects local steps and parallel sampling in monotone variational inequalities (VIs), with m workers, K oracle calls per worker per round, and N rounds. Under the strong growth condition (SGC), we determine the minimax rate for affine VIs, attained by local extragradient with worker averaging. For nonlinear monotone VIs and convex-concave saddle problems with Lipschitz operators satisfying SGC, we improve the stochastic terms of bounded-variance expected-gap guarantees from (KN)^−1/2 to (KN)^−1 with local steps and from (mKN)^−1/2 to (mKN)^−1 with minibatches. Under strong monotonicity, we improve the noise-dependent condition-number scaling of existing extragradient bounds from quadratic to linear. The resulting monotone-gap and strongly monotone accuracy bounds match lower bounds up to logarithmic factors in m. Under generalized smoothness and SGC, adaptive steps give polynomial dependence on the initial radius. For affine VIs with globally bounded oracle variance, we also attain the minimax rate: the deterministic rate over KN sequential calls plus the statistical rate over all mKN samples. For composite VIs with smooth convex sample interpolation and an exactly evaluated monotone Lipschitz component, accelerated mirror-prox sliding achieves an N^−2 gradient term, a (KN)^−1 monotone term, and a (mKN)^−1 sampling term, without assuming SGC.
ER -