LASA: Byzantine-Robust Decentralized Optimization via Local-Loss Aware Weighting

A key challenge in Byzantine-robust decentralized learning is to mitigate the adverse effects of Byzantine updates while preserving beneficial information exchange. To this end, we introduce aggregation budgets that provide loss-based control of Byzantine influence by bounding the weighted excess local loss relative to the self-candidate. We then propose a novel Local-Loss Aware Softmax Aggregator (LASA) with explicit aggregation budgets. Based on local-loss evaluations, LASA assigns positive weights to all candidates without prior Byzantine information, balancing robustness with opportunities for useful cooperation. For LASA and any other aggregator admitting such budgets, we establish global stationarity bounds for smooth convex objectives under a relative gradient heterogeneity condition without assuming an honest majority, and obtain sharper guarantees under an additional quadratic growth condition. We further provide sufficient conditions under which LASA admits a strictly tighter stationarity bound than self-only training. Experiments on MNIST and CIFAR-10 demonstrate the effectiveness of LASA across several communication graphs and Byzantine attacks.