Machine Learning, On-line Algorithms, and Optimization

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

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.