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.