
Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent
We study the statistical and computational complexities of the Polyak st...
read it

Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
Geometric median (Gm) is a classical method in statistics for achieving ...
read it

DPNormFedAvg: Normalizing Client Updates for PrivacyPreserving Federated Learning
In this paper, we focus on facilitating differentially private quantized...
read it

Enabling EfficiencyPrecision Tradeoffs for Label Trees in Extreme Classification
Extreme multilabel classification (XMC) aims to learn a model that can ...
read it

Nearly HorizonFree Offline Reinforcement Learning
We revisit offline reinforcement learning on episodic timehomogeneous t...
read it

Combinatorial Bandits without Total Order for Arms
We consider the combinatorial bandits problem, where at each time step, ...
read it

Linear Bandit Algorithms with Sublinear Time Complexity
We propose to accelerate existing linear bandit algorithms to achieve pe...
read it

Improved Convergence Rates for NonConvex Federated Learning with Compression
Federated learning is a new distributed learning paradigm that enables e...
read it

On Generalization of Adaptive Methods for Overparameterized Linear Regression
Overparameterization and adaptive methods have played a crucial role in...
read it

On the Benefits of Multiple Gossip Steps in CommunicationConstrained Decentralized Optimization
In decentralized optimization, it is common algorithmic practice to have...
read it

Extreme Multilabel Classification from Aggregated Labels
Extreme multilabel classification (XMC) is the problem of finding the r...
read it

Choosing the Sample with Lowest Loss makes SGD Robust
The presence of outliers can potentially significantly skew the paramete...
read it

Interaction Hard Thresholding: Consistent Sparse Quadratic Regression in Subquadratic Time and Space
Quadratic regression involves modeling the response as a (generalized) l...
read it

Learning Distributions Generated by OneLayer ReLU Networks
We consider the problem of estimating the parameters of a ddimensional ...
read it

Blocking Bandits
We consider a novel stochastic multiarmed bandit setting, where playing...
read it

Iterative Least Trimmed Squares for Mixed Linear Regression
Given a linear regression setting, Iterative Least Trimmed Squares (ILTS...
read it

Minimum norm solutions do not always generalize well for overparameterized problems
Stochastic gradient descent is the de facto algorithm for training deep ...
read it

Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
We characterize the effectiveness of a natural and classic algorithm for...
read it

Iteratively Learning from the Best
We study a simple generic framework to address the issue of bad training...
read it

The Sparse Recovery Autoencoder
Linear encoding of sparse vectors is widely popular, but is most commonl...
read it

Provable quantum state tomography via nonconvex methods
With nowadays steadily growing quantum processors, it is required to dev...
read it

Sparse Quadratic Logistic Regression in Subquadratic Time
We consider support recovery in the quadratic logistic regression settin...
read it

Single Pass PCA of Matrix Products
In this paper we present a new algorithm for computing a low rank approx...
read it

The Search Problem in Mixture Models
We consider the task of learning the parameters of a single component o...
read it

Nonsquare matrix sensing without spurious local minima via the BurerMonteiro approach
We consider the nonsquare matrix sensing problem, under restricted isom...
read it

Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
We consider the problem of solving mixed random linear equations with k ...
read it

Provable BurerMonteiro factorization for a class of normconstrained matrix problems
We study the projected gradient descent method on lowrank matrix proble...
read it

Tradingoff variance and complexity in stochastic gradient descent
Stochastic gradient descent is the method of choice for largescale mach...
read it

Dropping Convexity for Faster Semidefinite Optimization
We study the minimization of a convex function f(X) over the set of n× n...
read it

The local convexity of solving systems of quadratic equations
This paper considers the recovery of a rank r positive semidefinite matr...
read it

Convergence Rates of Active Learning for Maximum Likelihood Estimation
An active learner is given a class of models, a large set of unlabeled e...
read it

A New Sampling Technique for Tensors
In this paper we propose new techniques to sample arbitrary thirdorder ...
read it

Greedy Subspace Clustering
We consider the problem of subspace clustering: given points that lie on...
read it

Nonconvex Robust PCA
We propose a new method for robust PCA  the task of recovering a lowr...
read it

Tighter Lowrank Approximation via Sampling the Leveraged Element
In this work, we propose a new randomized algorithm for computing a low...
read it

Completing Any Lowrank Matrix, Provably
Matrix completion, i.e., the exact and provable recovery of a lowrank m...
read it

Phase Retrieval using Alternating Minimization
Phase retrieval problems involve solving linear equations, but with miss...
read it

Lowrank Matrix Completion using Alternating Minimization
Alternating minimization represents a widely applicable and empirically ...
read it

Improved Graph Clustering
Graph clustering involves the task of dividing nodes into clusters, so t...
read it

Greedy Learning of Markov Network Structure
We propose a new yet natural algorithm for learning the graph structure ...
read it

Finding the Graph of Epidemic Cascades
We consider the problem of finding the graph on which an epidemic cascad...
read it

A Dirty Model for Multiple Sparse Regression
Sparse linear regression  finding an unknown vector from linear measur...
read it

Clustering Partially Observed Graphs via Convex Optimization
This paper considers the problem of clustering a partially observed unwe...
read it

Lowrank Matrix Recovery from Errors and Erasures
This paper considers the recovery of a lowrank matrix from an observed ...
read it

Matrix completion with column manipulation: Nearoptimal samplerobustnessrank tradeoffs
This paper considers the problem of matrix completion when some number o...
read it

Robust PCA via Outlier Pursuit
Singular Value Decomposition (and Principal Component Analysis) is one o...
read it
Sujay Sanghavi
is this you? claim profile
Associate Professor in the Department of Electrical and Computer Engineering at The University of Texas at Austin, Assistant Professor at Electrical Engineering, University of Texas, Austin from 20092014, Visiting Scientist at Google Inc. 2014, Assistant Professor at Electrical Engineering, Purdue University from 20082009, Postdoctoral Scholar at Massachusetts Institute of Technology from 20062008, NSF CAREER award in January 2010.