Skip to content
conftrace_
2016 COLT COLT 2016

Open Problem: Second order regret bounds based on scaling time

Abstract

We argue that the second order bounds given in Cesa-Bianchi2006, which accumulate the square of the loss of each action separately, are loose. We propose a different form of a second order bound and conjecture the it is satisfied by NormalHedge ChaudhuriFrHs2009.

Authors

Yoav Freund

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Theory

Keywords

regret bound second-order bound normal hedge
Download PDF

More from COLT 2016

All COLT 2016 papers →
Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies
Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture
Open Problem: Kernel methods on manifolds and metric spaces. What is the probability of a positive definite geodesic exponential kernel?
Open Problem: Property Elicitation and Elicitation Complexity
Open Problem: Parameter-Free and Scale-Free Online Algorithms
An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives