  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 $\ell_2$-statistical rate and variable
selection consistency.
