NHNika Haghtalab

Nika Haghtalab

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Nika Haghtalab has a total of 37 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Learning in Stackelberg Games with Non-myopic Agents

    by Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, Alexander Wei

    New Framework for Learning Against Long-Lived, Forward-Looking Agents Repeated Stackelberg games are a canonical model for strategic principal-agent interactions. Learning in these games is well studied against myopic agents who greedily maximize their per-round payoff. However, complications arise with nonmyopic agents because they may strategically deviate from best responding to mislead the principal. In “Learning in Stackelberg Games with Nonmyopic Agents,” Haghtalab, Lykouris, Nietert, and Wei provide a general framework that reduces learning in the presence of nonmyopic agents to robust bandit optimization against myopic agents. This leads to a challenge of designing minimally reactive bandit algorithms, which balance the statistical efficiency of the principal’s learning algorithm against its effectiveness at inducing near-best responses. The authors tackle this challenge across problem domains, including security games, dynamic pricing, and strategic classification. Along the way, they uncover a structural property for learning in security games, enabling them to improve the state-of-the-art query complexity with n targets from [ ] to a near-optimal [ ].

  • Open Access

    Leakage-Robust Bayesian Persuasion

    by Nika Haghtalab, Mingda Qiao, Kunhe Yang


  • Open Access

    Smoothed Analysis with Adaptive Adversaries

    by Nika Haghtalab, Tim Roughgarden, Abhishek Shetty

    We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time step an adversary chooses an input distribution with density function bounded above pointwise by \(\tfrac{1}{\sigma }\) times that of the uniform distribution; nature then samples an input from this distribution. Here, σ is a parameter that interpolates between the extremes of worst-case and average case analysis. Crucially, our results hold for adaptive adversaries that can base their choice of input distribution on the decisions of the algorithm and the realizations of the inputs in the previous time steps. An adaptive adversary can nontrivially correlate inputs at different time steps with each other and with the algorithm’s current state; this appears to rule out the standard proof approaches in smoothed analysis. This paper presents a general technique for proving smoothed algorithmic guarantees against adaptive adversaries, in effect reducing the setting of an adaptive adversary to the much simpler case of an oblivious adversary (i.e., an adversary that commits in advance to the entire sequence of input distributions). We apply this technique to prove strong smoothed guarantees for three different problems: (1) Online learning: We consider the online prediction problem, where instances are generated from an adaptive sequence of σ-smooth distributions and the hypothesis class has VC dimension d . We bound the regret by \(\tilde{O}(\sqrt {T d\ln (1/\sigma)} + d\ln (T/\sigma))\) and provide a near-matching lower bound. Our result shows that under smoothed analysis, learnability against adaptive adversaries is characterized by the finiteness of the VC dimension. This is as opposed to the worst-case analysis, where online learnability is characterized by Littlestone dimension (which is infinite even in the extremely restricted case of one-dimensional threshold functions). Our results fully answer an open question of Rakhlin et al. [ 64 ]. (2) Online discrepancy minimization: We consider the setting of the online Komlós problem, where the input is generated from an adaptive sequence of σ-smooth and isotropic distributions on the ℓ 2 unit ball. We bound the ℓ ∞ norm of the discrepancy vector by \(\tilde{O}(\ln ^2(\frac{nT}{\sigma }))\) . This is as opposed to the worst-case analysis, where the tight discrepancy bound is \(\Theta (\sqrt {T/n})\) . We show such \(\mathrm{polylog}(nT/\sigma)\) discrepancy guarantees are not achievable for non-isotropic σ-smooth distributions. (3) Dispersion in online optimization: We consider online optimization with piecewise Lipschitz functions where functions with ℓ discontinuities are chosen by a smoothed adaptive adversary and show that the resulting sequence is \(({\sigma }/{\sqrt {T\ell }}, \tilde{O}(\sqrt {T\ell }))\) -dispersed. That is, every ball of radius \({\sigma }/{\sqrt {T\ell }}\) is split by \(\tilde{O}(\sqrt {T\ell })\) of the partitions made by these functions. This result matches the dispersion parameters of Balcan et al. [ 13 ] for oblivious smooth adversaries, up to logarithmic factors. On the other hand, worst-case sequences are trivially (0, T )-dispersed. 1


  • Open Access

    On-Demand Sampling: Learning Optimally from Multiple Distributions

    by Nika Haghtalab, Michael I. Jordan, Eric Zhao

    Social and real-world considerations such as robustness, fairness, social welfare and multi-agent tradeoffs have given rise to multi-distribution learning paradigms, such as collaborative learning, group distributionally robust optimization, and fair federated learning. In each of these settings, a learner seeks to uniformly minimize its expected loss over $n$ predefined data distributions, while using as few samples as possible. In this paper, we establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Importantly, our sample complexity bounds for multi-distribution learning exceed that of learning a single distribution by only an additive factor of $n \log(n) / \epsilon^2$. This improves upon the best known sample complexity bounds for fair federated learning by Mohri et al. and collaborative learning by Nguyen and Zakynthinou by multiplicative factors of $n$ and $\log(n)/\epsilon^3$, respectively. We also provide the first sample complexity bounds for the group DRO objective of Sagawa et al. To guarantee these optimal sample complexity bounds, our algorithms learn to sample from data distributions on demand. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving stochastic zero-sum games. In particular, we contribute stochastic variants of no-regret dynamics that can trade off between players' differing sampling costs.

  • Open Access

    Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty

    by Wenshuo Guo, Nika Haghtalab, Kirthevasan Kandasamy, Ellen Vitercik

  • Open Access

    Smoothed Analysis of Online Non-parametric Auctions

    by Naveen Durvasula, Nika Haghtalab, Manolis Zampetakis

    Online learning of revenue-optimal auctions is a fundamental problem in mechanism design without priors. Nevertheless, all the existing positive results assume that the auctioneer optimizes over a parameterized class of auctions, such as pricings and auctions with reserves. This is perhaps not surprising given that natural correlations that occur in online sequences pose a challenge to characterizing a succinct class of revenue-optimal auctions. This has left behind a significant gap in our understanding of online-learnability of general classes of non-parametric auctions. We provide the first positive results for online learnability of a non-parametric auction class, for smooth adversaries and the class of smooth auctions. In a nutshell, an online adversary is smooth (in the style of Smoothed analysis [Spielman and Teng, 2004] in online learning [Haghtalab et al., 2021]) if the bid distribution has bounded density at every time step, and an auction is smooth if the level sets of its revenue function have small boundaries. We prove the following fundamental guarantees: (1) Revenue maximization in the class of smooth auctions is online-learnable, against smooth adversaries. (2) It is impossible to construct a no-regret algorithm even for the class of smooth auctions against worst-case adversaries. (3) It is impossible to construct a no-regret algorithm for the class of all incentive-compatible auctions even against smooth adversaries. This gives a strong characterization of when and which class of non-parametric auctions are online-learnable. To illustrate the generality of the class of smooth auctions we show that it contains the class of all monotone-revenue auctions, as well as, the class of all competition-monotone auctions. This brings up an interesting observation: while independence across bids leads to the optimal auctions being monotone, significantly weaker assumptions, compared to monotonicity of revenue, are sufficient for learnability.


  • Open Access

    Competition, Alignment, and Equilibria in Digital Marketplaces

    by Meena Jagadeesan, Michael I. Jordan, Nika Haghtalab

    Competition between traditional platforms is known to improve user utility by aligning the platform's actions with user preferences. But to what extent is alignment exhibited in data-driven marketplaces? To study this question from a theoretical perspective, we introduce a duopoly market where platform actions are bandit algorithms and the two platforms compete for user participation. A salient feature of this market is that the quality of recommendations depends on both the bandit algorithm and the amount of data provided by interactions from users. This interdependency between the algorithm performance and the actions of users complicates the structure of market equilibria and their quality in terms of user utility. Our main finding is that competition in this market does not perfectly align market outcomes with user utility. Interestingly, market outcomes exhibit misalignment not only when the platforms have separate data repositories, but also when the platforms have a shared data repository. Nonetheless, the data sharing assumptions impact what mechanism drives misalignment and also affect the specific form of misalignment (e.g. the quality of the best-case and worst-case market outcomes). More broadly, our work illustrates that competition in digital marketplaces has subtle consequences for user utility that merit further investigation.

  • Open Access

    Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries

    by Nika Haghtalab, Yanjun Han, Abhishek Shetty, Kunhe Yang

    In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning. We focus on two settings. First, the smoothed analysis setting of [RST11,HRS22] where an adversary is constrained to generating samples from distributions whose density is upper bounded by $1/\sigma$ times the uniform density. Second, the setting of $K$-hint transductive learning, where the learner is given access to $K$ hints per time step that are guaranteed to include the true instance. We give the first known oracle-efficient algorithms for both settings that depend only on the pseudo (or VC) dimension of the class and parameters $\sigma$ and $K$ that capture the power of the adversary. In particular, we achieve oracle-efficient regret bounds of $ \widetilde{O} ( \sqrt{T d\sigma^{-1}} ) $ and $ \widetilde{O} ( \sqrt{T dK} ) $ for learning real-valued functions and $ O ( \sqrt{T d\sigma^{-\frac{1}{2}} } )$ for learning binary-valued functions. For the smoothed analysis setting, our results give the first oracle-efficient algorithm for online learning with smoothed adversaries [HRS22]. This contrasts the computational separation between online learning with worst-case adversaries and offline learning established by [HK16]. Our algorithms also achieve improved bounds for worst-case setting with small domains. In particular, we give an oracle-efficient algorithm with regret of $O ( \sqrt{T(d |\mathcal{X}|)^{1/2} })$, which is a refinement of the earlier $O ( \sqrt{T|\mathcal{X}|})$ bound by [DS16].

  • Open Access

    Learning in Stackelberg Games with Non-myopic Agents

    by Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, Alex Wei

    We study Stackelberg games where a principal repeatedly interacts with a long-lived, non-myopic agent, without knowing the agent's payoff function. Although learning in Stackelberg games is well-understood when the agent is myopic, non-myopic agents pose additional complications. In particular, non-myopic agents may strategically select actions that are inferior in the present to mislead the principal's learning algorithm and obtain better outcomes in the future. We provide a general framework that reduces learning in presence of non-myopic agents to robust bandit optimization in the presence of myopic agents. Through the design and analysis of minimally reactive bandit algorithms, our reduction trades off the statistical efficiency of the principal's learning algorithm against its effectiveness in inducing near-best-responses. We apply this framework to Stackelberg security games (SSGs), pricing with unknown demand curve, strategic classification, and general finite Stackelberg games. In each setting, we characterize the type and impact of misspecifications present in near-best-responses and develop a learning algorithm robust to such misspecifications. Along the way, we improve the query complexity of learning in SSGs with $n$ targets from the state-of-the-art $O(n^3)$ to a near-optimal $\widetilde{O}(n)$ by uncovering a fundamental structural property of such games. This result is of independent interest beyond learning with non-myopic agents.

  • Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries

    by Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, Ankit Sharma

    We study the stochastic matching problem with the goal of finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic k-cycle packing, in which the problem is to find a maximum packing of cycles, each of which exists with some probability. We provide polynomial-time adaptive and nonadaptive algorithms that provably yield a near-optimal solution, using a number of edge queries that is linear in the number of vertices. We are especially interested in kidney exchange, with which pairs of patients with end-stage renal failure and their willing but incompatible donors participate in a mechanism that performs compatibility tests between patients and donors and swaps the donors of some patients so that a large number of patients receive compatible kidneys. Because of the significant cost of performing compatibility tests, currently, kidney exchange programs perform at most one compatibility test per patient. Our theoretical results applied to kidney exchange show that, by increasing the number of compatibility tests performed per patient from one to a larger constant, we effectively get the full benefit of exhaustive testing at a fraction of the cost. We show, on both generated and real data from the UNOS nationwide kidney exchange, that even a small number of nonadaptive edge queries per vertex results in large gains in expected successful matches.