8 citations · 40 across the 29 of their papers we have counts for
31 papers
The Last Iterate of the Projected Stochastic Subgradient Method Pays a Logarithm, Even in Dimension One
Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni
We prove that the projected stochastic subgradient method with the standard anytime stepsizes can suffer expected last-iterate optimization error of order $(\log…
An Efficient Minimax-Optimal Algorithm for Adversarial -Set Bandits
Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni
We study adversarial combinatorial bandits with -set actions, where at each round the learner selects out of items and observes only the aggregate loss of the selected i…
No Extra Signals Needed: The Uniform Price of Explainable Information Design
Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni
In information design, an informed sender aims to influence a receiver's decision by committing to a signaling scheme. However, optimal signaling schemes often rely on randomizatio…
Sharp Dimension Dependence for the Last Iterate of the SubGradient Method
Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1
We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on . We prove that, for a finite horizon and a constan…
Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex
Tommaso Cesari, Roberto Colomboni
We establish the normalized covariance bound conjectured by Anari et al. (2026, Conjecture 3) for fixed-rank external-field measures. Let and . For $w\in(0,+\inf…
New Bounds for the Last Iterate of the Stochastic subGradient Method
Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1
We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon , we consider the standard fixed stepsizes $η…
Two-Action Apple Tasting with Switching Costs
Tommaso Cesari, Roberto Colomboni
We study the two-action apple-tasting problem with switching costs against an oblivious adversary. In an equivalent normalized formulation, at each round the learner chooses betwee…
Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning
Tommaso Cesari, Roberto Colomboni
We study stochastic decision-theoretic online learning with full information and event-level pure differential privacy. A COLT open problem of Hu and Mehta asks to determine the op…
Generalized Pinsker Inequality for Bregman Divergences of Negative Tsallis Entropies
Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni
The Pinsker inequality lower bounds the Kullback--Leibler divergence in terms of total variation and provides a canonical way to convert control…
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})…
A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage
François Bachoc, Tommaso Cesari, Roberto Colomboni
We study a contextual version of the repeated brokerage problem. In each interaction, two traders with private valuations for an item seek to buy or sell based on the learner's-a b…
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 Parametric Contextual Online Learning Theory of Brokerage
François Bachoc, Tommaso Cesari, Roberto Colomboni
We study the role of contextual information in the online learning problem of brokerage between traders. In this sequential problem, at each time step, two traders arrive with secr…
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…
Trading Volume Maximization with Online Learning
Tommaso Cesari, Roberto Colomboni
We explore brokerage between traders in an online learning framework. At any round , two traders meet to exchange an asset, provided the exchange is mutually beneficial. The bro…
An Online Learning Theory of Brokerage
Nataša Bolić, Tommaso Cesari, Roberto Colomboni
We investigate brokerage between traders from an online learning perspective. At any round , two traders arrive with their private valuations, and the broker proposes a trading…
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…
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…
Regret Analysis of Dyadic Search
François Bachoc, Tommaso Cesari, Roberto Colomboni +1
We analyze the cumulative regret of the Dyadic Search algorithm of Bachoc et al. [2022].
A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization
François Bachoc, Tommaso Cesari, Roberto Colomboni +1
This paper studies a natural generalization of the problem of minimizing a univariate convex function by querying its values sequentially. At each time-step , the optimizer…
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…
Bilateral Trade: A Regret Minimization Perspective
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni +2
Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they h…
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…