Piece-wise quadratic lego set for constructing arbitrary error potentials and their fast optimization

Alexander N. Gorban, Eugenij Moiseevich Mirkes, Andrei Yu. Zinovyev

Abstract

This paper introduces Piece-wise Quadratic Sub-quadratic (PQSQ) potentials, a framework for approximating arbitrary error functions using a "lego set" of parabolas. By leveraging the computational efficiency of quadratic functions while mimicking the robustness of non-quadratic norms like $L_1$, the proposed method enables machine learning algorithms such as PCA and regression to achieve significant speedups—often orders of magnitude faster than traditional robust methods—without sacrificing accuracy or outlier resistance.

Introduction

Most machine learning models rely on minimizing Mean Squared Error (MSE) because quadratic functions are computationally efficient to optimize. However, MSE is notoriously sensitive to outliers and the "curse of dimensionality." In noisy or high-dimensional environments, researchers often prefer $L_1$ norms or $L_p$ quasinorms ($0 < p < 1$) for their inherent robustness and ability to induce sparsity.

The primary drawback of these non-quadratic functions is their high optimization cost, often requiring complex linear programming or iterative reweighting schemes. This paper bridges the gap between the computational efficiency of quadratic methods and the robustness of non-quadratic norms through a universal approximation framework based on Piece-wise Quadratic Sub-quadratic (PQSQ) potentials.

The PQSQ Framework

The core of the proposed method is the construction of PQSQ potentials: continuous functions built from pieces of centered parabolas. This "lego" approach allows a PQSQ function to imitate almost any sub-quadratic error function—those that grow no faster than a parabola—by carefully selecting thresholds ($r_k$) and coefficients ($a_k, b_k$).

Approximation of an error function using piece-wise quadratic components.

Mathematically, the framework is grounded in the "cone of minorant functions" and utilizes concepts from min-plus algebra. The error function is treated as the lower envelope (minimum) of a set of quadratic functions, allowing complex potentials to be decomposed into simpler, manageable components.

Optimization via the Splitting Algorithm

Because the PQSQ potential is piece-wise quadratic, the authors introduce a "splitting" algorithm for optimization. This iterative process involves two main steps:

  1. Assignment: Each data point is assigned to a specific quadratic "piece" of the potential based on its current value.
  2. Minimization: A standard quadratic optimization problem is solved for the current assignment.
The iterative splitting algorithm for minimizing the PQSQ potential.

This algorithm is proven to converge in a finite number of steps. To further enhance performance in regression tasks (similar to Lasso), the authors implement a "black hole" trick: regression coefficients within a tiny epsilon of zero are immediately snapped to zero and removed from subsequent iterations, accelerating the path to sparse solutions.

Experimental Results

The PQSQ approach was evaluated against synthetic benchmarks and real-world datasets from the UCI Machine Learning Repository.

Robust PCA

In high-dimensional tests ($R^{100}$), PQSQ-based $L_1$ PCA successfully separated clusters even with 40% noise contamination, whereas standard $L_2$ PCA failed at just 2-3% noise. Computationally, the PQSQ method was 100 times faster than standard $L_1$-PCA and 500 times faster than the $L_1$-PCA* algorithm.

Sparse Regression

For regularized regression tasks, the PQSQ method achieved an average speedup of 120 times compared to the standard Matlab Lasso implementation across eight diverse real-world datasets, including medical and environmental data.

Discussion and Future Work

While the PQSQ splitting algorithm is highly efficient, it converges to a local minimum, similar to $k$-means. The authors suggest using smart initializations (such as $L_2$ results) or random restarts to mitigate this. Future work aims to extend this framework to more complex topological structures, such as principal graphs and manifolds, to better handle datasets with branching or circular logic. By providing a "lego set" for error potentials, this work opens new avenues for scalable, robust machine learning.

Summary updated

Abstract

Most of machine learning approaches have stemmed from the application of minimizing the mean squared distance principle, based on the computationally efficient quadratic optimization methods. However, when faced with high-dimensional and noisy data, the quadratic error functionals demonstrated many weaknesses including high sensitivity to contaminating factors and dimensionality curse. Therefore, a lot of recent applications in machine learning exploited properties of non-quadratic error functionals based on $L_1$ norm or even sub-linear potentials corresponding to quasinorms $L_p$ ($0<p<1$). The back side of these approaches is increase in computational cost for optimization. Till so far, no approaches have been suggested to deal with {\it arbitrary} error functionals, in a flexible and computationally efficient framework. In this paper, we develop a theory and basic universal data approximation algorithms ($k$-means, principal components, principal manifolds and graphs, regularized and sparse regression), based on piece-wise quadratic error potentials of subquadratic growth (PQSQ potentials). We develop a new and universal framework to minimize {\it arbitrary sub-quadratic error potentials} using an algorithm with guaranteed fast convergence to the local or global error minimum. The theory of PQSQ potentials is based on the notion of the cone of minorant functions, and represents a natural approximation formalism based on the application of min-plus algebra. The approach can be applied in most of existing machine learning methods, including methods of data approximation and regularized and sparse regression, leading to the improvement in the computational cost/accuracy trade-off. We demonstrate that on synthetic and real-life datasets PQSQ-based machine learning methods achieve orders of magnitude faster computational performance than the corresponding state-of-the-art methods.
BibTeX
@misc{gorban2016piece,
  author = {Alexander N. Gorban and Eugenij Moiseevich Mirkes and Andrei Yu. Zinovyev},
  title = {{Piece-wise quadratic lego set for constructing arbitrary error potentials and their fast optimization}},
  year = {2016},
  eprint = {1605.06276},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.06276},
}
Figure