Subgradient Methods for Nonsmooth Convex Functionswith Adversarial Errors
ACM SIGMETRICS Performance Evaluation Review · 31.03.2026 · 53 (4) · 109-110
DOI: 10.1145/3797823.3797856 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 31.03.2026. Verfasst von Martijn Gösgens und 1 weiteren Autor:innen. Die Arbeit nennt 9 Literaturangaben.
Abstract (Originalsprache)
We consider minimizing nonsmooth convex functions with bounded subgradients. However, instead of directly observing a subgradient at every step, the optimizer receives an adversarially corrupted subgradient. The adversary's power is limited to a finite corruption budget, with which the adversary can strategically time their perturbations. We show that the 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 [5]. The worst-case performance of each of our methods degrades only linearly with the corruption budget. Furthermore, we prove that all three proposed subgradient descent methods are nearoptimal and suffer a worst-case suboptimality gap which asymptotically matches our lower bound. Our subgradient descent methods achieve near-optimal performance without needing momentum nor averaging. This suggests that these techniques are not necessary in this context, which is in line with recent results by [9].
Zitieren
APA
Gösgens, M., & Parys, B. P. V. (2026). Subgradient Methods for Nonsmooth Convex Functionswith Adversarial Errors. ACM SIGMETRICS Performance Evaluation Review, 53(4), 109-110. https://doi.org/10.1145/3797823.3797856
Vancouver
Gösgens M, Parys BPV. Subgradient Methods for Nonsmooth Convex Functionswith Adversarial Errors. ACM SIGMETRICS Performance Evaluation Review. 2026;53(4):109-110. doi:10.1145/3797823.3797856
BibTeX
@article{Gsgens2026,
author = {Gösgens, Martijn and Parys, Bart P.G. Van},
title = {Subgradient Methods for Nonsmooth Convex Functionswith Adversarial Errors},
journal = {ACM SIGMETRICS Performance Evaluation Review},
year = {2026},
volume = {53},
number = {4},
pages = {109--110},
doi = {10.1145/3797823.3797856}
}
EUVIMED