Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits
Abstract
We study the classical Local Stochastic Extragradient method (Local SEG) for monotone variational inequalities under intermittent communication, where devices perform several local oracle calls between synchronization rounds. For affine monotone mean operators, including nonsymmetric bilinear saddle systems, we prove that equal device averaging commutes pathwise with both stages of the stochastic extragradient update. Local trajectories may therefore drift apart while their mean follows a centralized stochastic-extragradient recursion driven by averaged noise. The identity remains valid when individual oracle realizations are nonlinear and query dependent. Under conditionally centered oracle errors that are conditionally independent across devices within each stage, the reduction yields a restricted weak-gap rate that uses the local sequential depth for deterministic progress and the aggregate oracle budget across devices for variance reduction. When every device makes at least two local oracle calls per communication round, the bound contains no additional mixed client-drift term and is also attained by a terminal-only aggregation schedule. An affine Gaussian lower bound matches the depth and sample dependences before statistical saturation for distributed zero-respecting algorithms; its statistical component applies to arbitrary randomized algorithms. A complementary lower bound for feasible distributed zero-respecting methods shows that bounded geometry and query-dependent noise can create an additional communication-locality obstruction. These results delineate the exact-averaging regime of unconstrained affine Local SEG and a complexity boundary that arises under active feasibility constraints.
Related
- Lp-Integral Affine Surface Area-Variational Capacity Inequalities
- Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption
- Matching Higher-Order Oracle Complexity for Smooth Monotone Variational Inequalities
- Local Epochs, Averaging, and Variable Selection in Federated Lasso
- Affine variational functionals, isoperimetric problems and stability
BibTeX
@misc{dvinskikh2026federated,
title = {{Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits}},
author = {Darina Dvinskikh and Kirill Novoselov and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02598},
eprint = {2611.02598},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02598},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits
AU - Darina Dvinskikh
AU - Kirill Novoselov
AU - Alexander Gasnikov
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02598
UR - https://arxiv.org/abs/2611.02598
AB - We study the classical Local Stochastic Extragradient method (Local SEG) for monotone variational inequalities under intermittent communication, where devices perform several local oracle calls between synchronization rounds. For affine monotone mean operators, including nonsymmetric bilinear saddle systems, we prove that equal device averaging commutes pathwise with both stages of the stochastic extragradient update. Local trajectories may therefore drift apart while their mean follows a centralized stochastic-extragradient recursion driven by averaged noise. The identity remains valid when individual oracle realizations are nonlinear and query dependent. Under conditionally centered oracle errors that are conditionally independent across devices within each stage, the reduction yields a restricted weak-gap rate that uses the local sequential depth for deterministic progress and the aggregate oracle budget across devices for variance reduction. When every device makes at least two local oracle calls per communication round, the bound contains no additional mixed client-drift term and is also attained by a terminal-only aggregation schedule. An affine Gaussian lower bound matches the depth and sample dependences before statistical saturation for distributed zero-respecting algorithms; its statistical component applies to arbitrary randomized algorithms. A complementary lower bound for feasible distributed zero-respecting methods shows that bounded geometry and query-dependent noise can create an additional communication-locality obstruction. These results delineate the exact-averaging regime of unconstrained affine Local SEG and a complexity boundary that arises under active feasibility constraints.
ER -