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 are achieved with considerable computational speed-ups.
Introduction
In over-parameterized machine learning, models often have more parameters than training data points, allowing multiple solutions to perfectly interpolate the data. To prevent overfitting to noise, regularization is typically employed. While explicit regularization (e.g., adding a penalty term like the Lasso) is standard, it requires tuning a hyperparameter $\lambda$. This paper explores implicit (iterative) regularization, where an optimization algorithm is run on the unpenalized problem and stopped early, with the iteration count $k$ acting as the regularization parameter.
Methodology: Primal-Dual Iterative Regularization
The authors adapt the Chambolle-Pock (CP) algorithm, a first-order primal-dual method, to solve the problem of minimizing a convex function $J(w)$ subject to $Xw = y$. Unlike previous work focused on strongly convex biases, this research extends guarantees to general convex regularizers like the $L_1$ norm (for sparsity) or the nuclear norm (for low-rank matrices).
The core theoretical contribution is the analysis of the algorithm's stability under noisy data $y^\delta$. The authors derive early-stopping bounds and prove that to achieve optimal stability, the stopping time $k$ should scale inversely with the noise level ($k \propto 1/\delta$).
Key Insights: Semi-convergence
A critical phenomenon identified is semi-convergence. As the algorithm iterates, the distance to the true noiseless solution initially decreases. However, if left to run to convergence on noisy data, the iterates eventually diverge as they begin to fit the noise.
Results and Computational Efficiency
Empirical tests on synthetic and real-world datasets (such as rcv1-train) show that iterative regularization matches the performance of explicit penalization methods while offering significant computational advantages.
On the rcv1 dataset, the iterative CP approach achieved its optimal Mean Squared Error in just 0.5 seconds (20 iterations). In contrast, computing the standard Lasso path over a grid of 100 $\lambda$ values took 50 seconds, representing a 100x speedup. This demonstrates that stopping an efficient first-order algorithm early can be a powerful and fast alternative to traditional regularization paths.
Conclusion
This work provides a theoretical foundation for using primal-dual algorithms as implicit regularizers for general convex functions. By establishing stability bounds and demonstrating massive speedups, the authors show that iterative regularization is a viable and often superior alternative to explicit penalization in high-dimensional linear models. Future work will explore extensions to stochastic noise and non-linear models like deep neural networks.
Summary updated