3 citations · 6 across the 27 of their papers we have counts for
30 papers
Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
Martino Bernasconi, Giulio Malavolta
We study a multilinear optimization problem for tensors with bounded Frobenius norm, where each of the local factors of dimension is chosen from a convex set. We give a det…
A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +2
Subsampling theorems for constraint satisfaction problems (CSPs) guarantee that the value of the CSP is approximately preserved after restricting it to small random subsets of vari…
A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of degree- polynomials and any convex set ${H} \subseteq \mathbb{R}_{…
Theoretical Foundations of @ Reinforcement Learning
Riccardo Poiani, Martino Bernasconi, Andrea Celli
Reinforcement Learning is a cornerstone technique for modern large reasoning models. Usually, for difficult tasks such as code generation and theorem proving, the agent is evaluate…
The Complexity of Min-Max Optimization for Quadratic Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are mu…
Regret Minimization in Single-Dimensional Contract-Design with Binary Actions
Riccardo Poiani, Martino Bernasconi, Andrea Celli
We study principal-agent problems in which a principal commits to an outcome-dependent payment scheme (i.e., a contract) in order to induce an agent to take a costly action leading…
Min-Max Optimization Requires Exponentially Many Queries
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We study the query complexity of min-max optimization of a nonconvex-nonconcave function over . We show that, given oracle access to and to its grad…
Nonparametric Contextual Online Bilateral Trade
Emanuele Coccia, Martino Bernasconi, Andrea Celli
We study the problem of contextual online bilateral trade. At each round, the learner faces a seller-buyer pair and must propose a trade price without observing their private valua…
The Complexity of Min-Max Optimization with Product Constraints
Martino Bernasconi, Matteo Castiglioni
We study the computational complexity of the problem of computing local min-max equilibria of games with a nonconvex-nonconcave utility function . From the work of Daskalakis, S…
Optimal Rates for Feasible Payoff Set Estimation in Games
Annalisa Barbara, Riccardo Poiani, Martino Bernasconi +1
We study a setting in which two players play a (possibly approximate) Nash equilibrium of a bimatrix game, while a learner observes only their actions and has no knowledge of the e…
Online Learning in the Random Order Model
Martino Bernasconi, Andrea Celli, Riccardo Colini-Baldeschi +3
In the random-order model for online learning, the sequence of losses is chosen upfront by an adversary and presented to the learner after a random permutation. Any random-order in…
The Complexity of Correlated Equilibria in Generalized Games
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
Correlated equilibria -- and their generalization -equilibria -- are a fundamental object of study in game theory, offering a more tractable alternative to Nash equilibria in mu…
Non-Asymptotic Analysis of (Sticky) Track-and-Stop
Riccardo Poiani, Martino Bernasconi, Andrea Celli
In pure exploration problems, a statistician sequentially collects information to answer a question about some stochastic and unknown environment. The probability of returning a wr…
Pure Exploration with Infinite Answers
Riccardo Poiani, Martino Bernasconi, Andrea Celli
We study pure exploration problems in which the set of correct answers is possibly infinite. For example, such problems arise when regressing a continuous function on the means of…
Single-dimensional Contract Design: Efficient Algorithms and Learning
Martino Bernasconi, Matteo Castiglioni, Andrea Celli
We study a Bayesian contract design problem in which a principal interacts with an unknown agent. We consider the single-parameter uncertainty model introduced by Alon et al. [2021…
Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
Maria-Florina Balcan, Martino Bernasconi, Matteo Castiglioni +3
We study the problem of online learning in Stackelberg games with side information between a leader and a sequence of followers. In every round the leader observes contextual infor…
Improved Hardness Results for Min-Max Optimization with Coupled Constraints
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We investigate the computational complexity of min-max optimization under coupled constraints. The work of Daskalakis, Skoulakis, and Zampetakis [DSZ21] was the first to study min-…
Feature-Based Online Bilateral Trade
Solenne Gaucher, Martino Bernasconi, Matteo Castiglioni +2
Bilateral trade models the problem of facilitating trades between a seller and a buyer having private valuations for the item being sold. In the online version of the problem, the…
Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We address a generalization of the bandit with knapsacks problem, where a learner aims to maximize rewards while satisfying an arbitrary set of long-term constraints. Our goal is t…
No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
Martino Bernasconi, Matteo Castiglioni, Andrea Celli
In the bandits with knapsacks framework (BwK) the learner has resource-consumption (packing) constraints. We focus on the generalization of BwK in which the learner has a set o…
Agent-Designed Contracts: How to Sell Hidden Actions
Martino Bernasconi, Matteo Castiglioni, Andrea Celli
We study the problem faced by a service provider that has to sell services to a user. In our model the service provider proposes various payment options (a menu) to the user which…
Multi-Agent Contract Design beyond Binary Actions
Federico Cacciamani, Martino Bernasconi, Matteo Castiglioni +1
We study hidden-action principal-agent problems with multiple agents. Unlike previous work, we consider a general setting in which each agent has an arbitrary number of actions, an…
Regret-Minimizing Contracts: Agency Under Uncertainty
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi
We study the fundamental problem of designing contracts in principal-agent problems under uncertainty. Previous works mostly addressed Bayesian settings in which principal's uncert…
No-Regret Learning in Bilateral Trade via Global Budget Balance
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
Bilateral trade models the problem of intermediating between two rational agents -- a seller and a buyer -- both characterized by a private valuation for an item they want to trade…