Abstract
We investigate the modeling and the numerical solution of machine learning problems with prediction functions which are linear combinations of elements of a possibly infinite-dimensional dictionary. We propose a novel flexible composite regularization model, which makes it possible to incorporate various priors on the coefficients of the prediction function, including sparsity and hard constraints. We show that the estimators obtained by minimizing the regularized empirical risk are consistent in a statistical sense, and we design an error-tolerant composite proximal thresholding algorithm for computing such estimators. New results on the asymptotic behavior of the proximal forward-backward splitting method are derived and exploited to establish the convergence properties of the proposed algorithm. In particular, our method features a $o(1/m)$ convergence rate in objective values.
Introduction
In supervised learning, incorporating prior knowledge about model coefficients is essential for creating robust and interpretable models. Common requirements include sparsity—the idea that only a few features are truly relevant—and hard constraints, such as requiring parameters to remain within specific physical or logical bounds. While standard techniques like LASSO ($L_1$ regularization) or Ridge regression ($L_2$ regularization) handle these priors in isolation, they often struggle with "composite" priors that combine multiple requirements simultaneously.
This paper addresses the challenge of learning with these complex priors, particularly when working with infinite-dimensional dictionaries where the number of possible features is effectively limitless. The authors bridge the gap between flexible modeling and rigorous mathematical guarantees, ensuring both statistical consistency and algorithmic efficiency.
The Composite Regularization Model
The core innovation of this work is a generalized linear model where the prediction function is a combination of features from a dictionary, governed by a novel composite regularization function $g_k$. The regularizer is defined as:
$$g_k = \iota_{C_k} + \sigma_{D_k} + h_k$$
This formulation allows for three distinct types of regularization to be applied in unison:
- Hard Constraints ($\iota_{C_k}$): An indicator function that forces coefficients to stay within a closed interval $C_k$.
- Sparsity ($\sigma_{D_k}$): A support function that promotes sparsity, generalizing the well-known soft-thresholding operator.
- Stability ($h_k$): A convex function that ensures the optimization problem remains stable and well-behaved.
By selecting different parameters for these components, the model can simplify into established methods like Ridge regression, Elastic Net, or Bridge regression, while also supporting entirely new combinations of constraints that were previously difficult to optimize.
Statistical Consistency in Infinite Dimensions
A primary contribution of this research is the proof of statistical consistency. In high-dimensional or infinite-dimensional settings, it is mathematically challenging to guarantee that a model will eventually converge to the "truth" as more data is collected.
The authors establish Theorem 2.4, which provides the specific conditions under which the learned model is guaranteed to converge to the true target function as the number of samples $n$ goes to infinity. A key technical requirement for this stability is the "total convexity" of the regularizer on bounded sets, a property the authors rigorously prove to ensure the learning process remains robust even in complex feature spaces.
Error-Tolerant Optimization
To solve the resulting optimization problem, the paper introduces an error-tolerant proximal forward-backward splitting algorithm. In practical applications, computing the exact "proximal step" (the mathematical operation that applies the regularizer) is often impossible due to computational limits.
Unlike standard versions, this algorithm is designed to handle these inaccuracies. As long as the computational errors decrease at a certain rate, the algorithm is guaranteed to converge to the correct global minimum. Furthermore, the authors establish a convergence rate of $o(1/m)$ for the objective values. This is asymptotically faster than the standard $O(1/m)$ rate found in most first-order optimization methods, meaning the error drops more quickly as the number of iterations $m$ increases.
Conclusion
This work provides a unified framework for machine learning that balances flexible modeling with rigorous theoretical foundations. By introducing proximal thresholders that can simultaneously "shrink" and "clip" coefficients, the authors enable the use of sophisticated priors without sacrificing statistical or algorithmic guarantees. While the focus is theoretical, the $o(1/m)$ convergence rate and error-tolerance properties suggest significant potential for efficient implementations in high-dimensional data analysis.
Summary updated