Regularization Methods for Online Learning

在线学习的正则化方法

• 批准号: 0830410
• 负责人: Peter Bartlett
• 金额: $ 30万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830410&HistoricalAwards=false
• 关键词: Regularization; Methods; Online; Learning

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.

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