12 papers
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…
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…