Abstract: The adoption of machine learning (ML) based algorithms has increased over the past few years. The main reason for the success of these machine learning models is the growth of computational resources and digital data. Initially, the primary focus was to develop ML models with improved accuracy. However, there have been growing controversies about the decisions of these ML models being discriminatory to certain stakeholders involved.  A key aspect of ensuring fairness in such ML systems is promoting diversity in algorithmic outcomes—so that different attributes, or groups are adequately represented. In this direction, the present talk looks into Nearest Neighbor Search which is a fundamental problem in machine learning with wide-ranging applications, such as web search, recommendation systems, and, more recently, retrieval-augmented generations (RAG). In such recent applications, in addition to the relevance (similarity) of the returned neighbors, diversity among the neighbors is a central requirement. We develop principled welfare-based formulations in NNS for realizing diversity across attributes. With a particular focus on Nash social welfare, we note that our welfare-based formulations provide objective functions that adaptively balance relevance and diversity in a query-dependent manner. Notably, such a balance was not present in the prior constraint-based approach, which forced a fixed level of diversity and optimized for relevance.  In addition, our formulation provides a parametric way to control the trade-off between relevance and diversity, providing practitioners with flexibility to tailor search results to task-specific requirements. We develop efficient nearest neighbor algorithms with provable guarantees for  the welfare-based objectives. Notably, our algorithm can be applied on top of any standard approximate nearest neighbor (ANN) method (i.e., use standard ANN method as a subroutine) to efficiently find neighbors that approximately maximize our welfare-based objectives. Experimental results demonstrate that our approach is practical and substantially improves diversity while maintaining high relevance of the retrieved neighbors. Towards the end of talk, we also briefly discuss works in fair clustering and outline future research directions.

About the Speaker: Shivam Gupta is a Postdoctoral Researcher in the Department of Computer Science and Automation at the Indian Institute of Science (IISc), Bangalore, where he works with Prof. Siddharth Barman. His current research focuses on developing algorithmic frameworks for handling diversity in approximate nearest neighbor search, with applications to large-scale information retrieval and recommendation systems. He earned his Ph.D. in Computer Science and Engineering from IIT Ropar, under the supervision of Dr. Shweta Jain, with a thesis titled “Fair Algorithms for Clustering and Recommender Systems in Unsupervised Learning.” His doctoral research was supported by the Prime Minister’s Research Fellowship (MHRD) from 2021 to 2025. During his Ph.D., he received two Best Paper Awards at International conferences and several travel grants (including SERB ITS, ACM, and IndoML) to present his work at national and international venues. Before his Ph.D., Shivam completed his B.Tech. in Information Technology from the Indian Institute of Information Technology (IIIT) Sonipat (Mentor and Campus NIT Kurukshetra), as Department Rank 1 with a CGPA of 9.62. 

Shivam's research interests lie at the intersection of Machine Learning and Algorithmic Game Theory. Some topics of interest includes but not limited to Fairness and Explainablity in Machine Learning, Federated learning, Clustering, Recommender Systems and Deep learning. Passionate about advancing the state of AI, Shivam is actively contributing to the development of fairer and more efficient algorithms with broad applications in real-world problems.

We look forward to your active participation.