betaFeedback

WorksMathematics

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.

Funding. This work was supported by Ministry of Science and Higher Education of the Russian Federation (Grant No. 075-15-2024-529)

Introduction

Variational inequalities (VIs) are a standard framework for constrained convex optimization, convex–concave saddle problems, and equilibrium models. A VI asks for a feasible point whose operator value forms a nonnegative inner product with every feasible displacement. The operator may combine gradient and rotational components, which extends the model beyond ordinary minimization. Extragradient and Mirror-Prox methods address this difficulty by evaluating the operator twice per iteration [1, 2, 3].

Large-scale stochastic VIs are commonly addressed on distributed systems. Several devices can collect oracle samples in parallel, whereas synchronization is often slower than local computation. This motivates the intermittent-communication (IC) model: each communication opportunity is separated by several sequential oracle calls on every device [4, 5, 6]. The model is a standard abstraction for clusters and homogeneous federated systems. It distinguishes two computational resources: the length of the adaptive local trajectory and the total number of samples collected across all devices.

A central analytical question is whether a method can exploit both resources simultaneously. Minibatch methods pool parallel samples, so their deterministic horizon follows the synchronization count. A single-device method traverses the full local trajectory with one device’s sample budget. Local SGD and FedAvg seek to combine the two advantages in stochastic minimization [7, 8, 9, 10, 11]. The analogous question for VIs is more delicate because the second extragradient query depends on the first and disagreement can enter both stages of every update.

General intermittent-communication problems therefore exhibit a tension between parallel sampling and sequential local progress [5, 6]. Homogeneous quadratic minimization is an important exception: linear updates commute with device averaging, and one terminal communication can attain the optimal rate [12, 6]. We ask whether this exception extends beyond gradient fields to nonsymmetric affine monotone VIs and the two-stage extragradient recursion.

We analyze the established Local Stochastic Extragradient method (Local SEG) in this setting [13]. A particularly close comparison is the recent work of Wang and Kale on Local Extra SGD with an affine mean operator [14]. Their guarantee uses local computation and parallel sampling, but contains an additional mixed term arising from the control of client drift. This raises a structural question: does the device mean inherit that mixed term, or does affinity yield a simpler average trajectory?

For affine mean operators, the device average follows an exact centralized SEG recursion even when individual oracle realizations depend nonlinearly on the query. The resulting two-term weak-gap estimate uses both sequential depth and parallel sampling, and it can be attained with terminal-only aggregation. The lower bounds determine its order-optimal scope and identify a separate communication-locality obstruction on bounded domains.

Contributions. The paper makes three analytical contributions to the analysis of Local SEG.

  1. We extend the exact-averaging principle for linear-update methods on homogeneous quadratic objectives [12] to nonsymmetric affine monotone VIs and the two-stage Local SEG recursion. The reduction allows nonlinear, query-dependent oracle realizations and uses only their adapted moment bounds. In particular, it covers rotational bilinear saddle operators with a non-gradient mean field.

  1. The reduction removes the mixed client-drift term from the Wang–Kale affine Local Extra SGD analysis [14]. It yields a two-resource weak-gap guarantee and shows that one terminal aggregation suffices for the prescribed horizon.

  1. Two lower bounds describe both optimality and scope. An affine Gaussian construction matches the depth and sample dependences in the unconstrained problem. A separate bounded affine construction exhibits a communication-locality term for distributed zero-respecting methods when feasibility constraints and query-dependent noise are admitted.

Related work and scope. Distributed VI methods cover heterogeneous operators, decentralized mixing, similarity assumptions, variance reduction, and local updates [15, 16, 17, 18, 19, 20]. Polyak–Ruppert averaging studies temporal averages of stochastic-approximation iterates; our identity concerns averages across simultaneous device trajectories [21, 22, 23]. Accelerated federated minimization methods such as FedAc exploit gradient structure and measure objective suboptimality [24]. Our analysis uses the weak VI gap and affine monotone fields, so the two directions address complementary problem classes. Sadchikov et al. study how the quadratic exact-averaging phenomenon degrades beyond quadratic structure for Local SGD [25]. Their setting concerns gradient fields and one-stage stochastic-gradient updates. Our setting adds nonsymmetric affine operators, two coupled SEG stages, a restricted weak-gap criterion, and affine VI lower bounds. Interpolation and strong-growth assumptions provide a different route to reduced stochastic error [26, 27]. Under such noise models, the effective variance of Local SEG may also depend on disagreement among local query points, so this regime requires a separate analysis. The depth lower bound follows classical oracle-complexity, bilinear-chain, and distributed graph constructions [28, 5, 29]; its statistical component uses a standard two-point testing argument [30]. For the communication-locality boundary, we adapt the robust zero-chain idea of Woodworth et al. [6] to a bounded bilinear VI and compute the weak gap directly. Our contribution is the affine VI adaptation and the resulting boundary for exact averaging in the homogeneous model.

The main results concern an unconstrained affine mean operator. Because a global weak gap on an unbounded domain can be infinite away from a solution, we evaluate accuracy on a fixed ball around a root. This ball localizes only the merit function. The algorithm, its iterates, and its output remain unconstrained. The next section gives the formal definitions and assumptions.

Organization. § 2 defines the oracle model and Local SEG. § 3 proves the exact reduction, its rate, and the matching affine lower bound. § 4 identifies a constrained communication-locality boundary. § 5 gives a numerical illustration. The appendices contain the lower-bound constructions, technical SEG estimate, and experimental details.

Problem setting and Local SEG

This section introduces the communication model, the stochastic oracle, the weak-gap criterion, and the Local SEG recursion used in the main results.

Notation. Throughout, ∥⋅∥\lVert\cdot\rVert is the Euclidean norm for vectors and the induced operator norm for matrices, and ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle is the Euclidean inner product.

Intermittent communication

We use the standard homogeneous intermittent-communication model [5, 6]. There are MM devices and RR local-computation rounds. In each round, every device makes at most KK sequential calls to the same stochastic VI oracle, after which communication between the devices is allowed. Within a round, a device may adapt its queries to its own preceding oracle replies; information obtained by other devices becomes available after communication. Thus the total oracle budget is at most MKRMKR, while the maximal sequential depth is KRKR. Figure 1 illustrates this mechanism.

Intermittent-communication model

Figure 1. Intermittent-communication model. Each device performs up to KK sequential oracle calls per round, while information can flow across devices only at the communication boundaries between rounds.

Lower-bound algorithm class. The depth and communication-locality lower bounds concern distributed zero-respecting IC algorithms. Relative to the standard coordinate basis, such an algorithm may activate a coordinate only after that coordinate has appeared in an oracle reply available to it. The formal transcript and support conditions are given in Appendix § 8.§ 1. The statistical lower bound applies to arbitrary randomized IC algorithms.

Variational inequalities, oracle, and merit function

Let Z⊆Rn\mathcal{Z} \subseteq\mathbb{R}^{n} be nonempty, closed, and convex and let G:Z→RnG:\mathcal{Z}\to\mathbb{R}^{n}. The variational inequality (VI) is to find z⋆∈Zz^\star\in\mathcal{Z} such that

⟨G(z⋆),z−z⋆⟩≥0for every z∈Z.(1)\langle G(z^\star), z-z^\star\rangle\ge0 \qquad\text{for every } z\in\mathcal{Z}. \tag*{(1)}

For continuous monotone GG, this is equivalent to the weak formulation ⟨G(z),z⋆−z⟩≤0\langle G(z),z^\star-z\rangle\le0 for every z∈Zz\in\mathcal{Z}.

We model a deterministic mean operator GG accessed through a stochastic oracle. We therefore state the operator properties and the stochastic-oracle conditions separately.

When stochastic access is used, let Ξ\Xi be a sample space and let G^:Z×Ξ→Rn\widehat{G}:\mathcal{Z}\times\Xi\to\mathbb{R}^n denote the oracle response map.

Assumption 2.1 (Monotonicity). The operator GG is monotone on Z\mathcal{Z}: for every z,z′∈Zz,z'\in\mathcal{Z},

⟨G(z)−G(z′),z−z′⟩≥0.\langle G(z)-G(z'),z-z'\rangle\ge0.

Assumption 2.2 (Lipschitz continuity). For some L>0L>0, the operator GG is LL-Lipschitz on Z\mathcal{Z}: for every z,z′∈Zz,z'\in\mathcal{Z},

∥G(z)−G(z′)∥≤L∥z−z′∥.\lVert G(z)-G(z')\rVert\le L\lVert z-z'\rVert.

Assumption 2.3 (Stochastic oracle). For some σ≥0\sigma\ge0, before each call F\mathcal{F} denotes the complete history and the query zz is F\mathcal{F}-measurable. A new draw ζ∈Ξ\zeta\in\Xi satisfies

E[G^(z,ζ)∣F]=G(z),E[∥G^(z,ζ)−G(z)∥2∣F]≤σ2.\mathbb{E}\left[\widehat{G}(z,\zeta)\mid\mathcal{F}\right]=G(z),\qquad \mathbb{E}\left[\left\lVert\widehat{G}(z,\zeta)-G(z)\right\rVert^2\mid\mathcal{F}\right]\le\sigma^2.

Randomness used by simultaneous calls is conditionally independent given the pre-stage history. At a later stage, F\mathcal{F} includes all earlier replies.

For the unconstrained affine results in § 3, Z=Rn\mathcal{Z}=\mathbb{R}^n. We call z⋆z^\star a root of GG if G(z⋆)=0G(z^\star)=0; such a root solves (1). Whenever an affine instance has a specified root z⋆z^\star and radius Ω>0\Omega>0, we measure any candidate x∈Rnx\in\mathbb{R}^n by the root-centered restricted weak gap

Gap⁡Ω(x):=sup⁡∥z−z⋆∥≤Ω⟨G(z),x−z⟩.(2)\operatorname{Gap}_{\Omega}(x):=\sup_{\lVert z-z^\star\rVert\le\Omega}\langle G(z),x-z\rangle. \tag*{(2)}

The comparison ball in (2) only localizes the merit function; the algorithm, its iterates, and its output remain unconstrained in Rn\mathbb{R}^n. This localization is necessary because the unrestricted weak gap on Rn\mathbb{R}^n may be infinite away from a solution. Since the comparison ball contains z⋆z^\star and G(z⋆)=0G(z^\star)=0, we have Gap⁡Ω(x)≥0\operatorname{Gap}_{\Omega}(x)\ge0 for every xx. Monotonicity further gives Gap⁡Ω(z⋆)=0\operatorname{Gap}_{\Omega}(z^\star)=0.

Local SEG

We use the Local SEG recursion [13, 14]. Algorithm 1 records its two oracle stages and makes the equal-averaging schedule explicit. The initial states are F0\mathcal{F}_0-measurable, and all devices use a common deterministic stepsize.

Algorithm 1 Local SEG with an admissible equal-averaging schedule

Require: States z01,…,z0Mz_0^1,\ldots,z_0^M, horizon TT, stepsize γ>0\gamma> 0, and a synchronization schedule

  1. s0m←0s_0^m \leftarrow0 for every m=1,…,Mm = 1,\ldots,M

  2. for t=0,…,T−1t = 0,\ldots,T-1 do

  3. for all devices mm in parallel do

  4. ytm,−←ztm−γG^(ztm,ζtm)y_t^{m,-} \leftarrow z_t^m - \gamma\widehat{G}(z_t^m,\zeta_t^m)

  5. end for

  6. Set ytm←M−1∑jytj,−y_t^m \leftarrow M^{-1}\sum_j y_t^{j,-} for every mm if a half-stage synchronization is scheduled; otherwise set ytm←ytm,−y_t^m \leftarrow y_t^{m,-}

  7. for all devices mm in parallel do

  8. zt+1m,−←ztm−γG^(ytm,ζt+1/2m)z_{t+1}^{m,-} \leftarrow z_t^m - \gamma\widehat{G}(y_t^m,\zeta_{t+1/2}^m)

  9. st+1m←stm+ytms_{t+1}^m \leftarrow s_t^m + y_t^m

  10. end for

  11. Set zt+1m←M−1∑jzt+1j,−z_{t+1}^m \leftarrow M^{-1}\sum_j z_{t+1}^{j,-} for every mm if a terminal-stage synchronization is scheduled; otherwise set zt+1m←zt+1m,−z_{t+1}^m \leftarrow z_{t+1}^{m,-}

  12. end for

  13. return z~T=1MT∑m=1MsTm\widetilde{z}_T = \frac{1}{MT}\sum_{m=1}^{M}s_T^m

An admissible synchronization either leaves the corresponding stage outputs unchanged or replaces all of them by their equal-weight mean. No projection is applied. We write

zˉt:=1M∑m=1Mztm,yˉt:=1M∑m=1Mytm.\bar{z}_t := \frac{1}{M}\sum_{m=1}^{M}z_t^m,\qquad\bar{y}_t := \frac{1}{M}\sum_{m=1}^{M}y_t^m.

The two local extragradient stages are standard; the optional stage-wise averaging makes the schedule-independent mean identity explicit. Algorithm 1 records the method, and § 3 develops its exact-reduction analysis. Classical block Local SEG performs τ=⌊K/2⌋\tau= \lfloor K/2\rfloor completed SEG iterations per communication round, so T=RτT = R\tau. The terminal-only implementation leaves intermediate communication opportunities unused and aggregates the accumulated vectors sTms_T^m at the end.

Affine mean subclass

Assumption 2.4 (Affine mean structure). Let Z=Rn\mathcal{Z} = \mathbb{R}^n. The mean operator is affine:

G(z)=Jz+qG(z) = Jz + q

for some J∈Rn×nJ \in\mathbb{R}^{n\times n} and q∈Rnq \in\mathbb{R}^n. The affine condition applies to the conditional mean operator; individual oracle realizations may be nonlinear and query dependent.

For an affine operator on Rn\mathbb{R}^n, Assumption 2.1 is equivalent to J+J⊤⪰0J + J^\top\succeq0, whereas Assumption 2.2 with constant LL is equivalent to ∥J∥op≤L\lVert J\rVert_{\mathrm{op}} \le L. The class includes quadratic minimization and bilinear saddle problems. A nonsymmetric matrix JJ allows a non-gradient mean field. The pathwise identities below use the affine representation alone. Monotonicity and Lipschitz continuity enter the weak-gap estimate through Proposition B.1, while Assumption 2.3 supplies the conditional moment bounds.

Main results for unconstrained affine VIs

This section establishes the exact device-mean recursion, derives its restricted weak-gap consequence, and proves a corresponding affine lower bound.

Exact local-to-central equivalence

The theorem is structural: affinity makes equal averaging commute with both stages of the standard local SEG update. Its pathwise part is deterministic; the subsequent moment bounds invoke the stochastic-oracle assumption.

For each iteration, define the oracle residuals

εtm:=G^(ztm,ζtm)−G(ztm),εt+1/2m:=G^(ytm,ζt+1/2m)−G(ytm),\varepsilon_t^m := \widehat{G}(z_t^m,\zeta_t^m)-G(z_t^m), \qquad\varepsilon_{t+1/2}^m := \widehat{G}(y_t^m,\zeta_{t+1/2}^m)-G(y_t^m),

and let

εˉs:=1M∑m=1Mεsm,s∈{t,t+1/2}.\bar{\varepsilon}_s := \frac{1}{M}\sum_{m=1}^{M}\varepsilon_s^m, \qquad s \in\{t,t+1/2\}.

Theorem 3.1 (Exact device-mean recursion). Let Assumption 2.4 hold and run Algorithm 1 under any admissible synchronization schedule. Then, pathwise for every t=0,…,T−1t=0,\ldots,T-1,

yˉt=zˉt−γ(G(zˉt)+εˉt),zˉt+1=zˉt−γ(G(yˉt)+εˉt+1/2).(3)\bar{y}_t=\bar{z}_t-\gamma\left(G(\bar{z}_t)+\bar{\varepsilon}_t\right), \qquad\bar{z}_{t+1}=\bar{z}_t-\gamma\left(G(\bar{y}_t)+\bar{\varepsilon}_{t+1/2}\right). \tag*{(3)}

If Assumption 2.3 also holds and Fs\mathcal{F}_s denotes the history before oracle stage ss, then

E[εˉs∣Fs]=0,E[∥εˉs∥2∣Fs]≤σ2M,s∈{t,t+1/2}.\mathbb{E}\left[\bar{\varepsilon}_s \mid\mathcal{F}_s\right]=0, \qquad\mathbb{E}\left[\left\|\bar{\varepsilon}_s\right\|^2 \mid\mathcal{F}_s\right]\leq\frac{\sigma^2}{M}, \qquad s\in\{t,t+1/2\}.

Proof. At the first stage, affinity gives

yˉt=zˉt−γM∑m=1M(G(ztm)+εtm)=zˉt−γ(G(zˉt)+εˉt).\bar{y}_t=\bar{z}_t-\frac{\gamma}{M}\sum_{m=1}^{M}\left(G(z_t^m)+\varepsilon_t^m\right)=\bar{z}_t-\gamma\left(G(\bar{z}_t)+\bar{\varepsilon}_t\right).

The same calculation at the second stage gives the second identity in (3). Optional equal-weight synchronizations leave both means unchanged. Under Assumption 2.3, conditional centering gives the first-moment identities, and conditional independence eliminates cross terms; for example,

E[∥εˉt∥2∣Ft]=1M2∑m=1ME[∥εtm∥2∣Ft]≤σ2M.\mathbb{E}\left[\left\|\bar{\varepsilon}_t\right\|^2\mid\mathcal{F}_t\right]=\frac{1}{M^2}\sum_{m=1}^{M}\mathbb{E}\left[\left\|\varepsilon_t^m\right\|^2\mid\mathcal{F}_t\right]\leq\frac{\sigma^2}{M}.

Conditioning on Ft+1/2\mathcal{F}_{t+1/2} proves the second-stage estimate. □

Thus the device mean follows a centralized stochastic-extragradient recursion with conditionally centered noise whose variance is reduced by the number of devices. The pathwise identity uses affinity alone; the stochastic oracle assumption supplies the moment bounds.

Relation to quadratic minimization. When J=J⊤⪰0J=J^\top\succeq0, the operator is the gradient of a quadratic objective, and the theorem specializes to the exact-averaging principle for linear-update methods on homogeneous quadratics [12]. For nonsymmetric JJ, the same identity applies to non-gradient operators and preserves the two-stage mean recursion.

Weak-gap rate and terminal-only aggregation

The exact recursion transfers an unprojected SEG estimate with variance divided by MM. The common stepsize controls the balance between deterministic progress and stochastic error.

Corollary 3.2 (Restricted weak-gap rate). Suppose Assumptions 2.1, 2.2, 2.3, and 2.4 hold, and let z⋆z^\star be a root of GG. Suppose that the initial device states are F0\mathcal{F}_0-measurable and ∥zˉ0−z⋆∥≤Ω\|\bar{z}_0-z^\star\|\leq\Omega almost surely for some Ω>0\Omega>0. Then, for every admissible synchronization schedule, every integer T≥1T\geq1, and every 0<γ≤1/(2L)0<\gamma\leq1/(2L),

E[Gap⁡Ω(zˉT)]≤3Ω2γT+9γσ2M.(4)\mathbb{E}\left[\operatorname{Gap}_{\Omega}(\bar{z}_T)\right]\leq\frac{3\Omega^2}{\gamma T}+\frac{9\gamma\sigma^2}{M}. \tag*{(4)}

In particular, choose

γ=min⁡{12L,ΩMσT},\gamma= \min\left\{\frac{1}{2L}, \frac{\Omega\sqrt{M}}{\sigma\sqrt{T}}\right\},

where the second quantity is interpreted as +∞+\infty when σ=0\sigma=0. Then

E[Gap⁡Ω(z~T)]≤12(LΩ2T+σΩMT).(5)\mathbb{E}[\operatorname{Gap}_{\Omega}(\widetilde{z}_{T})] \le12\left(\frac{L\Omega^2}{T}+\frac{\sigma\Omega}{\sqrt{MT}}\right). \tag*{(5)}

Proof. Assumptions 2.1 and 2.2 provide the regularity required by Proposition B.1. Theorem 3.1 gives its adapted-error recursion with v=σ2/Mv=\sigma^2/M, proving (4). The restriction γ≤1/(2L)\gamma\le1/(2L) ensures stability. For the stated stepsize,

1γ≤2L+σTΩM,γ≤ΩMσT,\frac{1}{\gamma}\le2L+\frac{\sigma\sqrt{T}}{\Omega\sqrt{M}},\qquad\gamma\le\frac{\Omega\sqrt{M}}{\sigma\sqrt{T}},

with the usual convention when σ=0\sigma=0. Hence

3Ω2γT≤6LΩ2T+3σΩMT,9γσ2M≤9σΩMT.\frac{3\Omega^2}{\gamma T}\le\frac{6L\Omega^2}{T}+\frac{3\sigma\Omega}{\sqrt{MT}},\qquad\frac{9\gamma\sigma^2}{M}\le\frac{9\sigma\Omega}{\sqrt{MT}}.

Combining these estimates proves (5). □

IC specialization. For the standard block Local SEG schedule, every communication round contains τ:=⌊K/2⌋\tau:=\lfloor K/2\rfloor completed extragradient iterations followed by a terminal-state synchronization. Hence T=RτT=R\tau. For K≥2K\ge2, ⌊K/2⌋≥K/3\lfloor K/2\rfloor\ge K/3, and Corollary 3.2 gives

E[Gap⁡Ω(z~T)]≤C(LΩ2KR+σΩMKR).(6)\mathbb{E}[\operatorname{Gap}_{\Omega}(\widetilde{z}_{T})]\le C\left(\frac{L\Omega^2}{KR}+\frac{\sigma\Omega}{\sqrt{MKR}}\right). \tag*{(6)}

Terminal-only aggregation. The bound (6) is attained without intermediate synchronizations. Divide the local computation into RR blocks of ⌊K/2⌋\lfloor K/2\rfloor SEG iterations, leave the first R−1R-1 communication opportunities unused, and aggregate the accumulated half-iterate sums at the final opportunity. The resulting output is

z~T=1M∑m=1M(1T∑t=0T−1ytm).\widetilde{z}_{T}=\frac{1}{M}\sum_{m=1}^{M}\left(\frac{1}{T}\sum_{t=0}^{T-1}y_t^m\right).

Table 1 places the Local SEG upper bound beside two standard SEG baselines, the Wang–Kale analysis of Local Extra SGD, and the two lower bounds proved here.

Method / resultScopeWeak-gap boundInterpretation
Upper bounds
Minibatch SEG [2, 3]general monotone; bounded variance; R≥2R \ge2LΩ2R+σΩMKR\frac{L\Omega^2}{R}+\frac{\sigma\Omega}{\sqrt{MKR}}deterministic horizon is RR
Single-device SEG [1, 2, 3]general monotone; bounded variance; KR≥2KR \ge2LΩ2KR+σΩKR\frac{L\Omega^2}{KR}+\frac{\sigma\Omega}{\sqrt{KR}}variance has single-device scaling
Wang–Kale analysis of Local Extra SGD [14]affine mean; conditionally unbiased bounded-variance oracle; K≥2K \ge2LΩ2KR+σΩMKR+Ω4/3σ2/3L1/3K1/3R2/3\frac{L\Omega^2}{KR}+\frac{\sigma\Omega}{\sqrt{MKR}}+\frac{\Omega^{4/3}\sigma^{2/3}L^{1/3}}{K^{1/3}R^{2/3}}proved bound contains a client-drift term
Local SEG upper bound (this paper) (Corollary 3.2)affine monotone mean; conditional independence across devices within each stage; K≥2K \ge2LΩ2KR+σΩMKR\frac{L\Omega^2}{KR}+\frac{\sigma\Omega}{\sqrt{MKR}}two-term rate matched in the stated class
Lower bounds proved in this paper
Affine Gaussian lower bound (this paper) (Theorem 3.4)unconstrained affine VI; Gaussian noise; zero-respecting depth≥c[LΩ2KR+min⁡{LΩ2,σΩMKR}]\ge c\left[\frac{L\Omega^2}{KR}+\min\left\{L\Omega^2,\frac{\sigma\Omega}{\sqrt{MKR}}\right\}\right]order-matching before statistical saturation
Communication-locality lower bound (this paper) (Theorem 4.1)bounded affine VI; query-dependent noise; σ>0\sigma>0; feasible zero-respecting methods≥cmin⁡{LΩ2Rlog⁡(eM),σ2LKR}\ge c\min\left\{\frac{L\Omega^2}{R\log(eM)},\frac{\sigma^2}{LKR}\right\}communication-dependent constrained regime

Table 1. Expected weak-gap upper and lower bounds in the IC model, up to universal constants. The Local SEG upper bound and the two lower bounds in bold are proved in this paper; in the lower-bound rows; c>0c>0 denotes an absolute numerical constant.

The first four data rows are upper bounds, and the last two are lower bounds. The upper-bound comparison uses homogeneous mean operators and unconstrained Euclidean geometry. For our Local SEG bound, oracle errors are conditionally centered and conditionally independent across devices within each stage. The Wang–Kale and present Local SEG rows assume full participation, equal device weights, and a common deterministic stepsize. The final row describes a bounded-domain boundary case.

In the first five data rows, Ω\Omega is the radius of the root-centered comparison ball; in the last row, it bounds the diameter of the feasible set.

Matching affine lower bound

Definition 3.3 (Affine Gaussian instance). For L,Ω>0L,\Omega>0 and σ≥0\sigma\ge0, an affine Gaussian instance on Rn\mathbb{R}^n consists of a mean operator GG satisfying Assumptions 2.1, 2.2, and 2.4, with Lipschitz constant at most LL, and a root z⋆z^\star satisfying ∥z⋆∥≤Ω\lVert z^\star\rVert\le\Omega. At every oracle call, each device receives

G^(z)=G(z)+ξ,\widehat{G}(z)=G(z)+\xi,

where the errors are independent draws from the same centered, possibly degenerate Gaussian distribution and satisfy

E[∥ξ∥2]≤σ2.\mathbb{E}\left[\lVert\xi\rVert^2\right]\le\sigma^2.

The notation Gap⁡Ω\operatorname{Gap}_{\Omega} refers to the root-centered comparison ball in (2). All expectations include both oracle and algorithmic randomness.

Theorem 3.4 (Affine Gaussian lower bound). Let L,Ω>0L,\Omega>0, σ≥0\sigma\ge0, and let M,K,R≥1M,K,R\ge1 be integers. For every n≥4KR+4n\ge4KR+4 and every distributed zero-respecting IC algorithm on Rn\mathbb{R}^n, there is an affine Gaussian instance in the sense of Definition 3.3 such that

E[Gap⁡Ω(z^)]≥c[LΩ2KR+min⁡{LΩ2,σΩMKR}].(7)\mathbb{E}[\operatorname{Gap}_{\Omega}(\hat{z})]\ge c\left[\frac{L\Omega^2}{KR}+\min\left\{L\Omega^2,\frac{\sigma\Omega}{\sqrt{MKR}}\right\}\right]. \tag*{(7)}

where c>0c>0 is an absolute numerical constant independent of the problem parameters and the algorithm.

For every n≥1n\ge1 and every randomized IC algorithm on Rn\mathbb{R}^n with the same budgets, there is a possibly different affine Gaussian instance with these parameters for which

E[Gap⁡Ω(z^)]≥cmin⁡{LΩ2,σΩMKR}.\mathbb{E}[\operatorname{Gap}_{\Omega}(\hat{z})]\ge c\min\left\{L\Omega^2,\frac{\sigma\Omega}{\sqrt{MKR}}\right\}.

Proof sketch. The deterministic and statistical terms are obtained from two affine instances. For the deterministic term, a skew-symmetric bilinear zero chain reveals at most one new coordinate per sequential oracle call. After depth KRKR, a terminal coordinate remains hidden, and direct evaluation of the weak gap gives a lower bound of order LΩ2/(KR)L\Omega^2/(KR). For the statistical term, a one-dimensional affine root observed through additive Gaussian noise yields a two-point testing problem with MKRMKR observations. This gives the saturated statistical term for every randomized IC algorithm. The maximum of the two risks is at least half their sum, which proves (7). Appendix A contains the complete argument.

The deterministic construction starts at the origin and has ∥z⋆∥≤Ω\lVert z^\star\rVert\le\Omega, so it belongs to the upper class with common initialization z0=0z_0=0. Therefore the KRKR and MKRMKR dependences in Corollary 3.2 are order-optimal in the stated zero-respecting class whenever the statistical term is nonsaturated.

For the comparison in Table 1, Wang and Kale count extragradient iterations, whereas KK here counts oracle calls. Their comparison set is a ball centered at the initial device mean. Taking its radius to be 2Ω2\Omega covers the root-centered ball in (2); these conversions affect only absolute constants.

Limits of exact averaging

This section identifies a boundary of the unconstrained exact-reduction result. We retain an affine mean operator but require feasible queries and outputs on a bounded domain.

A communication-locality boundary

The exact reduction and its two-resource rate concern unconstrained Euclidean updates. The next theorem considers a bounded feasible set, where the algorithm must keep its queries and output feasible. For this result only, write

Gap⁡Z(x):=sup⁡z∈Z⟨G(z),x−z⟩,x∈Z.(8)\operatorname{Gap}_{\mathcal{Z}}(x) := \sup_{z\in\mathcal{Z}} \langle G(z),x-z\rangle,\qquad x\in\mathcal{Z}. \tag*{(8)}

This gap is nonnegative because the supremum includes z=xz=x.

Scope. The exact identity applies to an affine common mean operator, unprojected Euclidean updates, equal aggregation weights, a common deterministic stepsize, and homogeneous device operators. Individual oracle realizations may be nonlinear and query dependent, and their effective-noise laws may depend on the synchronization schedule. The boundary result below concerns feasible distributed zero-respecting algorithms on a bounded domain.

For L,Ω,σ>0L,\Omega,\sigma>0 and an integer M≥1M\ge1, set

ℓM:=log⁡(eM),p:=min⁡{1,L2Ω232σ2}.\ell_M := \log(eM),\qquad p:=\min\left\{1,\frac{L^2\Omega^2}{32\sigma^2}\right\}.

Theorem 4.1 (Communication-locality boundary). Let L,Ω,σ>0L,\Omega,\sigma>0, let M,K,R≥1M,K,R\ge1 be integers, and let nn be an integer satisfying n≥2∣4R(Kp+ℓM)∣+2n\ge2\lvert4R(Kp+\ell_M)\rvert+2. For every distributed zero-respecting IC algorithm on Rn\mathbb{R}^n that makes feasible queries and returns a feasible output, there exist a nonempty compact convex set Z⊆Rn\mathcal{Z}\subseteq\mathbb{R}^n of diameter at most Ω\Omega, an affine monotone LL-Lipschitz operator G:Z→RnG:\mathcal{Z}\to\mathbb{R}^n with a root in Z\mathcal{Z}, and a query-dependent stochastic oracle satisfying Assumption 2.3 with conditional variance bounded by σ2\sigma^2. The oracle law is common to all devices, and the output z^\hat z satisfies

E[Gap⁡Z(z^)]≥cmin⁡{LΩ2RℓM,σ2LKR}.(9)\mathbb{E}[\operatorname{Gap}_{\mathcal{Z}}(\hat z)]\ge c\min\left\{\frac{L\Omega^2}{R\ell_M},\frac{\sigma^2}{LKR}\right\}. \tag*{(9)}

where c>0c>0 is an absolute numerical constant.

Proof sketch. A query-dependent Bernoulli oracle reveals the next zero-chain coordinate only with probability pp. Rescaling a rare reveal by 1/p1/p preserves conditional unbiasedness, while the bounded feasible geometry controls its variance. In one IC round, the furthest of MM devices advances by only O(Kp+log⁡(eM))O(Kp+\log(eM)) coordinates in expectation. Choosing a chain longer than the progress attainable in RR rounds leaves a hidden terminal coordinate and hence a positive weak gap. Balancing pp with the variance budget gives the two regimes in (9). Appendix § 8.§ 4 supplies the full argument, which adapts the robust zero-chain construction of Woodworth et al. [6] to an affine bilinear VI.

In the regime σ2≥L2Ω2K/ℓM\sigma^2 \ge L^2\Omega^2K/\ell_M, the first term in (9) is active, so the error has an explicit 1/R1/R communication dependence. The two results cover distinct geometries. Theorem 3.1 concerns unprojected updates on Rn\mathbb{R}^n, while the hard instance above combines active feasibility geometry with a query-dependent revealing oracle.

Numerical illustration of the two-resource effect

The experiment isolates the two resources in Corollary 3.2: adaptive sequential depth and aggregate sampling across devices. Up to integer floors, minibatch SEG, single-device SEG, and Local SEG have the respective resource pairs (R,MKR)(R,MKR), (KR,KR)(KR,KR), and (KR,MKR)(KR,MKR), where the first entry is adaptive depth and the second is the sample budget entering variance reduction. Thus the two baselines separate the two advantages combined by Local SEG.

We use the ten-dimensional affine VI

G(z)=Jz,J=1∥[0AT−A0]∥op[0AT−A0],(10)G(z)=Jz,\qquad J=\frac{1}{\left\lVert\begin{bmatrix}0&A^{\mathsf T}\\-A&0\end{bmatrix}\right\rVert_{\mathrm{op}}}\begin{bmatrix}0&A^{\mathsf T}\\-A&0\end{bmatrix}, \tag*{(10)}

where A∈R5×5A\in\mathbb{R}^{5\times5} is one fixed Gaussian draw. Thus JT=−JJ^{\mathsf T}=-J, ∥J∥op=1\lVert J\rVert_{\mathrm{op}}=1, and z⋆=0z^\star=0. The comparison set is the unit ball, and a call returns Jz+ξJz+\xi with ξ∼N(0,I10/10)\xi\sim\mathcal{N}(0,I_{10}/10) independently across devices and stages. For a comparison radius Ω\Omega, the restricted weak gap is Gap⁡Ω(x)=Ω∥JTx∥\operatorname{Gap}_{\Omega}(x)=\Omega\lVert J^{\mathsf T}x\rVert; the experiment uses Ω=1\Omega=1.

Figure 2 compares minibatch SEG, single-device SEG, and classical Local SEG. Every method uses the same analytical, data-independent stepsize rule and the exact two-calls-per-SEG accounting described in Appendix § 10. The left panel fixes M=32M=32 and K=16K=16 and varies the communication budget. The right panel fixes K=16K=16 and R=64R=64 and varies the number of devices.

Figure 2. Separation of sequential-depth and device-averaging effects on the affine problem (10). Left: expected restricted weak gap as the communication budget increases. Right: expected restricted weak gap as the number of devices increases. Error bars are pointwise normal-approximation 95% Monte Carlo confidence intervals from 80 independent replications.

The left panel isolates adaptive depth: at the same communication and aggregate-oracle budgets, Local SEG extends the horizon from order RR to order KRKR and improves on minibatch SEG.

The right panel isolates device averaging. The single-device curve is nearly insensitive to MM. Minibatch SEG benefits from larger batches but approaches the deterministic floor associated with its shorter horizon, whereas Local SEG retains the longer horizon while its effective variance decreases with MM. This behavior is consistent with the deterministic and stochastic terms in (6).

Conclusion

We studied the classical Local SEG method for stochastic affine monotone VIs under intermittent communication. For unconstrained Euclidean updates with equal device weights and a common stepsize, affinity makes device averaging commute with both stages of the extragradient recursion. The identity is pathwise and continues to hold when individual oracle realizations are nonlinear and query dependent. Under conditionally centered errors that are conditionally independent across devices within each stage, the averaged oracle error has conditional second moment at most σ2/M\sigma^2/M. For K≥2K \ge2, this gives

O(LΩ2KR+σΩMKR)\mathcal{O}\left(\frac{L\Omega^2}{KR}+\frac{\sigma\Omega}{\sqrt{MKR}}\right)

for the expected restricted weak gap. The deterministic component depends on the local sequential depth, whereas the stochastic component depends on the aggregate oracle budget. The same finite-horizon guarantee is attained with one terminal aggregation.

The affine Gaussian lower bound matches these resource dependences before statistical saturation for distributed zero-respecting algorithms, while its statistical component applies to arbitrary randomized IC algorithms. The bounded-domain construction gives a complementary communication-locality lower bound for feasible distributed zero-respecting methods. Together, the results separate the unconstrained affine regime, in which the device-mean recursion closes exactly, from a constrained regime in which active geometry and query-dependent noise can restrict the propagation of information.

Extensions to approximately affine operators, projected or mirror updates, unequal aggregation weights, and heterogeneous device operators remain open. Interpolation-type noise models constitute a further direction because the effective noise may then depend on disagreement among local query points.

Acknowledgments

This work was supported by Ministry of Science and Higher Education of the Russian Federation (Grant No. 075-15-2024-529).

We thank Georgy Bondarenko for comments and discussions.

Declaration on the use of generative AI. Generative AI tools were used in a supporting role for language editing of the final manuscript, presentation-level organization, and limited assistance with research code. The research questions, mathematical results, experimental design, and scientific conclusions were developed by the authors. All AI-assisted text and code, as well as all proofs and numerical results, were reviewed and independently verified by the authors, who take full responsibility for the content of the manuscript.

Affine lower-bound constructions

This appendix proves the two lower-bound theorems. A bilinear zero chain gives the deterministic depth obstruction, and a one-dimensional two-point experiment gives the Gaussian statistical obstruction. The same chain, combined with a rare-revelation oracle, proves the communication-locality boundary on a bounded domain.

For an operator H:D→RdH:\mathcal{D}\to\mathbb{R}^{d}, a nonempty comparison set C⊆D\mathcal{C}\subseteq\mathcal{D}, and x∈Rdx\in\mathbb{R}^{d}, define

Gap⁡CH(x):=sup⁡z∈C⟨H(z),x−z⟩.\operatorname{Gap}_{\mathcal{C}}^{H}(x):=\sup_{z\in\mathcal{C}}\langle H(z),x-z\rangle.

When the operator is clear, we omit the superscript. Thus Gap⁡β\operatorname{Gap}_{\beta} and Gap⁡U×V\operatorname{Gap}_{\mathcal{U}\times\mathcal{V}} in this appendix are concrete instances of the same restricted weak-gap definition as Gap⁡Ω\operatorname{Gap}_{\Omega} in (2) and Gap⁡Z\operatorname{Gap}_{Z} in (8).

Formal IC transcript and support condition

For the lower bound it is enough to consider the following maximal-transcript envelope, which permits full sharing after every completed round. Let xk,rmx_{k,r}^{m} denote the kkth query of device mm in round rr, and let UalgU_{\mathrm{alg}} collect the shared algorithmic randomness. The query xk,rmx_{k,r}^{m} is measurable with respect to UalgU_{\mathrm{alg}}, all query–reply pairs from rounds r′<rr'<r, and the same device’s query–reply pairs with indices k′<kk'<k in round rr. The output z^\widehat{z} is measurable with respect to the full transcript and UalgU_{\mathrm{alg}}. A distributed zero-respecting algorithm additionally satisfies, almost surely,

supp⁡(xk,rm)⊆⋃1≤m′≤M, 1≤k′≤K1≤r′<rsupp⁡(G^(xk′,r′m′,ζk′,r′m′))∪⋃1≤k′<ksupp⁡(G^(xk′,rm,ζk′,rm)),(11)\operatorname{supp}(x_{k,r}^{m})\subseteq \bigcup_{\substack{1\le m'\le M,\ 1\le k'\le K\\1\le r'<r}} \operatorname{supp}\bigl(\widehat{G}(x_{k',r'}^{m'},\zeta_{k',r'}^{m'})\bigr) \cup \bigcup_{1\le k'<k} \operatorname{supp}\bigl(\widehat{G}(x_{k',r}^{m},\zeta_{k',r}^{m})\bigr), \tag*{(11)}
supp⁡(z^)⊆⋃1≤m≤M, 1≤k≤K1≤r≤Rsupp⁡(G^(xk,rm,ζk,rm)).(12)\operatorname{supp}(\widehat{z})\subseteq \bigcup_{\substack{1\le m\le M,\ 1\le k\le K\\1\le r\le R}} \operatorname{supp}\bigl(\widehat{G}(x_{k,r}^{m},\zeta_{k,r}^{m})\bigr). \tag*{(12)}

Shared randomness may choose measurable coefficients subject to (11)–(12). The statistical construction below applies to arbitrary randomized IC algorithms.

Bilinear zero chain

Lemma A.1 (Bilinear chain). Let N≥1N\ge1 be an integer and let r,κ>0r,\kappa>0. Define the upper bidiagonal matrix AN∈RN×NA_N\in\mathbb{R}^{N\times N} by (ANu)i=ui−ui+1(A_Nu)_i=u_i-u_{i+1} for i<Ni<N and (ANu)N=uN(A_Nu)_N=u_N. Put η=r/N\eta=r/\sqrt{N} and

Φ(u,v):=κ(⟨ANu,v⟩+ηu1),GN(u,v):=κ(ANTv+ηe1,−ANu).\Phi(u,v):=\kappa\bigl(\langle A_Nu,v\rangle+\eta u_1\bigr),\qquad G_N(u,v):=\kappa\bigl(A_N^{\mathsf T}v+\eta e_1,-A_Nu\bigr).

Then GNG_N is affine, monotone, and 2κ2\kappa-Lipschitz on R2N\mathbb{R}^{2N}, with root (u⋆,v⋆)=(0,−η1)(u^\star,v^\star)=(0,-\eta\mathbf{1}). Let U=V:={w∈RN:∥w∥≤r}\mathcal{U}=\mathcal{V}:=\{w\in\mathbb{R}^{N}:\|w\|\le r\}. For every (u^,v^)∈R2N(\widehat{u},\widehat{v})\in\mathbb{R}^{2N} with v^N=0\widehat{v}_N=0,

Gap⁡U×V(u^,v^)≥κr2N.(13)\operatorname{Gap}_{\mathcal{U}\times\mathcal{V}}(\widehat{u},\widehat{v})\ge\frac{\kappa r^2}{N}. \tag*{(13)}

Moreover, in the interleaved ordering (u1,v1,u2,v2,…)(u_1,v_1,u_2,v_2,\ldots), if w∈R2Nw\in\mathbb{R}^{2N} is supported on the first jj coordinates, where 0≤j≤2N0\le j\le2N, then GN(w)G_N(w) is supported on the first min⁡{j+1,2N}\min\{j+1,2N\} coordinates.

Proof. The linear part of GNG_N is skew-symmetric, so the operator is monotone. Since ∥AN∥op≤2\|A_N\|_{\mathrm{op}}\le2, its Lipschitz constant is at most 2κ2\kappa. Solving ANu=0A_Nu=0 and ANTv=−ηe1A_N^{\mathsf T}v=-\eta e_1 gives u⋆=0u^\star=0 and v⋆=−η1v^\star=-\eta\mathbf{1}.

For any candidate (u^,v^)(\widehat{u},\widehat{v}), direct expansion of the weak gap gives

Gap⁡U×V(u^,v^)=sup⁡u∈U, v∈V[Φ(u^,v)−Φ(u,v^)]=sup⁡v∈VΦ(u^,v)−inf⁡u∈UΦ(u,v^).\operatorname{Gap}_{\mathcal{U}\times\mathcal{V}}(\widehat{u},\widehat{v}) = \sup_{u\in\mathcal{U},\,v\in\mathcal{V}} \bigl[\Phi(\widehat{u},v)-\Phi(u,\widehat{v})\bigr] = \sup_{v\in\mathcal{V}}\Phi(\widehat{u},v) - \inf_{u\in\mathcal{U}}\Phi(u,\widehat{v}).

Because ∑i(ANu^)i=u^1\sum_i(A_N\hat{u})_i=\hat{u}_1,

sup⁡v∈VΦ(u^,v)=κηu^1+κr∥ANu^∥≥0.\sup_{v\in V}\Phi(\hat{u},v)=\kappa\eta\hat{u}_1+\kappa r\|A_N\hat{u}\|\ge0.

If v^N=0\hat{v}_N=0, the entries of AN⊤v^+ηe1A_N^\top\hat{v}+\eta e_1 sum to η\eta, and hence

−inf⁡u∈UΦ(u,v^)=κr∥AN⊤v^+ηe1∥≥κrηN=κr2N.-\inf_{u\in U}\Phi(u,\hat{v})=\kappa r\|A_N^\top\hat{v}+\eta e_1\|\ge\frac{\kappa r\eta}{\sqrt{N}}=\frac{\kappa r^2}{N}.

This proves (13). For the support claim, set v0=0v_0=0 and uN+1=0u_{N+1}=0. In the interleaved ordering,

(GN)ui=κ(vi−vi−1+η1{i=1}),(GN)vi=κ(ui+1−ui).(G_N)_{u_i}=\kappa(v_i-v_{i-1}+\eta\mathbf{1}_{\{i=1\}}),\qquad(G_N)_{v_i}=\kappa(u_{i+1}-u_i).

These coordinate identities prove the stated support property. □

Statistical affine-root obstruction

Lemma A.2 (Affine-root statistical lower bound). Let L,Ω>0L,\Omega>0, σ≥0\sigma\ge0, and let Nq≥1N_q\ge1 be an integer. For every possibly randomized adaptive algorithm using at most NqN_q oracle calls, there is a one-dimensional affine monotone operator with Lipschitz constant at most LL, a root z⋆z^\star satisfying ∣z⋆∣≤Ω/4|z^\star|\le\Omega/4, and an additive Gaussian oracle with independent noise of variance at most σ2\sigma^2 such that, for B:={z:∣z−z⋆∣≤Ω}\mathcal{B}:=\{z:|z-z^\star|\le\Omega\},

E[Gap⁡B(z^)]≥cmin⁡{LΩ2,σΩNq}.(14)\mathbb{E}[\operatorname{Gap}_{\mathcal{B}}(\hat{z})]\ge c\min\left\{L\Omega^2,\frac{\sigma\Omega}{\sqrt{N_q}}\right\}. \tag*{(14)}

where c>0c>0 is an absolute numerical constant.

Proof. The claim is immediate when σ=0\sigma=0, so suppose σ>0\sigma>0. Let θ∈{−β,+β}\theta\in\{-\beta,+\beta\} with β=Ω/4\beta=\Omega/4 and set

Gθ(z):=a(z−θ),a:=min⁡{L,c0σΩNq},G_\theta(z):=a(z-\theta),\qquad a:=\min\left\{L,\frac{c_0\sigma}{\Omega\sqrt{N_q}}\right\},

where c0>0c_0>0 is a sufficiently small numerical constant. The oracle returns Gθ(z)+ξG_\theta(z)+\xi with ξ∼N(0,σ2)\xi\sim\mathcal{N}(0,\sigma^2) independently at each call. At every query, the two conditional oracle means differ by 2aβ2a\beta. The chain rule for relative entropy therefore bounds the KL divergence between the two adaptive transcripts by Nq(2aβ)2/(2σ2)N_q(2a\beta)^2/(2\sigma^2). Le Cam’s two-point lemma [30 Section 2.2] then gives a constant lower bound on the probability of confusing the two roots.

For x∈Rx\in\mathbb{R}, write e=x−θe=x-\theta and q=z−θq=z-\theta. Directly from the weak-gap definition,

Gap⁡B(x)=asup⁡∣q∣≤Ωq(e−q)≥camin⁡{e2,Ω2}.\operatorname{Gap}_{\mathcal{B}}(x)=a\sup_{|q|\le\Omega}q(e-q)\ge ca\min\{e^2,\Omega^2\}.

Indeed, take q=e/2q=e/2 when ∣e∣≤2Ω|e|\le2\Omega and q=Ωsign⁡(e)q=\Omega\operatorname{sign}(e) otherwise. Predicting the sign of θ\theta from the sign of z^\hat{z}, a testing error implies ∣z^−θ∣≥Ω/4|\hat{z}-\theta|\ge\Omega/4. Thus the gap on that event is at least caΩ2ca\Omega^2, and the testing lower bound yields (14). More explicitly, averaging over the two equiprobable signs of θ\theta gives this lower bound for the average risk, so at least one of the two operators satisfies (14). □

Proof of Theorem 3.4. For the deterministic term, take the chain in Lemma A.1 with

N0:=2KR+2,κ:=L/2,r:=Ω/5,N_0:=2KR+2,\qquad\kappa:=L/2,\qquad r:=\Omega/\sqrt{5},

and use the noiseless, hence degenerate Gaussian, oracle. At the start of round ss, suppose the shared transcript is supported on the first (s−1)K(s-1)K interleaved coordinates. By (11), the first query of every device is supported on this prefix. Lemma A.1 permits at most one new coordinate per local reply, so after its kkth query a device has revealed at most the first (s−1)K+k(s-1)K+k coordinates. The union over devices remains supported on the same prefix. Induction over kk and ss gives final progress at most KRKR; in particular, the output satisfies v^N0=0\widehat{v}_{N_0}=0. The product set U×V\mathcal{U}\times\mathcal{V} lies in the ball of radius Ω\Omega centered at z⋆=(0,−η1)z^\star=(0,-\eta\mathbf{1}), because

∥(u,v)−z⋆∥2≤r2+(∥v∥+∥v⋆∥)2≤5r2=Ω2.\lVert(u,v)-z^\star\rVert^2 \le r^2+(\lVert v\rVert+\lVert v^\star\rVert)^2 \le5r^2=\Omega^2.

Consequently, Lemma A.1 gives

Gap⁡Ω(z^)≥κr2N0≥LΩ240KR.\operatorname{Gap}_{\Omega}(\widehat{z})\ge\frac{\kappa r^2}{N_0}\ge\frac{L\Omega^2}{40KR}.

The active dimension is 2N0=4KR+42N_0=4KR+4; extra coordinates are padded with zeros. For the statistical term, apply Lemma A.2 with Nq=MKRN_q=MKR, place the scalar construction in the first coordinate, and set all remaining operator and noise coordinates to zero. Its set B\mathcal{B} embeds in the first coordinate of the root-centered ball defining Gap⁡Ω\operatorname{Gap}_{\Omega}. Because the padded operator vanishes in all other coordinates, the resulting gap equals the scalar gap. Selecting the hard instance with the larger of the deterministic and statistical risks and using max⁡{a,b}≥(a+b)/2\max\{a,b\}\ge(a+b)/2 proves (7). The statistical construction applies to arbitrary randomized IC algorithms, which proves the second assertion of the theorem. □

Communication-locality construction

Proof of Theorem 4.1. We use Lemma A.1 with

κ:=L/2,r:=Ω22.\kappa:=L/2,\qquad r:=\frac{\Omega}{2\sqrt{2}}.

For any chain length NN, the product domain Z:=U×V\mathcal{Z}:=\mathcal{U}\times\mathcal{V} has diameter 22r=Ω2\sqrt{2}r=\Omega. Its root (0,−η1)(0,-\eta\mathbf{1}) is feasible because ∥η1∥=r\lVert\eta\mathbf{1}\rVert=r, and GNG_N is LL-Lipschitz.

We first define the stochastic oracle. Write the coordinates in the interleaved order from Lemma A.1, and put d:=2Nd:=2N. For 0≤j≤d0\le j\le d, let PjP_j denote the orthogonal projection onto the first jj interleaved coordinates, with P0=0P_0=0 and Pd=IP_d=I. For w∈Zw\in\mathcal{Z}, define

prog⁡(w):=max⁡{j:wj≠0},prog⁡(0):=0.\operatorname{prog}(w):=\max\{j:w_j\ne0\},\qquad\operatorname{prog}(0):=0.

With j=prog⁡(w)j=\operatorname{prog}(w), set

H0(w):=PjGN(w),H1(w):=GN(w),D(w):=H1(w)−H0(w).H_0(w):=P_jG_N(w),\qquad H_1(w):=G_N(w),\qquad D(w):=H_1(w)-H_0(w).

The zero-chain formulas in Lemma A.1 show that D(w)D(w) contains only the possible next frontier coordinate. More explicitly, letting euie_{u_i} and evie_{v_i} denote the basis vectors of the corresponding interleaved coordinates,

D(w)={κηeu1,j=0,−κuievi,j=2i−1,−κvieui+1,j=2i<2N,0,j=2N.D(w)= \begin{cases} \kappa\eta e_{u_1}, & j=0,\\ -\kappa u_i e_{v_i}, & j=2i-1,\\ -\kappa v_i e_{u_{i+1}}, & j=2i<2N,\\ 0, & j=2N. \end{cases}

Since w=(u,v)∈U×Vw=(u,v)\in\mathcal{U}\times\mathcal{V} and η≤r\eta\le r, this gives

∥D(w)∥≤κr,κ2r2=L2Ω232.(15)\lVert D(w)\rVert\le\kappa r,\qquad\kappa^2r^2=\frac{L^2\Omega^2}{32}. \tag*{(15)}

At each call, draw a new U∼Bernoulli⁡(p)U\sim\operatorname{Bernoulli}(p), independently across devices and calls conditional on the past, and return

G^N(w;U):=H0(w)+UpD(w).(16)\widehat{G}_N(w;U):=H_0(w)+\frac{U}{p}D(w). \tag*{(16)}

Because σ>0\sigma> 0, the probability pp belongs to (0,1](0,1]. Conditional on the pre-call history, ww is fixed and

E[G^N(w;U)∣F]=GN(w),(17)\mathbb{E}\left[\widehat{G}_N(w;U)\mid\mathcal{F}\right]=G_N(w), \tag*{(17)}
E[∥G^N(w;U)−GN(w)∥2∣F]=1−pp∥D(w)∥2≤σ2.(18)\mathbb{E}\left[\left\|\widehat{G}_N(w;U)-G_N(w)\right\|^2\mid\mathcal{F}\right]=\frac{1-p}{p}\|D(w)\|^2\leq\sigma^2. \tag*{(18)}

Indeed, the last inequality is immediate for p=1p=1. If p<1p<1, then p=L2Ω2/(32σ2)p=L^2\Omega^2/(32\sigma^2), and (15) gives the claim. Thus the same affine mean operator and the same oracle kernel are used on all devices, although the oracle realization depends on the query through its revealed support.

It remains to bound the revealed progress. Let Rs\mathcal{R}_s be the finite set of oracle replies produced through round ss, and define

Ss:=max⁡({0}∪⋃g∈Rssupp⁡(g)).S_s:=\max\left(\{0\}\cup\bigcup_{g\in\mathcal{R}_s}\operatorname{supp}(g)\right).

Before the first reply, S0=0S_0=0. A call with U=1U=1 reveals the next coordinate. Let Hs−1\mathcal{H}_{s-1} denote the history before round ss. Conditional on Hs−1\mathcal{H}_{s-1}, complete the KK-call sequence with independent coins and set

Xm,s:=∑k=1KUm,k,s∼Binomial⁡(K,p).X_{m,s}:=\sum_{k=1}^{K}U_{m,k,s}\sim\operatorname{Binomial}(K,p).

The support condition (11) then gives, almost surely,

Ss−Ss−1≤max⁡1≤m≤MXm,s.(19)S_s-S_{s-1}\leq\max_{1\leq m\leq M}X_{m,s}. \tag*{(19)}

For completeness, the conditional moment-generating-function estimate

E[exp⁡(max⁡mXm,s)∣Hs−1]≤M(1−p+pe)K≤exp⁡(log⁡M+(e−1)Kp)\mathbb{E}\left[\exp\left(\max_m X_{m,s}\right)\mid\mathcal{H}_{s-1}\right]\leq M(1-p+pe)^K\leq\exp\left(\log M+(e-1)Kp\right)

and conditional Jensen’s inequality imply

E[max⁡mXm,s∣Hs−1]≤2(Kp+ℓM).\mathbb{E}\left[\max_m X_{m,s}\mid\mathcal{H}_{s-1}\right]\leq2(Kp+\ell_M).

Iterating (19) yields

E[SR]≤2R(Kp+ℓM).(20)\mathbb{E}[S_R]\leq2R(Kp+\ell_M). \tag*{(20)}

Choose the active chain length

N:=⌈4R(Kp+ℓM)⌉+1.N:=\lceil4R(Kp+\ell_M)\rceil+1.

Markov’s inequality and (20) give P{SR<N}≥1/2\mathbb{P}\{S_R<N\}\geq1/2. On this event, (12) implies that the output has v^N=0\hat{v}_N=0. Lemma A.1 therefore gives Gap⁡Z(z^)≥κr2/N\operatorname{Gap}_Z(\hat{z})\geq\kappa r^2/N. Off this event the gap remains nonnegative because z^\hat{z} is feasible. Consequently,

E[Gap⁡Z(z^)]≥c0LΩ2R(Kp+ℓM)(21)\mathbb{E}[\operatorname{Gap}_Z(\hat{z})]\geq c_0\frac{L\Omega^2}{R(Kp+\ell_M)} \tag*{(21)}

where c0>0c_0>0 is an absolute numerical constant.

To express the two regimes, put q:=σ2/(L2Ω2)q:=\sigma^2/(L^2\Omega^2). If p=1p=1, then q≤1/32q\leq1/32 and

1K+ℓM≥12min⁡{1ℓM,qK}.\frac{1}{K+\ell_M}\geq\frac{1}{2}\min\left\{\frac{1}{\ell_M},\frac{q}{K}\right\}.

If p<1p<1, then p=1/(32q)p=1/(32q), and the same inequality, with a possibly smaller absolute constant, follows from

1Kp+ℓM=1K/(32q)+ℓM≥12min⁡{32qK,1ℓM}≥12min⁡{qK,1ℓM}.\frac{1}{Kp+\ell_M}=\frac{1}{K/(32q)+\ell_M}\geq\frac{1}{2}\min\left\{\frac{32q}{K},\frac{1}{\ell_M}\right\}\geq\frac{1}{2}\min\left\{\frac{q}{K},\frac{1}{\ell_M}\right\}.

Multiplying by LΩ2/RL\Omega^2/R in (21) proves (9).

Finally, the dimension condition in the theorem is exactly n≥2Nn\geq2N. Embed the product balls in the first 2N2N coordinates and pad the operator and oracle replies by zeros when n>2Nn>2N. □

Unprojected stochastic extragradient estimate

The main upper bound follows from a single centralized SEG estimate. Its adapted-error formulation accommodates the averaged residuals in Theorem 3.1, whose distribution may differ from that of a primitive oracle call at the mean query.

Proposition B.1 (Unprojected SEG with adapted errors). Let G:Rn→RnG : \mathbb{R}^{n} \to\mathbb{R}^{n} be monotone and LL-Lipschitz for some L>0L > 0, and suppose G(z⋆)=0G(z^{\star}) = 0. Fix an integer T≥1T \ge1, a stepsize 0<γ≤1/(2L)0 < \gamma\le1/(2L), and v≥0v \ge0. Let F0⊆F1/2⊆F1⊆⋯⊆FT−1/2⊆FT\mathcal{F}_{0} \subseteq\mathcal{F}_{1/2} \subseteq\mathcal{F}_{1} \subseteq\cdots\subseteq\mathcal{F}_{T-1/2} \subseteq\mathcal{F}_{T} be a filtration. For t=0,…,T−1t = 0, \ldots, T-1, let ztz_t be Ft\mathcal{F}_t-measurable. Let Δt\Delta_t and Δt+1/2\Delta_{t+1/2} be measurable with respect to Ft+1/2\mathcal{F}_{t+1/2} and Ft+1\mathcal{F}_{t+1}, respectively, and suppose

E[∥Δt∥2∣Ft]≤v,(22)\mathbb{E}\left[\left\|\Delta_t\right\|^2 \mid\mathcal{F}_t\right] \le v, \tag*{(22)}
E[Δt+1/2∣Ft+1/2]=0,E[∥Δt+1/2∥2∣Ft+1/2]≤v(23)\mathbb{E}\left[\Delta_{t+1/2} \mid\mathcal{F}_{t+1/2}\right] = 0,\qquad \mathbb{E}\left[\left\|\Delta_{t+1/2}\right\|^2 \mid\mathcal{F}_{t+1/2}\right] \le v \tag*{(23)}

Run

yt=zt−γ(G(zt)+Δt),zt+1=zt−γ(G(yt)+Δt+1/2).y_t = z_t - \gamma\left(G(z_t) + \Delta_t\right),\qquad z_{t+1} = z_t - \gamma\left(G(y_t) + \Delta_{t+1/2}\right).

If, for some Ω>0\Omega> 0, ∥z0−z⋆∥≤Ω\left\|z_0 - z^{\star}\right\| \le\Omega almost surely and B:={u:∥u−z⋆∥≤Ω}\mathcal{B} := \{u : \left\|u-z^{\star}\right\| \le\Omega\}, then, for z~T:=T−1∑t=0T−1yt\widetilde{z}_T := T^{-1}\sum_{t=0}^{T-1} y_t,

E[Gap⁡B(z~T)]≤3Ω2γT+9γv.(24)\mathbb{E}\left[\operatorname{Gap}_{\mathcal{B}}(\widetilde{z}_T)\right] \le\frac{3\Omega^2}{\gamma T} + 9\gamma v. \tag*{(24)}

Proof. Fix u∈Bu \in\mathcal{B}. Expanding the two unprojected updates gives

2γ⟨G(yt),yt−u⟩=∥zt−u∥2−∥zt+1−u∥2−∥yt−zt∥2−∥yt−zt+1∥2+2γ⟨G(yt)−G(zt),yt−zt+1⟩−2γ⟨Δt,yt−zt+1⟩+2γ⟨Δt+1/2,zt−zt+1⟩+2γ⟨Δt+1/2,u−zt⟩.\begin{aligned} 2\gamma\langle G(y_t),y_t-u\rangle ={}&\left\|z_t-u\right\|^2-\left\|z_{t+1}-u\right\|^2-\left\|y_t-z_t\right\|^2-\left\|y_t-z_{t+1}\right\|^2\\ &+2\gamma\langle G(y_t)-G(z_t),y_t-z_{t+1}\rangle-2\gamma\langle\Delta_t,y_t-z_{t+1}\rangle\\ &+2\gamma\langle\Delta_{t+1/2},z_t-z_{t+1}\rangle+2\gamma\langle\Delta_{t+1/2},u-z_t\rangle. \end{aligned}

Put a=∥yt−zt∥a=\left\|y_t-z_t\right\|, b=∥yt−zt+1∥b=\left\|y_t-z_{t+1}\right\|, d=∥Δt∥d=\left\|\Delta_t\right\|, and e=∥Δt+1/2∥e=\left\|\Delta_{t+1/2}\right\|. Since γL≤1/2\gamma L\le1/2, Lipschitz continuity and Young’s inequality give

−a2−b2+2γLab+2γdb+2γe(a+b)≤8γ2(d2+e2).-a^2-b^2+2\gamma Lab+2\gamma db+2\gamma e(a+b)\le8\gamma^2(d^2+e^2).

Indeed, the four positive terms are bounded by (a2+b2)/2(a^2+b^2)/2, b2/4+4γ2d2b^2/4+4\gamma^2d^2, a2/4+4γ2e2a^2/4+4\gamma^2e^2, and b2/4+4γ2e2b^2/4+4\gamma^2e^2, respectively. Substitution into the preceding identity leaves

2γ⟨G(yt),yt−u⟩≤∥zt−u∥2−∥zt+1−u∥2+8γ2(∥Δt∥2+∥Δt+1/2∥2)+2γ⟨Δt+1/2,u−zt⟩.(25)2\gamma\langle G(y_t),y_t-u\rangle\le\left\|z_t-u\right\|^2-\left\|z_{t+1}-u\right\|^2+8\gamma^2\left(\left\|\Delta_t\right\|^2+\left\|\Delta_{t+1/2}\right\|^2\right)+2\gamma\langle\Delta_{t+1/2},u-z_t\rangle. \tag*{(25)}

Monotonicity gives ⟨G(yt),yt−u⟩≥⟨G(u),yt−u⟩\langle G(y_t),y_t-u\rangle\ge\langle G(u),y_t-u\rangle. To control the supremum over uu prior to taking expectations, let p0=z⋆p_0=z^{\star} and let pt+1p_{t+1} be the Euclidean projection of pt+γΔt+1/2p_t+\gamma\Delta_{t+1/2} onto B\mathcal{B}. The projection inequality yields

sup⁡u∈B∑t=0T−1⟨Δt+1/2,u−pt⟩≤Ω22γ+γ2∑t=0T−1∥Δt+1/2∥2.(26)\sup_{u\in\mathcal{B}}\sum_{t=0}^{T-1}\langle\Delta_{t+1/2},u-p_t\rangle\le\frac{\Omega^2}{2\gamma}+\frac{\gamma}{2}\sum_{t=0}^{T-1}\left\|\Delta_{t+1/2}\right\|^2. \tag*{(26)}

The sequence pt−ztp_t-z_t is Ft+1/2\mathcal{F}_{t+1/2}-measurable. Conditional centering therefore gives

E[∑t=0T−1⟨Δt+1/2,pt−zt⟩]=0.\mathbb{E}\left[\sum_{t=0}^{T-1}\langle\Delta_{t+1/2},p_t-z_t\rangle\right]=0.

Sum (25), take the supremum over u∈Bu\in\mathcal{B}, and use (26). Since sup⁡u∈B∥z0−u∥2≤4Ω2\sup_{u\in\mathcal{B}}\left\|z_0-u\right\|^2\le4\Omega^2, the expected right-hand side is at most 5Ω2+17γ2Tv5\Omega^2+17\gamma^2Tv. Dividing by 2γT2\gamma T and rounding the constants upward proves (24). □

Experimental details

This appendix records the exact accounting used in § 5.

For a positive horizon TT and effective variance VV, every method uses

γ=min⁡{12L,ΩTV}.\gamma= \min\left\{\frac{1}{2L}, \frac{\Omega}{\sqrt{TV}}\right\}.

The second entry is interpreted as +∞+\infty when V=0V=0. The following table gives the values used by the implementation; a completed SEG iteration always consumes two oracle calls.

MethodTTVVActual calls
Minibatch SEG (R≥2R \ge2)⌊R/2⌋\lfloor R/2 \rfloorσ2/(MK)\sigma^2/(MK)2TMK2TMK
Single-device SEG (KR≥2KR \ge2)⌊KR/2⌋\lfloor KR/2 \rfloorσ2\sigma^22T2T
Classical Local SEG (K≥2K \ge2)R⌊K/2⌋R\lfloor K/2 \rfloorσ2/M\sigma^2/M2TM2TM

Table 2. Iteration horizons, effective variances, and actual oracle calls.

The corresponding horizons are positive under R≥2R \ge2 for minibatch SEG, KR≥2KR \ge2 for single-device SEG, and K≥2K \ge2 for classical Local SEG. All configurations in Figure 2 satisfy these conditions.

The experiment uses L=Ω=σ=1L=\Omega=\sigma=1 and the fixed pseudorandom seed 20260815. The matrix AA in (10) and the common initial point z0z_0 are drawn once and reused in every configuration; the initial point is rescaled so that ∥z0∥=0.8\lVert z_0\rVert=0.8. The rounds grid is {4,8,16,32,64,128}\{4, 8, 16, 32, 64, 128\} and the devices grid is {1,2,4,8,16,32,64}\{1, 2, 4, 8, 16, 32, 64\}. The left panel fixes M=32M=32 and K=16K=16; the right panel fixes K=16K=16 and R=64R=64. Since these values of KK and RR are even, minibatch SEG and Local SEG use exactly MKRMKR oracle calls in the corresponding comparisons.

Each point in Figure 2 is computed from 80 independent replications. The error bars equal 1.96 times the sample standard error. The output is the temporal average of the half-iterates, and its merit value is the closed-form gap following (10). The stepsize is fixed in advance according to the displayed rule.

References

  1. [1]Galina M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 12(4):747–756, 1976. In Russian.
  2. [2]Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229–251, 2004.DOI
  3. [3]Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17–58, 2011.
  4. [4]Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems, volume 28, pages 1756–1764, 2015.
  5. [5]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, pages 8496–8506, 2018.arxiv.org/abs/1805.10222
  6. [6]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
  7. [7]H. 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
  8. [8]Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
  9. [9]Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, volume 32, pages 11080–11092, 2019.arxiv.org/abs/1910.13598
  10. [10]Peter Kairouz, H. Brendan McMahan, Brendan Avent, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1–2):1–210, 2021.
  11. [11]Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U. Stich, Ziheng Cheng, Nirmit Joshi, and Nathan Srebro. The limits and potentials of local SGD for distributed heterogeneous learning with intermittent communication. In Proceedings of the 37th Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4115–4157, 2024.
  12. [12]Blake Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. 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
  13. [13]Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Vladimir Samokhin, Sebastian U. Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. In Advances in Neural Information Processing Systems, volume 35, pages 38116–38133, 2022.
  14. [14]Guanghui Wang and Satyen Kale. Faster rates for federated variational inequalities, 2026. arXiv:2602.09164.arxiv.org/abs/2602.09164
  15. [15]Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, and Alexander Gasnikov. Distributed saddle-point problems under data similarity. In Advances in Neural Information Processing Systems, volume 34, pages 8172–8184, 2021.DOI
  16. [16]Alexander Rogozin, Aleksandr Beznosikov, Darina Dvinskikh, Dmitry Kovalev, Pavel Dvurechensky, and Alexander Gasnikov. Decentralized distributed optimization for saddle point problems, 2021. arXiv:2102.07758.
  17. [17]Aleksandr Beznosikov, Vladimir Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, near-optimal and robust algorithms. Optimization Methods and Software, 40(5):1249–1266, 2025.
  18. [18]Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Mikhail Persianov, Peter Richtárik, and Alexander Gasnikov. Optimal algorithms for decentralized stochastic variational inequalities. In Advances in Neural Information Processing Systems, volume 35, pages 31073–31088, 2022.
  19. [19]Aleksandr Beznosikov, Eduard Gorbunov, Hugo Bérard, and Nicolas Loizou. Stochastic gradient decent-ascent: Unified theory and new efficient methods. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 172–235, 2023.
  20. [20]Aleksandr Beznosikov, Martin Takáč, and Alexander Gasnikov. Similarity, compression and local steps: Three pillars of efficient communications for distributed variational inequalities. In Advances in Neural Information Processing Systems, volume 36, pages 28663–28677, 2023.
  21. [21]David Ruppert. Efficient estimations from a slowly convergent Robbins–Monro process. Technical Report 781, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1988.
  22. [22]Boris T. Polyak and Anatoli B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992.DOI
  23. [23]Wenlong Mou, Chris Junchi Li, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan. On linear stochastic approximation: Fine-grained polyak–ruppert and non-asymptotic concentration. In Proceedings of the 33rd Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2947–2997, 2020.arxiv.org/abs/2004.04719
  24. [24]Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. In Advances in Neural Information Processing Systems, volume 33, pages 5332–5344, 2020.arxiv.org/abs/2006.08950
  25. [25]Andrey E. Sadchikov, Savelii A. Chezhegov, Aleksandr N. Beznosikov, and Alexander V. Gasnikov. Local SGD for near-quadratic problems: Improving convergence under unconstrained noise conditions. Russian Mathematical Surveys, 79(6):1017–1049, 2024.DOI
  26. [26]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
  27. [27]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, pages 7333–7345, 2021.arxiv.org/abs/2106.02720
  28. [28]Arkadi S. Nemirovsky and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.
  29. [29]Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1–2):1–35, 2021.
  30. [30]Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 2009.

Paper details

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

views · 3

downloads · 0

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

  • Mathematics

Generative AI tools

View statement
Looking for related papers…
Contents