research
∙
07/02/2023
Solving Linear Inverse Problems Provably via Posterior Sampling with Latent Diffusion Models
We present the first framework to solve linear inverse problems leveragi...
share
research
∙
06/15/2023
Logarithmic Bayes Regret Bounds
We derive the first finite-time logarithmic regret bounds for Bayesian b...
research
∙
04/22/2023
Understanding Lexical Biases when Identifying Gang-related Social Media Communications
Individuals involved in gang-related activity use mainstream social medi...
research
∙
02/13/2023
Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD
This work considers the problem of finding a first-order stationary poin...
research
∙
02/02/2023
A Theoretical Justification for Image Inpainting using Denoising Diffusion Probabilistic Models
We provide a theoretical justification for sample recovery using diffusi...
research
∙
10/05/2022
Tractable Optimality in Episodic Latent MABs
We consider a multi-armed bandit problem with M latent contexts, where a...
research
∙
10/05/2022
Reward-Mixing MDPs with a Few Latent Contexts are Learnable
We consider episodic reinforcement learning in reward-mixing Markov deci...
research
∙
05/29/2022
Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret
The stochastic multi-armed bandit setting has been recently studied in t...
research
∙
05/26/2022
Contextual Pandora's Box
Pandora's Box is a fundamental stochastic optimization problem, where th...
research
∙
02/11/2022
The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance
We study convergence rates of AdaGrad-Norm as an exemplar of adaptive st...
research
∙
01/30/2022
Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms
Motivated by online recommendation systems, we propose the problem of fi...
research
∙
11/04/2021
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
We study single-sample prophet inequalities (SSPIs), i.e., prophet inequ...
research
∙
10/07/2021
Reinforcement Learning in Reward-Mixing MDPs
Learning a near optimal policy in a partially observable system remains ...
research
∙
05/22/2021
Combinatorial Blocking Bandits with Stochastic Delays
Recent work has considered natural variations of the multi-armed bandit ...
research
∙
03/24/2021
Single-Sample Prophet Inequalities Revisited
The study of the prophet inequality problem in the limited information r...
research
∙
02/17/2021
Robust Estimation of Tree Structured Markov Random Fields
We study the problem of learning tree-structured Markov random fields (M...
research
∙
02/09/2021
RL for Latent MDPs: Regret Guarantees and a Lower Bound
In this work, we consider the regret minimization problem for reinforcem...
research
∙
01/30/2021
Recurrent Submodular Welfare and Matroid Blocking Bandits
A recent line of research focuses on the study of the stochastic multi-a...
research
∙
01/27/2021
On the computational and statistical complexity of over-parameterized matrix sensing
We consider solving the low rank matrix sensing problem with Factorized ...
research
∙
08/19/2020
Quarantines as a Targeted Immunization Strategy
In the context of the recent COVID-19 outbreak, quarantine has been used...
research
∙
07/07/2020
Robust Structured Statistical Estimation via Conditional Gradient Type Methods
Structured statistical estimation problems are often solved by Condition...
research
∙
06/16/2020
Robust compressed sensing of generative models
The goal of compressed sensing is to estimate a high dimensional vector ...
research
∙
06/10/2020
Robust Estimation of Tree Structured Ising Models
We consider the task of learning Ising models when the signs of differen...
research
∙
06/04/2020
On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression
We study the convergence rates of the EM algorithm for learning two-comp...
research
∙
03/06/2020
Contextual Blocking Bandits
We study a novel variant of the multi-armed bandit problem, where at eac...
research
∙
02/02/2020
EM Algorithm is Sample-Optimal for Learning Mixtures of Well-Separated Gaussians
We consider the problem of spherical Gaussian Mixture models with k ≥ 3 ...
research
∙
10/17/2019
Communication-Efficient Asynchronous Stochastic Frank-Wolfe over Nuclear-norm Balls
Large-scale machine learning training suffers from two prior challenges,...
research
∙
07/23/2019
Mix and Match: An Optimistic Tree-Search Approach for Learning Models from Mixture Distributions
We consider a co-variate shift problem where one has access to several m...
research
∙
07/14/2019
More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning
We consider the weakly supervised binary classification problem where th...
research
∙
06/14/2019
Disentangling Mixtures of Epidemics on Graphs
We consider the problem of learning the weighted edges of a mixture of t...
research
∙
06/06/2019
Primal-Dual Block Frank-Wolfe
We propose a variant of the Frank-Wolfe algorithm for solving a class of...
research
∙
05/28/2019
EM Converges for a Mixture of Many Linear Regressions
We study the convergence of the Expectation-Maximization (EM) algorithm ...
research
∙
03/06/2019
Learning Graphs from Noisy Epidemic Cascades
We consider the problem of learning the weighted edges of a graph by obs...
research
∙
01/25/2019
Robust estimation of tree structured Gaussian Graphical Model
Consider jointly Gaussian random variables whose conditional independenc...
research
∙
01/24/2019
High Dimensional Robust Estimation of Sparse Models via Trimmed Hard Thresholding
We study the problem of sparsity constrained M-estimation with arbitrary...
research
∙
10/12/2018
Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
The Expectation-Maximization algorithm is perhaps the most broadly used ...
research
∙
07/26/2018
Entropic Latent Variable Discovery
We consider the problem of discovering the simplest latent variable that...
research
∙
05/29/2018
High Dimensional Robust Sparse Regression
We provide a novel -- and to the best of our knowledge, the first -- alg...
research
∙
05/23/2018
Approximate Newton-based statistical inference using only stochastic gradients
We present a novel inference framework for convex empirical risk minimiz...
research
∙
03/01/2018
The Shape of Alerts: Detecting Malware Using Distributed Detectors by Robustly Amplifying Transient Correlations
We introduce a new malware detector - Shape-GD - that aggregates per-mac...
research
∙
11/22/2017
The Stochastic Firefighter Problem
The dynamics of infectious diseases spread is crucial in determining the...
research
∙
11/04/2017
Provable quantum state tomography via non-convex methods
With nowadays steadily growing quantum processors, it is required to dev...
research
∙
05/21/2017
Statistical inference using SGD
We present a novel method for frequentist statistical inference in M-est...
research
∙
09/12/2016
Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach
We consider the non-square matrix sensing problem, under restricted isom...
research
∙
08/19/2016
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 ...
research
∙
06/04/2016
Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems
We study the projected gradient descent method on low-rank matrix proble...
research
∙
05/25/2016
Fast Algorithms for Robust PCA via Gradient Descent
We consider the problem of Robust PCA in the fully and partially observe...
research
∙
11/27/2015
Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
Latent variable models are a fundamental modeling tool in machine learni...
research
∙
05/13/2015
Optimal linear estimation under unknown nonlinear transform
Linear regression studies the problem of estimating a model parameter β^...
research
∙
10/31/2014