arXiv CSopen access

\mathsf{VISTA}: Decentralized Machine Learning in Adversary Dominated Environments

VISTA: Decentralized Machine Learning in Adversary Dominated Environments

arXiv:2605.07841v1 [cs.LG] 8 May 2026

Hanzaleh Akbari Nodehi University of Minnesota [email protected] Soheil Mohajer University of Minnesota [email protected]

Parsa Moradi University of Minnesota [email protected] Mohammad Ali Maddah-Ali University of Minnesota [email protected]

Abstract Decentralized machine learning often relies on outsourcing computational tasks, such as gradient evaluations, to untrusted worker nodes. Existing robust aggregation methods, including median-based rules, can mitigate malicious behavior under honest-majority assumptions, where most workers follow the prescribed protocol. However, these methods can fail in permissionless environments in which adversaries may control a majority of the workers. To address this challenge, we consider an incentive-oriented framework in which workers’ reports are accepted and rewarded only when they are mutually consistent within a prescribed threshold. Upon acceptance, the submitted reports are used to estimate the desired computational output. This mechanism transforms the adversary from a pure saboteur into a rational agent that must balance the benefit of increasing the estimation error against the risk of rejection and loss of reward. We study iterative optimization under this adversary-dominated model, focusing on the problem of minimizing a loss function to train a machine learning model. Unlike one-shot computation, iterative optimization requires long-horizon decision making: the system must tune the acceptance rule to achieve fast and reliable convergence over time. This creates a fundamental tradeoff. Permissive acceptance rules can accelerate early progress but allow substantial adversarial corruption, whereas strict rules improve estimation accuracy at the cost of frequent rejections and slower optimization. We propose VISTA, an adaptive algorithm that dynamically tunes the acceptance threshold based on the observed history. We demonstrate the effectiveness of VISTA through numerical evaluations and complement these empirical results with a rigorous convergence analysis. These results show that, with suitable incentive-aware adaptation, adversary-dominated decentralized learning can retain the asymptotic convergence behavior of standard SGD without relying on an honest majority. To the best of our knowledge, this work is the first to address decentralized learning in an adversary-dominated regimes.

1

Introduction

Consider a setting in which a data collector (DC) or an aggregator needs to perform some computational task, but lacks enough computing power to execute it on its own. To address this limitation, it outsources the task to a set of worker nodes. Because some of these workers may act maliciously, the DC introduces redundancy by assigning the same (or related) computation to multiple nodes. The outsourced task may be a one-time computation, such as model inference, or a sequence of computations, such as minimizing a loss function during training. Some workers are honest and Preprint.

follow the protocol, although their outputs may still contain small inaccuracies due to approximation, quantization, or other benign system effects. Other workers, however, may behave adversarially and deliberately distort the reported computation in order to mislead the DC (see Fig. 1a). A key application of this framework is decentralized machine learning (DeML), where smart contracts (a computer program) deployed on a blockchain coordinate training or inference in a transparent and accountable manner [1–7]. In this context, the smart contract serves as the DC. Due to the computational limitations of blockchains, AI workloads are delegated to external worker nodes [8]. Also, these environments are typically permissionless, meaning that participating nodes may be adversarial, and in fact even the existence of an honest majority cannot be guaranteed [9–11]. When the environment is dominated by honest nodes, the DC can rely on robust aggregation methods, such as the geometric median, Krum, coordinate-wise median, to cope with the effect of adversarial behavior [12–27]. However, these methods generally lose their effectiveness when honest nodes are in the minority. To protect the computation in adversary dominated settings, the DC imposes a strict acceptance rule: the reported results are accepted only if the values returned by different workers are sufficiently close to one another, within a prescribed tolerance. Since at least a fraction, even one, of the workers are honest, the acceptance rule provides a basic level of reliability by rejecting highly divergent submissions. To motivate the adversarial nodes to collaborate, the DC also employs a reward policy under which all participating nodes, including both honest and adversarial ones, are compensated once the reported values satisfy the acceptance rule. For example, in DeML applications, this reward may take the form of cryptocurrency or token. This incentive mechanism fundamentally changes the role of the adversary. Rather than behaving as a pure saboteur, the adversary becomes a rational agent with a utility function that depends on two competing objectives: increasing the estimation error seen by the DC, and maintaining a sufficiently high probability of acceptance in order to receive the reward. As a result, the adversary must strategically choose its noise-injection. Outsourced computation tasks generally fall into two paradigms: single-shot operations, such as model inference, and multi-shot operations, such as iterative gradient descent. In the single-shot setting, the DC also faces a fundamental tradeoff. It prefers the computation to be accepted, since acceptance makes the result available and therefore encourages a more permissive acceptance rule, even at the risk of admitting adversarial outputs. Also, it seeks to keep the estimation error as small as possible, which favors a stricter acceptance rule. To balance these competing objectives, the DC relies on its own utility function to strategically calibrate the acceptance rule. This interaction naturally leads to a leader-follower game-theoretic framework: first, the DC, as the leader, announces the acceptance rule, and then the adversary, as the follower, chooses its noise in response (see Fig. 1b). This specific single-round dynamic, particularly in networks dominated by adversary, has been formalized and solved under the game of coding framework [28–32], which we detail in Section 5. Yh = L(W) + Nh Node 1

||Ya − Yh ||2 ≤ η∆

Yes

Estimation

L̂(U)

Ya = L(W) + Na Node 2 No

Data Collector

Reject

(a)

(b)

Figure 1: Fig. (a) shows a DC outsourcing the computation of L(W) to worker nodes due to limited resources. Honest workers follow the protocol but may return bounded noisy outputs, while adversaries may strategically inject arbitrary noise. We focus on the adversary dominated regime. Fig. (b) shows a two-node game-of-coding instance [28–32], with one honest and one adversarial node. The honest node returns Yh = L(W) + Nh , where ∥Nh ∥2 ≤ ∆, while the adversarial node returns Ya = L(W) + Na , with Na chosen strategically. The DC accepts reports only if ∥Ya − Yh ∥2 ≤ η∆, and forms an estimate only upon acceptance.

The dynamics shift significantly in multi-shot computational tasks, such as iterative optimization. Unlike single-shot scenarios, the DC does not maintain myopic, instantaneous preferences for individual computation rounds. Instead, the DC is driven by long-term objectives encompassing the entire sequence of interactions. In gradient descent, for example, the DC’s priority is not the marginal outcome of a single iteration, but rather the guarantee of rapid global convergence or the attainment of a specific accuracy threshold relative to the optimum. Consequently, a critical challenge arises: 2

Figure 2: Iterative game of coding framework. Since the DC does not have sufficient resources to evaluate ∇L(Wt−1 ) on its own, at each round t it broadcasts the current model parameter Wt−1 and the acceptance parameter ηt to the worker nodes. Each node i returns a noisy gradient report Yi,t = ∇L(Wt−1 ) + Ni,t . For honest workers, we have ∥Ni,t ∥2 ≤ ∆, while adversarial workers choose their noise strategically according to their utility function. The DC accepts the reports only if ∥Yu,t − Yv,t ∥2 ≤ ηt ∆ for all pairs of nodes u, v. b t and updates the model as Wt ← Wt−1 − Bt G b t ; otherwise, the model If accepted, it forms an estimate G remains unchanged, that is, Wt ← Wt−1 .

how can the DC’s long-term objectives be translated into a sequence of per-round acceptance rules that ensure a reliable convergence rate? This paper aims to bridge this gap. To be specific, in this paper, we consider the problem of minimizing a function L : Rd → R, which represents the optimization objective of interest. At each round (or equivalently iteration) t ∈ {0, 1, 2, . . . }, the objective is to update the current model parameter Wt−1 ∈ Rd as Wt ← Wt−1 − Bt ∇L(Wt−1 ), where Bt is the learning rate. However, the DC does not have computation power to compute ∇L(Wt−1 ). As an alternative, the DC announces the current model parameter Wt−1 together with an acceptance parameter ηt to all volunteer worker nodes. Each node i returns a noisy gradient estimate Yi,t = ∇L(Wt−1 ) + Ni,t . For honest workers, the noise Ni,t represents inherent system perturbations, such as quantization or approximation errors, and is typically bounded by ∥Ni,t ∥2 ≤ ∆. For adversarial nodes, Ni,t is sampled from a distribution strategically designed (as a function of ηt ) to balance its incentive for reward (i.e., having its computation accepted) with its objective of disrupting the optimization process (i.e., increasing the estimation error). Upon receiving these reports, the DC applies an acceptance policy requiring that ∥Yu,t − Yv,t ∥2 ≤ ηt ∆ for all pairs of nodes u and v. As noted earlier, because at least a fraction of the workers are honest and produce similar results, this condition provides a baseline level of reliability (see Fig. 2). Importantly, this acceptance verification is inherently a probabilistic event. Indeed, the condition ∥Yu,t − Yv,t ∥2 ≤ ηt ∆ is equivalent to ∥Nu,t − Nv,t ∥2 ≤ ηt ∆. Thus, even if the adversary strategically selects its injected noise, it does not know the realization of the honest noise in advance. As a result, it cannot guarantee acceptance, and instead must balance the amount of distortion it introduces against the probability that its report will still be accepted. Whenever the computation b t of the gradient ∇L(Wt−1 ). This estimate is generally is accepted, the DC forms an estimate G noisy, reflecting both the benign randomness of honest computation and the strategic perturbations introduced by adversarial nodes, as well as the stochastic variance inherent in algorithms such as b t . If stochastic gradient descent. The DC then updates the model according to Wt = Wt−1 − Bt G the computation is rejected, then no update is performed, that is, Wt = Wt−1 . The DC’s objective is to design the sequence of acceptance parameters {ηt }∞ t=0 and learning rates {Bt }∞ t=0 to guarantee convergence over time, in this adversary dominated network. In each iteration t for choosing ηt , the DC faces a dilemma: DC Dilemma: Choosing a larger ηt relaxes the acceptance condition, increasing the likelihood that Wt−1 is updated, but at the cost of higher error in estimating ∇L(Wt−1 ). Conversely, choosing a smaller ηt tightens the acceptance condition, reducing the likelihood that updates to Wt−1 are accepted; however, when updates do occur, the estimation error in ∇L(Wt−1 ) is smaller on average.

3

(a) A three-dimensional function

(b) Training loss on CIFAR-10 for ResNet-18.

Figure 3: A larger constant η enables faster initial progress through more frequent updates, but leads to higher error by admitting more adversarial noise. Smaller ones are more reliable but progress slowly due to frequent rejections. VISTA adapts ηt over time, using larger ηt early and smaller later to achieve best performance.

This paper resolves this dilemma by proposing an algorithm that adaptively selects the acceptance ∞ parameters {ηt }∞ t=0 and learning rates {Bt }t=0 , achieving near-optimal convergence rates over time, even under adversary dominated network conditions. At each iteration t, the proposed algorithm, called Variance-matched Iterative Step-size Tuning for Adaptive optimization (VISTA), dynamically determines ηt and learning rate bt , based on the history of the outcomes. Our main contributions are twofold: 1. Adaptive Design and Empirical Validation: We empirically demonstrate that VISTA significantly outperforms baseline schemes that rely on a constant η. As illustrated in Fig. 3a, the static baselines exhibit a clear “Tortoise-and-Hare effect”, which highlights the fundamental tradeoff between update frequency and update quality. For example, a highly permissive threshold, such as the brown curve with η = 60, allows frequent updates and yields rapid initial progress, but eventually plateaus at a relatively high error floor because it admits substantial adversarial noise (like the hare). In this phase, the norm of the gradient decays very slowly. In contrast, a stricter threshold, such as the blue curve with η = 10, suffers from a much slower start due to frequent computation rejections, yet eventually overtakes the more permissive baselines and achieves a considerably lower final error (like the tortoise). This behavior shows that any static choice of η is fundamentally inadequate, since the optimal threshold changes over the course of the optimization. More precisely, at the beginning, the model is far from the optimum, so the true gradient is large and dominates the adversarial perturbation. In this regime, a larger η is desirable because it enables more frequent updates and faster progress toward the optimum. Later, as the model approaches the optimum, the true gradient becomes small, and the adversarial noise can become comparable to, or even dominate, the useful signal. In that regime, η must be reduced in order to enforce more accurate and less corrupted updates. Our theoretical analysis of the expected descent in each iteration perfectly captures this phenomenon, and guides us to develop VISTA, which resolves this tension by dynamically adapting ηt and bt over time. As it is shown by the purple curve in Fig. 3a, the proposed algorithm outperforms any other choice of constant η at every single iteration. The proposed algorithm uses a larger ηt in the early stage to accelerate descent, and then progressively tightens the acceptance rule as the model approaches the optimum in order to suppress adversarial noise. As shown in Fig. 3a, this dynamic strategy achieves the best of both worlds, delivering both fast initial convergence and low final error. Additional experiments under other settings are provided in Section 4. 2. Asymptotic Optimality and Convergence Guarantees: We prove in Theorem 1 that the asymptotic convergence rate of VISTA matches the standard convergence rates of Stochastic Gradient Descent (SGD). To the best of our knowledge, this is the first rigorous mathematical framework for decentralized machine learning that guarantees asymptotic rates matching honest-majority settings, while operating in an adversary dominated network. Notation: We use uppercase letters for random variables and lowercase letters for deterministic values. Vectors are denoted in boldface and scalars in standard type. Unless stated otherwise, all Pd vectors lie in Rd , and for x = (x1 , . . . , xd ), we use the Euclidean norm ∥x∥2 = ( i=1 x2i )1/2 . 4

2

Problem Formulation

We consider a multi-round decentralized optimization setting, where the DC aims to minimize an objective function L : Rd → R. Examples of such objective functions include the training loss of a model over the parameter vector w ∈ Rd . The DC aims to perform (stochastic) gradient descent, and outsources the calculation of the gradient ∇L(w) ∈ Rd to a network of n external worker nodes, denoted by the set V = {1, . . . , n}. The network is partitioned into two disjoint sets: a set of honest nodes K and a set of adversarial nodes Q, where V = K ∪ Q. We specifically focus on the adversary dominated regime, where |Q| ≥ |K|. The true identities of the nodes are unknown to the DC. The optimization process unfolds over discrete iterative rounds t ∈ {0, 1, 2, . . . }. At each round t, the DC broadcasts the current model parameters Wt−1 ∈ Rd and an acceptance parameter ηt to all nodes in V. For the initial round t = 0, the DC uses the initial weight vector W−1 . Each honest node i ∈ K faithfully follows the protocol to calculate the true gradient ∇L(Wt−1 ). However, due to inherent computational limitations, such as stochastic approximations or floating point inaccuracies, the computed result contains random noise. The report sent to the DC by node i is Yi,t = ∇L(Wt−1 ) + Ni,t . For an honest node i ∈ K, the noise Ni,t ∈ Rd accounts for various imperfections, such as, randomness of the batch of data used for gradient evaluation, randomness of the data sample in SGD, or quantization. It is assumed to be bounded ∥Ni,t ∥2 ≤ ∆ with some symmetric distribution. In contrast, the adversarial nodes j ∈ Q are assumed to possess the exact realization of the true gradient ∇L(Wt−1 ). They collaborate to inject malicious noise into the system to corrupt the computation. The report sent by adversarial node j is Yj,t = ∇L(Wt−1 ) + Nj,t , where the injected adversarial noise vectors {Nj,t }j∈Q ⊂ Rd are drawn from an arbitrary joint probability density function g(·), strategically chosen by the adversary. Upon receiving Yt ≜ {Y1,t , . . . , Yn,t } = {Yi,t : i ∈ K} ∪ {Yj,t : j ∈ Q}, the DC first performs a consistency check parameterized by ηt . More precisely, the acceptance event, denoted by At , occurs if and only if ∥Yu,t − Yv,t ∥2 ≤ ηt ∆ for all u, v ∈ V. If the computation is accepted, the DC aggregates the reports using a predefined estimation function est : (Rd )n → Rd to form an estimated gradib t ∈ Rd . The estimated gradient could be a simple average est(Y1,t , . . . , Yn,t ) = 1 Pn Yi,t , ent G i=1 n or any sophisticated estimate. The DC then updates the model parameters using a learning rate b t . Conversely, if the computation is rejected, the model parameBt > 0 as Wt = Wt−1 − Bt G St ters remain unchanged, that is, Wt = Wt−1 . We define the history set Ht ≜ k=0 {Yi,k }i∈V . Moreover, the accepted gradient estimator is assumed to be conditionally unbiased, meaning that b t | Ht−1 , At ] = ∇L(Wt−1 ) (see Remark 1). Since honesty-based reports with error ∆ can E[G diverge by up to 2∆, we assume ηt ≥ 2 to ensure the DC does not reject valid computations. The interaction between the DC and the adversary fundamentally depends on two statistical metrics governed by the choice of ηt and the adversary’s chosen noise distribution g(·). Crucially, the acceptance event is inherently probabilistic. Although the adversary can strategically craft its own noise distribution g(·), it does not know the exact realization of the inherent random noise generated by the honest nodes. Because the adversarial nodes operate without knowing the honest nodes’ exact values, they cannot deterministically guarantee the acceptance of their reported results {Yi,t }i∈Q . Instead, the success of the threshold test depends entirely on how the adversary’s chosen noise distribution interacts with the acceptance parameter ηt . We formalize this by defining the probability of acceptance, which represents the system’s liveness at round t, as PA(g(·), ηt ) ≜ Pr(At | Ht−1 ), where the probability is evaluated over the fresh randomness of the current round, conditioned on the realized history. Furthermore, if the reports are accepted, we evaluate the resulting estimate using the b t ∥2 | Ht−1 , At ]. mean squared error MSE(g(·), ηt ) ≜ E[∥∇L(Wt−1 ) − G 2 The adversary faces a fundamental tradeoff between two competing objectives. On one hand, it seeks to maximize the error. On the other hand, since decentralized networks typically reward a node only when its computation is accepted, the adversary is also motivated to maintain a high probability of acceptance, in order to secure financial rewards. To capture this behavior, we model the interaction as a Stackelberg game [33]. More precisely, at the beginning of each round t, the DC announces its acceptance policy through the parameter ηt , and the adversary then chooses its noise distribution g(·) in response. We assume the adversary is rational and myopic, meaning that at each round it optimizes only its utility for the current interaction. Accordingly, it selects g(·) to maximize the utility
UAD (g(·), ηt ) ≜ QAD MSE(g(·), ηt ), PA(g(·), ηt ) , (1) 5

where QAD is strictly increasing in both arguments. Accordingly, at round t, the adversary’s optimal response to ηt is gη∗t (·) = arg max UAD (g(·), ηt ). This induces the equilibrium acceptance probability and mean squared error at round t, denoted by1 pηt ≜ PA(gη∗t (·), ηt )

and

ση2t ≜ MSE(gη∗t (·), ηt ).

(2)

Unlike the adversary, the DC does not optimize a local, per-round utility function. Its objective is instead long-term: to ensure that the optimization trajectory makes sustained progress on the global loss L(W) and converges, in the nonconvex sense, toward stationarity. Thus, the central challenge ∞ for the DC is to adaptively design the acceptance thresholds {ηt }∞ t=0 and learning rates {Bt }t=0 so as to guarantee fast and robust convergence despite adversarially corrupted accepted updates. While learning-rate schedules {Bt }∞ t=0 have been extensively studied [34–51], the acceptance sequence {ηt }∞ t=0 introduces a new control dimension. The threshold ηt determines how strictly the DC filters reports at each round, and a fixed choice is generally suboptimal. A small static η tightly limits the adversary and yields low-error accepted updates, but it also reduces pηt and slows progress. In contrast, a large static η increases acceptance and enables frequent updates, but gives the adversary more room to inject harmful noise and increase ση2t . The strategy must therefore adapt ηt over time. Far from the optimum W∗ , the gradient norm ∥∇L(Wt )∥2 is large, so the DC can use a larger threshold to increase pηt and obtain more frequent updates, while the gradient signal still dominates the bounded adversarial noise. Near W∗ , the gradient norm shrinks, and a large ηt allows adversarial noise to dominate the update and hinder convergence. Thus, the DC must gradually reduce ηt as the gradient signal weakens. This paper formalizes this principle and characterizes the decay of the acceptance sequence {ηt }∞ t=0 , jointly with the learning rate, to ensure robust convergence under strategic, dominant adversaries. Remark 1. As discussed in (1), the adversary has a per-round utility function. Under this myopic adversary model, prior game-of-coding works show that the equilibrium noise strategy is symmetric [28–30], which leads to an unbiased gradient estimate at the DC. By contrast, injecting a persistent directional bias would correspond to a non-myopic adversary with a multi-round utility. Learning and mechanism design against such non-myopic agents is a challenging problem in game theory [52–56], and we leave its study in this setting for future work.

3

MainResults

In this section, we first motivate and introduce our proposed algorithm, Variance-matched Iterative Step-size Tuning for Adaptive optimization (VISTA). acc b The update rule at iteration t can be expressed as Wt = Wt−1 − Iacc t Bt Gt , where It = 1{At } indicates whether the reports are accepted in round t, and Bt is the learning rate, which is a function of the history Ht−1 . Then, using the descent lemma [57] for ℓ-smooth functions, we can show

E[L(Wt ) | Ht−1 ] ≤ L(Wt−1 ) − Bt pηt (1 −

ℓBt ℓBt2 )∥∇L(Wt−1 )∥22 + pηt ση2t . 2 2

(3)

Let us define the expected descent at iteration t as Dt ≜ E[L(Wt−1 )−L(Wt ) | Ht−1 ], which ideally ℓBt2 2 2 t should be positive and large. From (3), we have Dt ≥ pηt (Bt (1 − ℓB 2 )∥∇L(Wt−1 )∥2 − 2 σηt ). One could use this lower bound as a surrogate objective for Dt and select the optimal ηt∗ by solving ηt∗ = arg

max η∈[ηmin ,ηmax ]

pηt (Bt (1 −

ℓBt ℓBt2 2 )∥∇L(Wt−1 )∥22 − σ ). 2 2 ηt

(4)

However, solving (4) is challenging and computationally intensive, since the relationship between pηt and ση2t is nonlinear and is induced by the adversary’s utility in (1). To resolve this challenge, let us take a closer look at the surrogate objective. This objective highlights the interaction between a positive term corresponding to the signal ∥∇L(Wt−1 )∥22 , and a negative term corresponding to the noise power ση2t . It provides two key insights. (i) The choice of ηt 1 The relationship between p

2 ηt and σηt has been characterized in other works for both cases where the adversary’s utility

is known [28–30] and where it is unknown [31, 32]. In this paper, we assume this relationship is given.

6

creates a fundamental tradeoff: increasing ηt increases pηt , which promotes more frequent updates and scales up the expected descent; however, it also increases ση2t , which can reduce Dt . This tradeoff indeed represents the DC dilemma discussed in the introduction. (ii) In the early stages of optimization, the gradient norm ∥∇L(Wt−1 )∥22 may be large because the model Wt−1 may still be far from a stationary point. Therefore, as long as ση2t remains small compared to ∥∇L(Wt−1 )∥22 , the useful signal dominates the noise, and the algorithm can tolerate a larger estimation error. In contrast, as the model approaches a stationary point, the gradient norm becomes small, that is, ∥∇L(Wt−1 )∥22 ≈ 0. In this regime, the noise term becomes comparatively more significant, and ηt must be adjusted to limit ση2t . This observation suggests choosing ηt so that ση2t = c∥∇L(Wt−1 )∥22 for some hyperparameter c > 0, thereby keeping the noise level proportional to the current signal strength. The hyperparameter c absorbs the effects of other coefficients in the surrogate objective, such as the Lipschitz constant ℓ. If the resulting threshold is smaller than ηmin = 2, then keeping the noise proportional to the signal is no longer possible within the feasible range, and the DC chooses 2 the strictest admissible threshold ηt = 2, equivalently ση2t = σmin . In addition, we restrict ηt to be at most ηmax . Putting these considerations together, the DC sets ηt as the smallest η satisfying 2 2 2 MSE(gη∗ , η) = σtarget ≜ min{σmax , max{σmin , c∥∇L(Wt−1 )∥22 }},

η ∈ [ηmin , ηmax ].

(5)

2 2 Note that (5) can be efficiently solved using a binary search since both ση2t ∈ [σmin , σmax ] and pηt ∈ [pmin , pmax ] are an increasing function of ηt .

Another point that needs to be clarified is the choice of the learning rate Bt . Whenever ηt > ηmin , which we refer to as the adaptive regime, the gradient norm is still large enough to guarantee ση2t ≤ c∥∇L(Wt−1 )∥22 , i.e., the noise power is upper bounded by a constant multiple of the squared gradient norm. This is reminiscent of the strong growth condition [58], where the stochastic error is bounded proportionally to the gradient norm. Motivated by this analogy, we keep the learning rate fixed within the adaptive regime, i.e., Bt = Bt−1 , so that the algorithm can benefit from larger updates while the gradient signal dominates the noise. When ηt reaches ηmin , the threshold cannot be tightened further, and the system enters the saturated regime. In this regime, the estimation 2 error is saturated at its minimum achievable level, ση2t = σmin . This is analogous to noisy or stochastic gradient descent with a persistent variance floor, where a decaying learning rate is required to guarantee convergence. Following the standard stochastic √optimization literature [34–51], we therefore use a learning rate that decays on the order of O(1/ t) during the saturated regime. The other less immediate issue is that when the DC selects ηt according to (5), it does not yet have access to ∥∇L(Wt−1 )∥22 or a fresh estimate of it. Indeed, announcing ηt is a prerequisite for asking the worker nodes to compute and report ∇L(Wt−1 ). To address this, for practical implementation, we use a bias-corrected exponential moving average of past accepted gradient e estimates of {∇L(Wk )}t−2 k=0 . We denote this one-step proxy for ∇L(Wt−1 ) by Gt−1 . Nevertheless, for theoretical analysis, we assume that an oracle provides the gradient norm ∥∇L(Wk )∥22 to the DC. The algorithm is not highly sensitive to small errors in this prediction, and empirically, this one-step proxy is sufficient for it, as discussed in Section 4, where our experimental results corroborate the convergence of VISTA, under using the proxy, instead of the actual gradient norm. Pt Algorithm 1 outlines the execution of VISTA. The algorithm tracks two counters, ut = k=0 Iacc k Pt acc sat and τt = k=0 Isat k , where Ik = 1 if round k is accepted, and Ik = 1 only if round k is accepted and ηk = ηmin . Thus, ut is the number of accepted rounds up to round t, while τt is the number of accepted saturated rounds. At each round t ≥ 0, the DC broadcasts (Wt−1 , ηt ) to all workers b t = est(Y ) and updates and receives the reports Yt . If round t is accepted, the DC forms G t −1/2 b bt Wt = Wt−1 − Bt Gt , where Bt = b0 (τt−1 + 1) . It also updates Mt = βMt−1 + (1 − β)G ut e e and Gt = Mt /(1 − β ). If the computation is rejected, then Wt , Mt , and Gt remain unchanged. e t ∥2 as a proxy for ∥∇L(Wt )∥2 . Therefore, instead of using (5), the DC chooses ηt+1 as We use ∥G 2 2 2 2 e t ∥2 }}. the smallest value of η ∈ [ηmin , ηmax ] satisfying MSE(gη∗ , η) = min{σmax , max{σmin , c∥G 2 We now establish the convergence of VISTA. We assume that L(w) ≥ L∗ for all w ∈ Rd . In addition, we assume that L(w) is ℓ-smooth, that is, for all u, v ∈ Rd , ∥∇L(u) − ∇L(v)∥2 ≤ ℓ∥u − v∥2 . Theorem 1 characterizes the asymptotic convergence rate of VISTA. e t ∥2 is a one-step prediction of ∥∇L(Wt )∥2 based on past accepted gradient estimates Recall that ∥G 2 2 of {∇L(Wk )}t−2 k=0 . This is motivated by a long line of stochastic optimization methods that use expo7

nential moving averages to smooth noisy gradient information and track first- or second-order gradient statistics [34–42]. This principle has also been used in distributed and Byzantine-robust optimization, where momentum-based history helps improve robustness to adversarial behavior [13, 15]. In the e t ∥2 ≈ ∥∇L(Wt )∥2 theorem below, we analyze the idealized setting in which the approximation ∥G 2 2 is exact up to oracle access to ∥∇L(Wt )∥22 . More precisely, instead of Line 7 of Algorithm 1, the threshold ηt is determined using (5). Theorem 1. Let L(w) be ℓ-smooth and bounded from below by L∗ . Under the execution of VISTA, where ηt is determined using (5) instead of Line 7 of Algorithm 1, with initial learning rate 1 √ T ). b0 ≤ ℓ(1+c) for some hyperparameter c > 0, we have min0≤t≤T E[∥∇L(Wt−1 )∥22 ] ≤ O( ln T Algorithm 1 Variance-matched Iterative Step-size Tuning for Adaptive optimization (VISTA) Require: b0 > 0, c > 0, β ∈ [0, 1), W−1 . e −1 ← 0, η0 ← (ηmin + ηmax )/2 1: Initialize: τ−1 ← 0, u−1 ← 0, M−1 ← 0, G 2: for round t = 0, 1, . . . do 3: The DC broadcasts (Wt−1 , ηt ) and receives Yt 4: if At is satisfied then √ b t ← est(Y ), Wt ← Wt−1 − Bt G b t , ut ← ut−1 + 1 5: Bt ← b0 / τt−1 + 1, G t ut b e 6: Mt ← βMt−1 + (1 − β)Gt , Gt ← Mt /(1 − β ) 2 2 e t ∥2 }}} , max{σmin , c∥G 7: ηt+1 ← inf{η ∈ [ηmin , ηmax ] : MSE(gη∗ , η) = min{σmax 2 8: if ηt = ηmin then τt ← τt−1 + 1 else τt ← τt−1 9: else et ← G e t−1 , ut ← ut−1 , τt ← τt−1 , ηt+1 ← ηt 10: Wt ← Wt−1 , Mt ← Mt−1 , G 11: end if 12: end for Remark 2. The bound in Theorem 1, implies that VISTA asymptotically achieves the same convergence rate as standard SGD despite the presence of dominated strategic adversaries. The detailed proof of Theorem 1 is provided in Appendix A; here, we highlight the key step. In the appendix, we show that for both the adaptive and saturated regimes, we have Bt pmin ℓσ 2 E[L(Wt ) | Ht−1 ] ≤ L(Wt−1 ) − ∥∇L(Wt−1 )∥22 + min Bt2 E[Isat (6) t | Ht−1 ]. 2 2 The last term in (6) contributes only in the saturated regime, where ηt = ηmin . In the adaptive regime, where ηt > ηmin , we have Isat t = 0, and hence the noise penalty vanishes. By rearranging (6), taking total expectation, and summing over t = 0, . . . , T , we obtain XT ℓσ 2 XT pmin XT 2 E[Bt ∥∇L(Wt−1 )∥22 ] ≤ E[L(Wt−1 ) − L(Wt )] + min E[Isat t Bt ] t=0 t=0 t=0 2 2 (a) (b) ℓσ 2 XT 2 ≤ L(W−1 ) − L∗ + min E[Isat t Bt ] ≤ O(ln T ), (7) t=0 2 PT where (a) follows from the telescoping sum t=0 (E[L(Wt−1 )] − E[L(Wt )]) = L(W−1 ) − E[L(WT )] ≤ L(W−1 ) − L∗ . Step (b) follows because the learning rate decays only during PT PT sat 2 accepted saturated rounds. Specifically, if S ≜ t=0 Isat t ≤ T + 1, then pathwise t=0 It Bt = PS 1 2 2 2 b0 k=1 k ≤ b0 (1 + ln S) ≤ b0 (1 + ln(T + 1)). This is why eliminating the noise penalty during the adaptive regime is essential. More precisely, in adaptive regime, the learning rate does not decay; ℓσ 2 therefore, if the penalty 2min Bt2 appeared in every round, summing it over T rounds could produce a linear O(T ) term. Instead, (6) multiplies this penalty by Isat t , so it contributes only during accepted saturated rounds, where the learning rate decays and the total contribution is only O(ln T ). To complete the proof of Theorem 1, we show that PT 2 (b) (a) ln T t=0 E[Bt ∥∇L(Wt−1 )∥2 ] min E[∥∇L(Wt−1 )∥22 ] ≤ ≤ O( √ ), (8) PT −1/2 0≤t≤T T b0 t=0 (t + 1) √ √ where (a) follows since τt−1 ≤ t, and hence Bt = b0 / τt−1 + 1 ≥ b0 / t + 1, together with the fact that the minimum of a nonnegative sequence is upper average. Moreover, √ √ bounded by its weighted PT −1/2 (b) follows from (7) and b0 t=0 (t + 1) ≥ 2b0 ( T + 2 − 1) = Ω( T ). 8

Figure 4: Training loss on MNIST for LeNet.

4

Experimental Results

In this section, we empirically evaluate VISTA. We use prior works on game of coding [28–32] to characterize pηt , ση2t , and the estimator est(·). Unless stated otherwise, we consider n = 2 nodes with |K| = |Q| = 1, and use adversarial utilities of the form UAD = log(MSE) + λ log(PA). All implementation details are provided in Appendix B. We also provide an ablation study on the hyperparameter c in Appendix C. For all baselines, “constant η” means that ηt is fixed, and Pt−1 √ Bt = b0 / ut−1 + 1, where ut−1 = k=0 Iacc k . Since rejected rounds do not update the iterate, this gives the same SGD-type decay over accepted rounds, so the comparison isolates the effect of dynamic thresholding. In figures with shaded regions, the shaded area represents standard deviation across independent runs. We start with the three-dimensional objective L(w) = 10w1 sin(w2 /10) + 10w2 sin(w3 /10) + 10w3 sin(w1 /2). We set (λ, c, b0 ) = (0.03, 1, 0.1). As shown in Fig. 3a, smaller constant η are more conservative, larger values provide faster initial progress, and VISTA achieves the best performance. Then, we evaluate VISTA on a practical learning task by training a LeNet model [59] on the MNIST dataset [60], where d = 23942. We set (λ, c, b0 ) = (0.0003, 15, 0.25). We report the average training loss using a moving average window of 100 for visualization. Fig. 4 shows the same pattern: larger values of η yield faster initial descent, while smaller values exhibit stronger later-stage improvement. VISTA exploits this tradeoff by starting with a relatively large threshold and reducing it over time. Finally, we evaluate VISTA by training a ResNet-18 model [61] on the CIFAR-10 dataset [62], where the dimension of w is d = 11173962. We set (λ, c, b0 ) = (0.00001, 5, 0.01). Fig. 3b shows a similar pattern, and the proposed scheme again achieves the best overall performance.

5

Related Works

Outsourcing computational tasks to external worker nodes has been widely studied, with federated learning as a prominent example, where a server aggregates local worker updates into a global model [63]. Robust federated learning methods protect this aggregation against adversarial behavior. Examples include Krum, coordinate-wise median, trimmed mean, Bulyan, and related robust SGD variants [12–27]. More recent methods further adapt their aggregation rules during training, for example by assigning trust weights, filtering malicious updates, or updating worker reliability scores over time [64–69]. However, all of these works operate under the honest-majority setting. In contrast, the focus of this paper is on adversary dominated settings, where |Q| ≥ |K|. This regime is especially relevant in Web 3.0 systems. Since the emergence of cryptocurrencies and smart contract platforms [70, 71], decentralized networks have been designed to operate without 9

trusted intermediaries. A central challenge in this setting is DeML, where heavy computational tasks must be offloaded to off-chain worker nodes because blockchains cannot natively support the computational scale of modern AI [8]. In such permissionless environments, these workers are anonymous and untrusted [9–11], which leads to a fundamental verification problem: how can the DC trust an outsourced computation without recomputing it? For DeML applications, a practical outsourcing framework should simultaneously provide low computational overhead, support approximate computation, fast finality, and resilience even under adversarial dominance. Existing approaches do not satisfy all of these requirements at once. Verifiable computing [72, 73] provides strong correctness by requiring cryptographic proofs, but proof generation remains expensive and slow [74–78], and it is not naturally aligned with approximate computation [78–82]. Optimistic verification [83, 84] is more efficient, but delays finality and also struggles with approximate computation. Coded computing [85–91] is fast and naturally compatible with approximate settings, but its guarantees collapse once adversaries become dominant. This limitation motivated the development of the game of coding framework [28–32], which models adversaries as rational, reward seeking agents rather than pure saboteurs. Under this perspective, the framework retains the efficiency of coding-based approaches while remaining effective even when |Q| ≥ |K|. The foundational work [28] introduced the game theoretic formulation and characterized the equilibrium behavior of the participants, showing that reliable operation is possible under adversarial dominance. Subsequent works established Sybil resilience [30], developed banditbased methods for learning system parameters when the adversary is unknown [31], and extended the equilibrium analysis to the general high dimensional setting [29]. Despite these advances, prior works on game of coding have focused on single-round computation, where the DC chooses one acceptance rule for one outsourced task. They do not address iterative settings such as multi-round optimization, where the threshold chosen in one round affects not only the current estimate but also the future optimization trajectory through Wt , the gradient norm, and the learning-rate schedule. This paper fills that gap by studying the multi-round setting, characterizing its fundamental tradeoffs, and developing an algorithm for training in adversary dominated environments.

6

Conclusion

We studied decentralized learning in adversary-dominated settings where honest-majority assumptions may not hold. By combining consistency-based acceptance with adaptive threshold selection, VISTA incentivizes workers to submit mutually reliable reports while maintaining progress in iterative optimization. Our theoretical analysis and experiments show that incentive-aware adaptation can recover the asymptotic convergence behavior of standard SGD, even when rational adversaries control a majority of workers. These results suggest that carefully designed acceptance-and-reward mechanisms offer a promising path toward robust permissionless machine learning.

7

Acknowledgment

The work of Mohammad Ali Maddah-Ali, Hanzaleh Akbari Nodehi, and Parsa Moradi has been partially supported by the National Science Foundation under Grant CCF-2348638. The work of Soheil Mohajer is supported in part by AFOSR under the grant FA9550-23-1-0057.

References [1] Muhammad Shafay, Raja Wasim Ahmad, Khaled Salah, Ibrar Yaqoob, Raja Jayaraman, and Mohammed Omar. Blockchain for deep learning: review and open challenges. Cluster Computing, 26(1):197–221, 2023. [2] Shengwen Ding and Chenhui Hu. Survey on the convergence of machine learning and blockchain. In Proceedings of SAI Intelligent Systems Conference, pages 170–189. Springer, 2022. [3] Safak Kayikci and Taghi M Khoshgoftaar. Blockchain meets machine learning: a survey. Journal of Big Data, 11(1):1–29, 2024. 10

[4] Hamed Taherdoost. Blockchain and machine learning: A critical review on security. Information, 14(5):295, 2023. [5] Hamed Taherdoost. Blockchain technology and artificial intelligence together: a critical review on applications. Applied Sciences, 12(24):12948, 2022. [6] Ruijiao Tian, Lanju Kong, Xinping Min, and Yunhao Qu. Blockchain for AI: A disruptive integration. In 2022 IEEE 25th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pages 938–943. IEEE, 2022. [7] Khaled Salah, M Habib Ur Rehman, Nishara Nizamuddin, and Ala Al-Fuqaha. Blockchain for AI: Review and open research challenges. IEEE Access, 7:10127–10149, 2019. [8] Lingchen Zhao, Qian Wang, Cong Wang, Qi Li, Chao Shen, and Bo Feng. VeriML: Enabling integrity assurances and fair payments for machine learning as a service. IEEE Transactions on Parallel and Distributed Systems, 32(10):2524–2540, 2021. [9] Jakub Sliwinski and Roger Wattenhofer. Blockchains cannot rely on honesty. In The 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020), 2019. [10] Runchao Han, Zhimei Sui, Jiangshan Yu, Joseph Liu, and Shiping Chen. Fact and fiction: Challenging the honest majority assumption of permissionless blockchains. In Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pages 817–831, 2021. [11] Joshua S Gans and Hanna Halaburda. "Zero Cost" majority attacks on permissionless blockchains. Technical report, National Bureau of Economic Research, 2023. [12] Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilient nonconvex stochastic gradient descent. arXiv preprint arXiv:2012.14368, 2020. [13] Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentums. In International Conference on Machine Learning, pages 6246–6283. PMLR, 2022. [14] Qiankun Shi, Jie Peng, Kun Yuan, Xiao Wang, and Qing Ling. Optimal complexity in byzantinerobust distributed stochastic optimization with data heterogeneity. Journal of Machine Learning Research, 26(268):1–58, 2025. [15] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning, pages 5311–5319. PMLR, 2021. [16] Rachid Guerraoui, Nirupam Gupta, and Rafael Pinot. Byzantine machine learning: A primer. ACM Computing Surveys, 56(7):1–39, 2024. [17] Banghua Zhu, Lun Wang, Qi Pang, Shuai Wang, Jiantao Jiao, Dawn Song, and Michael I Jordan. Byzantine-robust federated learning with optimal statistical rates. In International Conference on Artificial Intelligence and Statistics, pages 3151–3178. PMLR, 2023. [18] Yuchen Liu, Chen Chen, Lingjuan Lyu, Fangzhao Wu, Sai Wu, and Gang Chen. Byzantinerobust learning on heterogeneous data via gradient splitting. In International Conference on Machine Learning, pages 21404–21425. PMLR, 2023. [19] Haibo Yang, Xin Zhang, Minghong Fang, and Jia Liu. Byzantine-resilient stochastic gradient descent for distributed learning: A lipschitz-inspired coordinate-wise median approach. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5832–5837. IEEE, 2019. [20] Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Detox: A redundancy-based framework for faster and more robust gradient aggregation. Advances in Neural Information Processing Systems, 32, 2019. [21] Zhuohang Li, Luyang Liu, Jiaxin Zhang, and Jian Liu. Byzantine-robust federated learning through spatial-temporal analysis of local model updates. In 2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS), pages 372–379. IEEE, 2021. 11

[22] Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and Geovani Rizk. Robust distributed learning: Tight error bounds and breakdown point under data heterogeneity. Advances in Neural Information Processing Systems, 36:45744–45776, 2023. [23] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018. [24] El Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyên Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning). Advances in Neural Information Processing Systems, 34:25044–25057, 2021. [25] Rachid Guerraoui and Sébastien Rouault. The hidden vulnerability of distributed learning in Byzantium. In International Conference on Machine Learning, pages 3521–3530. PMLR, 2018. [26] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650–5659. PMLR, 2018. [27] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017. [28] Hanzaleh Akbari Nodehi, Viveck R. Cadambe, and Mohammad Ali Maddah-Ali. Game of coding: Beyond honest-majority assumptions. IEEE Transactions on Information Theory (submitted), 2024. URL https://arxiv.org/abs/2401.16643. [29] Hanzaleh Akbari Nodehi, Parsa Moradi, Soheil Mohajer, and Mohammad Ali Maddah-Ali. Game of coding for vector-valued computations. arXiv preprint arXiv:2602.04810, 2026. [30] Hanzaleh Akbari Nodehi, Viveck R. Cadambe, and Mohammad Ali Maddah-Ali. Game of coding: Sybil resistant decentralized machine learning with minimal trust assumption. arXiv preprint, 2024. https://arxiv.org/abs/2410.05540. [31] Hanzaleh Akbari Nodehi, Pejman Moradi, and Mohammad Ali Maddah-Ali. Game of coding with an unknown adversary. In 2025 IEEE International Symposium on Information Theory (ISIT), Ann Arbor, MI, USA, 2025. [32] Hanzaleh Akbari Nodehi, Viveck R Cadambe, and Mohammad Ali Maddah-Ali. Game of coding: Coding theory in the presence of rational adversaries, motivated by decentralized machine learning. arXiv preprint arXiv:2601.02313, 2026. [33] Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010. [34] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. [35] Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012. [36] Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv:1902.09843, 2019. [37] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018. [38] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017. [39] Daniel Morales-Brotons, Thijs Vogels, and Hadrien Hendrikx. Exponential moving average of weights in deep learning: Dynamics and benefits. arXiv preprint arXiv:2411.18704, 2024. 12

[40] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964. [41] Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning, pages 4596–4604. PMLR, 2018. [42] Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD. Advances in Neural Information Processing Systems, 32, 2019. [43] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400–407, 1951. [44] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018. [45] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011. [46] Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33:18795–18806, 2020. [47] Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.09237, 2019. [48] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1–30, 2020. [49] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International Conference on Machine Learning, pages 1139–1147. PMLR, 2013. [50] Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.06763, 2018. [51] Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by D-Adaptation. In International Conference on Machine Learning, pages 7449–7479. PMLR, 2023. [52] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. Learning in stackelberg games with non-myopic agents. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 917–918, 2022. [53] Natalie Collina, Varun Gupta, and Aaron Roth. Repeated contracting with multiple non-myopic agents: Policy regret and limited liability. arXiv preprint arXiv:2402.17108, 2024. [54] Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. Pareto-optimal algorithms for learning in games. In Proceedings of the 25th ACM Conference on Economics and Computation, 2024. [55] Marco Celentani, Drew Fudenberg, David K. Levine, and Wolfgang Pesendorfer. Maintaining a reputation against a long-lived opponent. Econometrica, 64(3):691–704, 1996. [56] Yurong Chen, Xiaotie Deng, Jiarui Gan, and Yuhao Li. Learning to manipulate a commitment optimizer. arXiv preprint arXiv:2302.11829, 2023. [57] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Springer, Boston, MA, 2004. ISBN 978-1-4020-7553-7. doi: 10.1007/978-1-4419-8853-9. [58] Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv, 2013. doi: 10.48550/arxiv.1308.6370. 13

[59] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 2002. [60] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online], 2, 2010. URL http://yann.lecun.com/exdb/mnist. [61] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016. [62] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. [63] 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, pages 1273–1282. PMLR, 2017. [64] Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. FLTrust: Byzantine-robust federated learning via trust bootstrapping. In Network and Distributed System Security Symposium, 2021. [65] Thien Duc Nguyen, Phillip Rieger, Huili Chen, Hossein Yalame, Helen Möllering, Hossein Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Sadegh Zeitouni, et al. FLAME: Taming backdoors in federated learning. In 31st USENIX Security Symposium, pages 1415–1432, 2022. [66] Xutong Mu, Ke Cheng, Yuxin Shen, Xin Li, Zhen Chang, Tao Zhang, and Xiaosong Ma. FedDMC: Efficient and robust federated learning via detecting malicious clients. IEEE Transactions on Dependable and Secure Computing, 21(6):5259–5274, 2024. [67] Siquan Huang, Yijiang Li, Chong Chen, Ying Gao, and Xiping Hu. FedID: Enhancing federated learning security through dynamic identification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47(10):8907–8922, 2025. [68] Isaac Marroqui Penalva, Enrique Tomás Martínez Beltrán, Manuel Gil Pérez, and Alberto Huertas Celdrán. RepuNet: A reputation system for mitigating malicious clients in decentralized federated learning. arXiv preprint arXiv:2506.19892, 2025. [69] Abolfazl Younesi, Leon Kiss, Zahra Najafabadi Samani, Juan Aznar Poveda, and Thomas Fahringer. FLARE: Adaptive multi-dimensional reputation for robust client reliability in federated learning. arXiv preprint arXiv:2511.14715, 2025. [70] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. [71] Vitalik Buterin et al. Ethereum white paper. GitHub repository, 1:22–23, 2013. [72] Justin Thaler. Proofs, arguments, and zero-knowledge. Foundations and Trends® in Privacy and Security, 4(2–4):117–660, 2022. [73] Boyuan Feng, Lianke Qin, Zhenfei Zhang, Yufei Ding, and Shumo Chu. ZEN: An optimizing compiler for verifiable, zero-knowledge neural network inferences. Cryptology ePrint Archive, 2021. [74] Tianyi Liu, Xiang Xie, and Yupeng Zhang. ZkCNN: Zero-knowledge proofs for convolutional neural network predictions and accuracy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 2968–2985, 2021. [75] Zhibo Xing, Zijian Zhang, Jiamou Liu, Ziang Zhang, Meng Li, Liehuang Zhu, and Giovanni Russello. Zero-knowledge proof meets machine learning in verifiability: A survey. arXiv preprint arXiv:2310.14848, 2023. [76] Payman Mohassel and Yupeng Zhang. SecureML: A system for scalable privacy-preserving machine learning. In 2017 IEEE Symposium on Security and Privacy (SP), pages 19–38. IEEE, 2017. 14

[77] Seunghwa Lee, Hankyung Ko, Jihye Kim, and Hyunok Oh. vCNN: Verifiable convolutional neural network based on zk-SNARKs. IEEE Transactions on Dependable and Secure Computing, 2024. [78] Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang. Mystique: Efficient conversions for Zero-Knowledge proofs with applications to machine learning. In 30th USENIX Security Symposium (USENIX Security 21), pages 501–518, 2021. [79] Shuo Chen, Jung Hee Cheon, Dongwoo Kim, and Daejun Park. Interactive proofs for rounding arithmetic. IEEE Access, 10:122706–122725, 2022. [80] Sanjam Garg, Abhishek Jain, Zhengzhong Jin, and Yinuo Zhang. Succinct zero-knowledge for floating point computations. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 1203–1216, 2022. [81] Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Andrew J Blumberg, and Michael Walfish. Taking Proof-Based verified computation a few steps closer to practicality. In 21st USENIX Security Symposium (USENIX Security 12), pages 253–268, 2012. [82] Sanjam Garg, Aarushi Goel, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, GuruVamsi Policharla, and Mingyuan Wang. Experimenting with zero-knowledge proofs of training. Cryptology ePrint Archive, 2023. [83] Suma Bhat, Canhui Chen, Zerui Cheng, Zhixuan Fang, Ashwin Hebbar, Sreeram Kannan, Ranvir Rana, Peiyao Sheng, Himanshu Tyagi, Pramod Viswanath, et al. Sakshi: Decentralized ai platforms. arXiv preprint arXiv:2307.16562, 2023. [84] KD Conway, Cathie So, Xiaohang Yu, and Kartin Wong. OPML: Optimistic machine learning on blockchain. arXiv preprint arXiv:2401.17555, 2024. [85] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential Coding Theory. Draft is Available, 2022. [86] Royee Yosibash and Ram Zamir. Frame codes for distributed coded computation. In 2021 11th International Symposium on Topics in Coding (ISTC), pages 1–5, 2021. [87] Ron M Roth. Analog error-correcting codes. IEEE Transactions on Information Theory, 66(7): 4075–4088, 2020. [88] Tayyebeh Jahani-Nezhad and Mohammad Ali Maddah-Ali. Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication. IEEE Transactions on Information Theory, 67(6):4185–4196, 2021. [89] Tayyebeh Jahani-Nezhad and Mohammad Ali Maddah-Ali. Berrut approximated coded computing: Straggler resistance beyond polynomial computing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):111–122, 2023. [90] Qian Yu, Mohammad Maddah-Ali, and Salman Avestimehr. Polynomial codes: an optimal design for high-dimensional coded matrix multiplication. Advances in Neural Information Processing Systems, 30, 2017. [91] Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and Salman A Avestimehr. Lagrange coded computing: Optimal design for resiliency, security, and privacy. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1215–1225. PMLR, 2019. [92] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification. In Proceedings of the IEEE International Conference on Computer Vision, pages 1026–1034, 2015. [93] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.

15

A

Proof of Theorem 1

In this section, we present the detailed proof of Theorem 1. Recall that Theorem 1 analyzes the idealized execution of VISTA, where ηt is determined using (5) instead of Line 7 of Algorithm 1. In this setting, the threshold is chosen using oracle access2 to the gradient norm ∥∇L(Wt−1 )∥22 . We analyze the convergence of VISTA for a non-convex, ℓ-smooth objective function L(w) that is bounded from below by L∗ . By the descent lemma [57], the ℓ-smoothness of L implies that ℓ L(Wt ) ≤ L(Wt−1 ) + ⟨∇L(Wt−1 ), Wt − Wt−1 ⟩ + ∥Wt − Wt−1 ∥22 . 2

(9)

According to the protocol of VISTA described in Algorithm 1, the parameter update can be compactly acc written using an indicator variable Iacc t ∈ {0, 1}. Recall that we define It = 1 if the probabilistic acceptance event At occurs at round t, and Iacc = 0 otherwise. Thus, the unified parameter update t rule can be expressed as b t. Wt = Wt−1 − Iacc Bt G (10) t

This formulation is universally applicable; if the computation is rejected (Iacc = 0), the indicat tor zeroes out the subtracting term, ensuring the parameters remain unchanged (Wt = Wt−1 ). Substituting the update step from (10) into (9) yields ℓ acc 2 b 2 b L(Wt ) ≤ L(Wt−1 ) − Iacc t Bt ⟨∇L(Wt−1 ), Gt ⟩ + It Bt ∥Gt ∥2 . 2

(11)

Recall that we defined history set Ht as the collection of the realizations of all random variables observed up to round t as Ht ≜

t [

{Yi,k }i∈V .

(12)

k=0

Based on this definition and the protocol in Algorithm 1, note that the learning rates {Bk }tk=0 are uniquely determined by the history Ht−1 . In addition, based on Line 7 of Algorithm 1, ηt is also uniquely determined by the history Ht−1 . As a consequence, the learning rate Bt and the threshold ηt are random variables that are deterministically evaluated once the history Ht−1 is realized. Therefore, when taking the expectation of (11) conditioned on Ht−1 , the learning rate Bt can be treated as a constant factor and moved outside the expectation. Moreover, conditioned on Ht−1 , the random variable Wt−1 is also deterministic. This yields to D h iE b E [L(Wt )|Ht−1 ] ≤ L(Wt−1 ) − Bt ∇L(Wt−1 ), E Iacc t Gt Ht−1 i ℓBt2 h acc b 2 E It ∥Gt ∥2 Ht−1 . + (13) 2 Tohsimplify (13),i we analyze each term individually, starting with the expectation in the cross-term b E Iacc t Gt Ht−1 . By applying the law of total expectation, we have h i h i h i acc b acc b c c b E Iacc t Gt Ht−1 = E It Gt Ht−1 , At Pr(At | Ht−1 ) + E It Gt Ht−1 , At Pr(At | Ht−1 ) h i (a) b t Ht−1 , At Pr(At | Ht−1 ) + 0 = E G (b)

= pηt ∇L(Wt−1 ),

(14)

c where (a) follows because the indicator Iacc t is equal to 1 given At and 0 given At . Step (b) follows b t | Ht−1 , At ] = ∇L(Wt−1 ) and from the from the conditional unbiasedness assumption E[G definition Pr(At | Ht−1 ) = pηt in (2). 2 Note that the oracle only needs to provide the gradient norm ∥∇L(W

2 t−1 )∥2 , not the gradient ∇L(Wt−1 ) itself. It is

worth noting that while the latter is a d-dimensional vector, its norm is a scalar.

16

i h b 2 For the third term in (13), we evaluate E Iacc t ∥Gt ∥2 Ht−1 . Note that h i b 2 E Iacc t ∥Gt ∥2 Ht−1 i h i h b t ∥2 Ht−1 , At Pr(At | Ht−1 ) + E Iacc ∥G b t ∥2 Ht−1 , Ac Pr(Ac | Ht−1 ) = E Iacc ∥ G t 2 t 2 t t i h (a) b t ∥2 Ht−1 , At pη + 0 = E ∥G 2 t  i h (b) b t | Ht−1 , At ]∥2 + E ∥G b t − E[G b t | Ht−1 , At ]∥2 Ht−1 , At pη = ∥E[G 2 2 t i  h b t − ∇L(Wt−1 )∥2 Ht−1 , At pη = ∥∇L(Wt−1 )∥22 + E ∥G 2 t

(c)

(d)

= ∥∇L(Wt−1 )∥22 + ση2t pηt ,

(15)

acc where (a) uses the fact that Iacc t = 1 given At and It = 0 otherwise, together with the definition Pr(At | Ht−1 ) = pηt in (2). Step (b) applies the decomposition E[∥X∥22 ] = ∥E[X]∥22 + E[∥X − E[X]∥22 ] to the conditional estimator. In (c), we substitute the conditional unbiasedness property b t | Ht−1 , At ] = ∇L(Wt−1 ). Finally, (d) follows directly from the conditional definition of the E[G equilibrium mean squared error ση2t in (2).

By substituting (14) and (15) into (13), we obtain
ℓBt2 pηt E [L(Wt )|Ht−1 ] ≤ L(Wt−1 ) − Bt pηt ∥∇L(Wt−1 )∥22 + ∥∇L(Wt−1 )∥22 + ση2t 2   ℓBt2 ℓBt ∥∇L(Wt−1 )∥22 + pηt ση2t . (16) = L(Wt−1 ) − Bt pηt 1 − 2 2 To further analyze the expected descend of the loss function, we need to study two disjoint cases, wherein the acceptance parameter ηt is determined differently. More precisely, we partition the rounds t ∈ {0, . . . , T } into two disjoint sets, the adaptive regime Ta = {t | ηt > ηmin } and the saturated regime Ts = {t | ηt = ηmin }, and for each of them we rearrange the bound in (16). Case 1 (t ∈ Ta ): Recall that in the idealized execution analyzed in Theorem 1, the DC computes the target variance as 2 2 2 σtarget = min{σmax , max{σmin , c∥∇L(Wt−1 )∥22 }},

(17)

and selects the threshold ηt ∈ [ηmin , ηmax ] as the smallest value such that 2 ση2t = σtarget .

(18)

Note that based on this threshold selection rule, for t ∈ Ta , we have ηt > ηmin , and hence 2 ση2t = σtarget ≤ c∥∇L(Wt−1 )∥22 .

(19)

2 2 This is due to the fact that otherwise, meaning if σtarget = σmin , we would have ηt = ηmin based on the threshold selection process, which contradicts our assumption of t ∈ Ta .

Also, note that we select the initial learning rate b0 such that b0 ≤ 1/(ℓ(1 + c)). Since Bt ≤ b0 for all t, this choice guarantees ℓBt (1 + c) 1 1− ≥ . (20) 2 2 Now, based on (16), we have   ℓBt ℓBt2 E [L(Wt )|Ht−1 ] ≤ L(Wt−1 ) − Bt pηt 1 − ∥∇L(Wt−1 )∥22 + pηt c∥∇L(Wt−1 )∥22 2 2   ℓBt (1 + c) = L(Wt−1 ) − Bt pηt 1 − ∥∇L(Wt−1 )∥22 2 (a)

(b)

≤ L(Wt−1 ) −

Bt pmin ∥∇L(Wt−1 )∥22 , 2 17

(21)

where (a) follows from substituting the upper bound of the estimation error ση2t from (19) into (16). Step (b) follows from applying the learning rate condition in (20) and utilizing the fact that the acceptance probability pηt is bounded from below by a minimum probability pmin , ensuring pηt ≥ pmin . Case 2 (t ∈ Ts ): In this case, by definition we have ηt = ηmin , and thus we have 2 ση2t = σmin .

(22)

Based on (16), we arrive at   ℓBt ℓBt2 2 E [L(Wt )|Ht−1 ] ≤ L(Wt−1 ) − Bt pηt 1 − ∥∇L(Wt−1 )∥22 + pηt σmin 2 2 (a)

ℓσ 2 Bt pmin ∥∇L(Wt−1 )∥22 + min pηt Bt2 , 2 2 where (a) follows from (22). Step (b) follows from the fact that, based on (20), we have (b)

≤ L(Wt−1 ) −

(23)

ℓBt ℓBt (1 + c) 1 ≥1− ≥ , (24) 2 2 2 and the acceptance probability pηt is bounded from below by a minimum probability pmin , ensuring pηt ≥ pmin . 1−

Unified Bound: Using the indicator function Isat t to distinguish the event that round t is accepted in the saturated regime, we can aggregate (21) and (23) into a single inequality for all t, and obtain E [L(Wt )|Ht−1 ] ≤ L(Wt−1 ) −

  Bt pmin ℓσ 2 ∥∇L(Wt−1 )∥22 + min Bt2 E Isat t Ht−1 . 2 2

(25)

Indeed, if t ∈ Ta , then ηt > ηmin and E[Isat t | Ht−1 ] = 0. If t ∈ Ts , then ηt = ηmin and E[Isat t | Ht−1 ] = Pr(At | Ht−1 ) = pηt , which matches the last term in (23). Equation (25) provides a unified descent step; in the adaptive regime, the error term vanishes due to the dynamic variance control, while in the saturated regime, the descent is subject to the constant 2 variance σmin . We rearrange (25) to get   Bt pmin ℓσ 2 ∥∇L(Wt−1 )∥22 ≤ L(Wt−1 ) − E [L(Wt )|Ht−1 ] + min Bt2 E Isat t Ht−1 . 2 2

(26)

Next, we take the expectation of both sides of (26) with respect to all the randomness in Ht−1 . Since Bt is Ht−1 -measurable, this yields     pmin  ℓσ 2 E Bt ∥∇L(Wt−1 )∥22 ≤ E[L(Wt−1 )] − EHt−1 [E [L(Wt )|Ht−1 ]] + min E Bt2 E Isat t Ht−1 2 2 2  sat 2  ℓσmin (a) E It Bt , (27) = E[L(Wt−1 )] − E[L(Wt )] + 2 where (a) follows from the law of total expectation and the fact that Bt is Ht−1 -measurable. Summing up (27) for t = 0 to T , we obtain T T T  X pmin X  ℓσ 2 X  sat 2  E Bt ∥∇L(Wt−1 )∥22 ≤ (E[L(Wt−1 )] − E[L(Wt )]) + min E It Bt . (28) 2 t=0 2 t=0 t=0

Next, we evaluate the two sums on the right side of (28). Note that the initial state W−1 is deterministic, and hence, E[L(W−1 )] = L(W−1 ). Using the assumption that L is bounded from below by L∗ , we have T X

(E[L(Wt−1 )] − E[L(Wt )]) = L(W−1 ) − E[L(WT )] ≤ L(W−1 ) − L∗ .

(29)

t=0

  ℓσ 2 PT 2 For the second sum 2min t=0 E Isat t Bt , we use the update rule of the decay counter described in sat acc VISTA (Algorithm 1). Recall that Isat t is an indicator where It = 1 if round t was accepted (It = 1) and the system was in the saturated regime (ηt = ηmin ), and 0 otherwise. Furthermore, recall that 18

Pt the decay counter at round t is defined as τt = k=0 Isat k , and the learning rate is determined by Bt = √ b0 , with the initial value of τ−1 = 0. τt−1 +1

Due to these definitions, the counter increments and the learning rate decays in iteration t only when PT sat Isat t−1 = 1, and otherwise we have τt−1 = τt−2 and hence Bt = Bt−1 . Let S = τT = t=0 It denote the total number of saturated rounds up to iteration T , and note that S ≤ T + 1. While Bt is 2 sat random, and may decay (when Isat = 1) or remain constant (when Isat t−1 = 0), the product Bt It 2 t−1  b0 takes each value of √k+1 for k = 0, . . . , S − 1, exactly once. Therefore, the only remaining randomness in the second summation is due to S, which can deterministically upper-bounded by S ≤ T + 1. Therefore, the sum of the squared learning rates over these rounds exactly forms a harmonic series, which is bounded by ! T S S X X X 1 1 2 sat 2 2 It Bt = b0 = b0 1 + k k t=0 k=1 k=2 ! S Z k X (a) 1 ≤ b20 1 + dx x k=2 k−1 ! Z S 1 dx = b20 1 + 1 x = b20 (1 + ln S) ≤ b20 (1 + ln(T + 1)),

(30)

where (a) follows because f (x) = 1/x is monotonically decreasing for x > 0, ensuring that for every integer k ≥ 2 we have Z k 1 1 ≤ dx. (31) k x k−1 Substituting (29) and the expectation of the bounded sum from (30) into (28) yields T  pmin X  ℓσ 2 b2 E Bt ∥∇L(Wt−1 )∥22 ≤ (L(W−1 ) − L∗ ) + min 0 (1 + ln(T + 1)). 2 t=0 2

(32)

To establish the final convergence rate, we use the property that the minimum value of a nonnegative sequence is always bounded above by any deterministic weighted average of that sequence. According to Algorithm 1, the decay in the learning rate only occurs when an update is accepted in the saturated regime; otherwise, the learning rate does not change. √ Since the decay counter increments at most once per round, we have the lower bound Bt ≥ b0 / t + 1 for all t ∈ {0, . . . , T }. Therefore, since ∥∇L(Wt−1 )∥22 is nonnegative, we have T T X X     1 √ E Bt ∥∇L(Wt−1 )∥22 ≥ b0 E ∥∇L(Wt−1 )∥22 t+1 t=0 t=0   X T   1 √ ≥ min E ∥∇L(Wt−1 )∥22 b0 . 0≤t≤T t +1 t=0

(33)

Next, we lower bound the deterministic weight sum. Note that b0

T X t=0

√

T Z t+1 X (a) 1 1 √ ≥ b0 dx t+1 x+1 t=0 t Z T +1 1 √ = b0 dx x+1 0 √ = 2b0 ( T + 2 − 1),

19

(34)

(a)

(b)

Figure 5: Equilibrium characterization for the three-dimensional experiment in Section 4. The adversarial utility is UAD = log(MSE) + 0.03 log(PA). Using the results of [29], we characterize the equilibrium values of pη and ση2 for each η ∈ [ηmin , ηmax ], where ηmin = 2 and ηmax = 240. Subfigure (a) shows the equilibrium acceptance probability pη , and subfigure (b) shows the corresponding equilibrium mean squared error ση2 . √ where (a) follows because f (x) = 1/ x + 1 is monotonically decreasing on [0, ∞), ensuring that for every integer t ≥ 0 we have Z t+1 1 1 √ √ ≥ dx. (35) t+1 x +1 t Combining (33) and (34), we obtain   PT   E Bt ∥∇L(Wt−1 )∥22 √ min E ∥∇L(Wt−1 )∥22 ≤ t=0 . (36) 0≤t≤T 2b0 ( T + 2 − 1) Therefore, substituting the upper bound of the sum from (32) into (36), we obtain the final convergence rate 2   2(L(W−1 ) − L∗ ) + ℓσmin b20 (1 + ln(T + 1)) √ min E ∥∇L(Wt−1 )∥22 ≤ . (37) 0≤t≤T 2pmin b0 ( T + 2 − 1) √ √ As T → ∞, the denominator 2pmin b0 ( T + 2 − 1) grows as Θ( T ) and the numerator grows as Θ(ln T ). Factoring out the leading terms and constants from (37), we obtain the final asymptotic upper bound     ln T min E ∥∇L(Wt−1 )∥22 ≤ O √ . (38) 0≤t≤T T

B

Experimental Details

In this section, we provide additional details for the experiments in Section 4. We also include a onedimensional experiment with n = 10 agents to illustrate a setting with more than two participating nodes. Throughout the experiments, we use prior game-of-coding results to obtain the equilibrium acceptance probability pη , the equilibrium mean squared error ση2 , the estimator est(·), and the adversarial noise strategy for each value of η. These quantities are not derived in this paper; rather, they are taken from the corresponding game-of-coding characterizations in the prior literature [28–32]. For instance, for d = 3, the evolution of pη and ση2 as functions of η are reported in Fig. 5. These functions are derived based on the work of [32] for the specific utility function UAD = log(MSE) + 0.03 log(PA), which is used for the three-dimensional experiment reported in Section 4. Note that in [32], it has been proved that the behavior of pη and ση2 depend on the dimension and adversary’s utility function, but not the objective function to be optimized. Nevertheless, characterizing the equilibrium noise strategy and the associated estimator is a separate game-theoretic problem and is beyond the scope of this paper. For scalar computations (d = 1), the general multi-node case has been characterized in prior gameof-coding works [28, 30]. For vector-valued computations (d > 1), the two-node case, consisting of 20

Figure 6: Convergence in the one-dimensional case. Larger values of η improve early progress but worsen final accuracy, while the proposed scheme achieves the best performance.

one honest node and one adversarial node, has been characterized in [29]. This is the vector-valued setting used in our experiments in Section 4. The general vector-valued case with more than two nodes remains open; once the corresponding equilibrium curve and estimator are available, VISTA can be applied to that setting without any changes. In particular, for each value of η, we use the equilibrium noise strategy and the corresponding equilibrium estimator induced by the cited game-of-coding characterization, and then use this estimator as est(·) inside VISTA. Thus, the contribution of this paper is not to solve the underlying single-round game again, but to show how the resulting equilibrium quantities can be used to design an adaptive threshold and learning-rate schedule for multi-round optimization. As mentioned earlier, we consider the complete-information setting in which this equilibrium curve is available. When the adversary model or utility is unknown, the same direction can be combined with the learning-based techniques in [31, 32], which we leave for future work. Consider a one-dimensional example, where L(w) = 10w sin(w/10), n = 10 agents, and up to 9 adversarial nodes. The adversarial utility is UAD = log(MSE) + 0.1 log(PA), and we set (c, b0 ) = (1, 0.1). We repeat the experiment over 500 independent runs and report the average performance. Fig. 6 shows a clear tortoise and hare effect. Smaller constant values of η are more conservative and therefore slower initially, while larger values of η descend faster at the beginning but eventually suffer from a higher error floor due to larger adversarial distortion. The proposed scheme, shown by the purple curve, combines the benefits of both behaviors by descending quickly at the beginning and achieving the best final performance. The corresponding evolution of ηt is shown in Fig. 7a. Table 1 summarizes the main implementation details used in the experiments in Section 4, together with the one-dimensional experiment reported in this appendix. For all experiments, we set ∆ = 1, ηmin = 2, and, similar to Adam [34], we set β = 0.9. The initial threshold is chosen as η0 = (ηmin + ηmax )/2. The value of ηmax is selected separately for each experiment so that the acceptance-probability range of (0, 1] is properly covered. In all experiments, we instantiate the honest noise by drawing it uniformly from the d-dimensional Euclidean ball of radius ∆. For the adversarial noise, we use the corresponding game-of-coding equilibrium construction. In the one-dimensional experiment, we use the scalar game-of-coding procedures [28, 30], where the equilibrium and adversarial noise strategy are characterized through their Algorithm 1 and Algorithm 2. For the three-dimensional and deep-learning experiments, we use the vector-valued game-of-coding procedure [29], where Algorithm 1 characterizes the equilibrium for each value of η and Algorithm 2 constructs the corresponding adversarial noise strategy. The adversarial utilities in Table 1 follow the same logarithmic form studied in prior game-of-coding works. The coefficient multiplying log(PA) controls the relative importance of acceptance probability compared with estimation error. Since the scale of MSE and the sensitivity of PA depend on the 21

dimension, objective, and noise geometry, this coefficient is chosen so that the induced game exhibits a meaningful tradeoff between acceptance probability and estimation error over the selected range of η. It is worth emphasizing that the proposed algorithm VISTA, is not restricted to this logarithmic utility form. For the deterministic synthetic experiments, we initialize the one-dimensional experiment at w−1 = 40 and the three-dimensional experiment at w−1 = (10, 20, 30). For the neural-network experiments, we initialize the model parameters using Kaiming initialization [92]. The batch size is 128 for both LeNet on MNIST and ResNet-18 on CIFAR-10. Table 1: Implementation details for the experiments in Section 4. In all experiments, ∆ = 1, ηmin = 2, η0 = (ηmin + ηmax )/2, and β = 0.9. Experiment 1D synthetic 3D synthetic LeNet on MNIST ResNet-18 on CIFAR-10

d

T

# runs

ηmax

η0

b0

c

Utility

Batch size

Initialization

1 3 23942 11173962

2000 10000 5000 5000

500 12000 16 16

60 240 24 80

31 121 13 41

0.1 0.1 0.25 0.01

1 1 15 5

log(MSE) + 0.1 log(PA) log(MSE) + 0.03 log(PA) log(MSE) + 0.0003 log(PA) log(MSE) + 0.00001 log(PA)

N/A N/A 128 128

w−1 = 40 w−1 = (10, 20, 30) Kaiming [92] Kaiming [92]

For each experiment, we run VISTA for T rounds and repeat the experiment over the number of independent runs reported in Table 1. The performance curves for the one-dimensional, threedimensional, LeNet, and ResNet-18 experiments are shown in Figs. 6, 3a, 4, and 3b, respectively. Whenever multiple independent runs are used, the reported curve is the average over those runs. In figures with shaded regions, the shaded area represents standard deviation across independent runs. The corresponding evolution of the adaptive threshold ηt is reported in Fig. 7 and 8. All experiments are implemented in PyTorch [93] and conducted on a single machine with an NVIDIA RTX 5090 GPU. The synthetic experiments, including all fixed-threshold baselines for each setting, take approximately 30 minutes per experimental setting. The LeNet and ResNet-18 experiments are run for T = 5000 rounds over 16 independent runs, and each of these neural-network experiments takes approximately 6 hours on the same machine.

(a)

(b)

Figure 7: Dynamic evolution of the acceptance threshold ηt across the experiments. (a) One-dimensional experiment. (b) Three-dimensional experiment. In both cases, the proposed scheme adapts ηt over time, starting from a larger value and gradually tightening the acceptance rule.

C

Sensitivity to the Hyperparameter c

In this section, we study the role of the hyperparameter c in VISTA. Recall that in Line 7 of Algorithm 1, the threshold for the next round is selected through 2 2 e t ∥2 }}}. ηt+1 = inf{η ∈ [ηmin , ηmax ] : MSE(gη∗ , η) = min{σmax , max{σmin , c∥G 2

(39)

Thus, c controls how much estimation error the DC is willing to tolerate relative to the current gradient-signal proxy. A smaller value of c imposes a stricter variance target, which leads to a smaller acceptance threshold and more accurate accepted updates, but it can also push the algorithm more quickly toward the saturated regime ηt = ηmin , where updates are accepted less frequently. In contrast, a larger value of c permits a larger variance target, which allows a larger threshold, increases the probability of acceptance, and keeps the algorithm in the adaptive regime for longer. Hence, c acts 22

(a)

(b)

Figure 8: Dynamic evolution of the acceptance threshold ηt across the experiments. (a) LeNet on MNIST. (b) ResNet-18 on CIFAR-10. In both cases, the proposed scheme adapts ηt over time, starting from a larger value and gradually tightening the acceptance rule.

as a signal-to-noise tolerance parameter: smaller values are more conservative, while larger values are more aggressive. Figures 9 and 10 demonstrates the robustness of VISTA to the value of the hyperparameter c in a wide range. In the one-dimensional experiment, the choices c = 0.1, c = 1, and c = 10 all achieve strong convergence, although they induce different threshold trajectories. In contrast, c = 0.01 offers a very slow convergence, even slower than the fixed choice of η = 35. This is due to the fact that, at 2 e t ∥2 , and hence, η will be set to ηmin very very early iterations of the algorithm, we have σmin > c∥G 2 early, leading to very infrequent acceptance of computations. In the acceptable range of c, the smaller value c = 0.1 tightens the acceptance rule more quickly, while the larger value c = 10 keeps ηt large for longer before gradually reducing it. As can be seen from the figure, any choice of c in the range of 0.1-10 leads a fast convergence. In the ResNet-18 experiment on CIFAR-10, increasing c from 1 to 5 and 15 improves performance in this setting, because the larger tolerance allows the algorithm to remain in the adaptive regime for more iterations and make faster progress before tightening the acceptance rule. These results suggest that c can be selected by a simple calibration procedure rather than by an exhaustive search. One practical approach is to perform a small logarithmic sweep over candidate values and choose a value that produces a stable threshold trajectory: ηt should be large enough at the beginning to permit frequent progress, but should decrease over time as the optimization approaches a stationary region. Equivalently, one can monitor ηt and the acceptance frequency during a short pilot run. If ηt reaches ηmin too early, then c is likely too small; if ηt remains large for too long and the loss or gradient norm plateaus at a high error floor, then c is likely too large. An adaptive choice of c is a natural extension and is left for future work. Overall, c provides a flexible mechanism for controlling the tradeoff between update frequency and update quality. The ablation results show that VISTA remains effective across a meaningful range of values of c.

23

(a) One-dimensional synthetic.

(b) ResNet-18 on CIFAR-10

Figure 9: Sensitivity of VISTA to the hyperparameter c. (a) Mean squared gradient in the one-dimensional experiment. Several values of c achieve strong convergence, showing that the method is not sensitive to a single value. (b) Training loss for ResNet-18 on CIFAR-10. Larger values of c improve performance in this high-dimensional setting by keeping the algorithm in the adaptive regime for longer.

(a) One-dimensional synthetic.

(b) ResNet-18 on CIFAR-10

Figure 10: Evolution of the acceptance threshold ηt for different values of c. (a) In the one-dimensional experiment, smaller c values reduce ηt more aggressively, while larger values keep the algorithm adaptive for longer. (b) In the ResNet-18 experiment, increasing c leads to larger thresholds during the early phase, which enables more frequent accepted updates before the threshold is gradually tightened.

24