
SGD without Replacement: Sharper Rates for General Smooth Convex Functions
We study stochastic gradient descent without replacement () for smooth ...
03/04/2019 ∙ by Prateek Jain, et al. ∙ 12 ∙ shareread it

Efficient Algorithms for Smooth Minimax Optimization
This paper studies first order methods for solving smooth minimax optimi...
07/02/2019 ∙ by Kiran Koshy Thekumparampil, et al. ∙ 10 ∙ shareread it

Leveraging Distributional Semantics for MultiLabel Learning
We present a novel and scalable label embedding framework for largescal...
09/18/2017 ∙ by Rahul Wadbude, et al. ∙ 0 ∙ shareread it

A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
This work provides a simplified proof of the statistical minimax optimal...
10/25/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Learning Mixture of Gaussians with Streaming Data
In this paper, we study the problem of learning a mixture of Gaussians w...
07/08/2017 ∙ by Aditi Raghunathan, et al. ∙ 0 ∙ shareread it

Recovery Guarantees for Onehiddenlayer Neural Networks
In this paper, we consider regression problems with onehiddenlayer neu...
06/10/2017 ∙ by Kai Zhong, et al. ∙ 0 ∙ shareread it

Accelerating Stochastic Gradient Descent
There is widespread sentiment that it is not possible to effectively uti...
04/26/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Parallelizing Stochastic Approximation Through MiniBatching and TailAveraging
This work characterizes the benefits of averaging techniques widely used...
10/12/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Efficient and Consistent Robust Time Series Analysis
We study the problem of robust time series analysis under the standard a...
07/01/2016 ∙ by Kush Bhatia, et al. ∙ 0 ∙ shareread it

Regret Bounds for Nondecomposable Metrics with Missing Labels
We consider the problem of recommending relevant labels (items) for a gi...
06/07/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Streaming PCA: Matching Matrix Bernstein and NearOptimal Finite Sample Guarantees for Oja's Algorithm
This work provides improved guarantees for streaming principle component...
02/22/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Structured Sparse Regression via Greedy HardThresholding
Several learning applications require solving highdimensional regressio...
02/19/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
Robust tensor CP decomposition involves decomposing a tensor into low ra...
10/15/2015 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Robust Regression via Hard Thresholding
We study the problem of Robust Least Squares Regression (RLSR) where sev...
06/08/2015 ∙ by Kush Bhatia, et al. ∙ 0 ∙ shareread it

Surrogate Functions for Maximizing Precision at the Top
The problem of maximizing precision at the top of a ranked list, often d...
05/26/2015 ∙ by Purushottam Kar, et al. ∙ 0 ∙ shareread it

Optimizing Nondecomposable Performance Measures: A Tale of Two Classes
Modern classification problems frequently present mild to severe label i...
05/26/2015 ∙ by Harikrishna Narasimhan, et al. ∙ 0 ∙ shareread it

To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout
Training deep belief networks (DBNs) requires optimizing a nonconvex fu...
03/06/2015 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Fast Exact Matrix Completion with Finite Samples
Matrix completion is the problem of recovering a low rank matrix by obse...
11/04/2014 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Nonconvex Robust PCA
We propose a new method for robust PCA  the task of recovering a lowr...
10/28/2014 ∙ by Praneeth Netrapalli, et al. ∙ 0 ∙ shareread it

Online and Stochastic Gradient Methods for Nondecomposable Loss Functions
Modern applications in sensitive domains such as biometrics and medicine...
10/24/2014 ∙ by Purushottam Kar, et al. ∙ 0 ∙ shareread it

On Iterative Hard Thresholding Methods for Highdimensional MEstimation
The use of Mestimators in generalized linear regression models in high ...
10/20/2014 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Tighter Lowrank Approximation via Sampling the Leveraged Element
In this work, we propose a new randomized algorithm for computing a low...
10/14/2014 ∙ by Srinadh Bhojanapalli, et al. ∙ 0 ∙ shareread it

Universal Matrix Completion
The problem of lowrank matrix completion has recently generated a lot o...
02/10/2014 ∙ by Srinadh Bhojanapalli, et al. ∙ 0 ∙ shareread it

Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
We study the problem of learning a distribution from samples, when the u...
11/12/2013 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Memory Limited, Streaming PCA
We consider streaming, onepass principal component analysis (PCA), in t...
06/28/2013 ∙ by Ioannis Mitliagkas, et al. ∙ 0 ∙ shareread it

Provable Inductive Matrix Completion
Consider a movie recommendation system where apart from the ratings info...
06/04/2013 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Phase Retrieval using Alternating Minimization
Phase retrieval problems involve solving linear equations, but with miss...
06/02/2013 ∙ by Praneeth Netrapalli, et al. ∙ 0 ∙ shareread it

On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions
In this paper, we study the generalization properties of online learning...
05/11/2013 ∙ by Purushottam Kar, et al. ∙ 0 ∙ shareread it

Lowrank Matrix Completion using Alternating Minimization
Alternating minimization represents a widely applicable and empirically ...
12/03/2012 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

The Interplay Between Stability and Regret in Online Learning
This paper considers the stability of online learning algorithms and its...
11/26/2012 ∙ by Ankan Saha, et al. ∙ 0 ∙ shareread it

Supervised Learning with Similarity Functions
We address the problem of general supervised learning when data can only...
10/22/2012 ∙ by Purushottam Kar, et al. ∙ 0 ∙ shareread it

Similaritybased Learning via Data Driven Embeddings
We consider the problem of classification using similarity/distance func...
12/22/2011 ∙ by Purushottam Kar, et al. ∙ 0 ∙ shareread it

Differentially Private Online Learning
In this paper, we consider the problem of preserving privacy in the onli...
09/01/2011 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Orthogonal Matching Pursuit with Replacement
In this paper, we consider the problem of compressed sensing where the g...
06/14/2011 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Metric and Kernel Learning using a Linear Transformation
Metric and kernel learning are important in several machine learning app...
10/30/2009 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Differentially Private Matrix Completion, Revisited
We study the problem of privacypreserving collaborative filtering where...
12/28/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Nonconvex Optimization for Machine Learning
A vast majority of machine learning algorithms train their models and pe...
12/21/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Smoothed analysis for lowrank solutions to semidefinite programs in quadratic penalty form
Semidefinite programs (SDP) are important in learning and combinatorial ...
03/01/2018 ∙ by Srinadh Bhojanapalli, et al. ∙ 0 ∙ shareread it

On the insufficiency of existing momentum schemes for Stochastic Optimization
Momentum based stochastic gradient methods such as heavy ball (HB) and N...
03/15/2018 ∙ by Rahul Kidambi, et al. ∙ 0 ∙ shareread it

Nonlinear Inductive Matrix Completion based on Onelayer Neural Networks
The goal of a recommendation system is to predict the interest of a user...
05/26/2018 ∙ by Kai Zhong, et al. ∙ 0 ∙ shareread it

NeuralGuided Deductive Search for RealTime Program Synthesis from Examples
Synthesizing userintended programs from a small number of inputoutput ...
04/03/2018 ∙ by Ashwin J. Vijayakumar, et al. ∙ 0 ∙ shareread it

Adaptive Hard Thresholding for Nearoptimal Consistent Robust Regression
We study the problem of robust linear regression with response variable ...
03/19/2019 ∙ by Arun Sai Suggala, et al. ∙ 0 ∙ shareread it

FastGRNN: A Fast, Accurate, Stable and Tiny Kilobyte Sized Gated Recurrent Neural Network
This paper develops the FastRNN and FastGRNN algorithms to address the t...
01/08/2019 ∙ by Aditya Kusupati, et al. ∙ 0 ∙ shareread it

Making the Last Iterate of SGD Information Theoretically Optimal
Stochastic gradient descent (SGD) is one of the most widely used algorit...
04/29/2019 ∙ by Prateek Jain, et al. ∙ 0 ∙ shareread it

Learning Functions over Sets via Permutation Adversarial Networks
In this paper, we consider the problem of learning functions over sets, ...
07/12/2019 ∙ by Chirag Pabbaraju, et al. ∙ 0 ∙ shareread it