Implicit Regularization Paths of Weighted Neural Representations

Summary

Neural networks are a powerful tool for extracting features from data, but these features can be very high-dimensional. This high dimensionality can be a bottleneck for training machine learning models, requiring computational power and memory. This manuscript investigates implicit regularization through subsampling and draws a connection to weighted regression problems. The authors provide theoretical results for the claimed connection between implicit regularization via subsampling and regression. The authors provide numerical evidence of their investigations.

Strengths

The manuscript is well-written and provides an interesting insight into the connection between subsampling approaches and explicit regularization.

Weaknesses

Some works have provided between subsampling and iterative least squares approaches, see Slagel et al., Sampled Tikhonov Regularization for Large Linear Inverse Problems.

Questions

see weaknesses.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

4

Limitations

yes.

Summary

This paper studies the weighted linear regression problem where the feature matrix is left-multiplied with a random matrix $\mathbf{W}$ denoting the sample weighting. Under the assumption of the asymptotic freeness between this weighting matrix and the feature matrix, the paper shows that the weighted ridge regression estimator is equivalent to a simple ridge regression estimator in the limit of infinite samples by establishing a connection between the regularization strengths of the weighted and the simple ridge regression. Based on this regularization path, the paper gives illustrative examples of concrete weighting matrix and feature matrix. Moreover, the paper also shows a equivalence between the risk of ensemble weighted and simple ridge regression under the same regularization path. Based on this result, the paper derives an optimal sub-sample size for the ensemble training. Theoretical results of this paper is accompanied by experimental verification.

Strengths

1. The paper considers a general scheme where $\mathbf{W}$ can be any random weighting matrix, which can generalize beyond the sub-sampling scenario. The assumption on the asymptotic freeness between the weighting matrix and the feature matrix is quite relaxed. 2. The paper derives an exact relationship between the regularization of the weighted ridge regression and that of the simple ridge regression in the limit of $n\rightarrow\infty$. This relationship is verified by the experiments presented in the paper. 3. The paper also derives the equivalence between risks of the ensemble weighted ridge regression and the simple ridge regression. The equivalence demonstrates a bias-variance trade-off and also validate the benefit of using a larger ensemble size. 4. Although the results is based on sophisticated mathematical notions, the paper uses intuitive explanation to make the results more comprehensible by a broader audience.

Weaknesses

1. The results derived in the paper has limited applicability. In particular, although it would be interesting to know the equivalence between the weighted ridge regression and the simple ridge regression, the regularization path does not tell much about how should we choose a weighting matrix, even assuming the optimal ridge regression regularization is known. Moreover, the optimal sub-sample size in Proposition 7 involves computing $\mu^*$ which cannot be done easily. Although the paper discussed a way to measure $\mu^*$, it is still computationally heavy, and even in the case where $\mu^*$ is known, one might not be able to measure the degree of freedom easily. 2. The paper considers an asymptotic regime where the sample size goes to infinity. The results in the paper will have better implications if a dependency on $n$ is given. 3. The paper's result is derived under the ridge regression setting. Although one can always choose $\Phi$ to be the output of some pre-trained neural network, the results barely connect to any property of neural network training.

Questions

1. Are there any example in real-world applications where the weighting matrix is not a diagonal matrix? 2. Based on the theoretical results in the paper, what would be the benefit of using a sub-sampling matrix with non-binary diagonal entries?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper has a good discussion of its limitations.

Summary

This paper investigates the implicit regularization effects of weighted pretrained features. It establishes a path of equivalence between different weighting matrices and ridge regularization with matching effective degrees of freedom. The study extends results to structured features and ensembles, providing theoretical validation for random and kernel features, and proposes an efficient cross-validation method to finetune subsampled pretrained representations in practice.

Strengths

- Table 1 provides a clear overview of the previous works, along with the contributions and organization of this paper. - The theoretical results are comprehensive and strong in terms of relaxed assumptions on the features and weights. - The theoretical results bring insights into designing a practical cross-validation algorithm, whose effectiveness is supported by experiments.

Weaknesses

- While Table 1 and the summary of results provide a relatively clear view of the theoretical contributions, the abstract and the motivation part of the introduction read somewhat confusing. For example, the "path of equivalence" is repeatedly mentioned in the abstract and introduction as one of the main contributions, but without a clear explanation/intuition of what it means until later. - The problem setup and notations are not clearly stated before being used. For example, in terms of setup, in Assumption A, it's unclear what the convergence refers to in "$W^\top W$ and $\Phi \Phi^\top/n$ converge almost surely to bounded operators". In terms of notations, $\|\cdot\|_{tr}$ and $\overline{tr}(\cdot)$ are used without clear definitions for reference. - Overall, the layout of the results is a little bit hard to follow, partially due to the lack of clear problem setup and notations mentioned before, and partially due to presuming prior knowledge of specific technical tools like free probability theory.

Questions

- In Definition A, what's the precise definition of $\overline{tr}(\cdot)$? What does it mean by saying "$W^\top W$ and $\Phi \Phi^\top/n$ converge almost surely to bounded operators"? If it refers to the convergence as $n \to \infty$, then does it mean the analysis is conducted in the asymptotic regime? - In line 196, if (5) implies $\lambda < \mu$, isn't the regularization level $\lambda$ of the subsampled estimator lower (instead of higher) than that of the full estimator $\mu$? - It's somehow counter-intuitive that the equivalence path results depend only on the subsample fraction $k/n$ under the "general" data assumption. Common analyses in the asymptotic regime reduce data properties to the subsample ratio $k/n$ usually based on strong assumptions on the data distribution like Gaussian, while data-agnostic subsampling on adversarial data should bring inevitable compromise compared to full data (e.g., with a direction that is only learnable through a single data point). It seems that the "infinitesimally freeness" in Assumption A implicitly circumvents this issue, but it's unclear in the current discussion. For example: - Whether Assumption A enforces a "nice" data distribution, a "good" subsampling strategy, or both? - If Assumption A implies a "good" subsampling strategy, can such subsampling matrix $W$ be efficiently constructed in practice?

Rating

5

Confidence

3

Soundness

2

Presentation

1

Contribution

3

Limitations

Limitations are well-discussed in the Conclusion. Some further limitations are mentioned in Weaknesses and Questions.

Response to the Author's Rebuttal

Thank you for your response. The authors response to [W1] and [Q1] further convinced me about the applicability of the results. Moreover, the author also discussed how to extend the result to finite $n$ in the response to [W2]. Therefore, I have raised my score accordingly.