In many applications, solutions of numerical problems are required to be non-negative, e.g., when retrieving pixel intensity values or physical densities of a substance. In this context, non-negative least squares (NNLS) is a ubiquitous tool, especially when seeking sparse solutions of high-dimensional statistical problems. Despite vast efforts since the seminal work of Lawson and Hanson in the '70s, the non-negativity assumption is still an obstacle for the theoretical analysis and scalability of many off-the-shelf solvers. In the different context of deep neural networks, we recently started to see that the training of overparametrized models via gradient descent leads to surprising generalization properties and the retrieval of regularized solutions. In this paper, we prove that, by using an overparametrized formulation, NNLS solutions can reliably be approximated via vanilla gradient flow. We furthermore establish stability of the method against negative perturbations of the ground-truth. Our simulations confirm that this allows to use vanilla gradient descent as a novel and scalable numerical solver for NNLS.
翻译:在许多应用中,数字问题的解决办法必须是非负性的,例如,当检索物质的像素强度值或物理密度时,数字问题的解决办法必须是非负性的。在这方面,非负性的最小正方形(NNLS)是一个无处不在的工具,特别是在寻求高维统计问题的零散解决办法时。尽管自劳森和汉森70年代的开创性工作以来作出了巨大努力,但非惯性假设仍然是许多现成溶液进行理论分析和缩放的障碍。在深神经网络的不同背景下,我们最近开始看到,通过梯度下降对过度平衡的模型进行的培训,导致令人惊讶的一般化特性和常规化解决办法的检索。在本文中,我们证明,通过过度平衡的公式,NNLS的解决方案可以可靠地通过香气梯流来接近。我们进一步确立方法的稳定性,防止地面图解的负性扰动性扰动性下降。我们的模拟证实,这允许将Vanilla梯度梯度梯度下降作为新的和可缩略的数值解。