Towards a Robust Theory of Adaptive Learning Algorithms

迈向稳健的自适应学习算法理论

• 批准号: RGPIN-2017-05085
• 负责人: Szepesvari, Csaba
• 金额: $ 4.9万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750523
• 关键词: Towards; Robust; Theory; Adaptive; Learning

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.

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