6 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}_{…
Scalable Decision Making for Games of Imperfect Information
Samuel Sokota, Eugene Vinitsky, Hengyuan Hu +3
Real-world decision-making generally involves hidden information, that is, information that is unknown to one agent but possessed by another. Unfortunately, the presence of large a…
Learning Correlated Reward Models: Statistical Barriers and Opportunities
Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Gabriele Farina +1
Random Utility Models (RUMs) are a classical framework for modeling user preferences and play a key role in reward modeling for Reinforcement Learning from Human Feedback (RLHF). H…
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…
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-…