Vatsal Sharan
Assistant Professor,
Thomas Lord Department of Computer Science,
University of Southern California
Email: vsharan at usc dot edu
Office: GCS 402P
Publications
(many papers have alphabetical author ordering)- Discovering Data Structures: Nearest Neighbor Search and Beyond
- The Rich and the Simple: On the Implicit Bias of Adam and SGD
- Simultaneous Swap Regret Minimization via KL-Calibration
- Improved Bounds for Swap Multicalibration and Swap Omniprediction
- On the Inherent Privacy of Zeroth Order Projected Gradient Descent
- Proper Learnability and the Role of Unlabeled Data
- Transformers Learn Low Sensitivity Functions: Investigations and Implications
- When is Multicalibration Post-Processing Necessary?
- Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression
- Pre-trained Large Language Models Use Fourier Features to Compute Addition
- Optimal Multiclass U-Calibration Error and Beyond
- Transductive Sample Complexities Are Compact
- On the Statistical Complexity of Sample Amplification
- Mitigating Simplicity Bias in Deep Learning for Improved OOD Generalization and Robustness
- Stability and Multigroup Fairness in Ranking with Uncertain Predictions
- Regularization and Optimal Multiclass Learning
- Open Problem: Can Local Regularization Learn All Multiclass Problems?Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Open Problem @ COLT, 2024
pdf - Fairness in Matching under Uncertainty
- KL Divergence Estimation with Multi-group Attribution
- NeuroSketch: A Neural Network Method for Fast and Approximate Evaluation of Range Aggregate Queries
- Efficient Convex Optimization Requires Superlinear Memory
- Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
- Multicalibrated Partitions for Importance Weights
- Omnipredictors
- One Network Fits All? Modular versus Monolithic Task Formulations in Neural Networks Learning
- Sample Amplification: Increasing Dataset Size even when Learning is Impossible
- PIDForest: Anomaly Detection via Partial IdentificationParikshit Gopalan, Vatsal Sharan, Udi Wieder
NeurIPS, 2019
Spotlight presentation
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 Error
- Recovery Guarantees for Quadratic Tensors with Limited Observations
- Efficient Anomaly Detection via Matrix Sketching
- A Spectral View of Adversarially Robust Features
- Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries
- Prediction with a Short Memory
- Sketching Linear Classifiers over Data Streams
- Learning Overcomplete HMMs
- Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
- Large Deviation Property for Waiting Times for Markov and Mixing Processes
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.
Is learning a distribution always necessary for generating new samples from the distribution? We introduce the problem of "sample amplification": given n independent draws from a distribution, D , to what extent is it possible to output a set of m > n datapoints that are indistinguishable from m i.i.d. draws from D ? Curiously, we show that nontrivial amplification is often possible in the regime where n is too small to learn D to any nontrivial accuracy.
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 Networks
- Energy Efficient Optimal Node-Source Localization using Mobile Beacon in Ad-Hoc Sensor Networks
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.