AF: Small: Algorithms for Diverse and Fair Optimization

AF：小：多样化且公平优化的算法

• 批准号: 1910423
• 负责人: Mohit Singh
• 金额: $ 40万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910423&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Diverse; Fair

The availability of enormous quantities of data has played a crucial role in the development of widely used machine-learning algorithms. A major challenge with this large quantity of data is how to pick out a smaller part that is representative of the whole but can be efficiently used in these algorithms. The project aims to find new models and algorithms to identify a small but representative part of a given collection of data. Fairness aspects in identification as well as representation of data will also be considered in the project. The PI will incorporate results from this project into curriculum-development activities at both the undergraduate and graduate level. The project will also involve training of undergraduate and graduate students, especially from underrepresented groups in STEM. The PI will also talk about the challenges and the results of the project to a wider audience, including K-12 students, at various outreach events. The project aims to introduce and develop a general framework for modeling diversity in subset-selection problems. The general framework encompasses problems froma variety of areas including determinantal point processes in machine learning, optimal design for linear regression, fair and efficient allocation of goods, and network-design problems. The project intends to bring algorithmic advances on these wide-ranging topics by studying them through a common lens. A second closely related focus of this project is to study fair representation of data, especially in algorithms for dimensionality reduction, which is increasingly important with the pervasive use of data in society. The algorithmic viewpoint on this problem is closely related to the structure of extreme points of semidefinite programs that the project aims to investigate and to develop an algorithmic framework generalizing the PI's work on linear programs.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.

大量数据的可用性在广泛使用的机器学习算法的发展中发挥了至关重要的作用。面对如此大量的数据，一个主要的挑战是如何挑选出一小部分，既能代表整体，又能有效地用于这些算法。该项目旨在寻找新的模型和算法来识别给定数据集合中一小部分但具有代表性的部分。该项目还将考虑识别和数据表示方面的公平性。PI将把这个项目的成果纳入本科和研究生阶段的课程开发活动。该项目还将涉及对本科生和研究生的培训，尤其是来自STEM领域代表性不足群体的学生。PI还将在各种推广活动中向包括K-12学生在内的更广泛的受众介绍项目的挑战和成果。该项目旨在介绍和开发一个通用框架，用于在子集选择问题中建模多样性。总体框架涵盖了各种领域的问题，包括机器学习中的决定性点过程、线性回归的最佳设计、公平有效的商品分配以及网络设计问题。该项目旨在通过一个共同的视角来研究这些广泛的主题，从而在算法上取得进展。该项目的第二个密切相关的重点是研究数据的公平表示，特别是在降维算法中，随着数据在社会中的普遍使用，降维算法变得越来越重要。该问题的算法观点与半定规划的极值点结构密切相关，该项目旨在研究半定规划的极值点结构，并开发一种算法框架，推广PI在线性规划上的工作。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Determinant Maximization via Matroid Intersection Algorithms

通过拟阵交集算法实现行列式最大化

• 发表时间: 2022
• 期刊: Annual Symposium on Foundations of Computer Science
• 作者: Brown, A;Laddha, A.;Pittu, M.;Singh, M.;Tetali, P.
• 通讯作者: Tetali, P.

Socially fair network design via iterative rounding

• DOI: 10.1016/j.orl.2022.07.011
• 发表时间: 2022-08
• 期刊: Oper. Res. Lett.
• 作者: Aditi Laddha;Mohit Singh;S. Vempala

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

通过凸和非凸规划加权纳什社会福利的近似算法

• 发表时间: 2024
• 期刊: Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Brown, A;Laddha, A;Pittu M;Singh, M.
• 通讯作者: Singh, M.

Multi-Criteria Dimensionality Reduction with Applications to Fairness

• 发表时间: 2019-02
• 作者: U. Tantipongpipat;S. Samadi;Mohit Singh;Jamie Morgenstern;S. Vempala

Maximizing Determinants under Matroid Constraints

• DOI: 10.1109/focs46700.2020.00059
• 发表时间: 2020-04
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: V. Madan;Aleksandar Nikolov;Mohit Singh;U. Tantipongpipat