Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates

Anik Kumar Paul, Nibedita Roy, Nagesh Talagani, Swetha Ganesh, Gugan Thoppe, Alexandre Reiffers-Masson · 2026

Read Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates by Anik Kumar Paul, Nibedita Roy, Nagesh Talagani, Swetha Ganesh, Gugan Thoppe, Alexandre Reiffers-Masson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-09337.txt.

Introduction

Paul and five colleagues propose FAR-SIGN, a method for learning that resists adversaries in parameter-server-worker systems. It updates along carefully designed directions using only signs, and a two-timescale mechanism offsets the bias that sign updates introduce. The method admits both first-order and zeroth-order versions and runs fully asynchronously, with no private reference dataset needed at the server.

The authors prove convergence to stationary points with probability one for smooth, nonconvex objectives. They also prove a near-optimal rate for first-order use and the standard rate for zeroth-order use, with iteration count driving both. Experiments on MNIST show FAR-SIGN beating robust aggregation methods on both accuracy and wall-clock time.

Catalog record

CREATORAnik Kumar Paul, Nibedita Roy, Nagesh Talagani, Swetha Ganesh, Gugan Thoppe, Alexandre Reiffers-Masson
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.09337

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates Anik Kumar Paul, Nibedita Roy, Nagesh Talagani, Swetha Ganesh, Gugan Thoppe, Alexandre Reiffers-Masson Abstract We propose FAR-SIGN (Fully Asynchronous Robust optimization via SIGNed directional projections) for adversary-resilient learning in parameter-server–worker systems. FAR-SIGN achieves robustness through sign-based updates along carefully designed directions and mitigates the resulting bias via a two-timescale mechanism. It admits both first-order and zeroth-order implementations and enables fully asynchronous execution without requiring a private reference dataset at the server. We establish almost-sure convergence of FAR-SIGN to the set of stationary points for smooth, nonconvex objectives. Moreover, we prove the near-optimal rate of O ( n − 1 / 4 + ϵ ) O(n^{-1/4+\epsilon}) in the first-order setting and the standard O ( n − 1 / 6 + ϵ ) O(n^{-1/6+\epsilon}) in the zeroth-order setting, where n n is the iteration count and ϵ > 0 \epsilon>0 can be chosen arbitrarily small. Experiments on MNIST show that FAR-SIGN outperforms robust aggregation-based methods in both accuracy and wall-clock time. 1 Introduction Modern machine learning systems increasingly rely on distributed data and worker-side computation to solve large-scale optimization problems ( 8 ) . By leveraging multiple worker machines to process data and provide gradient or function-value feedback, such systems enable scalability well beyond what a single processor can achieve ( 24 ; 30 ) . This distributed computational model, however, introduces significant challenges in robustness and reliability. Worker nodes may fail due to hardware faults, stalled computations, or unreliable communication. Alternatively, they may behave adversarially, deliberately transmitting corrupted information to degrade system performance ( 26 ) . Addressing such failures and adversarial behavior is therefore pivotal for reliable large-scale learning. A large literature has studied robust learning in parameter-server–worker architectures with adversarial or faulty workers ( 1 ; 9 ; 37 ; 13 ; 14 ; 12 ; 32 ; 36 ; 34 ; 17 ; 11 ; 21 ; 22 ; 7 ; 16 ) . Existing methods can be broadly categorized by the degree of synchronization required before the server updates. Most works consider synchronous round-based methods, where the server broadcasts its current iterate and waits for sufficiently many workers to return first- or zeroth-order gradient estimates computed at that iterate. Adversary-robustness is then enforced through redundancy-based techniques such as data encoding and error correction, or through server-side robust aggregation rules ( 1 ; 7 ; 9 ; 13 ; 14 ; 12 ; 37 ; 32 ; 22 ; 16 ) . While effective, such methods rely on coordinated worker participation and can be sensitive to heterogeneous computation times, communication delays, and stragglers. Table 1: Comparison with first-order methods . All methods achieve the optimal O(n^{-1/4}) rate, but FAR-SIGN is the only one achieving it while being adversary-robust and fully asynchronous. Legend: RA = robust aggregation; B = buffered; EF= error feedback; FDS = fixed dictionary sampling. \checkmark^{\dagger} = worker-side asynchrony only: server waits for multiple updates before aggregation. Method Fully asynchronous Adversary resilience Optimal O(n^{-1/4}) rate Technique Reference ( 20 ) ✗ ✗ ✓ SGD Thm. 2.1 ( 1 ) ✗ ✓ ✓ RA Thm. 3.2 ( 36 ) \checkmark^{\dagger} ✓ ✓ B-RA Thm. 2 ( 5 ) ✗ ✓ ✓ SignSGD Thm. 1 ( 23 ) ✗ ✗ ✓ EF-SignSGD Thm. II FAR-SIGN (ours) ✓ ✓ ✓ FDS-SignSGD Thm. 6 Adversary-robust asynchronous learning has therefore attracted increasing attention. In first-order settings, existing approaches either screen incoming updates using empirical Lipschitz-type tests or server-side reference data ( 11 ; 34 ; 17 ) , or buffer asynchronous updates before applying robust aggregation ( 36 ) . However, these methods either guarantee convergence only to a neighborhood of a stationary point ( 11 ) , rely on server-side reference data for update validation, or reintroduce server-side buffering, thereby limiting the utility, scalability, or responsiveness benefits of full asynchrony. By contrast, asynchronous adversary-robust zeroth-order optimization remains unexplored. Our work addresses the above limitations and its key highlights are as follows: 1. Fully asynchronous algorithmic framework : We propose FAR-SIGN, a signed directional projection method for adversary-resilient optimization with both first- and zeroth-order implementations. It updates upon individual worker estimate arrivals, requiring neither server-side reference data nor buffering. It is the first such fully asynchronous adversary-resilient method. 2. Almost-sure convergence : Using a two-timescale stochastic recursive inclusion framework, we prove boundedness and almost-sure convergence of FAR-SIGN to the set of stationary points for smooth, potentially nonconvex objectives under standard zero-mean, bounded-variance noise. Our two-timescale approach avoids the symmetry or unimodality assumptions often used to control sign bias in sign-SGD analyses ( 4 ) . 3. Convergence rates : FAR-SIGN achieves rates of O(n^{-1/4+\epsilon}) and O(n^{-1/6+\epsilon}) in the first- and zeroth-order regimes, respectively. These match the best known rates up to the \epsilon -slack, even without adversaries ( 2 ; 25 ) . With coupled noise, the zeroth-order rate improves to O(n^{-1/2+\epsilon}) . Tables 1 , 2 compare our results with existing work. 4. Empirical validation : On illustrative MNIST ( 27 ) simulations where the data is split near-homogeneously across workers, with 24\% Byzantine workers, FAR-SIGN’s non-buffered nature enables it to reach 80\% accuracy in 11 – 37 s across attacks, whereas the fastest robust-aggregation baseline requires 223 – 420 s. FAR-SIGN also achieves comparable or better final accuracy, attaining 89.6\% without attack and 89.0\% under constant attack, while several baselines fail under Gaussian or constant attacks. Table 2: Comparison with zeroth-order methods . While existing methods also achieve standard zeroth-order rates, FAR-SIGN is the only one achieving them while supporting both fully asynchronous execution and adversary resilience. Legend: DN = decoupled noise, CN = coupled noise, FDS = fixed dictionary sampling, and RDS = random direction sampling. Prior work Fully asynchronous Adversary resilience Convergence rate Technique Reference DN CN ( 20 ) ✗ ✗ – O(n^{-1/4}) SGD Thm. 3.2 ( 28 ) ✓ ✗ – O(n^{-1/4}) SGD Cor. 5 ( 28 ) ✓ ✗ – O(n^{-1/2}) FDS-SGD Cor. 5 ( 29 ) ✗ ✗ – O(n^{-1/4}) RDS-SignSGD Cor. 3 ( 6 ) ✗ ✗ O(n^{-1/6}) O(n^{-1/4}) SGD Thm. 1, 2 ( 16 ) ✗ ✓ – O(n^{-1/4}) SGD Thm. 5.7 FAR-SIGN (ours) ✓ ✓ \mathbf{\emph{O}(n^{-1/6})} \mathbf{\emph{O}(n^{-1/2})} FDS-SignSGD Thm. 8 2 Problem Setup, Proposed R-SIGN Algorithm, and Main Results We now introduce our distributed-feedback setting and FAR-SIGN, our fully asynchronous algorithm for adversary-resilient learning in this setting. Using two-timescale averaging and a directional robustness condition, we prove almost-sure convergence and nonasymptotic rates that closely match the standard first- and zeroth-order benchmarks. 2.1 Problem Setup We aim to minimize a smooth, possibly nonconvex objective f:\mathbb{R}^{d}\to\mathbb{R} in a parameter-server architecture with N workers. The server does not observe gradients or function values directly; instead, it obtains directional feedback from workers, where a fixed but unknown subset \mathcal{A}\subseteq[N] may be adversarial. Specifically, at each interaction, the server sends a point x\in\mathbb{R}^{d} and a direction a to a worker. Honest workers return directional derivative information, while adversarial workers may return arbitrary values. We study two honest-worker feedback models. In the first-order setting, an honest worker returns a^{\top}\widetilde{\nabla}f(x) , where \widetilde{\nabla}f(x) is a stochastic gradient sample. In the zeroth-order setting, an honest worker does not access gradients and instead returns the two-point finite-difference estimate [\hat{f}(x+\lambda a)-\hat{f}(x-\lambda

Read the complete text