{"id":"caffed21-c0a1-4e02-8e4a-112aec780dc3","arxiv_id":"2611.17228","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":5,"one_line_summary":"A polynomial-time algorithm based on restricted Hermite moments and moment peeling recovers all k regressors in unknown-index maximum self-selection, including max-affine regression.","lead":"This paper gives a randomized algorithm that recovers k hidden linear regressors from data where only the largest noisy response is observed, using time and samples polynomial in n, k and 1/eps when the model constants are fixed. It is the first polynomial-time algorithm for this self-selection problem and for max-affine regression, removing an exponential dependence on k from prior work.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"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.","rationale":"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.","tokens_in":77168,"tokens_out":828,"duration_ms":13342,"concrete_test":"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.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"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.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper presents a polynomial-time algorithm for linear regression with self-selection bias under the maximum self-selection criterion, also covering max-affine regression. The algorithm uses high-order Hermite moments of covariates conditioned on large responses, an implicit tensor decomposition via iterative projections, observable-operator learning, and a restricted least-squares refinement. The main result is Theorem 1.3: a randomized algorithm with sample complexity and running time eO((nk/ε)^{poly(B/Δ)} log(1/δ)). The paper claims this is the first polynomial-time algorithm for the unknown-index self-selection problem and for max-affine regression.","tokens_in":77592,"tokens_out":2196,"duration_ms":18751,"significance":"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.","major_comments":[{"comment":"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). 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.","section":"Theorem 1.3, Hyperparameters 4.1, line b62","authors_acknowledge":"We will also treat B, ∆ as absolute constants that disappears in the big-O notation.","authors_acknowledge_p":0.62},{"comment":"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 Δ. 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.","section":"Section 5, Theorem 5.1, Lemma 5.4, Lemma 5.7, Lemma 5.8, Lemma 5.9","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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. 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).","section":"Section 6.2, Theorem 6.3, sample complexity","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 7, Theorem 7.1, sample complexity","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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}}. 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.","section":"Section 9, Proof of Theorem 1.3, line b625","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"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 Δ.","section":"Abstract, line b1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The theorem statement uses eO notation but does not define it. It should be defined earlier or in the preliminaries.","section":"Section 1.1, Theorem 1.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 4.1, Hyperparameters 4.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 5, Theorem 5.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 6.2.1, Equation (49)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Section 8.1.1, Equation (108)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Appendix A, Proposition A.5","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The paper uses many acronyms (OLS, RLS, GMM, etc.) that are defined but could be listed in a notation table for convenience.","section":"General","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"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.\n\nThe 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.\n\nThe 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.\n\nCitation 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.","headline":"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.","tokens_in":78257,"tokens_out":2807,"duration_ms":24484},"pith_extraction":{"msc":["62J05","62H12","68Q87"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"Polynomial-time algorithm for linear regression with self-selection bias","keywords":["self-selection bias","linear regression","maximum self-selection","max-affine regression","Hermite moments","tensor decomposition","observable-operator learning","polynomial-time algorithm"],"falsifier":"Construct an instance with k=2, n=2, w_1=(1,0), w_2=(0.9, 0.1) (violating the angular separation condition because ⟨w_1,w_2⟩≈0.9 > min(||w_1||²,||w_2||²)-Δ² for any reasonable Δ), and test whether the algorithm can recover the regressors to within ε=0.1 using polynomially many samples. If it fails, the uncoveredness condition is necessary.","tokens_in":78622,"feed_emoji":"📊","tokens_out":1403,"duration_ms":14009,"temperature":0.7,"pith_summary":"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.","feed_headline":"Polynomial time for regression with self-selection bias","feed_subtitle":"First algorithm that runs in poly(n,k,1/ε) time for the unknown-index maximum self-selection problem, breaking exponential dependence on k.","key_machinery":"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_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduced the self-selection model and gave the first sample- and time-efficient algorithm with poly(n)exp(poly(k)) running time.","marker":"[CDIZ23]"},{"why":"Improved sample complexity to poly(n,k,1/ε) but with running time poly(n,k)+(1/ε)^{Õ(k)}; the current paper improves on this running time.","marker":"[GM24]"},{"why":"Provided a local convergence algorithm with poly(1/k) initialization radius; the current paper improves to O(1) radius.","marker":"[KMZ26]"},{"why":"Developed iterative projection methods for implicit high-order Hermite moments in Gaussian mixture clustering; the current paper adapts this technique.","marker":"[LL24]"},{"why":"Used implicit high-order moment tensors for learning latent-variable models; the current paper builds on their framework but handles irreducible error.","marker":"[DK25]"},{"why":"Introduced observable-operator learning for multi-view mixtures; the current paper uses a similar common-eigenbasis construction.","marker":"[AHK12]"},{"why":"Studied max-affine regression with exponential-time algorithm; the current paper gives the first polynomial-time algorithm for this problem.","marker":"[GPGR22]"}],"fun_headline_variants":["Poly-time breakthrough for self-selection bias","Cracking exponential dependence in max-affine regression","First polynomial algorithm for unknown-index self-selection","Hermite moments unlock linear regression with hidden bias"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Poly-time breakthrough for self-selection bias","Cracking exponential dependence in max-affine regression","First polynomial algorithm for unknown-index self-selection","Hermite moments unlock linear regression with hidden bias"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":9.9e-05,"raw_usage":{"cost":9.86622e-05,"is_byok":false,"cost_details":{"upstream_inference_cost":9.86622e-05,"upstream_inference_prompt_cost":8.81062e-05,"upstream_inference_completions_cost":1.0556e-05},"total_tokens":1231,"prompt_tokens":1173,"completion_tokens":58,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":1173,"tokens_out":58,"cost_source":"openrouter_usage","duration_ms":3420,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T09:08:06.572398+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"Construct an instance with k=2, n=2, w_1=(1,0), w_2=(0.9, 0.1) (violating the angular separation condition because ⟨w_1,w_2⟩≈0.9 > min(||w_1||²,||w_2||²)-Δ² for any reasonable Δ), and test whether the algorithm can recover the regressors to within ε=0.1 using polynomially many samples. If it fails, the uncoveredness condition is necessary.","supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}