Timezone: »
Quantile (and, more generally, KL) regret bounds, such as those achieved by NormalHedge (Chaudhuri, Freund, and Hsu 2009) and its variants, relax the goal of competing against the best individual expert to only competing against a majority of experts on adversarial data. More recently, the semi-adversarial paradigm (Bilodeau, Negrea, and Roy 2020) provides an alternative relaxation of adversarial online learning by considering data that may be neither fully adversarial nor stochastic (I.I.D.). We achieve the minimax optimal regret in both paradigms using FTRL with separate, novel, root-logarithmic regularizers, both of which can be interpreted as yielding variants of NormalHedge. We extend existing KL regret upper bounds, which hold uniformly over target distributions, to possibly uncountable expert classes with arbitrary priors; provide the first full-information lower bounds for quantile regret on finite expert classes (which are tight); and provide an adaptively minimax optimal algorithm for the semi-adversarial paradigm that adapts to the true, unknown constraint faster, leading to uniformly improved regret bounds over existing methods.
Author Information
Jeffrey Negrea (University of Toronto)
Blair Bilodeau (University of Toronto)
Nicolò Campolongo (Università degli Studi di Milano)
Francesco Orabona (Boston University)
Dan Roy (University of Toronto)
More from the Same Authors
-
2021 Spotlight: Towards a Unified Information-Theoretic Framework for Generalization »
Mahdi Haghifam · Gintare Karolina Dziugaite · Shay Moran · Dan Roy -
2021 : Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization »
Blair Bilodeau · Jeffrey Negrea · Dan Roy -
2022 Panel: Panel 4A-2: Adaptively Exploiting d-Separators… & On the Complexity… »
Blair Bilodeau · Ayush Sekhari -
2022 Poster: Robustness to Unbounded Smoothness of Generalized SignSGD »
Michael Crawshaw · Mingrui Liu · Francesco Orabona · Wei Zhang · Zhenxun Zhuang -
2022 Poster: Adaptively Exploiting d-Separators with Causal Bandits »
Blair Bilodeau · Linbo Wang · Dan Roy -
2021 Poster: The future is log-Gaussian: ResNets and their infinite-depth-and-width limit at initialization »
Mufan Li · Mihai Nica · Dan Roy -
2021 Poster: Towards a Unified Information-Theoretic Framework for Generalization »
Mahdi Haghifam · Gintare Karolina Dziugaite · Shay Moran · Dan Roy -
2020 Poster: Temporal Variability in Implicit Online Learning »
Nicolò Campolongo · Francesco Orabona -
2020 Poster: Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms »
Mahdi Haghifam · Jeffrey Negrea · Ashish Khisti · Daniel Roy · Gintare Karolina Dziugaite -
2019 Poster: Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates »
Jeffrey Negrea · Mahdi Haghifam · Gintare Karolina Dziugaite · Ashish Khisti · Daniel Roy -
2019 Poster: Momentum-Based Variance Reduction in Non-Convex SGD »
Ashok Cutkosky · Francesco Orabona -
2019 Poster: Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration »
Kwang-Sung Jun · Ashok Cutkosky · Francesco Orabona -
2017 Poster: Training Deep Networks without Learning Rates Through Coin Betting »
Francesco Orabona · Tatiana Tommasi -
2016 Poster: Coin Betting and Parameter-Free Online Learning »
Francesco Orabona · David Pal -
2014 Workshop: Second Workshop on Transfer and Multi-Task Learning: Theory meets Practice »
Urun Dogan · Tatiana Tommasi · Yoshua Bengio · Francesco Orabona · Marius Kloft · Andres Munoz · Gunnar Rätsch · Hal Daumé III · Mehryar Mohri · Xuezhi Wang · Daniel Hernández-lobato · Song Liu · Thomas Unterthiner · Pascal Germain · Vinay P Namboodiri · Michael Goetz · Christopher Berlind · Sigurd Spieckermann · Marta Soare · Yujia Li · Vitaly Kuznetsov · Wenzhao Lian · Daniele Calandriello · Emilie Morvant -
2014 Workshop: Modern Nonparametrics 3: Automating the Learning Pipeline »
Eric Xing · Mladen Kolar · Arthur Gretton · Samory Kpotufe · Han Liu · Zoltán Szabó · Alan Yuille · Andrew G Wilson · Ryan Tibshirani · Sasha Rakhlin · Damian Kozbur · Bharath Sriperumbudur · David Lopez-Paz · Kirthevasan Kandasamy · Francesco Orabona · Andreas Damianou · Wacha Bounliphone · Yanshuai Cao · Arijit Das · Yingzhen Yang · Giulia DeSalvo · Dmitry Storcheus · Roberto Valerio -
2014 Poster: Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning »
Francesco Orabona -
2013 Workshop: New Directions in Transfer and Multi-Task: Learning Across Domains and Tasks »
Urun Dogan · Marius Kloft · Tatiana Tommasi · Francesco Orabona · Massimiliano Pontil · Sinno Jialin Pan · Shai Ben-David · Arthur Gretton · Fei Sha · Marco Signoretto · Rajhans Samdani · Yun-Qian Miao · Mohammad Gheshlaghi azar · Ruth Urner · Christoph Lampert · Jonathan How -
2013 Poster: Dimension-Free Exponentiated Gradient »
Francesco Orabona -
2013 Spotlight: Dimension-Free Exponentiated Gradient »
Francesco Orabona -
2013 Poster: Regression-tree Tuning in a Streaming Setting »
Samory Kpotufe · Francesco Orabona -
2013 Spotlight: Regression-tree Tuning in a Streaming Setting »
Samory Kpotufe · Francesco Orabona -
2012 Poster: On Multilabel Classification and Ranking with Partial Feedback »
Claudio Gentile · Francesco Orabona -
2012 Spotlight: On Multilabel Classification and Ranking with Partial Feedback »
Claudio Gentile · Francesco Orabona -
2010 Poster: New Adaptive Algorithms for Online Classification »
Francesco Orabona · Yacov Crammer -
2010 Spotlight: Learning from Candidate Labeling Sets »
Jie Luo · Francesco Orabona -
2010 Poster: Learning from Candidate Labeling Sets »
Jie Luo · Francesco Orabona -
2009 Workshop: Learning from Multiple Sources with Applications to Robotics »
Barbara Caputo · Nicolò Cesa-Bianchi · David R Hardoon · Gayle Leen · Francesco Orabona · Jaakko Peltonen · Simon Rogers