2025/05/26 by Paul Liautaud, Pierre Gaillard, Liautaud, Paul +3
Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2505.19741
openalex publication_date 2025/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study online adversarial regression with convex losses against a rich class of continuous yet highly irregular prediction rules, modeled by Besov spaces B_pqs with general parameters 1 ≤ p,q ≤ ∞ and smoothness s > \tfracdp. We introduce an adaptive wavelet-based algorithm that performs sequential prediction without prior knowledge of (s,p,q), and establish minimax-optimal regret bounds against any comparator in B_pqs. We further design a locally adaptive extension capable of dynamically tracking spatially inhomogeneous smoothness. This adaptive mechanism adjusts the resolution of the predictions over both time and space, yielding refined regret bounds in terms of local regularity. Consequently, in heterogeneous environments, our adaptive guarantees can significantly surpass those obtained by standard global methods.