Understanding the implicit regularization imposed by neural network
architectures and gradient based optimization methods is a key challenge in
deep learning and AI. In this work we provide sharp results for the implicit
regularization imposed by the gradient flow of Diagonal Linear Networks (DLNs)
in the over-parameterized regression setting and, potentially surprisingly,
link this to the phenomenon of phase transitions in generalized hardness of
approximation (GHA). GHA generalizes the phenomenon of hardness of
approximation from computer science to, among others, continuous and robust
optimization. It is well-known that the $\ell^1$-norm of the gradient flow of
DLNs with tiny initialization converges to the objective function of basis
pursuit. We improve upon these results by showing that the gradient flow of
DLNs with tiny initialization approximates minimizers of the basis pursuit
optimization problem (as opposed to just the objective function), and we obtain
new and sharp convergence bounds w.r.t.\ the initialization size. Non-sharpness
of our results would imply that the GHA phenomenon would not occur for the
basis pursuit optimization problem -- which is a contradiction -- thus implying
sharpness. Moreover, we characterize $\textit{which}$ $\ell_1$ minimizer of the
basis pursuit problem is chosen by the gradient flow whenever the minimizer is
not unique. Interestingly, this depends on the depth of the DLN.

该研究探讨深度学习和人工智能中神经网络结构和梯度优化方法所施加的隐式规则化作用，并通过研究 Diagonal Linear Networks (DLNs) 的梯度流在过参数化回归设置下的隐式规则化，解释了泛化难度的相变现象与基础追踪优化问题收敛的关系，并且提出了新的收敛界限及其初值大小与选取最小化者的联系。