Giulia DeSalvo
Giulia DeSalvo has worked at Google Research since 2017. Her research interests are in both theory and applications of machine learning and recently, her primary focus has been on data efficiency of LLM and synthetic data generation. She received her PhD in mathematics from NYU’s Courant Institute of Mathematical Sciences with funding from NSF and received her B.A. in applied mathematics and Italian studies from UC Berkeley with highest honors.
Research Areas
Authored Publications
Sort By
GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
Gui Citovsky
Advances in Neural Information Processing Systems (2025)
Preview abstract
We introduce a novel subset selection problem called \emph{min-distance diversification with monotone submodular utility} (MDMS), which has a wide variety of applications in machine learning, e.g., data sampling and feature selection.
Given a set of points in a metric space, the goal of MDMS is to maximize an objective function combining a monotone submodular utility term and a min-distance diversity term between any pair of selected points, subject to a cardinality constraint.
We propose the $\GIST$ algorithm, which achieves a $\sfrac{1}{2}$-approximation guarantee for MDMS by approximating a series of maximum independent set problems with a bicriteria greedy algorithm.
We also prove that it is NP-hard to approximate to within a factor of $0.5584$.
Finally, we demonstrate that $\GIST$ outperforms existing benchmarks for on a real-world image classification task that studies single-shot subset selection for ImageNet.
View details
Two-step Active Learning for Instance Segmentation Neural Networks
Ke Yu
Suraj Kothawade
Abdullah Rashwan
Kayhan Batmanghelich
Xiaoqi(Michael) Yin
2023
Preview abstract
Training high quality instance segmentation models re-quires an abundance of labeled images containing instancemasks and classifications. Such data is often expensive toprocure. Active learning aims to achieve high performanceat minimal labeling cost by sampling only the most infor-mative and representative images to send for labeling. Ac-tive learning has been less explored for the task of instancesegmentation, than for other, less labeling intensive taskslike image classification. In this work, we propose a sim-ple, easy-to-implement, uncertainty based sampling strat-egy for instance segmentation, and an improvement whichadditionally incorporates diversity considerations.
View details
Firebolt: Weak Supervision Under Weaker Assumptions
Zhaobin Kuang
Chidubem Arachie
Bangyong Liang
Michael Quinn
Bert Huang
Geoffrey Downs
Yang Yang
International Conference on Artificial Intelligence and Statistics 2022
Preview abstract
Modern machine learning demands a large amount of training data. Weak supervision is a promising approach to meet this demand. It aggregates multiple labeling functions (LFs)—noisy, user-provided labeling heuristics---to rapidly and cheaply curate probabilistic labels for large-scale unlabeled data. However, standard assumptions in weak supervision---such as user-specified class balance, similar accuracy of an LF in classifying different classes, and full knowledge of LF dependency at inference time---might be undesirable in practice. In response, we present Firebolt, a new weak supervision framework that seeks to operate under weaker assumptions. In particular, Firebolt learns the class balance and class-specific accuracy of LFs jointly from unlabeled data. It carries out inference in an efficient and interpretable manner. We analyze the parameter estimation error of Firebolt and characterize its impact on downstream model performance. Furthermore, we show that on five publicly available datasets, Firebolt outperforms a state-of-the-art weak supervision method by up to 5.8 points in AUC. We also provide a case study in the production setting of a tech company, where a Firebolt-supervised model outperforms the existing weakly-supervised production model by 1.3 points in AUC and speedup label model training and inference from one hour to three minutes.
View details
Preview abstract
Consider a setting where we wish to automate an expensive task with a machine
learning algorithm using a limited labeling resource. In such settings, examples
routed for labeling are often out of scope for the machine learning algorithm. For
example, in a spam detection setting, human reviewers not only provide labeled
data but are such high-quality detectors of spam that examples routed to them no
longer require machine evaluation. A consequence is that distribution of examples
routed to the machine is intimately tied to the process generating labels. We
introduce a formalization of this setting, and give an algorithm that simultaneously
learns a model and decides when to request a label by leveraging ideas from both
the abstention and active learning literatures. We prove an upper bound on the
algorithm’s label complexity and a matching lower bound for any algorithm in this
setting. We conduct a thorough set of experiments including an ablation study to
test different components of our algorithm. We demonstrate the effectiveness of an
efficient version of our algorithm over margin sampling on a variety of datasets.
View details
Preview abstract
We derive a novel active learning algorithm in the streaming setting for binary classification tasks. The algorithm leverages weak labels to minimize the number of label requests, and trains a model to optimize a surrogate loss on a resulting set of labeled and weak-labeled points. Our algorithm jointly admits two crucial properties: theoretical guarantees in the general agnostic setting and a strong empirical performance. Our theoretical analysis shows that the algorithm attains favorable generalization and label complexity bounds, while our empirical study on 18 real-world datasets demonstrate that the algorithm outperforms standard baselines, including the Margin Algorithm, or Uncertainty Sampling, a high-performing active learning algorithm favored by practitioners.
View details
Batch Active Learning at Scale
Afshin Rostamizadeh
Anand Rajagopalan
Gui Citovsky
Laz Karydas
NeurIPS 2021
Preview abstract
The ability to train complex and highly effective models often requires an abundance of training data, which can easily become a bottleneck in cost, time, and computational resources. Batch active learning, which adaptively issues batched queries to a labeling oracle, is a common approach for addressing this problem. The practical benefits of batch sampling come with the downside of less adaptivity and the risk of sampling redundant examples within a batch -- a risk that grows with the batch size. In this work, we analyze an efficient active learning algorithm, which focuses on the large batch setting. In particular, we show that our sampling method, which combines notions of uncertainty and diversity, easily scales to batch sizes (100K-1M) several orders of magnitude larger than used in previous studies and provides significant improvements in model training efficiency compared to recent baselines.
View details
Understanding the Effects of Batching in Online Active Learning
Afshin Rostamizadeh
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (2020)
Preview abstract
Online active learning (AL) algorithms often assume immediate access to a label once a query has been made. However, due to practical constraints, the labels of these queried examples are generally only available in ``batches''. In this work, we present a novel analysis for a generic class of batch online AL algorithms and reveal that the effects of batching are in fact mild and only result in an additional term in the label complexity that is linear in the batch size. To our knowledge, this provides the first theoretical justification for such algorithms and we show how they can be applied to batch variants of three canonical online AL algorithms: IWAL, ORIWAL, and DHM. We also conduct an empirical study that corroborates the novel theoretical insights.
View details
Preview abstract
We present a new active learning algorithm that adaptively partitions the input space into a finite number of regions, and subsequently seeks a distinct predictor for each region, both phases actively requesting labels. We prove theoretical guarantees for both the generalization error and the label complexity of our algorithm, and analyze the number of regions defined by the algorithm under some mild assumptions. We also report the results of an extensive suite of experiments on several real-world datasets demonstrating substantial empirical benefits over existing single-region and nonadaptive region-based active learning baselines.
View details
Preview abstract
A general framework for online learning with partial information is one where feedback graphs specify which losses can be observed by the learner. We study a challenging scenario where feedback graphs vary with time stochastically and,more importantly, where graphs and losses are stochastically dependent. This scenario appears in several applications that we describe. We give a new algorithm for this scenario that exploits the stochastic properties of the graphs and that benefits from favorable regret guarantees in this challenging setting. We present a detailed theoretical analysis of this algorithm, and also report the results of a series of experiments on real-world datasets, which show that our algorithm outperforms standard baselines for online learning with feedback graphs.
View details
Preview abstract
We consider the scenario of online learning with the sleeping experts where not all experts are available at each round and analyze the general framework of learning with stochastic feedback graphs, where loss observations associated to each expert are characterized by a graph, thereby including both the bandit and full information settings as special cases. A critical assumption in this framework is that the loss observations and the set of sleeping experts at each round is independent. We first extend the classical algorithm of Kleinberg et al 2008 to use the loss information encoded by any sequence of feedback graphs and prove matching upper and lower bounds for the sleeping regret of this algorithm. Our main contribution is then to relax this independence assumption, present a finer notion of sleeping regret, and derive a general algorithm with strong theoretical guarantees. We instantiate our framework to the important scenario of online learning with abstention, where a learner can elect to abstain from making a prediction at the price of a certain cost. We empirically validate the improvement of our algorithm against multiple abstention algorithms on several real-world datasets
View details
