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.