Conditional Linear Regression for Heterogeneous Covariances
Not on the map. Why?
Abstract (arXiv)
Often machine learning and statistical models will attempt to describe the majority of the data. However, there may be situations where only a fraction of the data can be fit well by a linear regression model. Here, we are interested in a case where such inliers can be identified by a Disjunctive Normal Form (DNF) formula. We give a polynomial time algorithm for the conditional linear regression task, which identifies a DNF condition together with the linear predictor on the corresponding portion of the data. In this work, we improve on previous algorithms by removing a requirement that the covariances of the data satisfying each of the terms of the condition have to all be very similar in spectral norm to the covariance of the overall condition.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 20 of its 43 references that are in the map. First posted on arXiv 15 Nov 2021.
Builds on
20 of 43 references.
References · 20
- 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
- 2016Learning from Untrusted Datacited by 90
- 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
- 2018Robust Estimation via Robust Gradient Estimationcited by 76
- 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
- 2017The power of sum-of-squares for detecting hidden structurescited by 54
- 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
- 2019List-Decodable Linear Regressioncited by 42
- 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
- 2019List Decodable Learning via Sum of Squarescited by 37
- 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
- 2018High-dimensional estimation via sum-of-squares proofscited by 25
8 more
- 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
- 2016Polynomial-time Tensor Decompositions with Sum-of-Squarescited by 22
- 2020List-Decodable Mean Estimation via Iterative Multi-Filteringcited by 18
- 2013Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functionscited by 15
- 2017Fast and robust tensor decomposition with applications to dictionary learningcited by 14
- 2020A spectral algorithm for robust regression with subgaussian ratescited by 8
- 2016Conditional Sparse Linear Regressioncited by 4
- 2018Conditional Linear Regressioncited by 4
Built on by
Citing papers per year: 2025: 1.
1 paper.