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…
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 and optimization. It has been studied extensively in the full-informati…
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…
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…
Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
Yuheng Zhao, Yu-Hu Yan, Kfir Yehuda Levy +1
Smoothness is known to be crucial for acceleration in offline optimization, and for gradient-variation regret minimization in online learning. Interestingly, these two problems are…