Sparse Polynomial Regression under Anomalous Data
Roozbeh Abolpour, Mohammad Reza Hesamzadeh, Maryam Dehghani · 2025
Read Sparse Polynomial Regression under Anomalous Data by Roozbeh Abolpour, Mohammad Reza Hesamzadeh, Maryam Dehghani (2025) 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-2508-18199.txt.
Introduction
Fitting a polynomial curve to data is a common task, but real datasets carry outliers and most terms of the curve are usually useless. Abolpour, Hesamzadeh, and Dehghani tackle both problems at once. They rewrite the sparse fitting task, with bad points filtered out, as a mixed-integer linear program, then reshape it through two further forms.
The final form, a fractional program, is shown on paper to be easier to compute with than the earlier shapes. They then build a two-step method that loosens the problem into an easy convex form, solves it, and recovers a sparse answer. Tests on two datasets pit the method against several standard regression tools and learning models. The new method performed promisingly across the tests. The authors offer it for data work where a few wild points can drag a simple curve far off course.
Catalog record
| CREATOR | Roozbeh Abolpour, Mohammad Reza Hesamzadeh, Maryam Dehghani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-18199
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sparse Polynomial Regression under Anomalous Data Roozbeh Abolpour, Mohammad Reza Hesamzadeh, Maryam Dehghani Abstract This paper starts with the general form of the polynomial regression model. We reformulate the Sparse Polynomial Regression Model (SPRM) with anomalous data filtering as Mixed-Integer Linear Program (MILP). This MILP is then converted to a non-convex Quadratically Constrained Quadratic Program (QCQP). Through a proposed mapping, the derived QCQP is reformulated as a Fractional Program (FP). We theoretically show that the reformulated FP has better computational properties than the original QCQP. We then suggest a conic-relaxation-based algorithm to solve the proposed FP. A Two-Step Convex Relaxation and Recovery (TS-CRR) algorithm is proposed for sparse polynomial regression with anomalous data filtering. Through a series of comprehensive computational experiments (using two different datasets), we have compared the results of our proposed TS-CRR algorithm with the results from several regression and artificial intelligent models. The numerical results show the promising performance of our proposed TS-CRR algorithm as compared to those studied benchmark models. ∎ 1 Introduction Regression models are fundamental tools in statistics and data science which are widely used in disciplines such as data engineering [ 3 ] , prediction [ 4 ] , times series classification [ 14 ] , biomedical engineering [ 15 ] , economics [ 19 ] , and finance [ 20 ] . These models help uncover relationships between variables, support predictive analytics, and inform decision-making by analyzing historical data to understand how changes in independent variables affect a dependent variable [ 17 ] . Among various regression models, the polynomial regression is particularly valuable for capturing nonlinear patterns. They model the relationship between dependent and independent variables using polynomial functions with unknown parameters [ 8 ] . Authors in [ 5 ] discuss the statistical properties of a polynomial regression model. The hierarchical variable selection for polynomial regression models is proposed in [ 6 ] . The hierarchical polynomial regression model is applied in various domains, including predicting the global transmission of COVID-19 [ 12 ] , healthcare [ 26 ] , and marketing [ 22 ] . However, two key challenges arise when regression models are applied to real-world and high-dimensional data: (1) the presence of anomalous data that can distort model estimates [ 13 ] , and (2) the rapid growth in polynomial terms, which can lead to overfitting and computational complexity [ 7 ] . These challenges need to be properly addressed to ensure a practical and robust polynomial regression model. The first challenge is addressed in the literature by proposing robust polynomial regression approaches. Authors in [ 2 ] propose a polynomial regression model for cases where significant anomalous data exist. Their robust regression models have provable guarantees on estimation accuracy and computational efficiency. A robust local polynomial regression with similarity kernels is proposed in [ 23 ] to mitigate the effect of anomalous data. It uses similarity kernels thereby improving robustness and estimation accuracy. Reference [ 18 ] introduces a theoretical advance in robust polynomial regression. It presents a polynomial-time algorithm for univariate polynomial regression that is robust to nearly 50% adversarial outliers. Complementing this, [ 28 ] using wind-power data, demonstrates how robust polynomial regression techniques by removing anomalous data can significantly improve the prediction performance. The second challenge is mainly tackled in the literature by proposing sparsity-based techniques. Reference [ 16 ] provides the foundational theory and methods for sparse regression focusing on the Lasso (Least Absolute Shrinkage and Selection Operator) and its variations. Building on this foundation, a mixed-integer programming formulation for sparse polynomial regression is discussed in [ 6 ] . The problem is then cast as a bilevel minimization model and solved using a cutting-plane algorithm. In [ 25 ] sparsity-exploiting techniques for complex polynomial optimization is studied. The proposed approach in [ 25 ] can be potentially used for managing the computational complexities of polynomial regression models. In [ 10 ] , sparsity in multivariate regression is studied. It provides valuable theoretical support for selecting sparse modeling approaches in high-dimensional regression. A matching-pursuit–based sparse regression algorithm that is robust to adversarial corruptions in both predictors and responses is developed and suggested in [ 11 ] . Beyond classical regression context, [ 24 ] explores generalized sparse regression codes for communication systems showing its practical benefits. Furthermore, [ 1 ] compares sparse polynomial approximations to deep neural networks showing that former can achieve competitive performance while offering the interpretability and computational advantage. With this background, the current paper contributes to the relevant literature as follows: • The Sparse Polynomial Regression Model (SPRM) with anomalous data filtering is first formulated as a MILP and then as a nonconvex QCQP. Through an introduced fractional mapping, the nonconvex QCQP is reformulated as a Fractional Program (FP). • We theoretically prove that the reformulated FP has better computational properties than the original nonconvex QCQP. • We propose a conic-relaxation-based model to solve our proposed FP. Furthermore, a Two-Step Convex Relaxation and Recovery (TS-CRR) algorithm is proposed for sparse polynomial regression under anomalous data. • Through a set of comprehensive numerical experiments, we compare the results of our TS-CRR algorithm with those from several benchmark models. The comparative results show the promising performance of our proposed TS-CRR algorithm. This paper is organized as follows. Section 2 presents the problem formulation. Section 3 derives the proposed FP reformulation. The proposed TS-CRR algorithm is discussed in Section 4 . Two applications of our proposed regression approach under anomalous data are discussed in Section 5 . Finally, Section 6 concludes the paper. 2 Problem Formulation Suppose {\left\{x^{\left(k\right)}\right\}}^{N}_{k=1} and {\left\{y^{\left(k\right)}\right\}}^{N}_{k=1} are the given input and output data, respectively. The objective is to determine the following polynomial regression model y^{\left(k\right)}=\sum_{\alpha\in{\mathrm{\Gamma}}_{d}}{c_{\alpha}{x^{\left(k\right)}}^{\alpha}}+\epsilon^{\left(k\right)},\quad\forall k\in\left\{1,\dots,N\right\}, (1) where d is the polynomial degree, {\mathrm{\Gamma}}_{d}=\left\{\alpha\in{\mathbb{N}}^{n}\right|\ \sum^{n}_{i=1}{{\alpha}_{i}}\leq d\} with m_{d} distinct vectors (i.e. m_{d}=|{\mathrm{\Gamma}}_{d}| ), \epsilon^{k} is the error term, {x^{\left(k\right)}}^{\alpha}=\prod^{n}_{i=1}{{x^{\left(k\right)}_{i}}^{{\alpha}_{i}}\ } , and {\left\{c_{\alpha}\right\}}_{\alpha\in{\mathrm{\Gamma}}_{d}} is the set of polynomial coefficients. The following optimization problem determines these polynomial coefficients. \displaystyle\min_{\Omega_{1}} \displaystyle\quad\gamma (2a) \displaystyle s.t. \displaystyle\quad\left|y^{\left(k\right)}-\sum_{\alpha\in{\mathrm{\Gamma}}_{d}}{c_{\alpha}{x^{\left(k\right)}}^{\alpha}}\right|\leq\gamma,\quad\forall k\in\left\{1,\dots,N\right\}, (2b) where \Omega_{1}=\{c\in{\mathbb{R}}^{m_{d}},\gamma\in\mathbb{R}_{+}\} and \gamma is the regression error. Conventionally, a subset of the training data \{(x_{k},y_{k})\}_{k=1}^{N} is considered anomalous if its members deviate from the underlying mathematical model of the system. Hence, detecting the anomalous data requires a mathematical model, which may be unavailable in some real-world applications. To address this limitation, an alternative model-independent definition is proposed below. Definition 1 A subset \bar{J}\subset\{1,...,N\} is defined to contain the indices of anomalous data if it satisfies the following condition. \bar{J}=\underset{J\subset\{1,...,N\},|J|=|\bar{J}|}{\text{argmin}}\left(\max_{k\in\{1,...,N\}\setminus J}{\left|y^{\left(k\right)}-f(x^{(k)})\right|}\right), (3) where f(.) is the regression model.∎ This means, among all subsets J of a given size (same as \bar{J} ), we select the one whose removal from the dataset leads to the lowest possible maximum training error. This definition can be directly integrated into the training procedure, enabling the identification and elimination of anomalous data during training. To integrate both the anomalous-data definition 1 and the sparsity property into the polynomial regression optimization model ( 2 ), binary decision variables are introduced. Let set {\left\{s_{\alpha}\right\}}_{\alpha\in{\mathrm{\Gamma}}_{d}} include binary variables indicating whether each monomial term {\left\{{x}^{\alpha}\right\}}_{\alpha\in{\mathrm{\Gamma}}_{d}} is included in the regression model. In addition, let set {\left\{b_{k}\right\}}_{k=1}^{N} be binary variables indicating the inclusion of the k^{th} pair (x^{(k)},y^{(k)}) in training, where b_{k}=0