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.
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.
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.
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, is the Euclidean norm for vectors and the induced operator norm for matrices, and is the Euclidean inner product.
Intermittent communication
We use the standard homogeneous intermittent-communication model [5, 6]. There are devices and local-computation rounds. In each round, every device makes at most 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 , while the maximal sequential depth is . Figure 1 illustrates this mechanism.

Figure 1. Intermittent-communication model. Each device performs up to 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 be nonempty, closed, and convex and let . The variational inequality (VI) is to find such that
For continuous monotone , this is equivalent to the weak formulation for every .
We model a deterministic mean operator accessed through a stochastic oracle. We therefore state the operator properties and the stochastic-oracle conditions separately.
When stochastic access is used, let be a sample space and let denote the oracle response map.
Assumption 2.1 (Monotonicity). The operator is monotone on : for every ,
Assumption 2.2 (Lipschitz continuity). For some , the operator is -Lipschitz on : for every ,
Assumption 2.3 (Stochastic oracle). For some , before each call denotes the complete history and the query is -measurable. A new draw satisfies
Randomness used by simultaneous calls is conditionally independent given the pre-stage history. At a later stage, includes all earlier replies.
For the unconstrained affine results in § 3, . We call a root of if ; such a root solves (1). Whenever an affine instance has a specified root and radius , we measure any candidate by the root-centered restricted weak gap
The comparison ball in (2) only localizes the merit function; the algorithm, its iterates, and its output remain unconstrained in . This localization is necessary because the unrestricted weak gap on may be infinite away from a solution. Since the comparison ball contains and , we have for every . Monotonicity further gives .
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 -measurable, and all devices use a common deterministic stepsize.
Algorithm 1 Local SEG with an admissible equal-averaging schedule
Require: States , horizon , stepsize , and a synchronization schedule
for every
for do
for all devices in parallel do
end for
Set for every if a half-stage synchronization is scheduled; otherwise set
for all devices in parallel do
end for
Set for every if a terminal-stage synchronization is scheduled; otherwise set
end for
return
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
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 completed SEG iterations per communication round, so . The terminal-only implementation leaves intermediate communication opportunities unused and aggregates the accumulated vectors at the end.
Affine mean subclass
Assumption 2.4 (Affine mean structure). Let . The mean operator is affine:
for some and . The affine condition applies to the conditional mean operator; individual oracle realizations may be nonlinear and query dependent.
For an affine operator on , Assumption 2.1 is equivalent to , whereas Assumption 2.2 with constant is equivalent to . The class includes quadratic minimization and bilinear saddle problems. A nonsymmetric matrix 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
and let
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 ,
If Assumption 2.3 also holds and denotes the history before oracle stage , then
Proof. At the first stage, affinity gives
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,
Conditioning on 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 , 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 , 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 . 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 be a root of . Suppose that the initial device states are -measurable and almost surely for some . Then, for every admissible synchronization schedule, every integer , and every ,
In particular, choose
where the second quantity is interpreted as when . Then
Proof. Assumptions 2.1 and 2.2 provide the regularity required by Proposition B.1. Theorem 3.1 gives its adapted-error recursion with , proving (4). The restriction ensures stability. For the stated stepsize,
with the usual convention when . Hence
Combining these estimates proves (5). □
IC specialization. For the standard block Local SEG schedule, every communication round contains completed extragradient iterations followed by a terminal-state synchronization. Hence . For , , and Corollary 3.2 gives
Terminal-only aggregation. The bound (6) is attained without intermediate synchronizations. Divide the local computation into blocks of SEG iterations, leave the first communication opportunities unused, and aggregate the accumulated half-iterate sums at the final opportunity. The resulting output is
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 / result | Scope | Weak-gap bound | Interpretation |
| Upper bounds | |||
| Minibatch SEG [2, 3] | general monotone; bounded variance; | deterministic horizon is | |
| Single-device SEG [1, 2, 3] | general monotone; bounded variance; | variance has single-device scaling | |
| Wang–Kale analysis of Local Extra SGD [14] | affine mean; conditionally unbiased bounded-variance oracle; | 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; | 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 | order-matching before statistical saturation | |
| Communication-locality lower bound (this paper) (Theorem 4.1) | bounded affine VI; query-dependent noise; ; feasible zero-respecting methods | 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; 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, 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 and , an affine Gaussian instance on consists of a mean operator satisfying Assumptions 2.1, 2.2, and 2.4, with Lipschitz constant at most , and a root satisfying . At every oracle call, each device receives
where the errors are independent draws from the same centered, possibly degenerate Gaussian distribution and satisfy
The notation 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 , , and let be integers. For every and every distributed zero-respecting IC algorithm on , there is an affine Gaussian instance in the sense of Definition 3.3 such that
where is an absolute numerical constant independent of the problem parameters and the algorithm.
For every and every randomized IC algorithm on with the same budgets, there is a possibly different affine Gaussian instance with these parameters for which
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 , a terminal coordinate remains hidden, and direct evaluation of the weak gap gives a lower bound of order . For the statistical term, a one-dimensional affine root observed through additive Gaussian noise yields a two-point testing problem with 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 , so it belongs to the upper class with common initialization . Therefore the and 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 here counts oracle calls. Their comparison set is a ball centered at the initial device mean. Taking its radius to be 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
This gap is nonnegative because the supremum includes .
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 and an integer , set
Theorem 4.1 (Communication-locality boundary). Let , let be integers, and let be an integer satisfying . For every distributed zero-respecting IC algorithm on that makes feasible queries and returns a feasible output, there exist a nonempty compact convex set of diameter at most , an affine monotone -Lipschitz operator with a root in , and a query-dependent stochastic oracle satisfying Assumption 2.3 with conditional variance bounded by . The oracle law is common to all devices, and the output satisfies
where is an absolute numerical constant.
Proof sketch. A query-dependent Bernoulli oracle reveals the next zero-chain coordinate only with probability . Rescaling a rare reveal by preserves conditional unbiasedness, while the bounded feasible geometry controls its variance. In one IC round, the furthest of devices advances by only coordinates in expectation. Choosing a chain longer than the progress attainable in rounds leaves a hidden terminal coordinate and hence a positive weak gap. Balancing 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 , the first term in (9) is active, so the error has an explicit communication dependence. The two results cover distinct geometries. Theorem 3.1 concerns unprojected updates on , 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 , , and , 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
where is one fixed Gaussian draw. Thus , , and . The comparison set is the unit ball, and a call returns with independently across devices and stages. For a comparison radius , the restricted weak gap is ; the experiment uses .
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 and and varies the communication budget. The right panel fixes and 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 to order and improves on minibatch SEG.
The right panel isolates device averaging. The single-device curve is nearly insensitive to . 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 . 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 . For , this gives
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 , a nonempty comparison set , and , define
When the operator is clear, we omit the superscript. Thus and in this appendix are concrete instances of the same restricted weak-gap definition as in (2) and 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 denote the th query of device in round , and let collect the shared algorithmic randomness. The query is measurable with respect to , all query–reply pairs from rounds , and the same device’s query–reply pairs with indices in round . The output is measurable with respect to the full transcript and . A distributed zero-respecting algorithm additionally satisfies, almost surely,
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 be an integer and let . Define the upper bidiagonal matrix by for and . Put and
Then is affine, monotone, and -Lipschitz on , with root . Let . For every with ,
Moreover, in the interleaved ordering , if is supported on the first coordinates, where , then is supported on the first coordinates.
Proof. The linear part of is skew-symmetric, so the operator is monotone. Since , its Lipschitz constant is at most . Solving and gives and .
For any candidate , direct expansion of the weak gap gives
Because ,
If , the entries of sum to , and hence
This proves (13). For the support claim, set and . In the interleaved ordering,
These coordinate identities prove the stated support property. □
Statistical affine-root obstruction
Lemma A.2 (Affine-root statistical lower bound). Let , , and let be an integer. For every possibly randomized adaptive algorithm using at most oracle calls, there is a one-dimensional affine monotone operator with Lipschitz constant at most , a root satisfying , and an additive Gaussian oracle with independent noise of variance at most such that, for ,
where is an absolute numerical constant.
Proof. The claim is immediate when , so suppose . Let with and set
where is a sufficiently small numerical constant. The oracle returns with independently at each call. At every query, the two conditional oracle means differ by . The chain rule for relative entropy therefore bounds the KL divergence between the two adaptive transcripts by . 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 , write and . Directly from the weak-gap definition,
Indeed, take when and otherwise. Predicting the sign of from the sign of , a testing error implies . Thus the gap on that event is at least , and the testing lower bound yields (14). More explicitly, averaging over the two equiprobable signs of 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
and use the noiseless, hence degenerate Gaussian, oracle. At the start of round , suppose the shared transcript is supported on the first 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 th query a device has revealed at most the first coordinates. The union over devices remains supported on the same prefix. Induction over and gives final progress at most ; in particular, the output satisfies . The product set lies in the ball of radius centered at , because
Consequently, Lemma A.1 gives
The active dimension is ; extra coordinates are padded with zeros. For the statistical term, apply Lemma A.2 with , place the scalar construction in the first coordinate, and set all remaining operator and noise coordinates to zero. Its set embeds in the first coordinate of the root-centered ball defining . 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 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
For any chain length , the product domain has diameter . Its root is feasible because , and is -Lipschitz.
We first define the stochastic oracle. Write the coordinates in the interleaved order from Lemma A.1, and put . For , let denote the orthogonal projection onto the first interleaved coordinates, with and . For , define
With , set
The zero-chain formulas in Lemma A.1 show that contains only the possible next frontier coordinate. More explicitly, letting and denote the basis vectors of the corresponding interleaved coordinates,
Since and , this gives
At each call, draw a new , independently across devices and calls conditional on the past, and return
Because , the probability belongs to . Conditional on the pre-call history, is fixed and
Indeed, the last inequality is immediate for . If , then , 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 be the finite set of oracle replies produced through round , and define
Before the first reply, . A call with reveals the next coordinate. Let denote the history before round . Conditional on , complete the -call sequence with independent coins and set
The support condition (11) then gives, almost surely,
For completeness, the conditional moment-generating-function estimate
and conditional Jensen’s inequality imply
Iterating (19) yields
Choose the active chain length
Markov’s inequality and (20) give . On this event, (12) implies that the output has . Lemma A.1 therefore gives . Off this event the gap remains nonnegative because is feasible. Consequently,
where is an absolute numerical constant.
To express the two regimes, put . If , then and
If , then , and the same inequality, with a possibly smaller absolute constant, follows from
Multiplying by in (21) proves (9).
Finally, the dimension condition in the theorem is exactly . Embed the product balls in the first coordinates and pad the operator and oracle replies by zeros when . □
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 be monotone and -Lipschitz for some , and suppose . Fix an integer , a stepsize , and . Let be a filtration. For , let be -measurable. Let and be measurable with respect to and , respectively, and suppose
Run
If, for some , almost surely and , then, for ,
Proof. Fix . Expanding the two unprojected updates gives
Put , , , and . Since , Lipschitz continuity and Young’s inequality give
Indeed, the four positive terms are bounded by , , , and , respectively. Substitution into the preceding identity leaves
Monotonicity gives . To control the supremum over prior to taking expectations, let and let be the Euclidean projection of onto . The projection inequality yields
The sequence is -measurable. Conditional centering therefore gives
Sum (25), take the supremum over , and use (26). Since , the expected right-hand side is at most . Dividing by and rounding the constants upward proves (24). □
Experimental details
This appendix records the exact accounting used in § 5.
For a positive horizon and effective variance , every method uses
The second entry is interpreted as when . The following table gives the values used by the implementation; a completed SEG iteration always consumes two oracle calls.
| Method | Actual calls | ||
| Minibatch SEG () | |||
| Single-device SEG () | |||
| Classical Local SEG () |
Table 2. Iteration horizons, effective variances, and actual oracle calls.
The corresponding horizons are positive under for minibatch SEG, for single-device SEG, and for classical Local SEG. All configurations in Figure 2 satisfy these conditions.
The experiment uses and the fixed pseudorandom seed 20260815. The matrix in (10) and the common initial point are drawn once and reused in every configuration; the initial point is rescaled so that . The rounds grid is and the devices grid is . The left panel fixes and ; the right panel fixes and . Since these values of and are even, minibatch SEG and Local SEG use exactly 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]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]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]Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17–58, 2011.
- [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]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]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]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]Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
- [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]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]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]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]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]Guanghui Wang and Satyen Kale. Faster rates for federated variational inequalities, 2026. arXiv:2602.09164.arxiv.org/abs/2602.09164
- [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]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]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]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]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]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]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]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]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]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]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]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]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]Arkadi S. Nemirovsky and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.
- [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]Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 2009.
