Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks

Dan Zhao

TL;DR

This paper challenges the long-held belief that "depth" is a prerequisite for the implicit regularization that helps deep networks find low-rank solutions. By introducing a novel explicit penalty—the ratio of the nuclear norm to the Frobenius norm—and pairing it with the Adam optimizer, the author demonstrates that a single-layer (shallow) network can match or exceed the generalization performance of deep linear networks while converging significantly faster.

What Problem Does This Paper Address?

In deep learning, we often see models with far more parameters than data points still generalize remarkably well. Researchers usually attribute this to implicit regularization: the idea that the optimization process (like Gradient Descent) naturally steers the model toward "simple" solutions, such as low-rank matrices in completion tasks.

Previous studies suggested that depth is the secret sauce here. In deep linear networks, adding layers acts as a form of "pre-conditioning" that accelerates the path toward these low-rank solutions. However, depth comes with a computational cost. The author asks: Can we achieve the same beneficial regularization effects without the extra layers? Specifically, can we use an explicit mathematical penalty to "mimic" what depth does implicitly?

Methods

The author proposes a specific explicit regularizer $R(W)$ defined as the ratio between the nuclear norm (sum of singular values) and the Frobenius norm (square root of the sum of squares of entries):

$$R(W) = \frac{\|W\|_*}{\|W\|_F}$$

This is a spectral adaptation of the "Hoyer measure," often used to measure sparsity.

Impact of the ratio penalty on GD vs. Adam

The key methodological twist is the interplay between the penalty and the optimizer. As shown above, while this penalty does little for standard Gradient Descent (GD), it becomes incredibly powerful when used with Adam. The author provides a theoretical characterization showing how Adam’s variance-weighted updates interact with the gradient of this ratio penalty to create "depth invariance"—making the learning dynamics of a shallow network look almost identical to those of a deep one.

Datasets

The paper evaluates the approach on two main fronts:

  1. Synthetic Matrix Completion: Recovering a ground-truth rank-5 matrix of size $100 \times 100$ from a subset of observed entries.
  2. MovieLens100K: A classic real-world benchmark for recommendation systems consisting of 100,000 ratings from 944 users on 1,683 movies. This tests how the method handles discrete, noisy, and high-rank real-world data.

Key Insights and Ideas

  • Depth Invariance: This is the "aha moment." Usually, deeper networks find lower-rank solutions than shallow ones. With this specific penalty and Adam, a depth-1 network (a simple matrix) achieves the same rank reduction and generalization as a depth-5 network.
  • The Optimizer Matters: Explicit regularization isn't a silver bullet on its own. The results show that different optimizers have different "inductive biases." The proposed penalty specifically "mirrors" the effect of depth only when filtered through the lens of adaptive optimizers like Adam or Adamax.
  • Efficiency via Simplification: Because the single-layer network with the penalty performs as well as deep networks, we can effectively "compress" the benefits of depth into a much simpler, faster-to-train architecture.
  • Challenging the "Implicit-Only" Narrative: Recent AI research has leaned heavily into the idea that implicit bias is all you need. This paper suggests that a nuanced combination of explicit penalties and optimizer choice can be just as effective, if not more so.

Key Results

  • Speed: The penalized shallow network under Adam converges to a solution roughly 10 times faster than standard Gradient Descent on deep networks.
  • Performance: In low-data regimes (where very few matrix entries are known), the proposed method outperformed established techniques like SoftImpute and OptSpace.
Matrix completion performance across sample sizes
  • Real-World Success: On the MovieLens100K dataset, a simple Depth-1 Linear Neural Network with the ratio penalty achieved an RMSE of 0.915, outperforming significantly more complex models like GraphRec and AutoSVD++. It effectively matched the performance of state-of-the-art specialized architectures without needing side information or complex graph features.

Limitations and Future Work

  • Linearity: The study focuses primarily on linear networks. While linear networks are excellent "test-beds" for understanding optimization, it remains to be seen how these insights translate to non-linear architectures (like Transformers or CNNs) used in computer vision and NLP.
  • Hyperparameter Sensitivity: The penalty relies on a tuning parameter ($\lambda$). While the author notes the results are robust across a range of values, finding the optimal balance in a new domain might require search.
  • Theoretical Assumptions: The theoretical proofs for Adam's dynamics rely on certain approximations (approximating Adam via gradient flow). While these hold up empirically in the paper, they are simplifications of how the discrete algorithm actually behaves.

The author suggests that future work should explore whether this "ratio penalty" can improve efficiency in other areas like reinforcement learning or adversarial robustness, where low-rank structures are known to be beneficial.

Summary updated

Abstract

Works on implicit regularization have studied gradient trajectories during the optimization process to explain why deep networks favor certain kinds of solutions over others. In deep linear networks, it has been shown that gradient descent implicitly regularizes toward low-rank solutions on matrix completion/factorization tasks. Adding depth not only improves performance on these tasks but also acts as an accelerative pre-conditioning that further enhances this bias towards low-rankedness. Inspired by this, we propose an explicit penalty to mirror this implicit bias which only takes effect with certain adaptive gradient optimizers (e.g. Adam). This combination can enable a degenerate single-layer network to achieve low-rank approximations with generalization error comparable to deep linear networks, making depth no longer necessary for learning. The single-layer network also performs competitively or out-performs various approaches for matrix completion over a range of parameter and data regimes despite its simplicity. Together with an optimizer’s inductive bias, our findings suggest that explicit regularization can play a role in designing different, desirable forms of regularization and that a more nuanced understanding of this interplay may be necessary.
BibTeX
@inproceedings{zhao2022combining,
  author = {Dan Zhao},
  title = {{Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=sADLRl2STMe},
}
Figure