- Machine Learning
- Graph Algorithms
Thesis: Machine Learning Applications of Submodularity
Under the supervision of Professor Amin Karbasi.
- Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity (ICML 2019):
[main paper][supplementary material].
In regular submodular optimization, we have a fixed set of items and we want to pick a subset of these items to maximize some submodular function. In the streaming setting, we are shown items one at a time and we have to immediately choose whether to keep the item or throw it away forever. There are two existing approaches to this problem, one of which achieves the optimal memory requirement, while the other uses slightly more memory, but achieves a better approximation guarantee. In this paper, we present a new algorithm that uses the same optimal amount of memory as the first approach, but still achieves the superior approximation guarantee of the second approach. We also extend our results to the multi-stream setting.
- Data Summarization at Scale: A Two-Stage Submodular Approach (ICML 2018):
In many cases, the size of modern datasets has grown so large that even linear time algorithms can be prohibitively expensive for repeated optimization. In the two-stage submodular framework, the goal is to use some given training functions to reduce the ground set so that optimizing new functions over the reduced set provides almost as much value as optimizing them over the entire ground set. In this paper we present streaming and distributed solutions to this problem.
- Submodularity on Hypergraphs: From Sets to Sequences (AISTATS 2018):
In many problems, it makes more sense to model solutions as sequences rather than sets. For example, if a recommender system suggests that I watch the Star Wars franchise, the order of movies it recommends is very important. Although there have been many nice results in the field of submodularity, they are generally limited to the context of sets. In this paper, we establish new algorithms and theoretical guarantees for submodular functions when the desired output is a sequence rather than a set.
- Differentially Private Submodular Maximization (ICML 2017):
Submodularity and differential privacy are both burgeoning fields that have been attracting a lot of interest lately, particularly in a machine learning context. Submodular functions are essentially the class of all functions that exhibit diminishing returns. Differential privacy, on the other hand, aims to provably maintain privacy by guaranteeing that any one individual’s data does not significantly influence the outcome of an algorithm. In this paper, we present a general framework for privately maximizing submodular functions under a variety of constraints.
- Undergraduate Research at Simon Fraser University
- Supervised by Professors Martin Ester, Binay Bhattacharya, and Luis Goddyn.
- Awarded Natural Sciences and Engineering Research Council of Canada (NSERC) Undergraduate Student Research Award (USRA) in 2013 and 2014.
- Social network analysis of human genome project: investigated the effects of the Human Genome Project on the co-authorship network of researchers in the field of genomics.
- Adaptive selection: developed an algorithm for efficiently finding the kth smallest element in a large, read-only dataset, using as few passes through the data as possible.
- Part placement problem in computational geometry: [very brief overview]
- Hilbert bases in graphs and matroids: [poster presentation]
Facebook Ph.D. Intern (June 2019 – August 2019)
Research and development of deep learning models for Ads Ranking on Instagram.
Google Ph.D. Intern (May 2018 – August 2018)
Researched and implemented LSTMs and other deep learning models for anomaly detection in time series data as a part of the Counter Abuse Technology team.