7 papers
Towards Fully Parameter-Free Stochastic Optimization: Grid Search with Self-Bounding Analysis
Yuheng Zhao, Yu-Hu Yan, Amit Attia +3
Parameter-free stochastic optimization aims to design algorithms that are agnostic to the underlying problem parameters while still achieving convergence rates competitive with opt…
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1
We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation $V_T(u) = \sum_{t=2}^T \|\nabla f_t(u)-\nabla f…
A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization
Yi-Han Wang, Peng Zhao, Zhi-Hua Zhou
Online eXp-concave Optimization (OXO) is a fundamental problem in online learning, where the goal is to minimize regret when loss functions are exponentially concave. The standard…
Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
Hang Yu, Yu-Hu Yan, Peng Zhao
Gradient-variation online learning has drawn increasing attention due to its deep connections to game theory, optimization, etc. It has been studied extensively in the full-informa…
Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization
Peng Zhao, Yu-Hu Yan, Hang Yu +1
Universal online learning aims to achieve optimal regret guarantees without requiring prior knowledge of the curvature of online functions. Existing methods have established minima…
Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
In this work, we study offline convex optimization with smooth objectives, where the classical Nesterov's Accelerated Gradient (NAG) method achieves the optimal accelerated converg…