Piece-wise quadratic approximations of arbitrary error functions for fast and robust machine learning

Alexander N. Gorban, Eugenij Moiseevich Mirkes, Andrei Yu. ZinovyevNeural Networks 2016 · OpenReview

TL;DR

This paper introduces a novel framework called Piecewise Quadratic Subquadratic (PQSQ) potentials for approximating arbitrary error functions in machine learning. This allows for significantly faster and more robust optimization in various ML tasks, including data approximation and regularized regression, by offering a computationally efficient alternative to traditional quadratic or L1-norm based methods.

What Problem Does This Paper Address?

Traditional machine learning often relies on minimizing mean squared error, which is computationally efficient due to its quadratic nature. However, this approach struggles with high-dimensional, noisy data and can be overly sensitive to outliers. While non-quadratic error functions (like L1-norm) offer better robustness, they come with a significant computational cost. This paper addresses the need for a flexible and computationally efficient framework that can handle arbitrary error functions, bridging the gap between the speed of quadratic methods and the robustness of non-quadratic ones.

Methods

The core contribution is the development of Piecewise Quadratic Subquadratic (PQSQ) potentials. These potentials are continuous, monotonically growing functions constructed from segments of parabolas. The key idea is that any subquadratic error function can be approximated by a PQSQ function. The paper provides a theoretical framework based on the concept of "minorant functions" and "cones" to formalize this approximation.

For optimization, they propose a splitting algorithm that iteratively refines the approximation. This algorithm is guaranteed to converge to a local minimum. The paper demonstrates how this PQSQ framework can be applied to:

  • Data Approximation: k-means clustering, principal component analysis (PCA), principal curves, and manifolds.
  • Regularized Regression: Imitating Lasso and Elastic Net by using PQSQ potentials as penalty terms.

A novel "black hole trick" is also introduced to induce sparsity in regression solutions.

Datasets

The paper mentions using synthetic and real-life datasets for evaluation. Specific datasets are not detailed in the main text, but references to the UCI Machine Learning Repository are made for regression tasks. The authors also provide links to GitHub repositories containing Matlab implementations and scripts for generating datasets used in their experiments.

Key Insights and Ideas

  • Approximation Power: Piecewise quadratic functions can effectively approximate a wide range of subquadratic error potentials, including L1-norm and fractional quasinorms.
  • Computational Efficiency: By approximating complex error functions with PQSQ potentials, optimization can be performed almost as efficiently as with standard quadratic potentials.
  • Robustness: PQSQ potentials can be designed to be robust to outliers, either through the choice of intervals or by incorporating a "trimming" mechanism.
  • Flexibility: The framework is adaptable to various error metrics and can be integrated into existing machine learning algorithms.
  • Theoretical Foundation: The use of minorant functions and cones provides a solid theoretical basis for the PQSQ approach.

Key Results

  • Speedup: PQSQ-based machine learning methods achieve orders of magnitude faster computational performance compared to state-of-the-art methods, particularly for L1-based PCA and regularized regression. For instance, PQSQ-based PCA is reported to be 100 times faster than some L1-PCA implementations while maintaining comparable accuracy.
  • Accuracy: The PQSQ-based methods achieve similar or better approximation accuracy than existing methods, even in the presence of significant noise and outliers.
  • Robustness: PQSQ-based PCA demonstrates superior robustness to sparse noise contamination compared to standard L2-based PCA. For example, it can withstand up to 40% contamination in some scenarios.
  • Sparsity: The "black hole trick" effectively introduces sparsity in regularized regression, comparable to Lasso.

Limitations and Future Work

  • Local Minima: The proposed algorithms, like many in machine learning, converge to local minima, and the specific minimum found can depend on the initial approximation. The authors suggest running the algorithm multiple times with different initializations to mitigate this.
  • Parameter Tuning: The performance of PQSQ potentials depends on the choice of parameters, such as the number of intervals and the definition of the majorating function. Determining optimal parameters for specific datasets might require further study.
  • Arbitrary Functions: While PQSQ can approximate subquadratic functions, it is not directly applicable to functions with super-quadratic growth.
  • Future Work: The authors suggest that the PQSQ framework can be applied to a wider range of machine learning methods beyond those discussed. They also highlight the potential for further research into adaptive error potentials and more sophisticated parameter selection strategies.

Summary updated

BibTeX
@inproceedings{gorban2016piece,
  author = {Alexander N. Gorban and Eugenij Moiseevich Mirkes and Andrei Yu. Zinovyev},
  title = {{Piece-wise quadratic approximations of arbitrary error functions for fast and robust machine learning}},
  booktitle = {Neural Networks},
  year = {2016},
  url = {https://openreview.net/forum?id=opEa75oiX5G},
}

Loading related content...

Figure