EUVIMEDEUVIMED entdecken
Crossref

Subgradient Methods for Nonsmooth Convex Functionswith Adversarial Errors

Martijn Gösgens, Bart P.G. Van Parys

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →