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.