CAREER: Faster and Smaller Sketches for Bigger Data

职业：更快、更小的草图以获取更大的数据

• 批准号: 1750716
• 负责人: Huy Nguyen
• 金额: $ 49.99万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-02-01 至 2024-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750716&HistoricalAwards=false
• 关键词: CAREER; Faster; Smaller; Sketches; Bigger

The advent of new sensing and tracking technologies and expansive use of social networks detailing every walk of life have generated enormous new datasets. The difficulty in dealing with new datasets arises from not only the sheer volume but also the speed required for the analysis and the complex and heterogeneous nature of the data. Underlying these challenges is the need for suitable representations of the data that facilitate efficient computation and are sufficiently compact for storage and communication. This project aims to address fundamental gaps in our understanding of these representations (so-called sketches) and develops both new data representations and new algorithms for massive datasets in a holistic fashion. The project builds on techniques from a wide variety of areas including mathematical analysis, information theory, coding theory, combinatorics, and optimization, and enriches the deep connections among them. Undergraduate and graduate students will be trained and equipped with technical tools to work in these areas. The PI and the students involved in the project will also distill new findings into general audience surveys and give talks at workshops in different technical areas for broadest possible dissemination of information.This project aims to study sketching algorithms by focusing on three main thrusts:(a) Study time complexity of sketches in streaming algorithms in both upper and lower bounds.(b) Develop new forms of sketches for distributed environments. The project focuses on sketching for submodular functions, a popular model for machine learning, computer vision, economics, etc. Problems in these applications are modeled as submodular maximization subject to various types of constraints. (c) Study space complexity of linear sketches in sparse recovery with respect to different recovery guarantees.

新的感应和跟踪技术的出现以及社交网络的广泛使用详细介绍了各行各业的各行各业。处理新数据集的困难不仅源于分析所需的速度以及数据的复杂和异构性质所需的速度。这些挑战的根本是需要适当的数据表示，以促进有效的计算，并且足以使其进行存储和通信。该项目旨在解决我们对这些表示形式（所谓的草图）的理解中的基本差距，并以整体方式为大规模数据集开发新的数据表示和新算法。该项目以各种领域的技术为基础，包括数学分析，信息理论，编码理论，组合学和优化，并丰富了它们之间的深厚联系。本科生和研究生将接受培训和配备在这些领域工作的技术工具。 PI和参与该项目的学生还将将新的发现提炼成一般听众的调查，并在不同技术领域的研讨会上进行演讲，以广泛可能地传播信息。本项目旨在研究素描算法的三个主要力量：（a）在上层和下范围的绘制算法中的素描算法的研究时间复杂性，以开发上层和下层范围。该项目的重点是为子解多函数草图，这是机器学习，计算机视觉，经济学等的流行模型。这些应用程序中的问题被建模为按不同类型的约束的次数最大化。 （c）研究稀疏恢复中线性草图的空间复杂性相对于不同的恢复保证。

项目成果

Improved Frequency Estimation Algorithms with and without Predictions

• DOI: 10.48550/arxiv.2312.07535
• 发表时间: 2023-12
• 期刊: ArXiv
• 作者: Anders Aamand;Justin Y. Chen;Huy Le Nguyen;Sandeep Silwal;A. Vakilian

Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities

约束凸优化和变分不等式的自适应梯度法

• 发表时间: 2021
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Ene, Alina;Nguyen, Huy L;Vladu, Adrian
• 通讯作者: Vladu, Adrian

Differentially Private Clustering via Maximum Coverage

• DOI: 10.1609/aaai.v35i13.17375
• 发表时间: 2020-08
• 作者: Matthew D. Jones;Huy L. Nguyen;Thy Nguyen

Differentially Private Decomposable Submodular Maximization

• DOI: 10.1609/aaai.v35i8.16860
• 发表时间: 2020-05
• 期刊: ArXiv
• 作者: Anamay Chaturvedi;Huy L. Nguyen;Lydia Zakynthinou

Fast greedy for linear matroids

快速贪婪线性拟阵

• DOI: 10.1137/1.9781611975482.32
• 发表时间: 2019
• 期刊: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Nguyen, H.