Constantinos Daskalakis, Gabriele Farina, Brian Hu Zhang
原文摘要
We give a $\text{poly}(d, p, \log(1/ε))$-time algorithm that computes an $ε$-approximate fixed point of any $\ell_p$-nonexpansive map $f : \mathcal{X} \to \mathcal{X}$, where $\mathcal{X} \subset \mathbb R^d$ is a convex compact set and $p$ is an even integer. This is the first algorithm with $\text{poly}(d, \log(1/ε))$ runtime for any fixed $p \ne 2$. Our techniques are based on a computationally efficient version of Sion's theorem for non-compact minmax problems, and extend to more general total search problems that admit low-degree polynomial potentials.
We study, under a smoothed analysis perspective, the complexity of three PPAD-complete problems: computing Nash equilibria, computing fixed points, and solving variational inequalities. We consider a general perturbation model that bounds the probability density of the quantities evaluated by our algorithms. As special cases, it captures worst-case games perturbed by small random per-action costs, and worst-case maps perturbed by a small random affine function. Under these models, we show that classical algorithmic paradigms, cover-based search and homotopy path-following provably outperform the worst-case state-of-the-art. For games with a constant number of players and $n$ strategies per player, a recursive cover-based algorithm computes an $\varepsilon$-Nash equilibrium using $\log(1/\varepsilon)\cdot 2^{O(n)}$ expected payoff-vector computations, compared to the worst-case runtime tradeoffs of $\log(1/\varepsilon)\cdot n^{O(n)}$, $(1/\varepsilon)^{O(n)}$, $2^{O(\log^2 n/\varepsilon^2)}$, and $2^{O(n)}\mathrm{poly}(\log(1/\varepsilon))$. For fixed points and variational inequalities of bounded and Lipschitz maps on the $n$-dimensional $\ell_2$ unit ball, the same approach runs in expected time $\log(1/\varepsilon)\cdot 2^{O(n)}$, compared to the worst-case $(1/\varepsilon)^{O(n)}$; the $2^{Ω(n)}$ factor is necessary by prior work [Rubinstein, 2017]. For general smooth maps, we further analyze the classical predictor--corrector homotopy method, for which only qualitative convergence guarantees were previously known, showing that under perturbations the homotopy path is well conditioned and has length $2^{O(n)}$, so that the method finds an $\varepsilon$-approximate solution in time $2^{O(n)}\cdot\mathrm{poly}(1/p)/\varepsilon$ with probability at least $1-p$.
Phevos Paschalidis, Constantinos Daskalakis, Devavrat Shah
原文摘要
We study causal inference under outcome interference for sequential, observational settings. Specifically, we consider settings where the binary outcomes over N units are Markovian across T time steps. At each time step, the outcomes of N units have dependencies captured through an Ising model; each outcome is also impacted through an external field capturing the effects of its treatment as well as latent confounders. Similar to panel data literature, these latent confounders are modeled to have a low-rank factor structure. Our data is a single sample from this high-dimensional distribution. To estimate causal quantities of interest, we provide a computationally efficient method based on Maximum Pseudo-Likelihood Estimation (MPLE) for learning the model parameters. Under mild assumptions, we establish non-asymptotic consistency for parameter estimation and show this translates to faithful estimation of causal quantities of interest after sampling from the learned model. We demonstrate the efficacy of the method through synthetic experiments as well as a real-world case-study investigating causal effects of vaccine rates on COVID-19 death rates within US counties nationwide.