Optimization and Learning Over Convex Sets

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

This is a companion project with Software Capitalization Program Award CCR-95-28215, `` Fast Randomized Algorithms for Optimization and Other Applications of Geometric Random Walks''. Both of these linked awards are part of the PI's continuing long term project, started under CCR-92-08597, ``Random Walks, Parametric Integer Programming''. Under this previous grant, CCR-92-08597, random walk algorithms to sample from a wide class of multivariate probability distributions were developed. The goals of this project include: (a) The study of some algorithmic applications of the random walk technique, including (a1) producing and using random samples given a convex set, (a2) investigating the rapid generation and use of contingency tables, and (a3) exploring geometric and efficiency questions arising in the estimation of volumes of convex sets, the original motivation for random walks; (b) The study of some fundamental questions that arise in computational learning theory related to convex sets, including (b1)``synthesizing'' a convex set given random samples, (b2) generating algorithms and determining the complexity of certain multi-dimensional convex sets given samples from them, both when the learning is ``distribution-free'' (in the sense of Valiant) and when the samples are drawn from an uniform distribution on the convex set. ***