Implicit Bias and Low Complexity Networks (iLOCO)

习得的深度神经网络泛化得非常好，尽管训练样本的数量明显低于参数的数量。这一令人惊讶的现象与将过度拟合归因于泛化不良的传统智慧背道而驰。在这种过参数化设置中，损失函数具有许多全局最小值，对应于插值数据的神经网络，并且学习算法诱导对某些有利解的隐式偏差。根据奥卡姆剃刀原理，可以预见，良好的泛化与低复杂度的网络有关，（随机）梯度下降的标准算法似乎更倾向于复杂度远低于参数数量所暗示的网络。在这个项目中，我们的目标是推进最近的第一个结果，这些结果表明，对于深度线性网络的简单情况，通过梯度下降的训练促进了对网络权重的隐式偏差，其乘积是一个低秩矩阵。我们打算在这个方向上显著地扩展理论，并利用这种机制来可靠地解决低秩矩阵恢复问题，如矩阵补全。我们进一步致力于为学习深度非线性网络提供梯度下降的隐式偏差及其随机变量的理论基础。有证据表明，这种偏见再次倾向于低复杂性网络，我们打算探索其性质。我们利用训练好的非线性网络固有的低复杂度来设计新的压缩算法。特别地，我们的目标是将最近的结果扩展到深度网络，将近似的二阶网络微分与编码最优权重的某些非正交一阶分解联系起来。我们计划证明最优权重可以稳定可靠地计算出来。作为副产品，我们将展示从最小数量的样本中识别通用深度网络的鲁棒性和唯一性。除了在理论层面上推进外，该项目还将开发与机器学习、反问题解决和神经网络压缩在移动设备上使用的实际相关的新算法和软件。

Learned deep neural networks generalize very well despite being trained with a number of training samples that is significantly lower than the number of parameters. This surprising phenomenon goes against traditional wisdom which attributes overfitting with poor generalization. In such overparametrized setting the loss functional possesses many global minima corresponding to neural networks that interpolate the data, and the learning algorithm induces an implicit bias towards certain favored solutions. By the principle of Occam's razor, it can be anticipated that good generalization is connected with networks of low complexity and it seems that the standard algorithm of (stochastic) gradient descent favors networks whose complexity is much lower than suggested by the number of parameters. In this project we aim to advance recent first results, which show, for the simple case of deep linear networks, that training via gradient descent promotes implicit bias towards network weights whose product is a low rank matrix. We intend to significantly extend theory in this direction and exploit this mechanism for the reliable solution of low rank matrix recovery problems, such as matrix completion. We further aim at contributing to the theoretical foundations of the implicit bias of gradient descent and its stochastic variants for learning deep nonlinear networks. Evidence suggests that the bias is again towards low complexity networks, whose nature we intend to explore. We leverage the intrinsic low complexity of trained nonlinear networks to design novel algorithms for their compression. In particular, we aim at extending recent results to deep networks, which relate approximated second order network differentials to certain non-orthogonal rank one decompositions encoding optimal weights. We plan to prove that the optimal weights can be stably and reliably computed. As a byproduct we will show robust and unique identification of generic deep networks from a minimal number of samples. Besides advancing on the theoretical level, the project will develop new algorithms and software of practical relevance for machine learning, solution of inverse problems and compression of neural networks for their use on mobile devices.