arXiv:2611.17228v1 math.ST

다항 시간의 자기선택 편향 선형 회귀

Linear Regression with Self-Selection Bias in Polynomial Time

Felix Zhou

제출 2026-11-12

한국어 초록

우리는 Cherapanamjeri, Daskalakis, Ilyas, Zampetakis [CDIZ23, STOC]가 도입한 최대 자기선택 기준 하에서, $n$차원에서 자기선택 편향이 있는 $k$개의 선형 회귀자를 오차 $\varepsilon$ 이내로 추정하는 문제를 다시 살펴본다. 주요 결과는 이 문제의 미지 인덱스 변형에 대한 $\mathrm{poly}(n,k,1/\varepsilon)$ 시간 알고리즘이며, 이는 $k$에 대해 지수적 의존성을 갖는 Gaitonde와 Mossel [GM24] 및 Kalavasis, Mehrotra, Zhou [KMZ26, COLT]의 기존 최선 알고리즘의 실행 시간을 개선한다. 우리의 알고리즘은 회귀자 간 상관된 잡음이 존재하는 경우에도 성공하며, 이는 관련된 설정인 max-affine 회귀를 포괄한다. 그 결과 이 문제에 대한 최초의 다항 시간 알고리즘도 제시하며, 이는 $k$에 대해 지수적 의존성을 갖는 Ghosh, Pananjady, Guntuboyina, Ramchandran [GPGR22, IEEE Transactions on Information Theory] 및 Gaitonde와 Mossel [GM24]의 기존 연구를 개선한다. 기존 연구는 회귀자들이 생성하는 $k$차원 부분공간을 완전 탐색하며 응답의 조건부 적률로 후보를 검정한다. 반면 우리의 알고리즘은 공변량의 적률에 대한 향상된 이해를 바탕으로 한다. 큰 응답값을 갖는 관측으로 제한하면, 공변량의 차수-$(\log n)$ 에르미트 적률이 회귀자들의 텐서 거듭제곱의 합으로 근사적으로 분해됨을 보인다. 알고리즘의 첫 단계는 암묵적으로 표현된 이러한 고차 텐서에 대한 텐서 분해 알고리즘으로 볼 수 있으며, 회귀자와 평행한 단위 벡터를 출력한다. 보통 최소제곱법의 단순한 변형에 기반한 두 번째 단계는 이 단위 벡터가 주어졌을 때 회귀자의 추정값을 추출한다. 우리는 이러한 분석적 통찰과 알고리즘 구성요소가 다른 잠재 변수 문제를 위한 효율적 알고리즘 설계에 응용될 수 있다고 믿는다.

원문 초록

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]. 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$. 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-$(\log n)$ 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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.17228v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.