Vikram Kher

When can we learn from biased samples? We study regression when outcomes are observed only after passing through selection filters that depend on both covariates and outcomes themselves, a ubiquitous challenge spanning clinical trials with patient dropout, labor markets with self-selection, and auctions with strategic entry. Ignoring such selection yields systematically biased conclusions with real-world consequences.

This challenge has a long history in econometrics and statistics, starting with the seminal two-stage model of Heckman (1979) and followed by numerous generalizations, e.g., Lee (1982), Ahn and Powell (1993), and Das et al. (2003). While these works provide various sufficient conditions for identification, a complete characterization of when such regression is possible has remained elusive.

In this work, we provide a characterization for when regression is possible in the presence of sample selection bias. Our results establish the minimal assumptions required on the functional forms of selection processes under which regression remains possible, which are particularly relevant in modern settings where selection mechanisms are increasingly complex and opaque.

As a corollary of our characterization, we show that there are settings where the regression function can be identified even when the selection filter itself cannot. This observation already goes beyond the “estimate selection filter, then debias regression” paradigm that is followed by virtually all existing approaches.

Under natural strengthenings of our identification conditions, we also establish finite-sample estimation guarantees with explicit convergence rates and provide oracle-efficient algorithms. This yields the first general-purpose estimation method for this broad class of selection problems. Finally, we explore the implications of our results for several well-studied econometric settings with complex selection mechanisms such as auctions with entry costs and labor markets.

The remarkable success of machine learning (ML) in predictive tasks has led scientists to incorporate ML predictions as a core component of the scientific discovery pipeline. This was exemplified by the landmark achievement of AlphaFold (Jumper et al., 2021). In this paper, we study how ML predictions can be safely used in statistical analysis of data towards scientific discovery. In particular, we follow the framework introduced by Angelopoulos et al. (2023).

In this framework, we assume access to a small set of$n$ gold-standard labeled samples, a much larger set of$N$ unlabeled samples, and a ML model that can be used to impute the labels of the unlabeled data points. We introduce two new learning-augmented estimators: (1) Prediction-Augmented Residual Tree (PART), and (2) Prediction-Augmented Quadrature (PAQ). Both estimators have significant advantages over existing estimators like PPI and PPI++ introduced by Angelopoulos et al. (2023) and Angelopoulos et al. (2024), respectively.

PART is a decision-tree based estimator built using a greedy criterion. We first characterize PART’s asymptotic distribution and demonstrate how to construct valid confidence intervals. Then we show that PART outperforms existing methods in real-world datasets from ecology, astronomy, and census reports, among other domains. This leads to estimators with higher confidence, which is the result of using both the gold-standard samples and the machine learning predictions.

Finally, we provide a formal proof of the advantage of PART by exploring PAQ, an estimation that arises when considering the limit of PART when the depth its tree grows to infinity. Under appropriate assumptions in the input data we show that the variance of PAQ shrinks at rate of $O(N^{-1}+n^{-4})$, improving significantly on the$O(N^{-1}+n^{-1})$ rate of existing methods.

When can the distributional assumptions of theorems and learning algorithms be trusted? Inspired by this question, Rubinfeld and Vasilyan (2023) initiated the study of testable learning. In this schema, we always learn one of the following two things: either we have achieved the desired accuracy regardless of whether the distributional assumptions are satisfied, or the input distribution does not satisfy the original distributional assumptions. Motivated by the challenge of relying on strong distributional assumptions in many theorems in mechanism design, we develop a testable learning framework for mechanism design. Traditional models in mechanism design assume that value distributions satisfy some notion of regularity. Unfortunately, testing regularity is not possible in the original testable learning framework as we show. To bypass this impossibility, we propose a regularized version of the testable learning framework. Under this framework, we always learn one of the following two things: either we achieve high revenue compared to the best possible revenue of any regular distribution close to the input distribution, or the input distribution does not satisfy regularity. We then use this framework to provide: 1) a tester-learner pair for revenue optimal mechanisms, 2) a tester for whether the fundamental Bulow-Klemperer Theorem (Bulow and Klemperer, 1996) is applicable to a given dataset, and 3) a tester to confirm the existence of an anonymous reserve price that results in the anonymous price auction securing a constant fraction of the optimal revenue.

We introduce a novel definition for a small set$R$ of$k$ points being representative of a larger set in a metric space. Given a set$V$ (e.g., documents or voters) to represent, and a set$C$ of possible representatives, our criterion requires that for any subset$S$ comprising a$\theta$ fraction of $V$, the average distance of$S$ to their best$\theta \cdot k$ points in$R$ should not be more than a factor$\gamma$ compared to their average distance to the best$\theta \cdot k$ points among all of $C$. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size.

Since there are instances for which - unless$\gamma$ is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set$R$ of size$k$ as though its size were only $k/\alpha$, for $\alpha > 1$. Furthermore, motivated by the application to elections, we mostly focus on the ordinal model, where the algorithm does not learn the actual distances; instead, it learns only for each point$v$ in$V$ and each candidate pairs$c, c'$ which of$c, c'$ is closer to $v$. Our main result is that the Expanding Approvals Rule of Aziz and Lee is$(\alpha, \gamma)$ representative with $\gamma \leq 1 + 6.71 \cdot \frac{\alpha}{\alpha-1}$.

Our results lead to three notable byproducts. First, we show that the Expanding Approvals Rule achieves constant proportional fairness in the ordinal model, giving the first positive result on metric proportional fairness with ordinal information. Second, we show that for the core fairness objective, the Expanding Approvals Rule achieves the same asymptotic tradeoff between resource augmentation and approximation as the recent results of Li et al., which used full knowledge of the metric. Finally, our results imply a very simple single-winner voting rule with metric distortion at most 44.

Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model, it is known that optimal mechanisms can yield revenue infinitely higher than that of any “simple” mechanism—the ones with size polynomial in the number of items—even with just two items and a single buyer (Briest et al., 2015; Hart and Nisan, 2017).

We introduce a new parameterized class of mechanisms, buy-$k$ mechanisms, which smoothly interpolate between the classical buy-one mechanisms and the recently studied buy-many mechanisms (Chawla et al., 2022, 2019, 2020a, 2020b). Buy-$k$ mechanisms allow the buyer to buy up to$k$ many menu options. We show that restricting the seller to the class of buy-$n$ incentive-compatible mechanisms suffices to overcome the bizarre, infinite revenue properties of the buy-one model. Our main result is that the revenue gap with respect to bundling, an extremely simple mechanism, is bounded by$O(n^2)$ for any arbitrarily correlated distribution$\mathcal{D}$ over$n$ items for the case of an additive buyer. Our techniques also allow us to prove similar upper bounds for arbitrary monotone valuations, albeit with an exponential factor in the approximation.

On the negative side, we show that allowing the buyer to purchase a small number of menu options does not suffice to guarantee sub-exponential approximations, even when we weaken the benchmark to the optimal buy-$k$ deterministic mechanism. If an additive buyer is only allowed to buy$k = \Theta(n^{1/2-\varepsilon})$ many menu options, the gap between the revenue-optimal deterministic buy-$k$ mechanism and bundling may be exponential in $n$. In particular, this implies that no “simple” mechanism can obtain a sub-exponential approximation in this regime. As a complementary result, we show that when $k \geq \sqrt{n}$, bundling recovers a$\operatorname{poly}(n)$ fraction of the optimal deterministic buy-$k$ mechanism’s revenue.

Predictors of the need for intensive care and mechanical ventilation can help healthcare systems in planning for surge capacity for COVID-19. We used socio-demographic data, clinical data, and blood panel profile data at the time of initial presentation to develop machine learning algorithms for predicting the need for intensive care and mechanical ventilation. Among the algorithms considered, the Random Forest classifier performed the best with$\text{AUC} = 0.80$ for predicting ICU need and$\text{AUC} = 0.82$ for predicting the need for mechanical ventilation. We also determined the most influential features in making this prediction, and concluded that all three categories of data are important. We determined the relative importance of blood panel profile data and noted that the AUC dropped by 0.12 units when this data was not included, thus indicating that it provided valuable information in predicting disease severity. Finally, we generated RF predictors with a reduced set of five features that retained the performance of the predictors trained on all features. These predictors, which rely only on quantitative data, are less prone to errors and subjectivity.