Polynomial-time algorithm for list-decodable linear regression with batches.
problem Efficiently decoding linear regression with a fraction of adversarial data.
method Polynomial time algorithm using batches of i.i.d. samples.
result Returns a list of size O(1/α^2) with one item close to true parameter.
Statistical Query lower bound shows difficulty in list-decodable linear regression.
problem List-decodable linear regression with adversarial corruption.
method Statistical Query (SQ) lower bound analysis.
result Lower bound of d p o l y ( 1 / α ) d^{\mathrm{poly}(1/α)} d poly ( 1/ α ) for list-decodable linear regression. We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than 1 / 2 1/2 1/2 fraction of examples. For any α < 1 α< 1 α < 1 , our algorithm takes as input a sample { ( x i , y i ) } i ≤ n \{(x_i,y_i)\}_{i \leq n} {( x i , y i ) } i ≤ n of n n n linear equations where α n αn α n of the equations satisfy $y_i = \l…
Polynomial-time algorithm for estimating covariance in corrupted Gaussian data.
problem Estimating covariance in data with up to 1-α fraction of adversarial corruptions.
method Uses low-degree sum-of-squares certificates for anti-concentration and hypercontractivity.
result Outputs a list of candidate parameters with high probability containing a nearly correct covariance.
New algorithm for batch list-decodable linear regression with stronger guarantees.
problem Efficiently list-decoding linear regression with a fraction of corrupted batches.
method Uses higher-order moments and Sum-of-Squares (SoS) certification to achieve better guarantees.
result Achieves substantially smaller minimum batch size and final error, with optimal list size.
New method for estimating sparse means in noisy data.
problem Estimating the mean of a sparse distribution in the presence of outliers.
method Difference-of-Pairs Filtering technique for list-decodable sparse mean estimation.
result First sample and computationally efficient algorithm for list-decodable sparse mean estimation.
Paper tackles high-accuracy list-decodable learning for mean estimation.
problem Estimate the mean of a distribution with a small fraction coming from a nice distribution.
method Developed a novel proof of identifiability and a new algorithmic approach.
result Achieved high-accuracy guarantees for list-decodable mean estimation.
New algorithm for robust mean estimation in high dimensions with nearly-PCA time complexity.
problem Robust mean estimation in high-dimensional data with a minority of contaminated data.
method List-decodable mean estimation algorithm using a novel soft downweighting method, SIFT, and a Ky Fan matrix multiplicative weights procedure.
result Optimal sample complexity and error rate for list-decodable mean estimation with runtime nearly matching PCA.
New algorithm recovers mixture means even with many outliers.
problem Estimating mixture means when outliers overwhelm small groups.
method Proposes an algorithm for robust mixture learning with minimal list-size overhead.
result Order-optimal error guarantees for each mixture mean.
Algorithm estimates covariance from noisy data efficiently.
problem Estimating covariance from a noisy set of points.
method Spectral techniques for list-decodable covariance estimation.
result Efficient algorithm with poly(1/α) sample and time complexity.
Boosting improves accuracy with fewer calls to weak learners for certain concept classes.
problem Improving accuracy of learning algorithms with limited weak learner calls.
method Combines boosting and list-decodable codes to achieve better performance for specific concept classes.
result A new boosting algorithm that achieves strong learning with fewer calls to weak learners and additional samples.
Paper tackles MLR prediction error without assuming realizable models.
problem Prediction error in mixture of linear regressions without realizable assumptions.
method Developed algorithms for list-decoding MLR predictions and minimized empirical risk.
result Alternating minimization algorithm finds best fit lines in non-realizable settings.
A simple model explains phase transition in large language models.
problem Understanding the emergence of abilities in large language models.
method Modeling LLM as a sequence-to-sequence random function and using a list decoder.
result A critical threshold exists where the expected number of erroneous sequences grows exponentially.
New method estimates mean from noisy data with few outliers.
problem Estimate mean from noisy data with few outliers.
method Iterative multi-filtering approach.
result Achieves near-optimal error with practical efficiency.
New method certifies anti-concentration for various non-Gaussian distributions.
problem Efficiently certifying anti-concentration for non-Gaussian distributions.
method Sum-of-Squares relaxation of integer program for anti-concentration.
result Quasi-polynomial time certificates for non-Gaussian distributions.
New algorithm clusters data with almost-linear time, robust to corruption.
problem Clustering mixtures of distributions with adversarial corruption.
method List-decodable mean estimation, robust mean estimation, iterative multi-filtering.
result First almost-linear time algorithms for clustering mixtures of k well-behaved distributions.
Improved subspace recovery algorithm with dimension-independent error and polynomial time.
problem Efficiently recover a covariance matrix from a mix of inliers and adversarial outliers.
method List-decodable subspace recovery algorithm with faster fixed-polynomial time and less restrictive distributional assumptions.
result Achieved dimension-independent error guarantee of O(1/α) with poly(1/α d^O(1)) time complexity.
Proves subgaussian distributions are SoS-certifiably subgaussian, enabling efficient algorithms for various statistical tasks.
problem Efficiently learning from subgaussian distributions in high dimensions.
method Universal constant C C C and polynomial sum of squares (SoS) approach. result Proves subgaussian distributions are SoS-certifiably subgaussian.
This paper bridges outlier-robust estimation in robotics and computer vision with robust statistics.
problem Outlier-robust estimation for geometric perception in robotics and computer vision.
method Adapting and extending robust linear regression and list-decodable regression to non-convex domains and vector-valued measurements.
result Performance guarantees for modern estimation algorithms in the presence of outliers.
New algorithm reduces contamination in supervised learning.
problem Learning with contamination in supervised learning.
method Iterative polynomial filtering.
result Efficient learning of functions with contamination.
Smoothed analysis shows that many classes become learnable from positive-only samples.
problem Learning from positive-only samples is challenging due to negative results in worst-case settings.
method Smoothed analysis of positive-only learning, assuming samples from a reference distribution smooth with respect to the true distribution.
result All VC classes become learnable in the smoothed model with O ( V C / ε 2 ) O(VC/ε^2) O ( V C / ε 2 ) positive samples for ε ε ε classification error. Study on list learning with noisy data, showing limits and some learnable cases.
problem Learning from noisy data in a list learning context.
method Inspired by coding theory, extends list learning model to study sparse conjunctions and parities/majors.
result Sparse conjunctions can be efficiently list learned under certain conditions, but parities and majors cannot be efficiently learned.
Study shows private learning of mixtures of Gaussians is possible with polynomial samples.
problem Estimating mixtures of Gaussians under differential privacy constraints.
method Developed a new framework for privately learning mixtures of Gaussians without structural assumptions.
result Polynomial number of samples (poly(k,d,1/α,1/ε,log(1/δ))) sufficient for estimation up to total variation distance α with (ε, δ)-DP.
Efficiently estimates common mean in high-dimensional data with noisy subset.
problem Estimating common mean in high-dimensional data with noisy subset.
method Iterative refinement strategy with rejection sampling and dimension-reduction.
result Achieves near-optimal error of f ( α , N ) + D / ( α N ) f(α,N) + \sqrt{D/(αN)} f ( α , N ) + D / ( α N ) . Ability for accurate hospital case cost modelling and prediction is critical for efficient health care financial management and budgetary planning. A variety of regression machine learning algorithms are known to be effective for health care cost predictions. The purpose of this experiment was to build an Azure Machine…
Efficiently private regression for unbounded data.
problem Privacy constraints in regression settings with unbounded covariates.
method Differential privacy techniques on mean and covariance estimation extended to sub-gaussian regime.
result Unbiased estimate of true regression vector learned up to a scaling factor.
This paper studies robust regression in the settings of Huber's ε ε ε -contamination models. We consider estimators that are maximizers of multivariate regression depth functions. These estimators are shown to achieve minimax rates in the settings of ε ε ε -contamination models for various regression problems including nonpa…
This paper studies the nonparametric modal regression problem systematically from a statistical learning view. Originally motivated by pursuing a theoretical understanding of the maximum correntropy criterion based regression (MCCR), our study reveals that MCCR with a tending-to-zero scale parameter is essentially moda…
Proposes FARM model combining latent factor and sparse regression.
problem Testing adequacy of latent factor and sparse regression models.
method Factor Augmented sparse linear Regression Model (FARM) with FabTest and ANOVA type tests.
result Model robustness and effectiveness validated through experiments.
Survey of SDR methods for high-dimensional regression and embedding.
problem Reducing dimensionality in high-dimensional data.
method Involves both statistical and machine learning approaches, covering inverse and forward regression methods.
result Supervised Kernel Dimension Reduction is equivalent to supervised PCA.
This paper reviews SDR methods for multivariate response regression.
problem Handling sufficient dimension reduction for multivariate response regression.
method Characterizes SDR estimators as inverse or forward regression methods.
result Pooled marginal, projective resampling, distance-based, ordinary least squares, partial least squares, and semiparametric SDR estimators are discussed.
Paper introduces semi-supervised linear extremile regression for high-dimensional data.
problem Challenges in high-dimensional extremile regression due to data sparsity and overfitting.
method Proposes semi-supervised learning for linear extremile regression, achieving n \sqrt{n} n -consistency. result Demonstrates improved estimation efficiency and performance in high-dimensional settings.
Improves logistic regression performance with nonconvex programming.
problem Stochastic generalized linear regression with chance constraints.
method Nonconvex programming techniques, clustering, quantile estimation.
result Over 1 to 2 percent improvement in model performance.
Study improves H H H -consistency bounds for regression analysis.
problem Improving H H H -consistency bounds for regression analysis. method Generalized theorems and novel H H H -consistency bounds for various surrogate loss functions. result Derives principled surrogate losses for adversarial regression.
Prevalidated ridge regression simplifies logistic regression for high-dimensional data.
problem Efficient probabilistic classification in high-dimensional data with logistic regression.
method Developed a prevalidated ridge regression model that matches logistic regression's performance but is more computationally efficient.
result Prevalidated ridge regression achieves similar classification error and log-loss to logistic regression for high-dimensional data.
Introduces a new model for mapping matrices to matrices, subsuming linear regression.
problem Learning matrix-to-matrix mappings from data.
method Partial trace regression model, leveraging quantum information theory.
result Relevance demonstrated in matrix-to-matrix regression and positive semidefinite matrix completion.
Meta-theorems validate fair regression algorithms under demographic parity constraints.
problem Regression under demographic parity constraints.
method Meta-theorems and post-processing methods.
result Fair minimax optimal regression can be achieved through post-processing.
We analyzed optimism in linear and kernel regression models.
problem Understanding predictive complexity in regression models.
method Derived closed-form asymptotic optimism for linear and kernel regression models.
result Scaled optimism is a useful measure for model complexity.
A new optimizer, MVO, improves nonlinear regression performance.
problem Finding optimal coefficients in nonlinear regression models.
method Multi-Verse Optimizer (MVO) compared to Particle Swarm Optimizer (PSO).
result MVO statistically outperforms PSO in 10 nonlinear regression problems.
Brenier isotonic regression extends multi-output isotonic regression using optimal transport.
problem Enforcing cyclic monotonicity in multi-output regression.
method Leverage Kantorovich's optimal transport to find cyclically monotone couplings.
result Brenier isotonic regression outperforms baselines in probability calibration.
We simplify complex regression coefficients using linearization and feature comparison.
problem Interpreting high-dimensional regression coefficients from nonlinear responses.
method Developed a linearization method to derive feature coefficients and compare them with regression coefficients.
result Shows how regression coefficients relate to linearized feature coefficients and how they change under regularization.
Unified framework for fair regression under demographic parity.
problem Ensuring fairness in regression tasks subject to demographic parity constraints.
method Proposes a unified framework applicable to various regression tasks with a broad spectrum of loss functions, derived a novel characterization of the fair risk minimizer, and established theoretical consistency and convergence rates.
result Effective minimization of risk while satisfying fairness constraints across various regression settings.
Locally adaptive interpretable regression improves linear regression's predictability.
problem Linear regression's predictability is limited; it lacks adaptability.
method Locally adaptive interpretable regression (LoAIR) uses neural networks to predict percentile of a Gaussian distribution for regression coefficients.
result LoAIR achieves comparable or better predictive performance than state-of-the-art baselines.
Huber regression assessed for robustness in statistical learning.
problem Understanding Huber regression in nonparametric statistical learning.
method Assessment from statistical learning perspective, focusing on risk consistency, adaptive tuning, and convergence rates.
result Huber regression can be asymptotically mean regression calibrated under ( 1 + ε ) (1+ε) ( 1 + ε ) -moment conditions, justifying its robustness. Least Angle Regression is a promising technique for variable selection applications, offering a nice alternative to stepwise regression. It provides an explanation for the similar behavior of LASSO ( ℓ 1 \ell_1 ℓ 1 -penalized regression) and forward stagewise regression, and provides a fast implementation of both. The idea has…
We analyze coresets for regularized regression problems and propose a modified lasso that yields smaller coresets.
problem Analyzing coresets for regularized regression problems.
method Examined coresets for ridge regression and proposed a modified lasso problem.
result No coreset for regularized regression can be smaller than the unregularized version when r e q s r
eq s r e q s . Study uniform consistency in nonparametric mixture models and mixed regression.
problem Uniform consistency in nonparametric mixture models and mixed regression models.
method Construct uniformly consistent estimators under general conditions, develop novel technical tools.
result Prove uniform consistency results for nonparametric mixtures and mixed regression models.
We find a convex model for traditional nonlinear regression under L2 loss.
problem Nonlinear regression under L2 loss with non-convex optimization.
method Showed a convex nonlinear regression model for least squares problem.
result Existence of a convex model simplifies training complex systems.