Towards a Robust Theory of Adaptive Learning Algorithms

机器学习是一套为计算机编程的技术，通过向计算机提供数据，以便在我们对如何将数据转化为决策的理解有限时，计算机可以帮助完成任务。因此，机器学习是应对各种挑战的关键技术，无论这些挑战是出现在科学、经济、制造、技术开发还是任何其他领域。与计算科学的其他子学科类似，理论在机器学习中的作用是指导算法的设计和分析。这样的学习理论有助于确定哪些问题可以有效地学习，哪些问题不能有效地学习，以及当一个问题是“可学习的”时，需要多少数据才能达到期望的性能水平。 机器学习的大多数研究都集中在最坏情况的保证上，这在现有理论的预测和机器学习实践者的日常经验之间留下了很大的差距。特别是，多年来(如果不是几十年的话)，实践者已经收集了大量的证据，表明在实践中，具有微不足道或没有最坏情况保证的算法在某些实际感兴趣的特定任务上往往表现得相当好，而可以证明的是，近乎最坏情况的最优学习算法在相同的任务上表现不佳。最新的例子涉及深度神经网络，考虑到我们的知识状况，其前所未有的性能远远超出了我们的预期。 这一困境的一个潜在解决方案是开发能够适应数据的“易用性”或“规律性”的算法，如果存在这种规律性的话。类似于当底层矩阵是三角形时，我们如何期望用更少的代数运算来求解线性方程组的“聪明”算法，当用于具有某些额外结构的数据时，自适应算法也被期望更好地利用信息。 自适应是统计学和机器学习中研究较多的一个概念。然而，到目前为止，适应性一直是以个案的方式进行研究的，还没有全面的理论来帮助人们设计和分析自适应算法。 这项提案的第一个目标是填补这一空白。具体地说，主要目的是发展一种稳健的最优自适应学习算法理论，并通过将其应用于一些特定的学习场景来证明该理论的有效性。新理论的稳健性将来自于借鉴在线学习框架对数据生成机制做出最小假设，而最优适应性的概念来自于研究在某种最坏情况下健壮的学习算法中的任何学习算法在单个问题实例上的表现如何。这种方法的主要好处是，自适应性的定义不依赖于数据规律性的特殊概念，而是导致了规律性的“自然”概念。

Machine learning is a set of techniques for programming computers by feeding them data so that they can help with tasks when our understanding of how to turn data into decisions is limited. As such, machine learning is a key technology for addressing various challenges regardless of whether they arise in science, economics, manufacturing, technology development or any other area. Similarly to other sub-disciplines of computing science, the role of theory in machine learning is to guide the design and analysis of algorithms. Such learning theory helps to determine which problems can or cannot be learned efficiently, and, when a problem is "learnable"', how much data is needed to reach a desired performance level. Most research in machine learning focuses on worst-case guarantees, which leaves a significant gap between the predictions of existing theory and the everyday experience of machine learning practitioners. In particular, over many years (if not decades), practitioners have collected plenty of evidence that in practice algorithms with meager or no worst-case guarantees often perform quite well on some particular task of practical interest, while provably nearly worst-case optimal learning algorithms can behave poorly on the same tasks. The most recent surge of examples involve deep neural networks, whose unprecedented performance is anything but expected given our state of knowledge. A potential solution to this dilemma is to develop algorithms that have the ability to adapt to the "easiness", or "regularities" of data, if and when such regularities exist. Similarly to how we expect a "clever" algorithm to solve a linear system of equations with fewer algebraic operations when the underlying matrix is triangular, adaptive algorithms are also expected to make better use of information when used on data that has some extra structure. Adaptivity is a much studied idea both in statistics and machine learning. However, so far adaptivity has been studied in a case-by-case fashion and there is no comprehensive theory that would help one to design and analyze adaptive algorithms. The first goal of this proposal is to fill this void. In particular, the main aim is to develop a robust theory of optimally adaptive learning algorithms and also to demonstrate the usefulness of the theory by applying it to some specific learning scenarios. The robustness of the new theory will come from making minimal assumptions on the data generating mechanism borrowing ideas from the framework of online learning, while the notion of optimal adaptivity arises from the novel idea of studying how well any learning algorithm amongst those that are robust in some worst-case sense can behave on a single, individual problem instance. The main benefit of this approach is that adaptivity is defined without relying on ad-hoc notions of data regularity and leads to "natural" notions of regularity instead.