Marko Mitrovic

Marko Mitrovic

Ph.D. Student
Department of Computer Science
Yale University

e-mail: marko.mitrovic@yale.edu
CV

I will be starting at Google in September 2020 🙂

Research

Thesis: Modern Challenges for Machine Learning Applications of Submodularity: Privacy, Scalability, and Sequences [pdf]
Under the supervision of Professor Amin Karbasi.

• Adaptive Sequence Submodularity (NeurIPS 2019):
  [full paper][poster]
  .

  Many real-world recommender systems are constantly asking for user feedback to improve future personalization. This paper builds on the Submodularity on Hypergraphs paper (detailed further below), which focused on problems where the solution should be modeled as a sequence rather than a set. In this paper, we establish a novel framework that provides both a theoretical and a practical foundation for sequential algorithms that are also adaptive and can thus utilize feedback during runtime to improve their solutions.

• Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity (ICML 2019):
  [main paper][supplementary material][poster]
  .

  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.

  Datasets

  • encoded_frames
  • tweets
  • This work is licensed under under the Creative Commons license: CC-BY-SA without access restrictions or confidentiality requirements (https://creativecommons.org/licenses)

• Data Summarization at Scale: A Two-Stage Submodular Approach (ICML 2018):
  [main paper][full version]
  .

  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):
  [main paper][full version][poster]
  .

  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):
  [pdf][full version][poster]
  .

  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 k^th 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]

Work Experience

 Facebook Ph.D. Intern (June 2019 – August 2019)

Worked with the Instagram Ads Ranking team on instability understanding for deep learning-based recommender systems.

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.