Coordinate Descent Algorithm for Least Absolute Deviations Regression
Zehaan Naik, Debasis Kundu · 2026
Read Coordinate Descent Algorithm for Least Absolute Deviations Regression by Zehaan Naik, Debasis Kundu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19336.txt.
Introduction
Naik and Kundu speed up least absolute deviations regression, a robust fit that shrinks outlier pull. Classic solvers lean on simplex methods that grow costly in high dimensions. Their coordinate descent updates one weight at a time, with no matrix inversion. Each update has a closed form given by a median or weighted median. The method stays valid even when predictors outnumber the data rows. Tests match the accuracy of linear-programming solvers on real and fake data. It also scales better and stays stable in hard regimes.
Catalog record
| CREATOR | Zehaan Naik, Debasis Kundu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49522 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.19336
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Coordinate Descent Algorithm for Least Absolute Deviations Regression Zehaan Naik, Debasis Kundu Abstract Least Absolute Deviations (LAD) regression provides a robust alternative to ordinary least squares by minimizing the sum of absolute residuals. However, its widespread use has been limited by the computational cost of existing solvers, particularly simplex-based methods in high-dimensional settings. We propose a coordinate descent algorithm for LAD regression that avoids matrix inversion, naturally accommodates the non-differentiability of the objective function, and remains well-defined even when the number of predictors exceeds the number of observations. The key observation is that each coordinate update reduces to a one-dimensional minimization admitting a closed-form solution given by a median or weighted median. The resulting algorithm has per-iteration complexity O ( p n log n ) O(p\,n\log n) and is provably convergent due to the convexity of the LAD objective and the exactness of each coordinate update. Experiments on synthetic and real datasets show that the method matches the accuracy of linear-programming-based LAD solvers while offering improved scalability and stability in high-dimensional regimes, including cases where p ≥ n p\geq n . The method is easy to implement, requires no specialized optimization software, and provides a practical tool for robust linear models. Keywords: LAD regression, coordinate descent, robust modeling, high-dimensional statistics, simplex, OLS 1 Introduction Linear regression is a central tool in statistical modeling, used to relate a response variable to a set of covariates through a linear predictor. The most widely used estimator in this setting is Ordinary Least Squares (OLS), which minimizes the sum of squared residuals and admits a closed-form solution under mild conditions. Under the classical linear model assumptions (most notably homoscedastic errors with finite second moments), OLS enjoys optimality properties, as guaranteed by the Gauss-Markov theorem, yielding the minimum-variance linear unbiased estimator. However, because squared residuals place increasing weight on large deviations, the OLS estimator can be highly sensitive to outliers or heavy-tailed noise. This sensitivity motivates the study of alternative estimators that retain the interpretability of linear models while providing improved robustness. A natural robust alternative to OLS is the Least Absolute Deviations (LAD) estimator, which minimizes the sum of absolute residuals and corresponds to median regression. By penalizing deviations linearly rather than quadratically, LAD reduces the influence of extreme observations and remains well-behaved under heavy-tailed error distributions. Despite these robustness properties, LAD regression has historically been approached primarily through linear programming formulations. Classical methods solve the resulting optimization problem using simplex or interior-point algorithms, as in the foundational work of 2 , 1 , and 12 . While these approaches guarantee global optimality, they rely on specialized linear programming solvers and can become computationally expensive as the problem dimension grows ( 14 ; 6 ) . Moreover, in high-dimensional or rank-deficient settings, particularly when the number of predictors is comparable to or exceeds the number of observations, LP formulations may suffer from numerical ill-conditioning or reduced reliability, limiting their practical scalability ( 15 ; 14 ) . To address these limitations, we propose a simple, scalable coordinate descent algorithm for LAD regression. We consider the standard linear regression model y_{i}=x_{i}^{\top}\beta+\varepsilon_{i},\qquad i=1,\dots,n, where y_{i}\in\mathbb{R} is the response, x_{i}\in\mathbb{R}^{p} is a vector of covariates (including an intercept when appropriate), and \beta\in\mathbb{R}^{p} is an unknown coefficient vector. Let X\in\mathbb{R}^{n\times p} denote the design matrix. This notation is used across the article. No parametric assumptions are imposed on the distribution of the error terms in implementing the proposed algorithm except E(\varepsilon_{i})=0 . However, additional assumptions on the error distribution may be required when deriving asymptotic statistical properties of the estimator. The Least Absolute Deviations (LAD) estimator is defined as any solution to \widehat{\beta}_{\mathrm{LAD}}=\arg\min_{\beta\in\mathbb{R}^{p}}\sum_{i=1}^{n}\bigl|y_{i}-x_{i}^{\top}\beta\bigr|, which corresponds to estimating the conditional median of y_{i} given x_{i} . Although this objective is convex, it is generally nondifferentiable and may admit multiple minimizers, particularly in high-dimensional or rank-deficient settings. To compute LAD estimators efficiently, we exploit the structure of the objective. Fixing all coordinates except \beta_{j} yields the univariate subproblem \beta_{j}\;\in\;\arg\min_{t\in\mathbb{R}}\sum_{i=1}^{n}\bigl|r_{i}^{(j)}-x_{ij}t\bigr|,\qquad r_{i}^{(j)}=y_{i}-\sum_{k\neq j}x_{ik}\beta_{k}, whose solution is given by a median or weighted median. This leads naturally to a coordinate descent scheme ( 16 ; 4 ) with exact updates (see Algorithm 1 ). By maintaining an incremental residual, the resulting algorithm avoids matrix inversion and reduces the cost of a full coordinate sweep to O(p\,n\log n) . Owing to the convexity of the LAD objective and the exactness of each coordinate update, the method is provably convergent to a global minimizer. Empirically, it remains stable in high-dimensional and underdetermined regimes, including cases where p\geq n , and achieves predictive performance comparable to LP-based LAD solvers when those methods are applicable. We also provide proof of convergence of this method. We assess the proposed method through synthetic experiments and real-world benchmarks commonly used in the robust and quantile regression literature, including the Boston Housing, Air Quality, and Concrete Compressive Strength datasets ( 12 ; 14 ; 9 ; 18 ) . Across these settings, the coordinate descent algorithm attains predictive accuracy comparable to LP-based LAD solvers when applicable, while remaining stable in high-dimensional regimes where LP formulations become unreliable. In experiments with p\geq n , ridge-initialized LAD-CD consistently improves upon unrefined initial estimates, with reductions in prediction error of up to 30-40%. These results complement the theoretical convergence guarantees and demonstrate the practical effectiveness of the proposed approach. The remainder of the paper is organized as follows. Section 2 reviews the LAD regression problem and the univariate optimization results that underpin coordinate-wise updates. Section 3 introduces the proposed coordinate descent algorithm, establishes its convergence properties, and presents computational optimizations and warm-start strategies. Section 4 reports empirical results on synthetic and real-world datasets, including high-dimensional and outlier-contaminated settings. Section 5 concludes with a discussion of practical implications and directions for future work. 2 Background This section reviews the Least Absolute Deviations (LAD) regression problem and summarizes classical solution strategies that motivate our proposed approach. We focus on two fundamental univariate optimization problems whose solutions form the basis of the coordinate descent algorithm developed in subsequent sections. 2.1 Minimizing Deviations from a Constant The first and most basic subproblem is to find a single constant a\in\mathbb{R} that best represents a set of observations \{y_{1},\dots,y_{n}\} in the L_{1} sense. This amounts to minimizing \mathcal{L}(a)=\sum_{i=1}^{n}|y_{i}-a|. (1) It is a classical result that any minimizer of ( 1 ) is a sample median of the observations \{y_{i}\} . This follows from a subgradient argument. The subgradient of |y_{i}-a| with respect to a is -\mathrm{sgn}(y_{i}-a) , where \mathrm{sgn}(\cdot) denotes the sign function. Consequently, the subdifferential of \mathcal{L}(a) is \partial\mathcal{L}(a)=\sum_{i=1}^{n}-\mathrm{sgn}(y_{i}-a). A necessary and sufficient condition for optimality is that 0\in\partial\mathcal{L}(a) , which holds precisely when the number of observations greater than a is at least as large as the number less than a , and vice versa. This characterizes the sample median ( 12 ) . 2.2 Minimizing Deviations for a No-Intercept Model The second subproblem concerns the estimation of a single slope coefficient b in a linear regression model without an intercept. The objective is \mathcal{L}(b)=\sum_{i=1}^{n}|y_{i}-bx_{i}|. (2) Assuming x_{i}\neq 0 , the objective can be rewritten as \mathcal{L}(b)=\sum_{i=1}^{n}|x_{i}|\left|\frac{y_{i}}{x_{i}}-b\right|. (3) (Observations with x_{i}=0 contribute a constant term to the objective and do not affect the minimizer.)