AF: Small: Fundamental High-Dimensional Algorithms

AF：小：基本的高维算法

基本信息

批准号：
2007443
负责人：
Santosh Vempala
金额：
$ 40万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-08-01 至 2024-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007443&HistoricalAwards=false
关键词：
AF Small Fundamental Dimensional Algorithms

项目摘要

The availability of high-dimensional data in a myriad of applications makes efficient and general-purpose algorithmic tools a critical need. This project explores basic questions to address this need in high dimension: How to compute the volume? How to optimize with constraints? How to sample from a desired distribution? How to learn from samples? Progress on these questions will build the foundations of the emerging science of data. The investigator routinely collaborates with scientists from other disciplines to identify specific challenges. He will continue to organize collaborative workshops, write up-to-date research surveys informed by the discoveries of this project, as well as a textbook on Continuous Algorithms, and maintain open-source software for state-of-the-art sampling.The major goal of this project is to extend algorithmic techniques in three ways: from Euclidean to non-Euclidean geometries, from convex to non-convex settings and from optimization to sampling problems. Concretely, it will explore algorithms for non-convex optimization and sampling, for robust clustering and learning (in the presence of adversarial noise), for faster sampling by utilizing Riemannian geometries, and for volume computation by leveraging recent progress on the Kannan-Lovasz-Simonovits hyperplane conjecture. It will also explore such a conjecture for manifolds, and the possibility of a deterministic algorithm for polytope volume.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

高维数据在无数应用程序中的可用性使得高效且通用的算法工具成为迫切需求。该项目探讨了解决高维度这一需求的基本问题：如何计算体积？如何在约束条件下进行优化？如何从所需的分布中采样？如何从样本中学习？这些问题的进展将为新兴数据科学奠定基础。研究人员定期与其他学科的科学家合作，以确定具体的挑战。他将继续组织协作研讨会，根据该项目的发现撰写最新的研究调查以及连续算法教科书，并维护用于最先进采样的开源软件。该项目的主要目标是以三种方式扩展算法技术：从欧几里德几何到非欧几里德几何，从凸到非凸设置以及从优化到采样问题。具体来说，它将探索非凸优化和采样算法、鲁棒聚类和学习算法（在存在对抗性噪声的情况下）、利用黎曼几何实现更快采样，以及利用 Kannan-Lovasz 的最新进展进行体积计算。西蒙诺维茨超平面猜想。它还将探索流形的这种猜想，以及多胞体体积确定性算法的可能性。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Is Planted Coloring Easier than Planted Clique?

种植着色比种植派更容易吗？

DOI：
发表时间：
2023-01
期刊：
Conference on Learning Theory
影响因子：
0
作者：
Kothari, Pravesh;Vempala, Santosh S.;Wein, Ale;Xu, Jeff
通讯作者：
Xu, Jeff

Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast

吉布斯采样的收敛：快速协调“打了就跑”的混合

DOI：
10.4230/lipics.socg.2021.51
发表时间：
2021-01
期刊：
ACM Symposium on Computational Geometry
影响因子：
0
作者：
Laddha, Aditi;Vempala, Santosh S.
通讯作者：
Vempala, Santosh S.

How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization.

随机反馈如何以及何时发挥作用：低秩矩阵分解的案例研究。

DOI：
发表时间：
2022-01
期刊：
AISTATS
影响因子：
0
作者：
Garg, Shivam;Vempala, Santosh S.
通讯作者：
Vempala, Santosh S.

Socially Fair k-Means Clustering

社会公平 k 均值聚类

DOI：
10.1145/3442188.3445906
发表时间：
2020-10-29
期刊：
Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency
影响因子：
0
作者：
Mehrdad Ghadiri;S. Samadi;S. Vempala
通讯作者：
S. Vempala

The Mirror Langevin Algorithm Converges with Vanishing Bias

镜像 Langevin 算法收敛并消除偏差