Machine Learning, On-line Algorithms, and Optimization

这项研究涉及在机器学习、在线算法和优化领域之间建立新的联系，并利用这些联系来解决所有三个领域的基本问题。在机器学习中，本研究的一个重点是如何最好地将少量有标记的数据与大量的未标记数据相结合，以产生高质量的预测。考虑到现在网络上可用数据的爆炸性增长，这类问题变得尤为重要。这项研究正在探索如何使用优化文献中的网络流和图割等技术来提供一种新的攻击手段，以及如何最好地做出在这种方法中出现的一些设计选择。这项工作研究的另一个基本问题是，在高噪声数据存在的情况下，什么类型的概念可以被自动学习，以及在多大程度上可能有实质性的新类型的算法。PI最近给出了第一个算法，在存在噪声的情况下学习一类概念，这类概念是被称为统计查询方法的一大类技术所无法学习的。目前的研究旨在扩大这项工作，并探索HIT可以进一步推进的程度。所研究的学习问题的类型与密码学中出现的解码随机线性码和寻找近似最短格子向量的问题密切相关。学习算法的改进也应该影响对这些问题的理解。这项研究的另一个主要目的是使用机器学习的技术来解决在线算法中的问题。特别是，机器学习中高度发展的“加权专家”技术为组合多个在线算法提供了新的方法，这些算法可能会简化一些长期存在的公开问题。这项工作正在研究这种联系在多大程度上可以提供对几个基本问题的洞察，如搜索树中的动态最优化和加权缓存问题。最后，本研究还研究了一些基本的可近似性问题，并探索了分析局部搜索技术的新框架。

This research involves developing new connections between the areas ofmachine learning, on-line algorithms, and optimization, and usingthese connections to address fundamental problems in allthree areas.In machine learning, one focus of this research is how to best combinea small sample of labeled data with a large amount of unlabeled datain order to produce high quality predictions. This type of problemhas become especially important given the explosion of data nowavailable over the web. This research is exploring how techniquessuch as network flow and graph cuts from the optimization literaturecan be used to provide a new means of attack, and how to best make anumber of design choices that arise in this approach. Another basicquestion this work investigates is what kinds of concepts can beautomatically learned in the presence of highly noisy data, and towhat extent substantially new types of algorithms may be possible.The PI recently gave the first algorithm to learn a class of conceptsin the presence of noise that is provably not learnable by a wideclass of techniques known as Statistical Query methods. The currentresearch aims to expand on this work and explore the extent to whichit can be pushed much further. The types of learning problems beingstudied have close connections to problems of decoding random linearcodes and finding approximate shortest lattice vectors that arise incryptography. Improvements to the learning algorithms should impactour understanding of those problems as well.Another major thrust of this research is the use of techniques frommachine learning to address problems in online algorithms. Inparticular, the highly-developed "weighted experts" technology inmachine learning suggests new approaches for combining multiple onlinealgorithms that may simplify a number of longstanding open problems.This work is studying the extent to which this connection can provideinsight into several basic questions, such as dynamic optimality insearch trees and the weighted caching problem. Finally, this researchis also studying a number of basic approximability questions, as wellas exploring new frameworks for the analysis of local searchtechniques.