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.