High-Dimensional Analysis for Generalized Nonlinear Regression: From Asymptotics to Algorithm

Jian Li, Yong Liu, Weiping WangAAAI 2024 · OpenReview

TL;DR

This paper introduces a unified theoretical framework for analyzing high-dimensional nonlinear regression, bridging the gap between complex models like neural networks and traditional complexity measures like "effective dimension." They propose a new algorithm, RFRed, that leverages these insights to improve generalization by jointly optimizing feature mappings and model parameters, demonstrating its effectiveness in experiments.

What Problem Does This Paper Address?

The field of machine learning has observed a phenomenon called "benign overfitting," where models, particularly deep neural networks, can perfectly fit training data (even to the point of memorization) yet still generalize surprisingly well to unseen data. While this has been studied for linear models and kernel methods, a unified theoretical understanding for general nonlinear regression models, especially concerning their complexity and generalization, has been lacking. Existing analyses often result in complex self-consistency equations that are hard to interpret or connect to established notions of model complexity. Furthermore, the role of techniques like subsampling in improving generalization alongside overparameterization remains an open question. This paper aims to fill this gap by providing a generalized high-dimensional asymptotic analysis framework for nonlinear regression, connecting it to effective dimension, and developing a practical algorithm based on these findings.

Methods

The authors develop a generalized high-dimensional analysis framework for nonlinear regression models. Key to their approach is the introduction of an "implicit regularization parameter" and its asymptotic equivalence to the "effective dimension," a classical measure of model complexity. They extend this to analyze both nonlinear ridge regression and its "ridgeless" counterpart.

Their theoretical framework is built upon several assumptions about the feature mapping and subsampling matrices. They then derive asymptotic risks for these models, finding that the limiting risks decrease as the effective dimension decreases. This theoretical insight motivates the proposal of a new algorithm called RFRed (Random Feature Regression with Effective Dimension). RFRed is designed to improve generalization by jointly optimizing the feature mapping (specifically, random Fourier features) and the model parameters, with the goal of minimizing both the training loss and the effective dimension. The algorithm employs a bi-level optimization approach, alternating between optimizing the model parameters and the hyperparameters (including regularization strength and feature mapping parameters).

Datasets

The paper uses the MNIST dataset for evaluation. The experiments involve generating synthetic data to test the theoretical findings and the proposed algorithm.

Key Insights and Ideas

  • Unified Framework for Nonlinear Regression: The paper provides a much-needed general asymptotic analysis framework for a broad class of nonlinear regression models, unifying insights from linear models, kernel methods, and neural networks.
  • Effective Dimension as a Key Complexity Measure: They establish a direct link between the asymptotic performance of nonlinear regression models and the "effective dimension," offering a more interpretable way to understand generalization beyond complex self-consistency equations.
  • Implicit Regularization and Subsampling Synergy: The work highlights how implicit regularization (arising from overparameterization) and explicit regularization (like ridge regression) interact with subsampling to influence generalization. They show that subsampling can potentially improve generalization even when downsampling data.
  • RFRed Algorithm for Improved Generalization: The proposed RFRed algorithm directly leverages the theoretical findings to actively minimize effective dimension, leading to better generalization performance. This is a practical outcome of the theoretical analysis.
  • Double Descent and Regularization: The experiments demonstrate how different levels of regularization affect the "double descent" phenomenon, with stronger regularization often smoothing out the performance curve and improving generalization in certain regimes.

Key Results

  • The theoretical analysis shows that the limiting excess risk in nonlinear regression decreases with the effective dimension.
  • Experiments with RFRed and various regularization parameters on the MNIST dataset demonstrate that the proposed algorithm can achieve good generalization performance.
  • The paper illustrates that subsampling, when applied appropriately, can sometimes improve generalization, contrary to a naive expectation that reducing data always hurts performance.
  • The study shows that stronger regularization can mitigate the negative effects of overparameterization and reduce the impact of the double descent phenomenon.

Limitations and Future Work

  • Strict Assumptions on Subsampling Matrix: Assumption 4, regarding orthogonal subsampling matrices, is noted as being "relatively strict" and may not hold for all i.i.d. sketching matrices.
  • Computational Complexity of Effective Dimension: While the paper proposes RFRed to optimize effective dimension, computing this metric can be computationally expensive, especially in the over-parameterized regime. The paper mentions using approximations and alternating optimization to mitigate this.
  • Future Work: The authors suggest further experiments, including the impact of trainable feature mappings and comparisons with other state-of-the-art methods, which are left for the appendix. The theoretical framework could potentially be extended to other learning settings.

Summary updated

Abstract

Overparameterization often leads to benign overfitting, where deep neural networks can be trained to overfit the training data but still generalize well on unseen data. However, it lacks a generalized asymptotic framework for nonlinear regressions and connections to conventional complexity notions. In this paper, we propose a generalized high-dimensional analysis for nonlinear regression models, including various nonlinear feature mapping methods and subsampling. Specifically, we first provide an implicit regularization parameter and asymptotic equivalents related to a classical complexity notion, i.e., effective dimension. We then present a high-dimensional analysis for nonlinear ridge regression and extend it to ridgeless regression in the under-parameterized and over-parameterized regimes, respectively. We find that the limiting risks decrease with the effective dimension. Motivated by these theoretical findings, we propose an algorithm, namely RFRed, to improve generalization ability. Finally, we validate our theoretical findings and the proposed algorithm through several experiments.
BibTeX
@inproceedings{li2024high,
  author = {Jian Li and Yong Liu and Weiping Wang},
  title = {{High-Dimensional Analysis for Generalized Nonlinear Regression: From Asymptotics to Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=NjjXMNm1Ym},
}
Figure