Machine Learning, On-line Algorithms, and Optimization

点击翻译按钮获取中文摘要

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.