research
∙
06/25/2023
Near Optimal Heteroscedastic Regression with Symbiotic Learning
We consider the problem of heteroscedastic linear regression, where, giv...
share
research
∙
02/01/2023
Simplicity Bias in 1-Hidden Layer Neural Networks
Recent works have demonstrated that neural networks exhibit extreme simp...
research
∙
10/18/2022
Consistent Multiclass Algorithms for Complex Metrics and Constraints
We present consistent algorithms for multiclass learning with complex pe...
research
∙
10/11/2022
Multi-User Reinforcement Learning with Low Rank Rewards
In this work, we consider the problem of collaborative multi-user reinfo...
research
∙
10/04/2022
Learning an Invertible Output Mapping Can Mitigate Simplicity Bias in Neural Networks
Deep Neural Networks are known to be brittle to even minor distribution ...
research
∙
09/29/2022
Optimistic MLE – A Generic Model-based Algorithm for Partially Observable Sequential Decision Making
This paper introduces a simple efficient learning algorithms for general...
research
∙
08/19/2022
DAFT: Distilling Adversarially Fine-tuned Models for Better OOD Generalization
We consider the problem of OOD generalization, where the goal is to trai...
research
∙
06/17/2022
All Mistakes Are Not Equal: Comprehensive Hierarchy Aware Multi-label Predictions (CHAMP)
This paper considers the problem of Hierarchical Multi-Label Classificat...
research
∙
06/17/2022
MET: Masked Encoding for Tabular Data
We consider the task of self-supervised representation learning (SSL) fo...
research
∙
02/09/2022
Reproducibility in Optimization: Theoretical Framework and Limits
We initiate a formal study of reproducibility in optimization. We define...
research
∙
12/02/2021
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
We study the complexity of optimizing highly smooth convex functions. Fo...
research
∙
10/16/2021
Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs
Q-learning is a popular Reinforcement Learning (RL) algorithm which is w...
research
∙
10/06/2021
Focus on the Common Good: Group Distributional Robustness Follows
We consider the problem of training a classification model with group an...
research
∙
06/02/2021
Minimax Optimization with Smooth Algorithmic Adversaries
This paper considers minimax optimization min_x max_y f(x, y) in the cha...
research
∙
05/24/2021
Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
We consider the setting of vector valued non-linear dynamical systems X_...
research
∙
05/18/2021
Sample Efficient Linear Meta-Learning by Alternating Minimization
Meta-learning synthesizes and leverages the knowledge from a given set o...
research
∙
03/10/2021
Streaming Linear System Identification with Reverse Experience Replay
We consider the problem of estimating a stochastic linear time-invariant...
research
∙
02/25/2021
Do Input Gradients Highlight Discriminative Features?
Interpretability methods that seek to explain instance-specific model pr...
research
∙
10/05/2020
Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
We consider the classical setting of optimizing a nonsmooth Lipschitz co...
research
∙
10/05/2020
No quantum speedup over gradient descent for non-smooth convex optimization
We study the first-order convex optimization problem, where we have blac...
research
∙
06/19/2020
Learning Minimax Estimators via Online Learning
We consider the problem of designing minimax estimators for estimating t...
research
∙
06/16/2020
Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms
We study the problem of least squares linear regression where the data-p...
research
∙
06/13/2020
The Pitfalls of Simplicity Bias in Neural Networks
Several works have proposed Simplicity Bias (SB)—the tendency of standar...
research
∙
06/13/2020
Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games
We consider the problem of online learning and its application to solvin...
research
∙
05/12/2020
MOReL : Model-Based Offline Reinforcement Learning
In offline reinforcement learning (RL), the goal is to learn a successfu...
research
∙
03/28/2020
Efficient Domain Generalization via Common-Specific Low-Rank Decomposition
Domain generalization refers to the task of training a model which gener...
research
∙
10/21/2019
Non-Gaussianity of Stochastic Gradient Noise
What enables Stochastic Gradient Descent (SGD) to achieve better general...
research
∙
07/02/2019
Efficient Algorithms for Smooth Minimax Optimization
This paper studies first order methods for solving smooth minimax optimi...
research
∙
04/29/2019
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure
There is a stark disparity between the step size schedules used in pract...
research
∙
04/29/2019
Making the Last Iterate of SGD Information Theoretically Optimal
Stochastic gradient descent (SGD) is one of the most widely used algorit...
research
∙
03/19/2019
Online Non-Convex Learning: Following the Perturbed Leader is Optimal
We study the problem of online learning with non-convex losses, where th...
research
∙
03/04/2019
SGD without Replacement: Sharper Rates for General Smooth Convex Functions
We study stochastic gradient descent without replacement () for smooth ...
research
∙
02/13/2019
Stochastic Gradient Descent Escapes Saddle Points Efficiently
This paper considers the perturbed stochastic gradient descent algorithm...
research
∙
02/11/2019
A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
In this note, we derive concentration inequalities for random vectors wi...
research
∙
02/02/2019
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal
Minmax optimization, especially in its general nonconvex-nonconcave form...
research
∙
03/15/2018
On the insufficiency of existing momentum schemes for Stochastic Optimization
Momentum based stochastic gradient methods such as heavy ball (HB) and N...
research
∙
03/01/2018
Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Semidefinite programs (SDP) are important in learning and combinatorial ...
research
∙
11/28/2017
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
Nesterov's accelerated gradient descent (AGD), an instance of the genera...
research
∙
11/22/2017
Leverage Score Sampling for Faster Accelerated Regression and ERM
Given a matrix A∈R^n× d and a vector b ∈R^d, we show how to compute an ϵ...
research
∙
10/25/2017
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...
research
∙
04/26/2017
Accelerating Stochastic Gradient Descent
There is widespread sentiment that it is not possible to effectively uti...
research
∙
03/02/2017
How to Escape Saddle Points Efficiently
This paper shows that a perturbed form of gradient descent converges to ...
research
∙
10/12/2016
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging
This work characterizes the benefits of averaging techniques widely used...
research
∙
05/26/2016
Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
Matrix completion, where we wish to recover a low rank matrix by observi...
research
∙
04/13/2016
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
This paper considers the problem of canonical-correlation analysis (CCA)...
research
∙
02/22/2016
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
This work provides improved guarantees for streaming principle component...
research
∙
06/08/2015
Convergence Rates of Active Learning for Maximum Likelihood Estimation
An active learner is given a class of models, a large set of unlabeled e...
research
∙
02/03/2015
Learning Planar Ising Models
Inference and learning of graphical models are both well-studied problem...
research
∙
11/04/2014
Fast Exact Matrix Completion with Finite Samples
Matrix completion is the problem of recovering a low rank matrix by obse...
research
∙
10/28/2014
