2025/06/15 by Jiujia Zhang, Zhang, Jiujia, Ashok Cutkosky +1 · 2 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Advanced Wireless Network Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2506.12781
openalex publication_date 2025/06/15 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
This paper addresses online learning with ``corrupted'' feedback. Our learner is provided with potentially corrupted gradients gt instead of the ``true'' gradients gt. We make no assumptions about how the corruptions arise: they could be the result of outliers, mislabeled data, or even malicious interference. We focus on the difficult ``unconstrained'' setting in which our algorithm must maintain low regret with respect to any comparison point u ∈ ℝd. The unconstrained setting is significantly more challenging as existing algorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our algorithms guarantee regret ‖u‖G (√(T) + k) when G ≥ maxt ‖gt‖ is known, where k is a measure of the total amount of corruption. When G is unknown we incur an extra additive penalty of (‖u‖2+G2) k.