Bypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors
summary
Shows that knowing the set of covariates in advance and using transductive priors with continuous exponential weights yields regret bounds for unbounded losses (square, logistic, hinge) that drop any dependence on the norm of the optimal parameter or on covariate radii, giving d log T regret (and therefore statistical risk O(d log T / T). The construction mixes deterministic labels outside a bounded slab with exponential‑weights inside, bypasses Littlestone hardness, but current algorithms are exponential in dimension (poly in T).
AI-written summary · about
chapters (10)
- 0:00Online learning challenges
- 2:30Sequential linear regression
- 7:19Transductive online setup
- 10:06Improving regression bounds
- 14:09Exponential weights approach
- 21:11Sparsity and regret bounds
- 22:59Logistic regression analysis
- 27:30Implications for IID cases
- 30:34Algorithm and gray zones
- 33:56Extensions and conclusions
related talks
01h 01mRobustness, Stochastics, Uncertainty 2
44mParsimonious Learning-Augmented Algorithms
48mA Simple Condition for Constant Regret in Online Decision-Making
35mOnline Learning with A Lot of Batch Data
58mMemory-Regret Tradeoff for Online Learning
33mOnline Multivalid Learning: Means, Moments, and Prediction Intervals
45mFollow the Leader with Dropout Perturbations
41mTransfer learning via local convergence rates of the nonparametric least squares estimator