General Theory of Implicit Regularization

在大数据时代--以大型，高维和分布式数据集为特征-我们越来越多地面临着建立可扩展方法的挑战，这些方法可以在计算约束下实现最佳的统计保证。为了从根本上应对这一挑战，需要建立新的模式。在过去的50年里，统计学习理论一直依赖于显式正则化的框架来控制估计器的模型复杂性。通过设计，这种方法混淆了统计最优性和计算效率的概念，在应用中，往往导致昂贵的模型选择程序。这个框架面临着基本的限制，以解释现代机器学习范式的实际成功，这是基于运行简单的梯度下降方法，没有任何显式的努力来控制模型的复杂性，克服这些限制提示迭代算法的隐式正则化属性的调查，即偏置强制执行的优化例程和调整参数的选择的副产品。隐式正则化在结构上结合了统计和优化，它有可能促进围绕统计和计算最优性概念构建的新算法范例的设计。然而，为了充分发挥其潜力，需要克服若干挑战。该项目旨在开发一种隐式正则化的一般理论，可以最佳地解决现代应用中的基本原语-例如，涉及稀疏和低秩噪声模型，分散式多智能体学习以及自适应和鲁棒程序-并建立具有深远影响的新型跨学科联系。这一目标将通过将高维概率中随机结构研究的非渐近工具与优化和在线学习的镜像下降的一般框架相结合来实现。

In the era of Big Data---characterized by large, high-dimensional and distributed datasets---we are increasingly faced with the challenge of establishing scalable methodologies that can achieve optimal statistical guarantees under computational constraints. To fundamentally address this challenge, new paradigms need to be established. Over the past 50 years, statistical learning theory has relied on the framework of explicit regularization to control the model complexity of estimators. By design, this approach decouples notions of statistical optimality and computational efficiency and, in applications, often leads to expensive model selection procedures. This framework faces fundamental limitations to explain the practical success of modern machine learning paradigms, which are based on running simple gradient descent methodologies without any explicit effort to control model complexity.Overcoming these limitations prompts for the investigation of the implicit regularization properties of iterative algorithms, namely the bias enforced as a by-product of the very choice of optimization routine and tuning parameters. Implicit regularization structurally combines statistics with optimization and it has the potential to promote the design of new algorithmic paradigms built around the notion of statistical and computational optimality. However, to fully realize its potential, several challenges need to be overcome. This project aims to develop a general theory of implicit regularization that can optimally address fundamental primitives in modern applications---e.g. involving sparse and low-rank noisy models, decentralized multi-agent learning, and adaptive and robust procedures---and establish novel cross-disciplinary connections with far-reaching consequences. This goal will be achieved by combining non-asymptotic tools for the study of random structures in high-dimensional probability with the general framework of mirror descent from optimization and online learning.