Optimization and Learning Over Convex Sets

这是软件资本化计划奖CCR-95-28215的姊妹项目，“几何随机游走优化和其他应用的快速随机算法”。 这两个相关奖项都是PI持续长期项目的一部分，该项目始于CCR-92-08597，"随机漫步，参数化编程“。 在先前的授权CCR-92-08597下，开发了从广泛的多变量概率分布中采样的随机游走算法。 该项目的目标包括： (a)随机游走技术的一些算法应用的研究，包括（a1）产生和使用给定凸集的随机样本，（a2）研究列联表的快速生成和使用，以及（a3）探索凸集体积估计中出现的几何和效率问题，这是随机游走的原始动机; (b)对计算学习理论中出现的与凸集有关的一些基本问题的研究，包括（b1）给定随机样本“合成”凸集，（b2）生成算法并确定给定样本的某些多维凸集的复杂性，当学习是“无分布”（在Valiant的意义上）时，以及当样本是从凸集上的均匀分布中提取时。 ***

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. ***