CAREER: Beyond Worst-Case Analysis: New Approaches in Approximation Algorithms and Machine Learning

职业：超越最坏情况分析：近似算法和机器学习的新方法

基本信息

批准号：
1652491
负责人：
Aravindan Vijayaraghavan
金额：
$ 50.53万
依托单位：
Northwestern University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-03-15 至 2024-02-29
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1652491&HistoricalAwards=false
关键词：
CAREER Beyond Worst Case Analysis

项目摘要

Combinatorial optimization problems such as clustering, and unsupervised learning of probabilistic models are important computational problems that arise in diverse areas including machine learning, computer vision, operations research and data analysis. However, there is a large disconnect between our theoretical and practical understanding of these problems -- while theory tells us that many interesting computational problems in combinatorial optimization and machine learning are intractable in the worst case, practitioners in areas such as machine learning and computer vision have made significant progress in solving such theoretically hard problems. This project focuses on bridging the fundamental gap between theory and practice by developing paradigms and machinery that will allow us to reason about the performance of algorithms on real-world instances. This research has the potential to have broad impact on both theory and practice of computational problems across different areas of computer science, machine learning and statistics. The project will involve students at all levels of research, will integrate aspects of average-case analysis in both graduate and undergraduate courses, and will include outreach activities in high schools in Evanston and the broader Chicago area.The PI will study several problems in machine learning and combinatorial optimization by using realistic average-case models and smoothed analysis. Broad goals include designing new model-independent algorithms with provable guarantees for realistic average-case models of graph partitioning and clustering and challenging average-case settings where there is no unique or planted solution. These algorithms will also lead to new algorithmic techniques for learning probabilistic models such as mixtures of Gaussians and stochastic block models that are robust to various kinds of modeling errors and noise. Another focus of the project is on developing new efficient algorithms for learning latent variable models and for reasoning about the performance of algorithms using smoothed analysis.

聚类和概率模型无监督学习等组合优化问题是机器学习、计算机视觉、运筹学和数据分析等不同领域中出现的重要计算问题。然而，我们对这些问题的理论和实践理解之间存在很大的脱节——虽然理论告诉我们，组合优化和机器学习中的许多有趣的计算问题在最坏的情况下都是棘手的，但机器学习和计算机视觉等领域的从业者在解决此类理论上的难题方面取得了重大进展。该项目的重点是通过开发范式和机制来弥合理论与实践之间的根本差距，使我们能够推理算法在现实世界实例上的性能。这项研究有可能对计算机科学、机器学习和统计学不同领域的计算问题的理论和实践产生广泛的影响。该项目将涉及各级研究的学生，将在研究生和本科生课程中整合平均案例分析的各个方面，并将包括在埃文斯顿和更广泛的芝加哥地区的高中的外展活动。PI将研究机器中的几个问题通过使用现实的平均情况模型和平滑分析进行学习和组合优化。广泛的目标包括设计新的独立于模型的算法，为图分区和聚类的实际平均情况模型提供可证明的保证，并在没有唯一或固定解决方案的情况下挑战平均情况设置。这些算法还将带来用于学习概率模型的新算法技术，例如对各种建模误差和噪声具有鲁棒性的高斯混合模型和随机块模型。该项目的另一个重点是开发新的有效算法来学习潜变量模型并使用平滑分析来推理算法的性能。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Estimating Principal Components under Adversarial Perturbations

估计对抗性扰动下的主成分

DOI：
发表时间：
2020-01
期刊：
PMLR 125:323-362
影响因子：
0
作者：
Awasthi, Pranjal;Chen, Xue;Vijayaraghavan, Aravindan
通讯作者：
Vijayaraghavan, Aravindan

Clustering Semi-Random Mixtures of Gaussians

对高斯半随机混合物进行聚类

DOI：
发表时间：
2017-01
期刊：
Proceedings of Machine Learning Research
影响因子：
0
作者：
Awasthi, Pranjal;Vijayaraghavan, Aravindan
通讯作者：
Vijayaraghavan, Aravindan

Adversarial robustness via robust low rank representations

通过稳健的低秩表示实现对抗稳健性

DOI：
10.1002/admi.202100038
发表时间：
2020-07-13
期刊：
ArXiv
影响因子：
0
作者：
Pranjal Awasthi;Himanshu Jain;A. Rawat;Aravindan Vijayaraghavan
通讯作者：
Aravindan Vijayaraghavan

Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay

在具有通信延迟的相关机器上调度优先级受限的作业

DOI：
10.1109/focs46700.2020.00082
发表时间：
2020-01
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
0
作者：
Maiti, Biswaroop;Rajaraman, Rajmohan;Stalfa, David;Svitkina, Zoya;Vijayaraghavan, Aravindan
通讯作者：
Vijayaraghavan, Aravindan

Towards Learning Sparsely Used Dictionaries with Arbitrary Supports

在任意支持下学习稀疏使用的词典