Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond

Alkis Kalavasis, Anay Mehrotra, Felix Zhou

Abstract

We revisit the problem of estimating $k$ linear regressors with self-selection bias in $d$ dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC'23]. Our main result is a $\operatorname{poly}(d,k,1/\varepsilon) + {k}^{O(k)}$ time algorithm for this problem, which yields an improvement in the running time of the algorithms of [CDIZ23] and [GM24, arXiv]. We achieve this by providing the first local convergence algorithm for self-selection, thus resolving the main open question of [CDIZ23]. To obtain this algorithm, we reduce self-selection to a seemingly unrelated statistical problem called coarsening. Coarsening occurs when one does not observe the exact value of the sample but only some set (a subset of the sample space) that contains the exact value. Inference from coarse samples arises in various real-world applications due to rounding by humans and algorithms, limited precision of instruments, and lag in multi-agent systems. Our reduction to coarsening is intuitive and relies on the geometry of the self-selection problem, which enables us to bypass the limitations of previous analytic approaches. To demonstrate its applicability, we provide a local convergence algorithm for linear regression under another self-selection criterion, which is related to second-price auction data. Further, we give the first polynomial time local convergence algorithm for coarse Gaussian mean estimation given samples generated from a convex partition. Previously, only a sample-efficient algorithm was known due to Fotakis, Kalavasis, Kontonis, and Tzamos [FKKT21, COLT'21].

Introduction

Self-selection bias is a pervasive issue in statistical analysis, occurring when the observed data is influenced by the choices of the subjects being studied. A classic example is the "fisherman problem": an analyst wishes to understand how various factors influence the income of different professions (e.g., hunters, fishermen, woodcutters). However, individuals typically choose the profession that offers them the highest income. Consequently, the analyst only observes the maximum income achieved across potential choices, rather than the counterfactual outcomes for each profession.

Technically, this involves estimating $k$ linear regressors $w^*_1, \dots, w^*_k$ from observations $y_{max} = \max_i \{x^\top w^*_i + \xi_i\}$. Previous algorithmic approaches suffered from exponential runtime dependencies on precision ($\epsilon^{-k}$), making high-precision estimation computationally intractable for even small $k$.

Methodology: From Selection to Coarsening

The core innovation of this work is a geometric reduction of self-selection to a statistical problem known as coarsening. Coarsening occurs when an exact sample is not observed; instead, one observes a subset of the sample space (a "coarse" label) containing the sample.

Examples of partitions in coarsening problems, including convex partitions and regions defined by selection criteria.

The authors demonstrate that the "maximum" operator effectively partitions the $k$-dimensional space into specific "L-shaped" regions. By analyzing these partitions, they prove that these regions preserve sufficient information to identify the underlying parameters. Specifically, the true parameters are shown to be the unique local minimizers of the Negative Log-Likelihood (NLL) objective.

Local Convexity and Convergence

The primary technical challenge in using gradient-based methods for this problem is the non-convex nature of the global NLL landscape, which contains multiple local minima due to the permutation symmetry of the $k$ regressors. However, the authors prove that the NLL objective is locally convex in a neighborhood around the ground truth.

The NLL objective $f(x)$ exhibits local convexity near the global minimum, despite potential non-convexity elsewhere in the landscape.

This local "bowl-shaped" geometry allows for the application of Projected Stochastic Gradient Descent (PSGD). Given a "warm start" (a rough initial estimate), PSGD can efficiently converge to the exact parameters. Notably, the radius of this convex region depends on $k$ but is independent of the feature dimension $d$, ensuring scalability for high-dimensional problems.

Key Results

The proposed algorithm achieves a runtime of $\operatorname{poly}(d, k, 1/\epsilon) + k^{O(k)}$, a significant improvement over the previous $\epsilon^{-k}$ dependency. This shift from exponential to polynomial time with respect to precision $\epsilon$ resolves a major open question in the field. Furthermore, the algorithm maintains optimal sample complexity of $O(d) \cdot \operatorname{poly}(k, 1/\epsilon)$.

Beyond the "max" criterion, the framework extends to other self-selection models, such as second-price auction data, and provides the first polynomial-time local convergence algorithm for coarse Gaussian mean estimation under convex partitions.

Conclusion and Future Work

While this work provides a robust local convergence theory, several challenges remain. The requirement for a "warm start" means that global convergence in polynomial time is still an open problem. Additionally, extending these results to non-Gaussian noise distributions and exploring other types of structured non-convex partitions are promising avenues for future research.

Summary updated

Abstract

We revisit the problem of estimating $k$ linear regressors with self-selection bias in $d$ dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC'23]. Our main result is a $\operatorname{poly}(d,k,1/\varepsilon) + {k}^{O(k)}$ time algorithm for this problem, which yields an improvement in the running time of the algorithms of [CDIZ23] and [GM24, arXiv]. We achieve this by providing the first local convergence algorithm for self-selection, thus resolving the main open question of [CDIZ23]. To obtain this algorithm, we reduce self-selection to a seemingly unrelated statistical problem called coarsening. Coarsening occurs when one does not observe the exact value of the sample but only some set (a subset of the sample space) that contains the exact value. Inference from coarse samples arises in various real-world applications due to rounding by humans and algorithms, limited precision of instruments, and lag in multi-agent systems. Our reduction to coarsening is intuitive and relies on the geometry of the self-selection problem, which enables us to bypass the limitations of previous analytic approaches. To demonstrate its applicability, we provide a local convergence algorithm for linear regression under another self-selection criterion, which is related to second-price auction data. Further, we give the first polynomial time local convergence algorithm for coarse Gaussian mean estimation given samples generated from a convex partition. Previously, only a sample-efficient algorithm was known due to Fotakis, Kalavasis, Kontonis, and Tzamos [FKKT21, COLT'21].
BibTeX
@misc{kalavasis2025can,
  author = {Alkis Kalavasis and Anay Mehrotra and Felix Zhou},
  title = {{Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond}},
  year = {2025},
  eprint = {2504.07133},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.07133},
}
Figure