Implicit regularization for convex regularizers

Cesare Molinari, Mathurin Massias, Lorenzo Rosasco, Silvia Villa

Abstract: We study iterative regularization for linear models, when the bias is convex but not necessarily strongly convex. We characterize the stability properties of a primal-dual gradient based approach, analyzing its convergence in the presence of worst case deterministic noise. As a main example, we specialize and illustrate the results for the problem of robust sparse recovery. Key to our analysis is a combination of ideas from regularization theory and optimization in the presence of errors. Theoretical results are complemented by experiments showing that state-of-the-art performances can be achieved with considerable computational speed-ups.

Introduction

In modern machine learning, we often encounter "over-parametrized" models where the number of parameters significantly exceeds the number of data points. In such regimes, many solutions can perfectly fit the training data, but most are highly sensitive to noise and generalize poorly. To address this, researchers typically employ a "bias" or penalty, such as the $\ell_1$ norm for sparsity.

Traditionally, this is achieved through explicit regularization (e.g., Tikhonov regularization or the Lasso), which involves solving a penalized optimization problem. However, this can be computationally prohibitive. An alternative is iterative regularization, where the optimization algorithm itself provides stability. By stopping the algorithm early, one can naturally find a solution that generalizes well. While this phenomenon is well-understood for simple Euclidean norms, this paper extends the theory to general convex biases that are not strongly convex, such as those used in sparse recovery.

Methodology: The Chambolle-Pock Algorithm

The authors propose using the Chambolle-Pock (CP) algorithm, a first-order primal-dual method widely used in image processing. The core idea is to treat the number of iterations ($k$) as the regularization parameter rather than running the algorithm to full convergence, which would eventually overfit the noise.

CP is computationally efficient, requiring only matrix-vector multiplications and proximity operators. The authors provide a rigorous theoretical framework to analyze how CP behaves under worst-case deterministic noise. They utilize Bregman divergence—a generalized distance measure—to prove that iterates remain stable and converge toward the true solution before the noise begins to dominate the process.

Key Insights: Stability and Semi-convergence

A central insight of this work is that an optimization algorithm can serve as a standalone regularization tool. The path taken by the algorithm is itself the solution path. This leads to the phenomenon of semi-convergence: in the presence of noise, iterates initially move closer to the clean ground truth but eventually diverge as they begin to fit the noise. Early stopping captures the "sweet spot" at the peak of this curve.

Figure 1: Convergence and stability of the Chambolle-Pock iterates. The plot shows the Bregman divergence (blue), distance to ground truth (orange), and residual (green) over iterations.

Furthermore, the theoretical stability results are "dimension-free." This means the guarantees hold even as the number of features becomes extremely large or infinite, a critical property for modern high-dimensional machine learning applications.

Experimental Results

The approach was evaluated on synthetic sparse recovery, matrix completion, and real-world text classification using the rcv1-train dataset ($n=20,242$, $p=26,683$).

  • Computational Efficiency: On the rcv1 dataset, the iterative CP approach reached optimal performance in just 0.5 seconds, compared to 50 seconds for the traditional Lasso (Tikhonov) approach—a 100x speedup.
  • Predictive Performance: Despite the speedup, the iterative approach achieved a Mean Squared Error (MSE) of 0.21, nearly matching the 0.19 achieved by the slower Lasso method.
  • Theoretical Alignment: The empirical optimal stopping time was found to scale roughly as $1/\delta$ (where $\delta$ is the noise level), validating the authors' theoretical predictions.

Limitations and Future Work

While the results are promising, the current analysis focuses on worst-case deterministic noise. Extending these proofs to stochastic noise models would be a significant next step for broader ML applications. Additionally, while linear models are foundational, exploring how these implicit regularization properties translate to non-linear models, such as deep neural networks, remains a major open question. Finally, the authors suggest that future work could establish "lower bounds" to determine if these stability results are mathematically optimal.

Summary updated

Abstract

We study iterative regularization for linear models, when the bias is convex but not necessarily strongly convex. We characterize the stability properties of a primal-dual gradient based approach, analyzing its convergence in the presence of worst case deterministic noise. As a main example, we specialize and illustrate the results for the problem of robust sparse recovery. Key to our analysis is a combination of ideas from regularization theory and optimization in the presence of errors. Theoretical results are complemented by experiments showing that state-of-the-art performances can be achieved with considerable computational speed-ups.
BibTeX
@inproceedings{molinari2021implicit,
  author = {Cesare Molinari and Mathurin Massias and Lorenzo Rosasco and Silvia Villa},
  title = {{Implicit regularization for convex regularizers}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=Sd-ZizeEHx5},
}
Figure