Optimal Estimator for Unlabeled Linear Regression
Unlabeled linear regression, or ``linear regression with an unknown permutation'', has attracted increasing attentions due to its applications in linkage record and de-anonymization. However, its computation proves to be cumbersome and all existing algorithms require considerable time in the high dimensional regime. This paper proposes a one-step estimator which are optimal from both the computational and statistical sense. From the computational perspective, our estimator exhibits the same order of computational time as that of the oracle case, where the covariates are known in advance and only the permutation needs recovery. From the statistical perspective, when comparing with the necessary conditions for permutation recovery, our requirement on \emph{signal-to-noise ratio} ($\snr$) agrees up to $O\bracket{\log \log n}$ difference in certain regimes. Numerical experiments have also been provided to corroborate the above claims.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSimilar Papers 제목 키워드 기반
Efficient and Adaptive Linear Regression in Semi-Supervised Settings
We consider the linear regression problem under semi-supervised settings wherein the available data typically consists of: (i) a small or moderate sized 'labeled' data, and (ii) a much larger sized 'unlabeled' data. Such…
ImputationregressionOptimal and Safe Estimation for High-Dimensional Semi-Supervised Learning
We consider the estimation problem in high-dimensional semi-supervised learning. Our goal is to investigate when and how the unlabeled data can be exploited to improve the estimation of the regression parameters of linea…
parameter estimationregressionVocal Bursts Intensity PredictionTrimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models
We study the problem of learning generalized linear models under adversarial corruptions. We analyze a classical heuristic called the iterative trimmed maximum likelihood estimator which is known to be effective against …
regressionSemi-Supervised Empirical Risk Minimization: Using unlabeled data to improve prediction
We present a general methodology for using unlabeled data to design semi supervised learning (SSL) variants of the Empirical Risk Minimization (ERM) learning process. Focusing on generalized linear regression, we analyze…
regressionTuned Regularized Estimators for Linear Regression via Covariance Fitting
We consider the problem of finding tuned regularized parameter estimators for linear models. We start by showing that three known optimal linear estimators belong to a wider class of estimators that can be formulated as …
regression