1.6k citations · 1.8k across the 18 of their papers we have counts for
19 papers
An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
Tim van Erven, Jack Mayo, Julia Olkhovskaya +1
We present an oracle-efficient, near-optimal algorithm for linear contextual bandits with adversarial losses and stochastic action sets, only requiring a linear optimization oracle…
Generalization Guarantees via Algorithm-dependent Rademacher Complexity
Sarah Sachs, Tim van Erven, Liam Hodgkinson +2
Algorithm- and data-dependent generalization bounds are required to explain the generalization behavior of modern machine learning algorithms. In this context, there exists informa…
The Risks of Recourse in Binary Classification
Hidde Fokkema, Damien Garreau, Tim van Erven
Algorithmic recourse provides explanations that help users overturn an unfavorable decision by a machine learning system. But so far very little attention has been paid to whether…
Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
Hédi Hadiji, Sarah Sachs, Tim van Erven +1
In the first-order query model for zero-sum matrix games, players observe the expected pay-offs for all their possible actions under the randomized action played by the…
Accelerated Rates between Stochastic and Adversarial Online Convex Optimization
Sarah Sachs, Hedi Hadiji, Tim van Erven +1
Stochastic and adversarial data are two widely studied settings in online learning. But many optimization tasks are neither i.i.d. nor fully adversarial, which makes it of fundamen…
Adaptive Selective Sampling for Online Prediction with Experts
Rui M. Castro, Fredrik Hellström, Tim van Erven
We consider online prediction of a binary sequence with expert advice. For this setting, we devise label-efficient forecasting algorithms, which use a selective sampling scheme tha…
Attribution-based Explanations that Provide Recourse Cannot be Robust
Hidde Fokkema, Rianne de Heide, Tim van Erven
Different users of machine learning methods require different explanations, depending on their goals. To make machine learning accountable to society, one important goal is to get…
Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness
Sarah Sachs, Hédi Hadiji, Tim van Erven +1
Stochastic and adversarial data are two widely studied settings in online learning. But many optimization tasks are neither i.i.d. nor fully adversarial, which makes it of fundamen…
Scale-free Unconstrained Online Learning for Curved Losses
Jack J. Mayo, Hédi Hadiji, Tim van Erven
A sequence of works in unconstrained online convex optimisation have investigated the possibility of adapting simultaneously to the norm of the comparator and the maximum norm…
Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
Wouter M. Koolen, Peter Grünwald, Tim van Erven
We consider online learning algorithms that guarantee worst-case regret rates in adversarial environments (so they can be deployed safely and will perform robustly), yet adapt opti…
MetaGrad: Multiple Learning Rates in Online Learning
Tim van Erven, Wouter M. Koolen
In online convex optimization it is well known that certain subclasses of objective functions are much easier than arbitrary convex functions. We are interested in designing adapti…
PAC-Bayes Mini-tutorial: A Continuous Union Bound
Tim van Erven
When I first encountered PAC-Bayesian concentration inequalities they seemed to me to be rather disconnected from good old-fashioned results like Hoeffding's and Bernstein's inequa…
A Second-order Bound with Excess Losses
Pierre Gaillard, Gilles Stoltz, Tim Van Erven
We study online aggregation of the predictions of experts, and first show new second-order regret bounds in the standard setting, which are obtained via a version of the Prod algor…
Follow the Leader If You Can, Hedge If You Must
Steven de Rooij, Tim van Erven, Peter D. Grünwald +1
Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has terrible performance for worst-case data.…
Rényi Divergence and Kullback-Leibler Divergence
Tim van Erven, Peter Harremoës
Rényi divergence is related to Rényi entropy much like Kullback-Leibler divergence is related to Shannon's entropy, and comes up in many settings. It was introduced by Rényi as a m…
Adaptive Hedge
Tim van Erven, Peter Grünwald, Wouter M. Koolen +1
Most methods for decision-theoretic online learning are based on the Hedge algorithm, which takes a parameter called the learning rate. In most previous analyses the learning rate…
Freezing and Sleeping: Tracking Experts that Learn by Evolving Past Posteriors
Wouter M. Koolen, Tim van Erven
A problem posed by Freund is how to efficiently track a small pool of experts out of a much larger set. This problem was solved when Bousquet and Warmuth introduced their mixing pa…
Switching between Hidden Markov Models using Fixed Share
Wouter M. Koolen, Tim van Erven
In prediction with expert advice the goal is to design online prediction algorithms that achieve small regret (additional loss on the whole data) compared to a reference scheme. In…
Rényi Divergence and Majorization
Tim van Erven, Peter Harremoës
Rényi divergence is related to Rényi entropy much like information divergence (also called Kullback-Leibler divergence or relative entropy) is related to Shannon's entropy, and com…