Marko Mitrovic

Ph.D. Student
Department of Computer Science
Yale University


Research Interests

  • Machine Learning
  • Graph Algorithms
  • Time Series




Thesis: Machine Learning Applications of Submodularity
Under the supervision of Professor Amin Karbasi.
Funded by Yale University Fellowship.

  • 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.

  • Submodularity on Hypergraphs: From Sets to Sequences (AISTATS 2018):
    [pdf][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.

  • Data Summarization at Scale: A Two-Stage Submodular Approach (ICML 2018):
    [pdf][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.

  • Undergraduate Research at Simon Fraser University
    • Supervised by Professors Martin EsterBinay 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]


Work Experience

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.