Assistant Professor,

Department of Computer Science,

University of Southern California

vatsal.sharan1 at gmail dot com

I joined the Computer Science Department at USC as an assistant professor in Fall 2021. Previously, I was a Norbert Wiener postdoc at MIT hosted by Ankur Moitra. I obtained my Ph.D. from Stanford advised by Greg Valiant, and was a part of the Theory Group and the Statistical Machine Learning Group at Stanford.

I work on machine learning, statistics and theoretical computer science. My research aims to understand how to solve learning and inference tasks in the face of various computational and statistical constraints, such as limited memory or too little data. I am also broadly interested in the desiderata in practical applications beyond these constraints as well---particularly in notions of robustness. My interests are both in developing theoretical frameworks to understand the fundamental limits in these modern settings, and in designing practical algorithms to tackle these problems. If you're interested in learning more, some of my recent work studies the following questions:

- What is the role of memory in learning and optimization? How do we learn concepts with small memory? Are there inherent trade-offs between the amount of memory required for learning or optimization, and the amount of data or computation required?
- How can we ensure that trained models are robust even when evaluated on data distributions which differ from the original training distribution? How do we detect anomalies and shifts in the data distribution?
- What is the relationship between learning an unknown distribution
*D*, testing properties of*D*, and generating new samples from*D*?

CV [as of Dec'19]

- Multicalibrated Partitions for Importance WeightsParikshit Gopalan*, Omer Reingold*, Vatsal Sharan*, Udi Wieder*

*arXiv, 2021*

**arXiv**|**pdf** - One Network Fits All? Modular versus Monolithic Task Formulations in Neural Networks LearningAtish Agarwala*, Abhimanyu Das*, Brendan Juba*, Rina Panigrahy*, Vatsal Sharan*, Xin Wang*, Qiuyi Zhang*

*ICLR, 2021*

**abstract**|**arXiv**|**pdf**|**video** - Sample Amplification: Increasing Dataset Size even when Learning is ImpossibleBrian Axelrod*, Shivam Garg*, Vatsal Sharan*, Gregory Valiant*

*ICML, 2020*

**abstract**|**pdf**|**arXiv**|**video** - PIDForest: Anomaly Detection via Partial IdentificationParikshit Gopalan*, Vatsal Sharan*, Udi Wieder*

*NeurIPS, 2019***(Spotlight)**

**abstract**|**pdf**|**arXiv**|**code**|**spotlight video** - Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed DataVatsal Sharan*, Kai Sheng Tai*, Peter Bailis, Gregory Valiant

*ICML, 2019*

**abstract**|**pdf**|**arXiv**|**code**|**spotlight video** - Memory-Sample Tradeoffs for Linear Regression with Small ErrorVatsal Sharan, Aaron Sidford, Gregory Valiant

*STOC, 2019*

**abstract**|**pdf**|**arXiv** - Recovery Guarantees for Quadratic Tensors with Limited ObservationsHongyang Zhang, Vatsal Sharan, Moses Charikar and Yingyu Liang

*AISTATS, 2019*

**abstract**|**pdf**|**arXiv** - Efficient Anomaly Detection via Matrix SketchingVatsal Sharan, Parikshit Gopalan, Udi Wieder

*NeurIPS, 2018*

**abstract**|**pdf**|**arXiv** - A Spectral View of Adversarially Robust FeaturesShivam Garg, Vatsal Sharan*, Brian Zhang*, Gregory Valiant

*NeurIPS, 2018***(Spotlight)**

**abstract**|**pdf**|**arXiv** - Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation QueriesEdward Gan, Jialin Ding, Kai Sheng Tai, Vatsal Sharan, Peter Bailis

*VLDB, 2018*

**abstract**|**pdf**|**arXiv**|**code** - Prediction with a Short MemoryVatsal Sharan, Sham Kakade, Percy Liang, Gregory Valiant

*STOC, 2018*

**abstract**|**pdf**|**arXiv**|**blog**|**video** - Sketching Linear Classifiers over Data StreamsKai Sheng Tai, Vatsal Sharan, Peter Bailis, Gregory Valiant

*SIGMOD, 2018*

**abstract**|**pdf**|**arXiv**|**code** - Learning Overcomplete HMMsVatsal Sharan, Sham Kakade, Percy Liang, Gregory Valiant

*NeurIPS, 2017*

**abstract**|**pdf**|**arXiv** - Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical UseVatsal Sharan, Gregory Valiant

*ICML, 2017*

**abstract**|**pdf**|**arXiv**|**code** - Large Deviation Property for Waiting Times for Markov and Mixing ProcessesVatsal Sharan, R.K. Bansal

*ISIT, 2014*

**abstract**|**pdf**

Can deep learning solve multiple, very different tasks simultaneously? We investigate this question in this work, and do a systematic study of how the properties of the underlying tasks affect the ability of a single neural network to learn them jointly. We present theoretical and empirical findings that neural networks are capable of learning multiple tasks when these tasks are naturally clustered and well-separated. We also show that multi-task learning can be provably hard---even though the individual tasks are easy to learn---in settings where such a natural separation does not exist, and validate this through experiments.

Jump to 50:00 (or topic #27) in this video.

We propose a definition of an anomaly that captures the intuition that anomalies are easy to distinguish from the overwhelming majority of points by relatively few attribute values: we call this partial identification. Formalizing this intuition, we propose a geometric anomaly measure for a point that we call PIDScore, which measures for the minimum density of data points over all subcubes containing the point. We present PIDForest: a random forest based algorithm that finds anomalies based on this definition, and show that it performs favorably in comparison to several popular anomaly detection methods, across a broad range of benchmarks.

Jump to 35:30 (or topic #47) in this video.

What learning algorithms can be run directly on compressively-sensed data? If we compress a high dimensional matrix via a random projection, then what is the relationship between the factors of the original matrix and the factors of the compressed matrix? While it is well-known that random projections preserve a number of geometric properties of a dataset, this work shows that random projections can also preserve certain solutions to non-convex, NP-Hard problems like non-negative matrix factorization---both in theory and in practice.

Jump to 53:20 in this video.

What is the role of memory in continuous optimization and learning? Are there inherent trade-offs between the available memory and the data requirement? Is it possible to achieve the sample complexity of second-order optimization methods with significantly less memory? We raise these questions, and show the first nontrivial lower bounds for linear regression with super-linear memory: we show that there is a gap between the sample complexity of algorithms with quadratic memory and that of any algorithm with sub-quadratic memory.

We consider the tensor completion problem of predicting the missing entries of a tensor. The commonly used CP model has a triple product form, but an alternate family of quadratic models which are the sum of pairwise products instead of a triple product have emerged from applications such as recommendation systems. Non-convex methods are the method of choice for learning quadratic models, and this work studies their sample complexity and error guarantees via theoretical results and experiments on real and synthetic data.

PCA based anomaly scores are commonly used for finding anomalies in high-dimensional data. The naive algorithms for computing these scores explicitly compute the PCA of the covariance matrix which uses space quadratic in the dimensionality of the data. Using matrix sketching tools and new matrix perturbation inequalities, we give the first streaming algorithms for computing these scores that use space that is linear or sublinear in the dimension.

Despite a surge of recent effort, there is still much that we do not understand about why models are vulnerable to adversarial perturbations, or how to reduce this vulnerability. In this work, we introduce the simpler, intermediate task of learning a set of "robust features"---features which are stable to adversarial perturbations. These features can subsequently be used as inputs to a classifier, which will then inherit the robustness properties. We propose one approach to constructing robust features, which leverages a tight connection between robustness and spectral properties of the neighbourhood graph of the data.

We propose a compact and efficiently mergeable sketch for answering quantile queries on a dataset. This data structure, which we refer to as the moments sketch, operates with a small memory footprint (200 bytes) and achieves computationally efficient (50ns) merges by tracking only a set of summary statistics, notably the sample moments.

When is it necessary to remember significant information from the distant past to make good predictions about the future in sequential prediction tasks? How do we consolidate and reference memories about the past in order to predict the future? This work studies these questions, and the findings are perhaps counterintuitive: we show that a simple (Markov) model which bases its predictions on only the most recent observations and the statistics of short windows, can achieve small error on average with respect to a large class of sequences, such as those generated by Hidden Markov Models (HMMs). This shows that long-term memory may not be necessary for making good predictions on average, even on sequences generated by complex processes that have long-range dependencies.

We introduce a new sub-linear space sketch---the Weight-Median Sketch---for learning compressed linear classifiers over data streams while supporting the efficient recovery of large-magnitude weights in the classifier. The Weight-Median Sketch adopts the core data structure used in the Count-Sketch, but, instead of sketching counts, it captures sketched gradient updates to the model parameters. We establishes recovery guarantees for our sketch and demonstrate empirical improvements in memory-accuracy trade-offs over alternative memory-budgeted methods.

We study the problem of learning overcomplete HMMs---those that have many hidden states but a small output alphabet. Despite having significant practical importance, such HMMs are poorly understood with no known positive or negative results for efficient learning. In this paper, we present several new results---both positive and negative---which help define the boundaries between the tractable and intractable settings.

The popular Alternating Least Squares (ALS) algorithm for tensor decomposition is efficient and easy to implement, but often converges to poor local optima. We propose a modification of the ALS approach that is as efficient as standard ALS, but provably recovers the true factors with random initialization under standard incoherence assumptions on the factors of the tensor. We demonstrate the significant practical superiority of our approach over traditional ALS on a variety of synthetic and real-world tasks.

We show a concentration theorem for the waiting time until the opening string in the realization of a random process first appears in an independent realization of the same or a different process.

During undergrad, I worked on localization in sensor networks.

- Localization of Acoustic Beacons using Iterative Null Beamforming over Ad-hoc Wireless Sensor NetworksVatsal Sharan, Sudhir Kumar, and Rajesh Hegde

*IEEE Asilomar Conference on Signals, Systems, and Computers, 2013*

**abstract**|**pdf** - Energy Efficient Optimal Node-Source Localization using Mobile Beacon in Ad-Hoc Sensor NetworksSudhir Kumar, Vatsal Sharan and Rajesh Hegde

*IEEE Global Communications Conference (Globecom), 2013*

**abstract**|**pdf**

We propose an iterative method to localize and separate multiple audio beacons using the principle of null beam forming.

We propose a single mobile beacon based method to localize nodes using the principle of maximum power reception.