【普林斯顿博士论文】在线学习：优化、控制与学习理论

在线学习（Online Learning）是学习理论中的一种基础范式，主要研究如何从序列化数据中进行预测的问题。最初，在线学习被提出作为一种可学习性的数学模型，而如今，它已发展成为一个通用而灵活的理论框架，被广泛应用于优化、控制、经济学等多个领域，推动了算法创新与实证研究的进步。本论文系统探讨了在线学习的多方面理论问题，涵盖其基本极限与在优化和控制中的应用。 论文的第一部分聚焦于在线凸优化（Online Convex Optimization）。我们提出了更高效的自适应遗憾最小化算法，在查询效率与投影效率上均实现了改进。同时，我们还针对更具挑战性的在线非凸优化（Online Non-Convex Optimization）问题，提出了一种新的归约方法。 论文的第二部分关注在线非随机控制（Online Nonstochastic Control），这是对经典最优控制理论的推广，放宽了对代价结构与扰动模型的假设。我们提出了一种新的框架，用于控制边界稳定线性动态系统（Marginally Stable Linear Dynamical Systems）——这一类系统历来以分析困难著称。此外，我们设计了一种适用于具有一般损失函数的bandit非随机控制最优算法，并进一步开发了一种能够整合多个基础控制算法的元算法（meta-algorithm）。 论文的最后一部分转向**学习理论（Learning Theory）中的核心问题。我们建立了一种用于归纳推理（Inductive Reasoning）的充要条件——这是流行病学中的一个基础性问题——并揭示了其与在线学习理论之间的新联系。同时，我们还在多模态学习理论（Multimodal Learning Theory）**方面提出了新的结果，展示了在统计与计算层面上均可证明的性能优势。 综上所述，本论文在推进在线学习理论理解的同时，也拓展了其在更广泛领域中的适用性，为研究者与实践者提供了新的洞见与方法工具。