Collaborative Research: Mathematical Programming for Streaming Data

大量的数据现在可以很容易地以流媒体的方式实时获取：新闻、交通、温度或其他由手机传感器发送的物理测量数据。将统计和机器学习方法应用于这些流数据集，为更好地实时理解复杂的物理、社会或经济现象提供了巨大的机会。例如，这些算法可以用来了解新闻媒体如何报道某些主题的趋势，以及这些趋势如何随着时间的推移而演变，或者跟踪交通网络中的事件。不幸的是，大多数用于大规模数据分析的算法都不是为流数据设计的；通常，添加数据点（例如，表示来自美联社的今天的一批新闻文章）需要重新解决整个问题。此外，这些算法中的许多都要求将考虑的整个数据集存储在一个地方。这些约束使得经典方法对现代的实时数据集不实用。该项目的重点是在线模式下的优化算法，以便在新数据或约束条件添加到问题中时更快、可能是实时地更新解决方案。有效的在线算法目前只适用于少数特殊情况。使用同伦方法和相关的思想，这项工作将寻求允许在线更新现代数据分析问题的主机。将特别强调涉及稀疏性或分组约束的问题；例如，这些约束对于理解数据集中的几个关键特性如何解释数据中的大多数变化是很重要的。这些新的在线算法将适用于分布式实现，允许将部分数据存储在不同的服务器上。这些方法将适用于来自美国主要媒体的流媒体新闻数据，也适用于在线检测问题，这是在以在线方式跟踪一些重要信号时出现的，比如通信网络。

A large amount of data is now easily accessible in real-time in a streaming fashion: news, traffic, temperature or other physical measurements sent by sensors on cell phones. Applying statistical and machine learning methods to these streaming data sets represents tremendous opportunities for a better real-time understanding of complex physical, social or economic phenomena. These algorithms could be used, for example, to understand trends in how news media cover certain topics, and how these trends evolve over time, or to track incidents in transportation networks.Unfortunately, most algorithms for large-scale data analysis are not designed for streaming data; typically, adding data points (representing, say, today's batch of news articles from the Associated Press) requires re-solving the entire problem. In addition, many of these algorithms require the whole data set under consideration to be stored in one place. These constraints make classical methods impractical for modern, live data sets.This project's focus is on optimization algorithms designed to work in online mode, allowing for faster, possibly real-time, updating of solutions when new data or constraints are added to the problem. Efficient online algorithms are currently known for just a few special cases. Using homotopy methods and related ideas, this work will seek to allow online updating for a host of modern data analysis problems. A special emphasis will be put on problems involving sparsity or grouping constraints; such constraints are important for example to understand how a few key features in the data set that explain most of the changes in the data. These new online algorithms will be amenable to distributed implementations to allow for parts of the data to be stored on different servers.These methods will be applied to streaming news data coming from major US media, and also to the problem of online detection, which arises when tracking some important signal over, say, a communication network, in an online fashion.