Regularization Methods for Online Learning

有许多顺序决策问题可以适当地建模为重复博弈，其中决策者与对手竞争。例如，在计算机网络中的病毒检测问题中，目标是将传入的数据包标记为干净或受感染，而黑客的目标是设计受感染的数据包以逃避检测。类似的问题出现在计算机安全的其他领域（包括垃圾邮件过滤和检测拒绝服务攻击），在互联网搜索（如决定一个高链接的网页是否真正权威，应该有较高的页面排名），以及在金融应用（如投资组合优化）。在这些问题中，决策者的目标是表现得几乎和某些比较类的最佳元素一样好。即使对于本质上不是对抗性的决策问题，也经常以这种方式对它们进行建模，因为假设足够弱，因此这些对抗性设置的有效学习算法非常适用。许多解决在线学习问题的关键算法方法都可以被视为涉及正则化的方法，正则化的思想起源于解决病态问题，如统计估计问题。本项目旨在利用这种正则化观点来分析和设计复杂的在线学习问题的方法。特别是，它的目标是(1)开发有限反馈决策问题的技术。(2)开发具有复杂损失的决策问题的技术，这些损失不能简单地分解为跨试验的总和。(3)开发高效的学习算法，能够同时有效地与各种丰富的比较类和对手的各种约束进行竞争。(4)提高我们对在线决策问题（对抗性设置）和统计决策问题（概率设置）之间关系的理解。该项目的成功研究成果可能会增加我们对复杂顺序决策问题的理解，并为这些问题的有效学习算法提供设计方法，因此在许多应用领域具有重要的实际影响潜力，包括计算机安全和计算金融。

There are many sequential decision problems which can be appropriately modeled as a repeated game, in which the decision-maker is competing with an adversary. For instance, in the problem of virus detection in a computer network, the aim is to label incoming packets as either clean or infected, while a hacker aims to design infected packets that escape detection. Similar problems arise in other areas of computer security (including spam filtering and detection of denial-of service attacks), in internet search (such as deciding if a highly-linked web page is genuinely authoritative and should have high page rank), and in financial applications (such as portfolio optimization). In these problems, the decision-maker aims to perform almost as well as the best element of some comparison class. Even for decision problems that are not inherently adversarial, it is often appealing to model them in this way, since the assumptions are sufficiently weak that effective learning algorithms for these adversarial settings are very widely applicable. Many of the key algorithmic approaches to online learning problems can be viewed as methods involving regularization, an idea that has its origins in the solution of ill-posed problems, such as statistical estimation problems. This project aims to exploit this regularization viewpoint in the analysis and design of methods for complex online learning problems. In particular, its aims are (1) To develop techniques for decision problems with limited feedback. (2) To develop techniques for decision problems with complex losses that cannot be simply decomposed into a sum across trials. (3) To develop efficient learning algorithms that can simultaneously compete effectively with a variety of rich comparison classes and a variety of constraints on the adversary. (4) To improve our understanding of the relationships between online decision problems (in adversarial settings) and statistical decision problems (in probabilistic settings). Successful research outcomes of this project are likely to increase our understanding of complex sequential decision problems and to provide design methodologies for effective learning algorithms for these problems, and hence have a significant potential for practical impact in many application areas, including computer security and computational finance.