Optimization and Learning Over Convex Sets

凸集的优化和学习

• 批准号: 9528973
• 负责人: Ravindran Kannan
• 金额: $ 24万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-02-01 至 1999-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9528973&HistoricalAwards=false
• 关键词: Optimization; 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. ***

这是软件资本化计划奖 CCR-95-28215“用于几何随机游走优化和其他应用的快速随机算法”的配套项目。 这两个相关奖项都是 PI 持续长期项目的一部分，该项目是在 CCR-92-08597“随机游走，参数整数规划”下启动的。 根据之前的资助 CCR-92-08597，开发了从多种多元概率分布中进行采样的随机游走算法。 该项目的目标包括：（a）研究随机游走技术的一些算法应用，包括（a1）生成和使用给定凸集的随机样本，（a2）研究列联表的快速生成和使用，以及（a3）探索凸集体积估计中出现的几何和效率问题，这是随机游走的原始动机； （b）研究计算学习理论中与凸集相关的一些基本问题，包括（b1）“合成”给定随机样本的凸集，（b2）生成算法并确定给定样本的某些多维凸集的复杂性，当学习是“无分布”（在Valiant意义上）和抽取样本时 来自凸集上的均匀分布。 ***