I am broadly interested in theoretical computer science. In particular, my research focuses on theoretical problems at the intersection of algorithms, learning, game theory, networks, and randomness.
Preprints
- Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics, with Elchanan Mossel.
Preprint.
[Abstract] [PDF]
A popular method for sampling from high-dimensional distributions is the Gibbs sampler, which iteratively resamples sites from the conditional distribution of the desired measure given the values of the other coordinates. But to what extent does the order of site updates matter in the mixing time? Two natural choices are (i) standard, or random scan, Glauber dynamics where the updated variable is chosen uniformly at random, and (ii) the systematic scan dynamics where variables are updated in a fixed, cyclic order. We first show that for systems of dimension $n$, one round of the systematic scan dynamics has spectral gap at most a factor of order $n$ worse than the corresponding spectral gap of a single step of Glauber dynamics, tightening existing bounds in the literature by He, et al. [NeurIPS '16] and Chlebicka, Łatuszy\'nski, and Miasodejow [Ann. Appl. Probab. '24]. This result is sharp even for simple spin systems by an example of Roberts and Rosenthal [Int. J. Statist. Prob. '15]. We complement this with a converse statement: if all, or even just one scan order rapidly mixes, the Glauber dynamics has a polynomially related mixing time, resolving a question of Chlebicka, Łatuszy\'nski, and Miasodejow. Our arguments are simple and only use elementary linear algebra and probability.
- Efficiently Learning Markov Random Fields from Dynamics, with Ankur Moitra and Elchanan Mossel.
Preprint.
[Abstract] [PDF]
An important task in high-dimensional statistics is learning the parameters or dependency structure of an undirected graphical model, or Markov random field (MRF). Much of the prior work on this problem assumes access to i.i.d. samples from the MRF distribution and state-of-the-art algorithms succeed using $n^{\Theta(k)}$ runtime, where $n$ is the dimension and $k$ is the order of the interactions. However, well-known reductions from the sparse parity with noise problem imply that given i.i.d. samples from a sparse, order-$k$ MRF, any learning algorithm likely requires $n^{\Omega(k)}$ time, impeding the potential for significant computational improvements. In this work, we demonstrate that these fundamental barriers for learning MRFs can surprisingly be completely circumvented when learning from natural, dynamical samples. We show that in bounded-degree MRFs, the dependency structure and parameters can be recovered using a trajectory of Glauber dynamics of length $O(n\log n)$ with runtime $O(n^2\log n)$. The implicit constants depend only on the degree and non-degeneracy parameters of the model, but not the dimension $n$. In particular, learning MRFs from dynamics is provably computationally easier than learning from i.i.d. samples under standard hardness assumptions.
- Sample-Efficient Linear Regression with Self-Selection Bias, with Elchanan Mossel.
In submission.
[Abstract] [PDF]
We consider the problem of linear regression with self-selection bias in the unknown-index setting, as introduced in recent work by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [STOC 2023]. In this model, one observes m i.i.d. samples $(\mathbf{x}_{\ell},z_{\ell})_{\ell=1}^m$ where $z_{\ell}=\max_{i\in [k]}\{\mathbf{x}_{\ell}^T\mathbf{w}_i+\eta_{\ell,i}\}$, but the maximizing index $i_{\ell}$ is unobserved. Here, the $\mathbf{x}_{\ell}$ are assumed to be $\mathcal{N}(0,I_n)$ and the noise distribution $\mathbf{\eta}\sim \mathcal{D}$ is centered and independent of $\mathbf{x}_{\ell}$. We provide a novel and near optimally sample-efficient (in terms of $k$) algorithm to recover $\mathbf{w}_1,\ldots,\mathbf{w}_k\in \mathbb{R}^n$ up to additive $\ell_2$-error $\varepsilon$ with polynomial sample complexity $\tilde{O}(n)\cdot \mathsf{poly}(k,1/\varepsilon)$ and significantly improved time complexity $\mathsf{poly}(n,k,1/\varepsilon)+O(\log(k)/\varepsilon)^{O(k)}$. When $k=O(1)$, our algorithm runs in $\mathsf{poly}(n,1/\varepsilon)$ time, generalizing the polynomial guarantee of an explicit moment matching algorithm of Cherapanamjeri, et al. for $k=2$ and when it is known that $\mathcal{D}=\mathcal{N}(0,I_k)$. Our algorithm succeeds under significantly relaxed noise assumptions, and therefore also succeeds in the related setting of max-linear regression where the added noise is taken outside the maximum. For this problem, our algorithm is efficient in a much larger range of $k$ than the state-of-the-art due to Ghosh, Pananjady, Guntuboyina, and Ramchandran [IEEE Trans. Inf. Theory 2022] for not too small $\varepsilon$, and leads to improved algorithms for any $\varepsilon$ by providing a warm start for existing local convergence methods.
Journal Papers
- Bounds on the Covariance Matrix of the Sherrington-Kirkpatrick Model, with Ahmed El Alaoui.
Electronic Communications in Probability 2024.
[Abstract] [PDF]
We consider the Sherrington-Kirkpatrick model with no external field and inverse temperature $\beta<1$ and prove that the expected operator norm of the covariance matrix of the Gibbs measure is bounded by a constant depending only on $\beta$.
This answers an open question raised by Talagrand, who proved a bound of $C(\beta) (\log n)^8$.
Our result follows by establishing an approximate formula for the covariance matrix which we obtain by differentiating the TAP equations and then optimally controlling the associated error terms. We complement this result by showing diverging lower bounds on the operator norm, both at the critical and low temperatures.
- The Price of Anarchy of Strategic Queuing Systems, with Éva Tardos.
Journal of the ACM 2023 (JACM 2023)
[Abstract] [PDF]
Bounding the price of anarchy, which quantifies the damage to social welfare due to selfish behavior of the participants, has been an important area of research in algorithmic game theory. Classical work on such bounds in repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent beyond any influence on play from past history. This work studies such bounds in environments that themselves change due to the actions of the agents. Concretely, we consider this problem in discrete-time queuing systems, where competitive queues try to get their packets served. In this model, a queue gets to send a packet at each step to one of the servers, which will attempt to serve the oldest arriving packet, and unprocessed packets are returned to each queue. We model this as a repeated game where queues compete for the capacity of the servers, but where the state of the game evolves as the length of each queue varies.
We analyze this queuing system from multiple perspectives. As a baseline measure, we first establish precise conditions on the queuing arrival rates and service capacities that ensure all packets clear efficiently under centralized coordination. We then show that if queues strategically choose servers according to independent and stationary distributions, the system remains stable provided it would be stable under coordination with arrival rates scaled up by a factor of just $e/(e-1)$. Finally, we extend these results to no-regret learning dynamics: if queues use learning algorithms satisfying the no-regret property to choose servers, then the requisite factor increases to 2, and both of these bounds are tight. Both of these results require new probabilistic techniques compared to the classical price of anarchy literature and show that in such settings, no-regret learning can exhibit efficiency loss due to myopia.
Conference Papers
- A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width, with Elchanan Mossel.
Symposium on Theory of Computing 2024 (STOC 2024) .
[Abstract] [PDF]
We revisit the problem of efficiently learning the underlying parameters of Ising models from data. Current algorithmic approaches achieve essentially optimal sample complexity when given i.i.d. samples from the stationary measure and the underlying model satisfies "width" bounds on the total $\ell_1$ interaction involving each node. We show that a simple existing approach based on node-wise logistic regression provably succeeds at recovering the underlying model in several new settings where these assumptions are violated:
- Given dynamically generated data from a wide variety of local Markov chains, like block or round-robin dynamics, logistic regression recovers the parameters with optimal sample complexity up to loglogn factors. This generalizes the specialized algorithm of Bresler, Gamarnik, and Shah [IEEE Trans. Inf. Theory'18] for structure recovery in bounded degree graphs from Glauber dynamics.
- For the Sherrington-Kirkpatrick model of spin glasses, given $\mathsf{poly}(n)$ independent samples, logistic regression recovers the parameters in most of the known high-temperature regime via a simple reduction to weaker structural properties of the measure. This improves on recent work of Anari, Jain, Koehler, Pham, and Vuong [SODA'23] which gives distribution learning at higher temperature.
- As a simple byproduct of our techniques, logistic regression achieves an exponential improvement in learning from samples in the M-regime of data considered by Dutt, Lokhov, Vuffray, and Misra [ICML'21] as well as novel guarantees for learning from the adversarial Glauber dynamics of Chin, Moitra, Mossel, and Sandon [ArXiv'23].
Our approach thus significantly generalizes the elegant analysis of Wu, Sanghavi, and Dimakis [Neurips'19] without any algorithmic modification.
- Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence, with Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins.
Innovations in Theoretical Computer Science 2023 (ITCS 2023).
[Abstract] [PDF] [ITCS Talk]
We study the aggregate welfare and individual regret guarantees of dynamic pacing algorithms in the context of repeated auctions with budgets.
Such algorithms are commonly used as bidding agents in Internet advertising platforms.
We show that when agents simultaneously apply a natural form of
gradient-based pacing, the liquid welfare obtained over the course of the learning dynamics is at least half the optimal expected liquid welfare obtainable by any allocation rule.
Crucially, this result holds without requiring convergence of the dynamics,
allowing us to circumvent known complexity-theoretic obstacles of finding equilibria.
This result is also robust to the correlation structure between agent valuations and holds for any core auction, a broad class of auctions that includes first-price, second-price, and generalized second-price auctions. For individual guarantees, we further show such pacing algorithms enjoy dynamic regret bounds for individual value maximization, with respect to the sequence of budget-pacing bids, for any auction satisfying a monotone bang-for-buck property.
- Eigenstripping, Spectral Decay, and Edge-Expansion on Posets, with Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang.
International Conference on Randomization and Computation 2022 (RANDOM 2022).
[Abstract] [PDF]
Fast mixing of random walks on hypergraphs (simplicial complexes) has recently led to myriad breakthroughs throughout theoretical computer science. Many important applications, however, (e.g.\ to LTCs, 2-2 games) rely on a more general class of underlying structures called \emph{posets}, and crucially take advantage of non-simplicial structure. These works make it clear that the global expansion properties of posets depend strongly on their underlying architecture (e.g.\ simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different poset architectures in both a spectral and combinatorial sense, highlighting how \emph{regularity} controls the spectral decay and edge-expansion of corresponding random walks.
We show that the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha APPROX-RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the regularity of the underlying poset. This gives a simple condition to identify poset architectures (e.g. the Grassmann) that exhibit strong (even exponential) decay of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay linearly---a crucial distinction in applications to hardness of approximation and agreement testing such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight characterization of edge-expansion on expanding posets in the $\ell_2$-regime (generalizing recent work of Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization of expansion used in the proof of the 2-2 Games Conjecture which relies on $\ell_\infty$ rather than $\ell_2$-structure.
- Fractional Pseudorandom Generators from Any Fourier Level, with Eshan Chattopadhyay, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty.
Computational Complexity Conference 2021 (CCC 2021).
[Abstract] [PDF] [CCC Talk]
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [CHHL18, CHLT19] that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the $k$-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with $k$. This interpolates previous works, which either require Fourier bounds on all levels [CHHL18], or has polynomial dependence on the error parameter in the seed length [CHLT19], and thus answers an open question in [CHLT19]. As an example, we show that for polynomial error, Fourier bounds on the first $O(\log n)$ levels is sufficient to recover the seed length in [CHHL], which requires bounds on the entire tail.
We obtain our results by an alternate analysis of fractional PRGs using Taylor's theorem and bounding the degree-$k$ Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the $L_1$ notion in previous works. By generalizing a connection established in [CHHLZ20], we give a new reduction from constructing PRGs to proving correlation bounds.
Finally, using these improvements we show how to obtain a PRG for $\mathbb{F}_2$ polynomials with seed length close to the state-of-the-art construction due to Viola [Vio08].
- Virtues of Patience in Strategic Queuing Systems, with Éva Tardos.
The Twenty-Second ACM Conference on Economics and Computation (EC 21).
[Abstract] [PDF] [EC Talk]
We consider the problem of selfish agents in discrete-time queuing systems, where competitive queues try to get their packets served. In this model, a queue gets to send a packet each step to one of the servers, which will attempt to serve the oldest arriving packet, and unprocessed packets are returned to each queue. We model this as a repeated game where queues compete for the capacity of the servers, but where the state of the game evolves as the length of each queue varies, resulting in a highly dependent random process. In classical work for learning in repeated games, the learners evaluate the outcome of their strategy in each step---in our context, this means that queues estimate their success probability at each server. Earlier work by the authors [in EC'20]
shows that with no-regret learners the system needs twice the capacity as would be required in the coordinated setting to ensure queue lengths remain stable, despite the selfish behavior of the queues. In this paper, we demonstrate that this myopic way of evaluating outcomes is suboptimal: if more patient queues choose strategies that selfishly maximize their long-run success rate, stability can be ensured with just $\frac{e}{e-1}\approx 1.58$ times extra capacity, strictly better than what is possible assuming the no-regret property.
As these systems induce highly dependent random processes, our analysis draws heavily on techniques from the theory of stochastic processes to establish various game-theoretic properties of these systems. Though these systems are random even under any
fixed stationary policies by the queues, we show using careful probabilistic arguments that surprisingly, under such fixed policies, these systems have essentially deterministic and explicit asymptotic behavior. We show that the growth rate of a set can be written as the ratio of a submodular and modular function, and
use the resulting explicit description to show that the subsets of queues with largest growth rate is closed under union and non-disjoint intersections, which we use in turn to prove the claimed sharp bicriteria result for the equilibria of the resulting system. Our equilibrium analysis relies on a novel deformation argument towards a more analyzable
solution that is quite different from classical price of anarchy bounds. While the intermediate points in this deformation will not be Nash, the structure will ensure the relevant constraints and incentives similarly hold to establish monotonicity along this continuous path.
- Polarization in Geometric Opinion Dynamics, with Jon Kleinberg and Éva Tardos.
The Twenty-Second ACM Conference on Economics and Computation (EC 21).
[Abstract] [PDF] [EC Talk]
In light of increasing recent attention to political polarization, understanding how polarization can arise poses an important theoretical question. While more classical models of opinion dynamics seem poorly equipped to study this phenomenon, a recent novel approach by Hᶏz
la, Jin, Mossel, and Ramnarayan [HJMR20] proposes a simple geometric model of opinion evolution that provably exhibits strong polarization in specialized cases. Moreover, polarization arises quite organically in their model: in each time step, each agent updates opinions according to their correlation/response with an issue drawn at random. However, their techniques do not seem to extend beyond a set of special cases they identify, which benefit from fragile symmetry or contractiveness assumptions, leaving open how general this phenomenon really is.
In this paper, we further the study of polarization in related geometric models. We show that the exact form of polarization in such models is quite nuanced: even when strong polarization does not hold, it is possible for weaker notions of polarization to nonetheless attain. We provide a concrete example where weak polarization holds, but strong polarization provably fails. However, we show that strong polarization provably holds in many
variants of the HJMR model, which are also robust to a wider array of distributions of random issues---this suggests that the form of polarization introduced by HJMR is more universal than suggested by their special cases. We also show that the
weaker notions connect more readily to the theory of Markov chains on general state spaces.
- Stability and Learning in Strategic Queuing Systems, with Éva Tardos.
The Twenty-First ACM Conference on Economics and Computation (EC 20).
[Abstract] [PDF] [EC Talk]
Bounding the price of anarchy, which quantifies the damage to social welfare due to selfish behavior of the participants, has been an important area of research. In this paper, we study this phenomenon in the context of a game modeling queuing systems: routers compete for servers, where packets that do not get service will be resent at future rounds, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. We model this as an (infinitely) repeated game, where the system holds a state (number of packets held by each queue) that arises from the results of the previous round. We assume that routers satisfy the no-regret condition, e.g. they use learning strategies to identify the server where their packets get the best service.
Classical work on repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent (beyond the influence on learning from past history). The carryover effect caused by packets remaining in this system makes learning in our context result in a highly dependent random process. We analyze this random process and find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, and queues use no-regret learning algorithms, then the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. This paper is the first to study the effect of selfish learning in a queuing system, where the learners compete for resources, but rounds are not all independent: the number of packets to be routed at each round depends on the success of the routers in the previous rounds.
- Adversarial Perturbations of Opinion Dynamics in Networks, with Jon Kleinberg and Éva Tardos.
The Twenty-First ACM Conference on Economics and Computation (EC 20).
[Abstract] [PDF] [EC Talk]
We study the connections between network structure, opinion dynamics, and an adversary's power to artificially induce disagreements. We approach these questions by extending models of opinion formation in the social sciences to represent scenarios, familiar from recent events, in which external actors seek to destabilize communities through sophisticated information warfare tactics via fake news and bots. In many instances, the intrinsic goals of these efforts are not necessarily to shift the overall sentiment of the network, but rather to induce discord. These perturbations diffuse via opinion dynamics on the underlying network, through mechanisms that have been analyzed and abstracted through work in computer science and the social sciences. We investigate the properties of such attacks, considering optimal strategies both for the adversary seeking to create disagreement and for the entities tasked with defending the network from attack. We show that for different formulations of these types of objectives, different regimes of the spectral structure of the network will limit the adversary's capacity to sow discord; this enables us to qualitatively describe which networks are most vulnerable against these perturbations. We then consider the algorithmic task of a network defender to mitigate these sorts of adversarial attacks by insulating nodes heterogeneously; we show that, by considering the geometry of this problem, this optimization task can be efficiently solved via convex programming. Finally, we generalize these results to allow for two network structures, where the opinion dynamics process and the measurement of disagreement become uncoupled, and determine how the adversary's power changes; for instance, this may arise when opinion dynamics are controlled an online community via social media, while disagreement is measured along "real-world" connections.
Teaching