13 citations · 67 across the 44 of their papers we have counts for
45 papers
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…
Online Budget Allocation with Censored Semi-Bandit Feedback
François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari +1
We study a stochastic budget-allocation problem over tasks. At each round , the learner chooses an allocation . Task succeeds with probability $F_k(X_{t,k})…
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…
Market Making without Regret
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
We consider a sequential decision-making setting where, at every round , a market maker posts a bid price and an ask price to an incoming trader (the taker) with a p…
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…
Fair Online Bilateral Trade
François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari +1
In online bilateral trade, a platform posts prices to incoming pairs of buyers and sellers that have private valuations for a certain good. If the price is lower than the buyers' v…
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}_…
Adaptive maximization of social welfare
Nicolo Cesa-Bianchi, Roberto Colomboni, Maximilian Kasy
We consider the problem of repeatedly choosing policies to maximize social welfare. Welfare is a weighted sum of private utility and public revenue. Earlier outcomes inform later p…
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…
Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts
Dirk van der Hoeven, Ciara Pike-Burke, Hao Qiu +1
We investigate online classification with paid stochastic experts. Here, before making their prediction, each expert must be paid. The amount that we pay each expert directly influ…
The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item's value only if the auction is won. Our ma…
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…
Online Learning in Supply-Chain Games
Nicolò Cesa-Bianchi, Tommaso Cesari, Takayuki Osogami +2
We study a repeated game between a supplier and a retailer who want to maximize their respective profits without full knowledge of the problem parameters. After characterizing the…
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…