Parameter-free Regret in High Probability with Heavy Tails

2022/10/25 by Jiujia Zhang, Zhang, Jiujia, Ashok Cutkosky +1 · 6 citations
Decision Sciences · Engineering · Computer Science · #Advanced Bandit Algorithms Research #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2210.14355

Abstract

We present new algorithms for online convex optimization over unbounded domains that obtain parameter-free regret in high-probability given access only to potentially heavy-tailed subgradient estimates. Previous work in unbounded domains considers only in-expectation results for sub-exponential subgradients. Unlike in the bounded domain case, we cannot rely on straight-forward martingale concentration due to exponentially large iterates produced by the algorithm. We develop new regularization techniques to overcome these problems. Overall, with probability at most δ, for all comparators u our algorithm achieves regret O(‖ u ‖ T^1/\mathfrakp log (1/δ)) for subgradients with bounded \mathfrakp^th moments for some \mathfrakp ∈ (1, 2].

Cited by

• Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
• The Convergence Behavior of Adam under Heavy-Tailed Noise
• Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications
• Can SGD Handle Heavy-Tailed Noise?
• Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises

Related

• Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
• Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications
• Parameter-Free Online Convex Optimization with Sub-Exponential Noise
• Improved Regret Bounds for Projection-free Bandit Convex Optimization
• Efficient online algorithms for fast-rate regret bounds under sparsity