PaperlayerView exact revision on arXiv

Source-linked AI summary

Outlier Detection Using Nonconvex Penalized Regression

Yiyuan She, Art B. Owen

arXiv:1006.2592v3stat.MEcs.LGstat.CO

TL;DR

The paper addresses robust outlier detection and estimation through penalized regression. It introduces Θ-estimators and reports successful outlier identification and coefficient estimation, while noting limitations for high-dimensional settings.

  • Problem

    Outliers complicate statistical data analysis, while raw residuals can fail for identifying observations that might be outliers.

  • Method

    The paper considers Θ-estimators within penalized regressions and uses residual-based procedures, including hard-IPOD with BIC-based parameter tuning.

  • Results

    The robust regression algorithms worked better than competitors on simulated data and successfully identified outliers while estimating coefficients in some settings.

  • Takeaways & Limitations

    The proposed penalized-regression framework jointly supports outlier identification and coefficient estimation in the reported settings.

  • Takeaways & Limitations

    In high-dimensional settings, the methodology is subject to the condition that both the coefficient vector and outlier pattern are sparse.

Abstract

from arXiv · show

This paper studies the outlier detection problem from the point of view of penalized regressions. Our regression model adds one mean shift parameter for each of the $n$ data points. We then apply a regularization favoring a sparse vector of mean shift parameters. The usual $L_1$ penalty yields a convex criterion, but we find that it fails to deliver a robust estimator. The $L_1$ penalty corresponds to soft thresholding. We introduce a thresholding (denoted by $Θ$) based iterative procedure for outlier detection ($Θ$-IPOD). A version based on hard thresholding correctly identifies outliers on some hard test problems. We find that $Θ$-IPOD is much faster than iteratively reweighted least squares for large data because each iteration costs at most $O(np)$ (and sometimes much less) avoiding an $O(np^2)$ least squares estimate. We describe the connection between $Θ$-IPOD and $M$-estimators. Our proposed method has one tuning parameter with which to both identify outliers and estimate regression coefficients. A data-dependent choice can be made based on BIC. The tuned $Θ$-IPOD shows outstanding performance in identifying outliers in various situations in comparison to other existing approaches. This methodology extends to high-dimensional modeling with $p\gg n$, if both the coefficient vector and the outlier pattern are sparse.

1 Introduction

The paper frames outlier detection as a regression problem requiring both reliable identification and robust coefficient estimation. It models potential outliers with sparse mean shifts and develops thresholding-based procedures because convex L1 penalization can fail under multiple-outlier masking and swamping.

  • Motivation: OLS can be highly sensitive to outliers, and raw residuals may fail to detect outliers at leverage points.The paper motivates robust regression and outlier-specific procedures as alternatives to ordinary residual screening.
  • Motivation: Multiple outliers create masking and swamping, causing outliers to go undetected or good observations to appear outlying.These effects make multiple-outlier detection substantially harder than detecting a single outlier.
  • Model: The mean-shift model y = Xβ + γ + ε assigns one parameter γ_i to each observation, with nonzero values representing outliers.Because the model has n + p parameters for n observations, sparsity on γ is imposed to avoid the trivial estimate γ̂ = y and obtain a meaningful β estimate.
  • Proposed approach: The resulting Θ-IPOD procedure replaces the usual L1-based soft-thresholding approach with general thresholding rules, including hard thresholding.The paper investigates nonconvex criteria because the convex L1 procedure is not robust and can fail on challenging multiple-outlier cases.
  • Computation: Θ-IPOD iterations cost at most O(np), avoiding the O(np^2) least-squares computation required by IRLS at each iteration.The paper reports that Θ-IPOD is much faster than IRLS for the large problems investigated, despite possibly requiring more iterations.
  • Tuning and scope: The method uses one tuning parameter for outlier identification and coefficient estimation, with data-dependent selection possible through BIC.The paper also extends the methodology to p > n when both the coefficient vector and outlier pattern are sparse.

2 Survey of robust regression

The survey distinguishes direct procedures that search for clean subsets from indirect procedures that use residuals from robust fits. It emphasizes that multiple-outlier detection must address masking and swamping while balancing robustness against computational cost.

  • Challenges: Multiple-outlier detection is challenging because masking and swamping can cause outliers to be missed or good observations to be flagged.The HBK and HS datasets are cited as examples exhibiting swamping effects.
  • Method classes: Direct methods include forward search and backward selection, while indirect methods identify outliers from residuals of a robust regression estimate.The survey lists M-estimators, Least Trimmed Squares, LMS, S-estimators, MM-estimators, and related procedures across these categories.
  • Initialization: Most indirect procedures begin with an initial high-breakdown-point estimate, such as one obtained from LTS, S, MTS, or PY procedures.These initial estimates need not be efficient, and PY’s theoretical breakdown-point property is described as not well established.
  • Computational limits: High-breakdown-point methods typically have costs that grow exponentially with dimension, limiting practical use in higher-dimensional settings.The survey notes that most published outlier-detection examples use 10 or fewer dimensions.
  • Problem distinction: Outlier identification and robust regression are related but distinct: even with the true β, overlap between residual distributions creates type I and type II errors.Conversely, perfectly identifying gross outliers makes robust coefficient estimation relatively easy even with multiple outliers.

3 Soft-IPOD

Soft-IPOD alternates OLS updating of β with soft-thresholding updates of sparse mean shifts γ. Although convex and convergent, it is non-robust under leverage-driven masking and swamping, motivating nonconvex Θ-based procedures.

  • Algorithm: Soft-IPOD fits the mean-shift model by alternating an OLS update for β with coordinatewise soft-thresholding for γ.Given γ, β is obtained by regressing y − γ on X; given β, the L1 problem in γ is orthogonal and separable.
  • Algorithm: Soft-IPOD is guaranteed to converge because its L1 objective is jointly convex in β and γ.The paper distinguishes convergence from robustness: convexity does not prevent failures under multiple leverage-point contamination.
  • Failure case: In the HBK example, soft-IPOD estimated cases 11–14 as serious outliers even though cases 1–10 were the actual outliers.The paper states that this erroneous identification was not a matter of parameter tuning.
  • Failure case: Across the relevant λ range, cases 11–14 remain swamped while cases 1–10 are likely masked, so the L1 approach cannot identify the correct outliers without swamping.This illustrates the reported failure of soft-IPOD in the presence of multiple moderate- or high-leverage outliers.
  • Connection to M-estimation: The L1-penalized regression corresponds to Huber’s M-estimation, whose known difficulty with leverage points helps explain the same masking and swamping behavior.The paper states that Huber’s method cannot handle moderate leverage points well and has breakdown point 0.
  • Nonconvex extension: Θ-IPOD replaces soft-thresholding with an appropriate general thresholding operator to obtain estimates of γ and β under potentially nonconvex penalties.The paper reports that some nonconvex criteria properly identify multiple outliers in challenging standard test cases.

4 Θ-IPOD

Θ-IPOD replaces soft-thresholding with a general thresholding-based iterative procedure for sparse outlier effects, connecting penalized regression to M-estimation. Hard-IPOD resolves masking and swamping in the challenging HBK example while providing convergence and robust regression properties.

  • Θ-IPOD procedure: Θ-IPOD iteratively updates sparse mean-shift parameters with a chosen thresholding rule and returns a limit-point estimate (β̂, γ̂).The procedure is defined for general threshold functions and jointly supports outlier detection through γ̂ and regression estimation through β̂.
  • Outlier detection: Hard-IPOD resolves masking and swamping in the challenging HBK example.Using an LTS scale estimate and a zero start, the method perfectly detects the true outliers and obtains the clean-data OLS coefficient estimate.
  • Convergence: The Θ-IPOD iteration monotonically decreases the penalized objective at each update.Theorem 4.1 states that every limit point is stationary for the associated objective, establishing convergence under the stated thresholding and penalty conditions.
  • Penalized regression: A thresholding rule can correspond to multiple penalties, including infinitely many penalties yielding hard thresholding and the L0 penalty.The construction uses an auxiliary nonnegative function q, which may be nonzero while preserving the thresholding behavior.
  • Connection to M-estimators: Θ-IPOD estimates a sparse outlier vector γ̂ and a robust regression coefficient β̂, with β̂ corresponding to an M-estimate under the stated ψ condition.Unlike M-estimators that typically require a residual cutoff for explicit outlier identification, minimizing the penalized objective directly yields sparse outlier effects.
  • Computational formulation: The simplified Θ-IPOD algorithm applies to TISP results and extends to a p > n sparsity formulation when using the reduced model.Its iteration avoids matrix inversion, can exploit sparsity, and has an implementation based on the hat matrix.

5 Θ-IPOD vs. IRLS

Θ-IPOD is presented as an alternative way to compute M-estimates, replacing iteratively reweighted least squares with thresholding updates. In the simulation, its speed advantage increased with sample size and predictors, while IRLS sometimes became unstable.

  • M-estimation and IRLS: M-estimates can be represented as weighted least-squares estimates, and iteratively updating the weights yields the IRLS algorithm.The weights are defined from the ψ function and can downweight bad observations.
  • Simulation design: The simulation compared IRLS and simplified Θ-IPOD under additive outliers and leverage points across varying sample sizes and contamination settings.The design used p = n/10, n from 30 to 1000, leverage values L ∈ {15, 20, 30}, and outlier counts O ∈ {5, 10, 20}.
  • Stability: IRLS sometimes encountered singular weighted-least-squares problems for redescending ψ functions when fewer than p weights were nonzero.Θ-IPOD remained very stable in these cases, although sparsity could not reduce the cost of its Hγ update when the relevant vector was not sufficiently sparse.
  • Scope of speed results: The computational advantage of Θ-IPOD can be moot when the preliminary method is very expensive.The authors treat speed as secondary to robustness.

6 Parameter Tuning in Outlier Detection

The section develops data-dependent tuning for Θ-IPOD using a modified local BIC and evaluates tuned hard-IPOD against robust outlier-detection methods. Simulations show strong masking and joint-detection performance, with a modest swamping trade-off.

  • Cross-validation is difficult because a large prediction error may reflect either a suboptimal β or an outlier.
  • BIC can be applied to the reduced model when the proportion of outliers is not large, because the transformed observations are clean.
  • The method constructs a local BIC over a proper degrees-of-freedom interval along the Θ-IPOD solution path.
  • For hard-IPOD, the detected outlier shifts use an OLS estimate and the degrees of freedom equal the number of detected outliers.
  • The simulations compare tuned hard-IPOD with MM, GY, S1S, and LTS using masking, swamping, and joint detection measures.
  • Θ-IPOD dominates competing methods for masking and joint detection, while being slightly worse for swamping; this trade-off is considered acceptable because masking causes more harm.

7 Outlier Detection with p > n

The paper extends Θ-IPOD to p > n by jointly imposing sparsity on regression coefficients and outlier shifts. The approach supports variable selection and outlier identification, and performs well on a 700-wavelength sugar dataset.

  • The large-p formulation works in an augmented space with B = [X I] when both β and the mean-shift outlier pattern are sparse.
  • TISP convergence is guaranteed even when n < p under the stated augmented-design condition.
  • The nonzero components of β select relevant predictors, while γ identifies outliers and measures their outlyingness.
  • L1 soft-thresholding fails for this challenging sparsity problem, motivating thresholdings associated with redescending ψ functions.
  • Hard-ridge thresholding combines L0-induced sparsity with L2 shrinkage, allowing partial rather than complete removal of mildly outlying observations’ influence.
  • Using all 700 wavelengths, the sugar-data model selected 15 wavelengths and flagged observation 99 as a possible outlier.
  • The test-data mean-squared error was 0.219, improving the reported MCMC results by about 39%.

8 Discussion

The discussion presents Θ-estimators as a nonconvex penalized-regression framework for jointly identifying outliers and estimating coefficients, including in high-dimensional settings. It reports strong empirical performance while emphasizing dependence on preliminary robust fits and tuning choices.

  • Contributions: Θ-estimators provide a new penalized-regression characterization associated with M-estimators.The framework generalizes nonconvex penalized least-squares methodology.
  • Contributions: The method successfully identifies outliers while estimating regression coefficients robustly.The methodology was generalized to high-dimensional problems with sparse coefficients and sparse outlier patterns.
  • Leverage points: When outliers are leverage points, the reduced-model Gram matrix can exhibit problematic correlation between clean observations and outliers for small h_i.The discussion connects this setting to difficulties encountered by the convex L1 penalty and motivates nonconvex penalties with redescending ψ-functions.
  • Tuning: Choosing λ in a data-dependent way is crucial for good detection performance, while the framework uses tuning to determine both M-estimator efficiency and the outlier cutoff.The discussion links these tuning choices to the mean-shift outlier model.
  • Empirical findings: The robust regression algorithms performed better than competitors on simulated data and gave correct answers on some small, well-studied real datasets.The claim is explicitly limited to the reported simulations and selected real datasets.
  • Limitations: All studied methods rely on a preliminary robust fit, whose cost can grow exponentially with dimension; p = 15 is already large for the most robust fits.In high-dimensional problems, the PY procedure performed well in the examples but does not necessarily have high breakdown.
  • Limitations: A failed preliminary fit may not be corrected by Θ-IPOD or related follow-up methods, although hard-IPOD worked from a non-robust start on the HBK problem.The authors expect improvements in high-dimensional preliminary fitting methods to benefit Θ-IPOD iterations; low-dimensional methods such as LTS are fast enough.

A Proofs

The appendix proofs establish thresholding-based characterizations of penalized regression estimates and connect the resulting fixed-point equations to Huber-type and L1-penalized regression formulations.

  • Connection to robust regression: The joint KKT equations for L1-penalized regression coincide with the corresponding equations for Huber’s method with joint scale estimation.When σ is fixed, the two minimizations still yield the same β-estimate.
  • Connection to robust regression: The proofs note that Huber’s method behaves poorly for moderate leverage and that avoiding masking and swamping requires a redescending ψ-function.The argument relates these robustness properties to the regression matrix I − H and its column norms.
  • Thresholding characterization: Any Θ-IPOD estimate has an outlier vector γ that is a fixed point of the thresholding update.The update is expressed through Θ(Hγ + (I − H)y; λ).
  • Thresholding characterization: For continuous thresholding rules, the thresholded value ˆθ = Θ(t; λ) minimizes the associated penalized objective.The proof allows penalties that may be nondifferentiable at zero and nonconvex.
Loading 1006.2592v3…