CAREER: Stochastic Processes in High Dimensions: from Asymptotic Analysis to Algorithms

职业：高维随机过程：从渐近分析到算法

• 批准号: 1551829
• 负责人: Antonius Dieker
• 金额: $ 28.46万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1551829&HistoricalAwards=false
• 关键词: CAREER; Stochastic; Processes; Dimensions; Asymptotic

The objective of this Faculty Early Career Development (CAREER) Program award is to devise and study algorithms for large-scale random systems where direct computation is infeasible despite today's ever-increasing availability and affordability of computing resources. This project focuses on three stylized settings: (1) The project aims to introduce new Monte Carlo algorithms for rare event simulation and to show how these are widely applicable, including in cases where no efficient algorithms have currently been found. (2) The project aims to devise and assess the performance of resource allocation algorithms in large-scale stochastic networks such as computer clouds, specifically to increase the understanding of how allocation algorithms affect quality of service. This requires developing a novel methodology for stochastic networks and their scaling properties. (3) The project aims to study a class of algorithms for sampling from high-dimensional sets, where the specific focus lies on algorithms that exploit boundaries. If successful, the results of this research will lead to effective algorithms for large-scale random systems, along with accompanying qualitative insights and mathematical performance analysis. The results will for instance help in computing probabilities of rare but significant events. They will also help in understanding and managing large-scale service systems. Furthermore, they will aid in improving internal efficiencies in large-scale computer systems, which becomes ever more important in the face of rising energy costs and associated environmental impact.

这个教师早期职业发展（CAREER）计划奖的目的是设计和研究算法的大规模随机系统，直接计算是不可行的，尽管今天的不断增加的可用性和可负担的计算资源。这个项目侧重于三个程式化的设置：（1）该项目旨在为稀有事件模拟引入新的蒙特卡罗算法，并展示这些算法如何广泛适用，包括目前尚未找到有效算法的情况。（2）该项目旨在设计和评估计算机云等大规模随机网络中的资源分配算法的性能，特别是增加对分配算法如何影响服务质量的理解。这就需要为随机网络及其标度特性开发一种新的方法。(3)该项目旨在研究一类从高维集合中采样的算法，其中具体重点在于利用边界的算法。如果成功，这项研究的结果将导致有效的算法，大规模随机系统，沿着伴随着定性的见解和数学性能分析。例如，这些结果将有助于计算罕见但重要事件的概率。它们还将有助于理解和管理大型服务系统。此外，它们将有助于提高大型计算机系统的内部效率，这在能源成本上升和相关的环境影响面前变得越来越重要。