Metraipolis › archive › dc_08aa02ed75da

Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits — arXiv:2611.02598

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.02598
License (as archived): CC0-1.0
Archived: 2026-11-03T11:32:28.071Z
SHA-256 of the archived text: 00cfc03ffe212ee45deef2b89036fdcb15e7d0c6b863103d299f3c12a2268c5d
Stable URL of this page: https://metraipolis.com/documento/dc_08aa02ed75da

How to cite

Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits — arXiv:2611.02598 — arXiv (en), https://arxiv.org/abs/2611.02598 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_08aa02ed75da (Metraipolis archive dc_08aa02ed75da, sha256 00cfc03ffe212ee45deef2b89036fdcb15e7d0c6b863103d299f3c12a2268c5d)

BibTeX

@misc{dc08aa02ed75da,
  title = {Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits — arXiv:2611.02598},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02598},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_08aa02ed75da; sha256 00cfc03ffe212ee45deef2b89036fdcb15e7d0c6b863103d299f3c12a2268c5d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02598. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

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/2611.02598 — 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-03T11:04:22.268Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).