Aviad Rubinstein

Binghui Peng, Aviad Rubinstein

In the experts problem, on each of $T$ days, an agent needs to follow the advice of one of $n$ ``experts''. After each day, the loss associated with each expert's advice is revealed. A fundamental result in learning theory says that the agent can achieve vanishing regret, i.e. their cumulative loss is within $o(T)$ of the cumulative loss of the best-in-hindsight expert. Can the agent perform well without sufficient space to remember all the experts? We extend a nascent line of research on this question in two directions: $\bullet$ We give a new algorithm against the oblivious adversary, improving over the memory-regret tradeoff obtained by [PZ23], and nearly matching the lower bound of [SWXZ22]. $\bullet$ We also consider an adaptive adversary who can observe past experts chosen by the agent. In this setting we give both a new algorithm and a novel lower bound, proving that roughly $\sqrt{n}$ memory is both necessary and sufficient for obtaining $o(T)$ regret.

Nima Anari, Ruiquan Gao, Aviad Rubinstein

We show how to use parallelization to speed up sampling from an arbitrary distribution $μ$ on a product space $[q]^n$, given oracle access to counting queries: $\mathbb{P}_{X\sim μ}[X_S=σ_S]$ for any $S\subseteq [n]$ and $σ_S \in [q]^S$. Our algorithm takes $O({n^{2/3}\cdot \operatorname{polylog}(n,q)})$ parallel time, to the best of our knowledge, the first sublinear in $n$ runtime for arbitrary distributions. Our results have implications for sampling in autoregressive models. Our algorithm directly works with an equivalent oracle that answers conditional marginal queries $\mathbb{P}_{X\sim μ}[X_i=σ_i\;\vert\; X_S=σ_S]$, whose role is played by a trained neural network in autoregressive models. This suggests a roughly $n^{1/3}$-factor speedup is possible for sampling in any-order autoregressive models. We complement our positive result by showing a lower bound of $\widetildeΩ(n^{1/3})$ for the runtime of any parallel sampling algorithm making at most $\operatorname{poly}(n)$ queries to the counting oracle, even for $q=2$.

Binghui Peng, Aviad Rubinstein

We give a simple and computationally efficient algorithm that, for any constant $\varepsilon>0$, obtains $\varepsilon T$-swap regret within only $T = \mathsf{polylog}(n)$ rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum and Mansour 2007]. Our algorithm has an exponential dependence on $\varepsilon$, but we prove a new, matching lower bound. Our algorithm for swap regret implies faster convergence to $\varepsilon$-Correlated Equilibrium ($\varepsilon$-CE) in several regimes: For normal form two-player games with $n$ actions, it implies the first uncoupled dynamics that converges to the set of $\varepsilon$-CE in polylogarithmic rounds; a $\mathsf{polylog}(n)$-bit communication protocol for $\varepsilon$-CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein'2017, Goos-Rubinstein'2018, Ganor-CS'2018]); and an $\tilde{O}(n)$-query algorithm for $\varepsilon$-CE (resolving an open problem of [Babichenko'2020] and obtaining the first separation between $\varepsilon$-CE and $\varepsilon$-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for $\mathit{normal}$ $\mathit{form}$ $\mathit{correlated}$ $\mathit{equilibria}$, a solution concept often conjectured to be computationally intractable (e.g. [Stengel-Forges'08, Fujii'23]).

Jingyi Liu, Aviad Rubinstein, Ertem Nusret Tas et al.

Classical optimal auction theory assumes that bids reach the seller directly. We study how this picture changes when a revenue-maximizing intermediary controls access to the seller's auction. Motivated by blockchain auctions, online platforms, and other intermediated markets, we consider a single-item auction with independent private values and a monopolist intermediary who can decide which bidder messages are forwarded to the seller. We establish approximation guarantees and impossibility results across three timing models: seller-first, intermediary-first, and simultaneous. In the seller-first model, arbitrary deterministic seller mechanisms collapse to posted-price mechanisms, and the intermediary's best response is a shifted Myerson auction. This yields a sharp separation: for regular distributions, the seller's revenue can be arbitrarily small relative to the no-intermediary optimum, while for $α$-strongly regular distributions, posted prices recover a constant fraction of the optimum with a tight dependence on $α$. We further show that timing matters: neither Stackelberg order uniformly dominates, and simultaneous play can leave both parties unboundedly worse off than in either sequential model.

Aviad Rubinstein, Sahil Singla

We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed constraints. When elements have binary values, all three problems admit a tight $\tildeΘ(\log n)$-factor approximation guarantee. For general (non-binary) values, however, the best known algorithms lose an additional $\log n$ factor when discretizing to binary values, leaving a quadratic gap of $\tildeΘ(\log n)$ vs. $\tildeΘ(\log^2 n)$. We resolve this quadratic gap for all three problems, showing $\tildeΩ(\log^2 n)$-hardness for two of them and an $O(\log n)$-approximation algorithm for the third. While the technical details differ across settings, and between algorithmic and hardness proofs, all our results stem from a single core observation, which we call the Big-Decisions-First Principle: Under uncertainty, it is better to resolve high-stakes (large-value) decisions early.

Aviad Rubinstein, Junyao Zhao

We study repeated first-price auctions and general repeated Bayesian games between two players, where one player, the learner, employs a no-regret learning algorithm, and the other player, the optimizer, knowing the learner's algorithm, strategizes to maximize its own utility. For a commonly used class of no-regret learning algorithms called mean-based algorithms, we show that (i) in standard (i.e., full-information) first-price auctions, the optimizer cannot get more than the Stackelberg utility -- a standard benchmark in the literature, but (ii) in Bayesian first-price auctions, there are instances where the optimizer can achieve much higher than the Stackelberg utility. On the other hand, Mansour et al. (2022) showed that a more sophisticated class of algorithms called no-polytope-swap-regret algorithms are sufficient to cap the optimizer's utility at the Stackelberg utility in any repeated Bayesian game (including Bayesian first-price auctions), and they pose the open question whether no-polytope-swap-regret algorithms are necessary to cap the optimizer's utility. For general Bayesian games, under a reasonable and necessary condition, we prove that no-polytope-swap-regret algorithms are indeed necessary to cap the optimizer's utility and thus answer their open question. For Bayesian first-price auctions, we give a simple improvement of the standard algorithm for minimizing the polytope swap regret by exploiting the structure of Bayesian first-price auctions.

Xiao Mao, Aviad Rubinstein

We present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant $ε>0$, compute a $(1+ε)$-approximation for ED and a $(1-ε)$-approximation for LCS in time $n^2 / 2^{\log^{Ω(1)}(n)}$ for two strings of total length at most $n$. This running time improves upon the classical quadratic-time dynamic programming algorithms by a quasi-polynomial factor. Our results yield significant insights into fine-grained complexity: Firstly, for ED, prior work indicates that any exact algorithm cannot be improved beyond a few logarithmic factors without refuting established complexity assumptions [Abboud, Hansen, Vassilevska Williams, Williams, 2016]; our quasi-polynomial speed-up shows a separation the complexity of approximate ED from that of exact ED, even for approximation factor arbitrarily close to $1$. Secondly, for LCS, obtaining similar approximation-time tradeoffs via deterministic algorithms would imply breakthrough circuit lower bounds [Chen, Goldwasser, Lyu, Rothblum, Rubinstein, 2019]; our randomized algorithm demonstrates derandomization hardness for LCS approximation.

Moshe Babaioff, Aviad Rubinstein, Xizhi Tan et al.

A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets with strategic agents. As achieving the full GFT is generally impossible, much of the literature has focused on constant-factor approximations. Existing results, however, are limited to the highly structured settings of bilateral trade and double auctions, in which every buyer can trade with every seller. We consider the significantly more general setting of two-sided matching markets with arbitrary downward-closed constraints on the family of allowed matchings. For this setting, we present a simple randomized truthful mechanism that guarantees a constant-factor approximation to the optimal expected GFT. This result also resolves an open problem posed by Cai, Goldner, Ma, and Zhao (2021).

Binghui Peng, Aviad Rubinstein

We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in $\mathit{extensive}$-$\mathit{form}$ $\mathit{games}$, assuming $\mathsf{PPAD} \not\subset \mathsf{TIME}(n^{\mathsf{polylog}(n)})$, any polynomial-time learning algorithms must take at least $2^{\log_2^{1-o(1)}(|\mathcal{I}|)}$ iterations to converge to the set of $ε$-approximate correlated equilibrium, where $|\mathcal{I}|$ is the number of nodes in the game and $ε> 0$ is an absolute constant. This nearly matches, up to the $o(1)$ term, the algorithms of [PR'24, DDFG'24] for learning $ε$-approximate correlated equilibrium, and resolves an open question of Anagnostides, Kalavasis, Sandholm, and Zampetakis [AKSZ'24]. Our lower bound holds even for the easier solution concept of $ε$-approximate $\mathit{coarse}$ correlated equilibrium On the positive side, we give uncoupled dynamics that reach $ε$-approximate correlated equilibria of a $\mathit{Bayesian}$ $\mathit{game}$ in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.

Eric Balkanski, Aviad Rubinstein, Yaron Singer

In this paper we consider the following question: can we optimize objective functions from the training data we use to learn them? We formalize this question through a novel framework we call optimization from samples (OPS). In OPS, we are given sampled values of a function drawn from some distribution and the objective is to optimize the function under some constraint. While there are interesting classes of functions that can be optimized from samples, our main result is an impossibility. We show that there are classes of functions which are statistically learnable and optimizable, but for which no reasonable approximation for optimization from samples is achievable. In particular, our main result shows that there is no constant factor approximation for maximizing coverage functions under a cardinality constraint using polynomially-many samples drawn from any distribution. We also show tight approximation guarantees for maximization under a cardinality constraint of several interesting classes of functions including unit-demand, additive, and general monotone submodular functions, as well as a constant factor approximation for monotone submodular functions with bounded curvature.

Siu On Chan, Dimitris Papailiopoulos, Aviad Rubinstein

It is well known that Sparse PCA (Sparse Principal Component Analysis) is NP-hard to solve exactly on worst-case instances. What is the complexity of solving Sparse PCA approximately? Our contributions include: 1) a simple and efficient algorithm that achieves an $n^{-1/3}$-approximation; 2) NP-hardness of approximation to within $(1-\varepsilon)$, for some small constant $\varepsilon > 0$; 3) SSE-hardness of approximation to within any constant factor; and 4) an $\exp\exp\left(Ω\left(\sqrt{\log \log n}\right)\right)$ ("quasi-quasi-polynomial") gap for the standard semidefinite program.