Statistics Theory · arXiv:2611.17228 v1 · submitted 12 Nov 2026 · 32 references
Linear Regression with Self-Selection Bias in Polynomial Time
The paper says
“We revisit the problem of estimating k linear regressors with self-selection bias in n dimensions up to error ε with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC].”
more of the abstract
Our main result is a poly(n,k,1/ε) time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on k. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on k. Prior works exhaustively search over a k-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-(logn) Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
The passes disagreed. Reader: holds up. Skeptic: holds up only with conditions. Referee: major revision.
First polynomial-time algorithm for unknown-index maximum self-selection and max-affine regression; the main claim holds under the stated fixed-constant B,Δ regime, and the paper deserves a serious referee. This line is wrong
5 major objections · 8 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 32 references say.
The paper says, at Theorem 1.3, Hyperparameters 4.1, line b62
The review did not quote this passage.
A classifier read this sentence of the paper as acknowledging the concern (probability 0.62):
“We will also treat B, ∆ as absolute constants that disappears in the big-O notation.”
Pith says: Objection 1 of 5 · major
The running time is eO((nk/ε)^{poly(B/Δ)} log(1/δ)). The exponent poly(B/Δ) is never explicitly bounded; it is only said to be a 'sufficiently large constant depending only on the geometric quantities' (Hyperparameters 4.1). The paper treats B and Δ as absolute constants that 'disappear in the big-O notation' (line b62).
more of objection 1
However, if B and Δ are part of the problem instance and not fixed constants, the exponent could be arbitrarily large, and the algorithm would not be polynomial in the usual sense. The paper acknowledges this implicitly (line b62), but this is a critical limitation: the algorithm is only polynomial if B and Δ are fixed constants, not if they are input parameters. The problem definition (Definition 1.1) does not fix B and Δ; they are introduced in Assumption 1.2 as 'absolute constants'. The claim of 'polynomial time' is therefore only valid under the interpretation that B and Δ are absolute constants, which is not standard for a problem where the instance includes the regressors. This should be clarified: either the algorithm is polynomial in n, k, 1/ε, and also in B and Δ (i.e., poly(n,k,1/ε,B,Δ)), or the exponent poly(B/Δ) is actually a fixed constant independent of the instance. The paper's own wording suggests the latter, but the hyperparameters K = 16(1+B^2)^3/Δ^4 and s = K^4 log n make the exponent depend on B and Δ polynomially, which is not a constant. This is a load-bearing issue for the central claim of polynomial time.
The paper says, at Section 5, Theorem 5.1, Lemma 5.4, Lemma 5.7, Lemma 5.8, Lemma 5.9
The review did not quote this passage.
Pith says: Objection 2 of 5 · major
The proof of Theorem 5.1 relies on several lemmas that use the hyperparameters K, T, s chosen in Hyperparameters 4.1. These choices depend on B and Δ. The bounds in Theorem 5.1(ii) and (iii) involve K and s, which are functions of B and Δ.
more of objection 2
The near-orthogonality bound in Theorem 5.1(iii) is e^{-s/K} = e^{-K^3 log n}, which is super-polynomially small in n but still depends on K. The error bounds in Theorem 5.1(i) involve e^{8s log K - T^2/(2K)}. With T = 2K^2 sqrt(s) and s = K^4 log n, this becomes e^{8K^4 log n log K - 2K^3 sqrt(K^4 log n)} = e^{O(K^4 log n log K) - Omega(K^5 sqrt(log n))}. For large K, the negative term dominates, but the exponent still depends on K. The paper's claim that the error is 'negligible' is justified by the choice of hyperparameters, but the dependence on B and Δ through K is not made explicit in the final complexity. This is related to the first major comment: the polynomial dependence on B and Δ is hidden in the exponent.
The paper says, at Section 6.2, Theorem 6.3, sample complexity
The review did not quote this passage.
Pith says: Objection 3 of 5 · major
The sample complexity of EstimateProjectedMoments is stated as eO((nk)^{O(K^{10})} log(1/δ)). Since K = poly(B/Δ), this is eO((nk)^{poly(B/Δ)} log(1/δ)). The exponent poly(B/Δ) is not explicitly bounded; it is only said to be a 'sufficiently large constant'. This makes the algorithm's polynomial-time claim dependent on B and Δ being fixed constants.
more of objection 3
If B and Δ are part of the input, the algorithm is not polynomial in the usual sense. The paper should either provide an explicit bound on the exponent in terms of B and Δ, or clarify that the algorithm is polynomial only when B and Δ are absolute constants (i.e., not part of the input).
The paper says, at Section 7, Theorem 7.1, sample complexity
The review did not quote this passage.
Pith says: Objection 4 of 5 · major
The sample complexity of RestrictedLeastSquares is eO((nk/ε)^{5K^2} log(1/δ)). Again, K = poly(B/Δ), so the exponent depends on B and Δ. This is consistent with the overall complexity, but the same caveat applies.
The paper says, at Section 9, Proof of Theorem 1.3, line b625
The review did not quote this passage.
Pith says: Objection 5 of 5 · major
The proof assumes that the recovered regressors have estimation error at most e^{-K^6 s}. This is used to satisfy the input accuracy requirement of ImplicitTensorDecomposition. However, the algorithm's own refinement step (RestrictedLeastSquares) is called with accuracy ε_int = min{ε, e^{-K^6 s}}.
more of objection 5
This creates a circular dependence: the decomposition requires accuracy e^{-K^6 s}, which is achieved by the refinement, but the refinement itself requires the decomposition to provide unit vectors with error at most Δ^2/(16B^2). This is not circular because the decomposition only needs rough unit vectors (error Δ^2/(16B^2)), not the high accuracy e^{-K^6 s}. The high accuracy is only needed for the recovered regressors to be used in the peeling step of the next round. The paper should clarify this point to avoid confusion.
8 minor objections
The paper says, at Abstract, line b1
Pith says: minor objection 1 of 8
The abstract states 'poly(n,k,1/ε) time algorithm' but the theorem states eO((nk/ε)^{poly(B/Δ)} log(1/δ)). The abstract should qualify that the polynomial depends on B and Δ.
The paper says, at Section 1.1, Theorem 1.3
Pith says: minor objection 2 of 8
The theorem statement uses eO notation but does not define it. It should be defined earlier or in the preliminaries.
show 6 more
The paper says, at Section 4.1, Hyperparameters 4.1
Pith says: minor objection 3 of 8
The hyperparameters K, s, T, ε_int, Γ are defined in terms of B, Δ, n, ε. The choice of K = 16(1+B^2)^3/Δ^4 is explicit, but the paper later treats K as a 'sufficiently large constant'. This is fine, but the dependence on B and Δ should be made clear in the complexity statements.
The paper says, at Section 5, Theorem 5.1
Pith says: minor objection 4 of 8
The theorem statement is dense and spans multiple pages. It would be helpful to include a brief summary of the key bounds in the main text, with the full details in the appendix.
The paper says, at Section 6.2.1, Equation (49)
Pith says: minor objection 5 of 8
The recursion for Cr+1 is given as Cr+1 = V_{r+1} (C_r ⊗ I_n). It should be clarified that V_{r+1} is a matrix of eigenvectors, and the product is a matrix multiplication.
The paper says, at Section 8.1.1, Equation (108)
Pith says: minor objection 6 of 8
The definition of ω_R uses F_R(T+1|X) - F_R(T|X). It should be noted that this is the conditional probability that Y_{max,R} ∈ [T, T+1] given X.
The paper says, at Appendix A, Proposition A.5
Pith says: minor objection 7 of 8
The reference [Han22, Theorem 5.8(6),(8)] is for a truncated Gaussian second moment. The proposition states that for a nondegenerate Gaussian with mean ≤ 0, E[G^2 1_{G>0}] ≤ Var(G) P(G>0). This is a known inequality, but the reference should be verified.
This objection may describe the copy Pith gave the reviewer, not the paper.
The paper says, at General
Pith says: minor objection 8 of 8
The paper uses many acronyms (OLS, RLS, GMM, etc.) that are defined but could be listed in a notation table for convenience.
What would settle it
Re-express the running time bound with explicit dependence on B and Delta, not hiding them in the exponent. Compute the exponent poly(B/Delta) explicitly (e.g., from Hyperparameters 4.1: K = 16(1+B^2)^3/Delta^4, so poly(B/Delta) includes terms like (B/Delta)^{O(1)}). Then check whether the algorithm remains polynomial in n,k,1/eps when B and Delta are allowed to grow polynomially with n,k,1/eps. If the exponent grows with B and Delta, the algorithm is not polynomial in the usual sense.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up
- Skeptic agrees: says it holds up only with conditions The algorithm's polynomial-time guarantee depends on B and Delta being absolute constants, but the exponent poly(B/Delta) is not explicitly bounded and could be enormous, making the 'polynomial' claim potentially misleading.
- Editor wrote the verdict above
- Referee major revision: 5 major objections, 8 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
I read the whole thing, and I think this is the real result: first poly(n,k,1/ε) time for unknown-index maximum self-selection, and the first polynomial-time algorithm for max-affine regression at ρ=1. The new idea is the restricted Hermite moment decomposition: conditioning on a large response makes the degree-logn covariate moment look like a weighted sum of tensor powers of the regressors, up to a controlled remainder. From there the iterative projections, observable-operator step, and peeling recursion are assembled carefully. The proof chain is explicit, the constants are fixed in Hyperparameters 4.1, and I found no circularity and no fitting-to-data. I did not find a concrete mathematical error.
The stress-test note worries that treating B and Δ as absolute constants is a sleight of hand. I disagree with the strength of that charge. The paper states Assumption 1.2 with B, Δ as absolute constants, and the runtime is Õ((nk/ε)poly(B/Δ) log(1/δ)). So the claim is literally true in the stated model: polynomial in n, k, and 1/ε when B and Δ are fixed. If you instead treat B and Δ as input parameters, the algorithm is not polynomial in them, and the exponent could be enormous. That is a genuine limitation and should be stated clearly in the abstract, but the authors flag it in b62, and it is standard in this literature. I would not call it load-bearing.
The more serious soft spot is verification burden. The proof is long; several steps are compressed as "by choice of hyperparameters" with details deferred to appendices, and there is no code or formalization. That lowers my confidence from high to moderate, not because I see an error, but because the chain is too long to fully certify by reading once. The subset-recovery structure (the authors acknowledge it in b54, b173, b447) makes the algorithm more intricate than a single tensor-decomposition call, and the peeling recursion depends on error bounds staying below thresholds across rounds.
Citation pattern is fine: prior algorithms are cited as baselines, borrowed tools are credited, and the self-citations are related work. Who gets value from this: researchers in algorithmic statistics, self-selection, max-affine regression, and implicit tensor methods. It is a substantial advance in that subarea. I would bring it to reading group and I would send it to peer review. My own verdict would be accept, subject to a careful proof check by someone willing to verify the appendix bounds.
The strongest objection
The paper's central claim is a poly(n,k,1/eps) time algorithm. However, the running time is eO((nk/eps)^{poly(B/Delta)} log(1/delta)). The exponent poly(B/Delta) is never explicitly bounded; it is only said to be a 'sufficiently large constant depending only on the geometric quantities' (Hyperparameters 4.1). The paper treats B and Delta as absolute constants that 'disappear in the big-O notation' (line b62), but this is a sleight of hand: if B and Delta are not fixed but part of the problem instance, the exponent could be arbitrarily large, and the algorithm would not be polynomial in the usual sense. The paper acknowledges this implicitly (line b62: 'We will also treat B, Delta as absolute constants that disappears in the big-O notation'), but this is a critical limitation: the algorithm is only polynomial if B and Delta are fixed constants, not if they are input parameters. The reader's weakest_assumption correctly identifies this, but the verdict ACCEPT does not flag this as a load-bearing concern. The paper's own sentences (b39-b40) state Assumption 1.2 with constants B and Delta, but the algorithm's dependence on them is not polynomial in the usual sense; it is exponential in poly(B/Delta). This is a genuine concern because the problem definition does not fix B and Delta; they are part of the input. The paper's claim of 'polynomial time' is therefore only valid under the interpretation that B and Delta are absolute constants, which is not standard for a problem where they are parameters. This is not a minor oversight; it is a fundamental issue with the claim's interpretation.
The reader's weakest_assumption correctly identifies that the algorithm's polynomial dependence relies on B and Delta being fixed constants. However, the reader's verdict ACCEPT does not flag this as a load-bearing concern; it merely notes it as an acknowledged limitation. I argue that this is a load-bearing concern because the central claim of polynomial time is ambiguous: if B and Delta are part of the input, the algorithm is not polynomial in the usual sense. The paper's own treatment (line b62) says 'We will also treat B, Delta as absolute constants that disappears in the big-O notation,' which is a significant caveat that undermines the generality of the polynomial-time claim. The concrete test would settle whether the algorithm is truly polynomial when B and Delta are not fixed. Therefore, the verdict should be CONDITIONAL: the paper's claim is valid only under the interpretation that B and Delta are absolute constants, which should be explicitly stated as a condition. The paper does not state this condition clearly; it only says 'absolute constants' in the overview, but the theorem statement (Theorem 1.3) does not specify that B and Delta are fixed. This is a genuine concern that warrants a conditional acceptance.
The referee's report
If correct, this result resolves a significant open problem: obtaining polynomial time for self-selection regression with unknown index, improving on prior exponential-in-k algorithms. The technical approach is novel, using high-order Hermite moments of covariates rather than responses, and combining iterative projections with observable-operator learning. The paper provides explicit proofs and hyperparameters. The result also implies the first polynomial-time algorithm for max-affine regression. The significance is high, but the dependence on B and Δ in the exponent is a notable caveat.
Pith's reading of the paper (a machine's summary, not the authors')
This paper presents the first algorithm for linear regression under maximum self-selection bias that runs in polynomial time in all parameters (dimension n, number of regressors k, and inverse error 1/ε). Previous algorithms required time exponential in k. The key insight is that conditional on large responses, the high-degree Hermite moments of the covariates approximately decompose into a sum of tensor powers of the regressors, allowing recovery via implicit tensor decomposition and observable-operator learning. If correct, this resolves a major open problem in the sample- and time-efficient estimation of self-selection models and max-affine regression.
What carries the argument. The central object is the restricted Hermite moments of the covariates, conditional on large responses. The key identity (Theorem 5.1) shows that these moments approximately decompose as weighted sums of tensor powers of the normalized regressors, with irreducible but controllable error. The algorithm uses iterative projections to implicitly access high-order tensors without materializing them, observable-operator learning to extract unit vectors parallel to regressors from the spectrum of projected moment matrices, and a restricted least-squares refinement to recover full regressors and biases from these directional estimates.
Core claim. The paper claims that under the boundedness and uncoveredness conditions (Assumption 1.2), there exists a randomized algorithm that, given k≥2, known noise correlation ρ∈[0,1], error ε∈(0,1), and failure probability δ∈(0,1/3), returns estimates (ŵ_i, b̂_i) such that with probability at least 1-δ, there is a permutation π of indices with max_i (||ŵ_i - w_{π(i)}||_2 + |b̂_i - b_{π(i)}|) ≤ ε. The sample complexity and running time are both Õ((nk/ε)^{poly(B/Δ)} log(1/δ)). This constitutes the first polynomial-time algorithm for the unknown-index maximum self-selection problem and, at ρ=1, for max-affine regression.
The premise it rests on. The algorithm requires known constants B and Δ such that every regressor has norm between Δ and B, all biases are at most B, and the inner product between distinct regressors is at most the smaller squared norm minus Δ². If these constants are unknown or the instance violates this uncoveredness condition, the algorithm's guarantees break down.
If the paper is right (Pith's inferences, not the authors')
If true, this gives the first polynomial-time algorithm for max-affine regression, a problem previously requiring exponential time in k.
The technique of decomposing restricted Hermite moments may apply to other latent-variable models where the latent selection mechanism induces a mixture structure in the covariate distribution.
The local convergence subroutine improves the initialization radius from poly(1/k) to O(1), which may simplify warm-start requirements in related problems.
The algorithm works under correlated noise between regressors, capturing the max-affine regression setting (ρ=1) as a special case.
The reliance on the boundedness and uncoveredness constants B and Δ appearing in the exponent of the sample complexity means that the algorithm is practical only when these constants are small; for ill-conditioned instances the polynomial degree could be large.
The irreducible error in the Hermite moment decomposition (even with exact moments) forces the algorithm to recover regressors one block at a time, preventing a single-shot recovery of all k regressors. This suggests a fundamental limitation: the method cannot handle regressors with very small norms that get washed out.
The algorithm requires known noise correlation ρ; extending to unknown ρ would require additional estimation steps and likely degrade the guarantees.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
We revisit the problem of estimating k linear regressors with self-selection bias in n dimensions up to error ε with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. Our main result is a poly(n,k,1/ε) time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on k. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on k. Prior works exhaustively search over a k-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-(logn) Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-14
The authors' main claim, as the classifier picked it out 1.00
“Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$.”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.82 · states limitation 0.11 · human participants 0.02 · controlled comparison 0.05 · randomized assignment 0.02 · states quantitative result 0.77 · compares with prior results 0.98 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| We revisit the problem of estimating $k$ linear regressors with self-selection bias in $n$ dimensions up to error $\varepsilon$ with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. | background 1.00 | 0.09 | 0.04 | unclear 0.50 |
| Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$. | result 0.63 | 0.95 | 0.97 | asserted 1.00 |
| Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. | result 0.64 | 0.87 | 0.04 | asserted 0.99 |
| Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on $k$. | result 0.49 | 0.92 | 0.16 | asserted 1.00 |
| Prior works exhaustively search over a $k$-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. | method 0.64 | 0.64 | 0.04 | asserted 1.00 |
| We show that, restricting to observations with large response values, the degree-$(\log n)$ Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. | result 0.42 | 0.93 | 0.06 | asserted 0.99 |
| The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. | method 0.96 | 0.92 | 0.05 | asserted 0.89 |
| A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. | method 1.00 | 0.91 | 0.04 | asserted 1.00 |
| We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems. | future work 0.84 | 0.23 | 0.04 | hedged possibility 0.94 |
What kind of paper the classifier reports this is: method or tool 0.91 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-14: 1 request, 7,943 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Figures (4)
Figures are the authors', reproduced from the paper.
References (32)
- [1] [AGHK+14] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky. “Tensor Decompositions for Learning Latent Variable Models”. In:Journal of Machine Learning Research15.80 (2014), pp. 2773–2832 (cit. on pp. 12, 15). [AH02] Susan Athey and Philip A. Hai... on Pith
- [2] PMLR, 2014, pp. 613–621 (cit. on p. 15). [YWS15] Yi Yu, Tengyao Wang, and Richard J. Samworth. “A useful variant of the Davis– Kahan theorem for statisticians”. In:Biometrika102.2 (2015), pp. 315–323 (cit. on p. 85). 80 [ZJD16] Kai Zhong, Prateek Jain, and Inderjit S. Dhillon.... on Pith
- [3] PMLR, 2013, pp. 1040– 1048 (cit. on p. 15). [CLS20] Sitan Chen, Jerry Li, and Zhao Song. “Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments”. In:Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computi... on Pith
- [11] 2025 (cit. on p. 15). [DIKZ25] Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, and Nikos Zarifis. “Robust Learning of Multi-index Models via Iterative Subspace Approximation”. In:2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2025, pp. ... on Pith
- [12] Proceedings of Machine Learning Research. PMLR, 2024, pp. 1364–1378 (cit. on pp. 15, 17). [DK25] Ilias Diakonikolas and Daniel M. Kane. “Implicit High-Order Moment Tensor Esti- mation and Learning Latent Variable Models”. In:2025 IEEE 66th Annual Symposium on Foundations of Co... on Pith
- [13] Proceedings of Machine Learning Research. PMLR, 2020, pp. 1514–1539 (cit. on pp. 15, 17). 75 [DKM09] Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. “Analysis of Perceptron-Based Active Learning”. In:Journal of Machine Learning Research10 (2009), pp. 281–299 (cit. o... on Pith
- [14] Proceedings of Machine Learning Research. PMLR, 2024, pp. 1336–1363 (cit. on p. 16). [DLB25] Alex Damian, Jason D. Lee, and Joan Bruna. “The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models”. In:Advances in Neural Information Proces... on Pith
- [15] 2025 (cit. on p. 15). [DLMF] National Institute of Standards and Technology.NIST Digital Library of Mathematical Functions(cit. on pp. 17, 24). [DLNS24] Anindya De, Huan Li, Shivam Nadimpalli, and Rocco A. Servedio. “Detecting Low- Degree Truncation”. In:Proceedings of the 56t... on Pith
- [17] Proceedings of Machine Learning Research. PMLR, 2024, pp. 1262–1262 (cit. on p. 15). [DRZ20] Constantinos Daskalakis, Dhruv Rohatgi, and Emmanouil Zampetakis. “Truncated Linear Regression in High Dimensions”. In:Advances in Neural Information Processing Systems. Vol on Pith
- [21] Proceedings of Machine Learning Research. PMLR, 2020, pp. 1727–1736 (cit. on p. 15). [KKL26] Haitham Kanj, Seonho Kim, and Kiryung Lee. “Sparse Max-Affine Regression”. In: SIAM Journal on Mathematics of Data Science8.4 (2026), pp. 1155–1178 (cit. on p. 15). [KL24] Seonho Kim a... on Pith
- [23] Proceedings of Machine Learning Research. PMLR, 2012, pp. 33.1–33.34 (cit. on pp. 4, 9, 15, 40). [AK05] Sanjeev Arora and Ravi Kannan. “Learning Mixtures of Separated Nonspherical Gaussians”. In:The Annals of Applied Probability15.1A (2005), pp. 69–92 (cit. on p. 15). [AM05] D... on Pith
- [25] Pro- ceedings of Machine Learning Research. PMLR, 2022, pp. 2815–2895 (cit. on p. 15). [LMZ24] Jane H. Lee, Anay Mehrotra, and Manolis Zampetakis. “Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians”. In:2024 IEEE 65th Annual Symposium o... on Pith
- [26] Proceedings of Machine Learning Research. PMLR, 2026, pp. 4724–4818 (cit. on p. 16). [MB09] Alessandro Magnani and Stephen P . Boyd. “Convex Piecewise-Linear Fitting”. In: Optimization and Engineering10.1 (2009), pp. 1–17 (cit. on pp. 3, 14). [Mil81] Paul R. Milgrom. “Good New... on PithPith's reviewarXiv
- [29] Curran Associates, Inc., 2016 (cit. on p. 15). [ZSJB+17] Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. “Re- covery Guarantees for One-Hidden-Layer Neural Networks”. In:Proceedings of the 34th International Conference on Machine Learning. Vol on Pith
- [32] 2025, pp. 99980–100014 (cit. on p. 16). 81 A Additional Preliminaries A.1 Gaussian Moments and Elementary Bounds Proposition A.1(Moment-Generating Function of a Gaussian Quadratic Form; [RS08, Theo- rem 5.2b]).Let G 0 ∼N(0, 1), m∈R, andτ≥0. For every a∈Rwith2aτ 2 <1, EG0 h ea(... on Pith
- [33] 2020 (cit. on p. 16). [FJ72] Ray C. Fair and Dwight M. Jaffee. “Methods of Estimation for Markets in Disequilib- rium”. In:Econometrica40.3 (1972), pp. 497–514 (cit. on pp. 1, 2). [FKKT21] Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. “Efficient Alg... on Pith
- [38] Proceedings of Machine Learning Research. PMLR, 2015, pp. 56–64 (cit. on p. 14). [Bha97] Rajendra Bhatia.Matrix Analysis. Vol on Pith
- [48] Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019 (cit. on p. 17). [WN14] Christopher S. Withers and Saralees Nadarajah. “Some conditional and uncondi- tional expectation identities for the multivariate normal with non-zero mean”. ... on Pith
- [51] Proceedings of Machine Learning Research. PMLR, 2016, pp. 1223–1231 (cit. on p. 15). [Tob58] James Tobin. “Estimation of Relationships for Limited Dependent Variables”. In: Econometrica26.1 (1958), pp. 24–36 (cit. on p. 16). [Vem10] Santosh S. Vempala. “Learning Convex Concept... on Pith
- [70] Proceedings of Machine Learning Research. PMLR, 2017, pp. 4140–4149 (cit. on p. 15). [ZZ25] Manolis Zampetakis and Felix Zhou. “Private Statistical Estimation via Truncation”. In:Advances in Neural Information Processing Systems. Vol on Pith
show 12 more
- [75] Proceedings of Machine Learning Research. PMLR, 2018, pp. 1125–1144 (cit. on p. 15). [LL24] Jerry Li and Allen Liu. “Clustering Mixtures with Almost Optimal Separation in Polynomial Time”. In:SIAM Journal on Computing(2024). Special section on STOC 2022, STOC22-46–STOC22-102 (... on Pith
- [99] Proceedings of Machine Learning Research. PMLR, 2019, pp. 955–960 (cit. on p. 16). [DIKR25] Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, and Lisheng Ren. “Algorithms and SQ Lower Bounds for Robustly Learning Real-Valued Multi-Index Models”. In: Advances in Neural Inf... on Pith
- [108] Proceedings of Machine Learning Research. PMLR, 2020, pp. 4463–4473 (cit. on p. 16). [Jae00] Herbert Jaeger. “Observable Operator Models for Discrete Stochastic Time Series”. In:Neural Computation12.6 (2000), pp. 1371–1398 (cit. on p. 15). 77 [JSA15] Majid Janzamin, Hanie Sedg... on PithPith's reviewarXiv
- [125] Proceedings of Machine Learning Research. PMLR, 2020, pp. 1161–1227 (cit. on p. 15). [CN24] Sitan Chen and Shyam Narayanan. “A Faster and Simpler Algorithm for Learning Shallow Networks”. In:Proceedings of Thirty Seventh Conference on Learning Theory. Vol on Pith
- [134] Proceedings of Machine Learning Research. PMLR, 2021, pp. 2060–2079 (cit. on p. 16). [GHK15] Rong Ge, Qingqing Huang, and Sham M. Kakade. “Learning Mixtures of Gaussians in High Dimensions”. In:Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. Assoc... on PithPith's reviewarXiv
- [169] Graduate Texts in Mathematics. Springer, 1997 (cit. on pp. 18, 84). [BS10] Mikhail Belkin and Kaushik Sinha. “Toward Learning Gaussian Mixtures with Arbitrary Separation”. In:Proceedings of the 23rd Annual Conference on Learning Theory. 2010, pp. 407–419 (cit. on p. 15). [BWY1... on Pith
- [178] Proceedings of Machine Learning Research. PMLR, 2022, pp. 5413–5452 (cit. on p. 15). [DMR23] Luc Devroye, Abbas Mehrabian, and Tommy Reddad.The total variation distance between high-dimensional Gaussians with the same mean. arXiv:1810.08693v7. 2023 (cit. on p. 66). [DPLB24] Al... on PithPith's reviewarXiv
- [195] Proceedings of Machine Learning Research. PMLR, 2023, pp. 5580–5614 (cit. on p. 15). [CDIZ23] Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas, and Mano- lis Zampetakis. “What Makes a Good Fisherman? Linear Regression under Self- Selection Bias”. In:Proceedings ... on Pith
- [247] Proceedings of Machine Learning Research. PMLR, 2024, pp. 981–994 (cit. on p. 15). [Das99] Sanjoy Dasgupta. “Learning Mixtures of Gaussians”. In:Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 1999, pp. 634– 644 (cit. on p. 1... on Pith
- [306] Proceed- ings of Machine Learning Research. PMLR, 2026, pp. 60603–60660 (cit. on p. 16). [KMV10] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. “Efficiently Learning Mixtures of Two Gaussians”. In:Proceedings of the 42nd ACM Symposium on Theory of Computing. Association... on Pith
- [336] Proceedings of Machine Learning Research. PMLR, 2026, pp. 3904–3905 (cit. on pp. i, 2, 4, 5, 12, 14, 16). [KMZZ+26] Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis, Felix Zhou, and Ziyu Zhu. “Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms”. In:... on Pith
- [3559] Lecture Notes in Computer Science. Springer, 2005, pp. 458–469 (cit. on p. 15). [BDJK+22] Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala. “Robustly Learning Mixtures of k Arbitrary Gaussians”. In:Proceedings of the 54th An... on Pith
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment