# Understanding Implicit Regularization in Over-Parameterized Single Index Model

arXiv: https://arxiv.org/abs/2007.08322 · HTML: https://mlsanity.com/paper/2007.08322/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 12 of 12)

- [Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.09974/) (2022)
- [Implicit Regularization of Gradient Flow on One-Layer Softmax Attention](https://mlsanity.com/paper/2403.08699/) (2024)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Are Latent Factor Regression and Sparse Regression Adequate?](https://mlsanity.com/paper/2203.01219/) (2022)
- [Improving Adaptivity via Over-Parameterization in Sequence Models](https://mlsanity.com/paper/2409.00894/) (2024)
- [The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensing](https://mlsanity.com/paper/2403.01420/) (2024)
- [Interactive Learning of Single-Index Models via Stochastic Gradient Descent](https://mlsanity.com/paper/2602.17876/) (2026)
- [Robust High-dimensional Tuning Free Multiple Testing](https://mlsanity.com/paper/2211.11959/) (2022)
- [A Consistent and Scalable Algorithm for Best Subset Selection in Single Index Models](https://mlsanity.com/paper/2309.06230/) (2023)
- [Theoretical Analysis of Sparse Optimization with Reparameterization, Weight Decay, and Adaptive Learning Rate](https://mlsanity.com/paper/2605.25134/) (2026)
- [Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors](https://mlsanity.com/paper/2609.33025/) (2026)

## Abstract (arXiv)

In this paper, we leverage over-parameterization to design regularization-free algorithms for the high-dimensional single index model and provide theoretical guarantees for the induced implicit regularization phenomenon. Specifically, we study both vector and matrix single index models where the link function is nonlinear and unknown, the signal parameter is either a sparse vector or a low-rank symmetric matrix, and the response variable can be heavy-tailed. To gain a better understanding of the role played by implicit regularization without excess technicality, we assume that the distribution of the covariates is known a priori. For both the vector and matrix settings, we construct an over-parameterized least-squares loss function by employing the score function transform and a robust truncation step designed specifically for heavy-tailed data. We propose to estimate the true parameter by applying regularization-free gradient descent to the loss function. When the initialization is close to the origin and the stepsize is sufficiently small, we prove that the obtained solution achieves minimax optimal statistical rates of convergence in both the vector and matrix cases. In addition, our experimental results support our theoretical findings and also demonstrate that our methods empirically outperform classical methods with explicit regularization in terms of both ℓ2-statistical rate and variable selection consistency.