13 citations · 67 across the 44 of their papers we have counts for
36 papers · 1 filter
Active Learning on Adversarially Corrupted Graphs
Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi +2
Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} insi…
Learning Conditional Averages
Marco Bressan, Nataly Brukhim, Nicolo Cesa-Bianchi +4
We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in…
Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach
Hao Qiu, Mengxiao Zhang, Nicolò Cesa-Bianchi
We study distributed adversarial bandits, where agents cooperate to minimize the global average loss while observing only their own local losses. We show that the minimax regre…
Of Dice and Games: A Theory of Generalized Boosting
Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi +4
Cost-sensitive loss functions are crucial in many real-world prediction problems, where different types of errors are penalized differently; for example, in medical diagnosis, a fa…
Distributed Online Optimization with Stochastic Agent Availability
Juliette Achddou, Nicolò Cesa-Bianchi, Hao Qiu
Motivated by practical federated learning settings where clients may not be always available, we investigate a variant of distributed online optimization where agents are active wi…
A Theory of Interpretable Approximations
Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito +3
Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning model…
Multitask Online Learning: Listen to the Neighborhood Buzz
Juliette Achddou, Nicolò Cesa-Bianchi, Pierre Laforgue
We study multitask online learning in a setting where agents can only exchange information with their neighbors on an arbitrary communication network. We introduce $\texttt{MT-CO}_…
High-Probability Risk Bounds via Sequential Predictors
Dirk van der Hoeven, Nikita Zhivotovskiy, Nicolò Cesa-Bianchi
Online learning methods yield sequential regret bounds under minimal assumptions and provide in-expectation risk bounds for statistical learning. However, despite the apparent adva…
Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning
Pier Giuseppe Sessa, Pierre Laforgue, Nicolò Cesa-Bianchi +1
Multitask learning is a powerful framework that enables one to simultaneously learn multiple related tasks by sharing information between them. Quantifying uncertainty in the estim…
Delayed Bandits: When Do Intermediate Observations Help?
Emmanuel Esposito, Saeed Masoudian, Hao Qiu +3
We study a -armed bandit with delayed feedback and intermediate observations. We consider a model where intermediate observations have a form of a finite state, which is observe…
A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs
Dirk van der Hoeven, Lukas Zierahn, Tal Lancewicki +2
We derive a new analysis of Follow The Regularized Leader (FTRL) for online learning with delayed bandit feedback. By separating the cost of delayed feedback from that of bandit fe…
On the Minimax Regret for Online Learning with Feedback Graphs
Khaled Eldowa, Emmanuel Esposito, Tommaso Cesari +1
In this work, we improve on the upper and lower bounds for the regret of online learning with strongly observable undirected feedback graphs. The best known upper bound for this pr…
Repeated Bilateral Trade Against a Smoothed Adversary
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
We study repeated bilateral trade where an adaptive -smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regime…
Linear Bandits with Memory: from Rotting to Rising
Giulia Clerici, Pierre Laforgue, Nicolò Cesa-Bianchi
Nonstationary phenomena, such as satiation effects in recommendations, have mostly been modeled using bandits with finitely many arms. However, the richer action space provided by…
Learning on the Edge: Online Learning with Stochastic Feedback Graphs
Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven +1
The framework of feedback graphs is a generalization of sequential decision-making with bandit or full information feedback. In this work, we study an extension where the directed…
Active Learning of Classifiers with Label and Seed Queries
Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi +2
We study exact active learning of binary and multiclass classifiers with margin. Given an -point set , we want to learn any unknown classifier on who…
A Regret-Variance Trade-Off in Online Learning
Dirk van der Hoeven, Nikita Zhivotovskiy, Nicolò Cesa-Bianchi
We consider prediction with expert advice for strongly convex and bounded losses, and investigate trade-offs between regret and "variance" (i.e., squared difference of learner's pr…
A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs
Chloé Rouyer, Dirk van der Hoeven, Nicolò Cesa-Bianchi +1
We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We pres…
AdaTask: Adaptive Multitask Online Learning
Pierre Laforgue, Andrea Della Vecchia, Nicolò Cesa-Bianchi +1
We introduce and analyze AdaTask, a multitask online learning algorithm that adapts to the unknown structure of the tasks. When the tasks are stochastically activated, we show…
Nonstochastic Bandits and Experts with Arm-Dependent Delays
Dirk van der Hoeven, Nicolò Cesa-Bianchi
We study nonstochastic bandits and experts in a delayed setting where delays depend on both time and arms. While the setting in which delays only depend on time has been extensivel…
A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits
Pierre Laforgue, Giulia Clerici, Nicolò Cesa-Bianchi +1
Motivated by the fact that humans like some level of unpredictability or novelty, and might therefore get quickly bored when interacting with a stationary policy, we introduce a no…
On Margin-Based Cluster Recovery with Oracle Queries
Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi +1
We study an active cluster recovery problem where, given a set of points and an oracle answering queries like "are these two points in the same cluster?", the task is to recove…
Beyond Bandit Feedback in Online Multiclass Classification
Dirk van der Hoeven, Federico Fusco, Nicolò Cesa-Bianchi
We study the problem of online multiclass classification in a setting where the learner's feedback is determined by an arbitrary directed graph. While including bandit feedback as…
Cooperative Online Learning with Feedback Graphs
Nicolò Cesa-Bianchi, Tommaso R. Cesari, Riccardo Della Vecchia
We study the interplay between communication and feedback in a cooperative online learning setting, where a network of communicating agents learn a common sequential decision-makin…