# Subgradient Methods for Nonsmooth Convex Functions with Adversarial Errors

arXiv: https://arxiv.org/abs/2510.03072 · HTML: https://mlsanity.com/paper/2510.03072/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2025.

## Built on by (most cited first, 1 of 1)

- [A stochastic subgradient method with optimal failure exponent](https://mlsanity.com/paper/2609.37425/) (2026)

## Abstract (arXiv)

We consider minimizing nonsmooth convex functions with bounded subgradients. However, instead of directly observing a subgradient at every step k∈ [0, dots, N-1], we assume that the optimizer receives an adversarially corrupted subgradient. The adversary's power is limited to a finite corruption budget, but allows the adversary to strategically time its perturbations. We show that the classical averaged subgradient descent method, which is optimal in the noiseless case, has worst-case performance that deteriorates quadratically with the corruption budget. Using performance optimization programming, (i) we construct and analyze the performance of three novel subgradient descent methods, and (ii) propose a novel lower bound on the worst-case suboptimality gap of any first-order method satisfying a mild cone condition proposed by Fatkhullin et al. (2025). The worst-case performance of each of our methods degrades only linearly with the corruption budget. Furthermore, we show that the relative difference between their worst-case suboptimality gap and our lower bound decays as mathcal O(log(N)/N), so that all three proposed subgradient descent methods are near-optimal. Our methods achieve such near-optimal performance without a need for momentum or averaging. This suggests that these techniques are not necessary in this context, which is in line with recent results by Zamani and Glineur (2025).