252 citations · 435 across the 19 of their papers we have counts for
13 papers · 1 filter
Online Learning and Bandits with Queried Hints
Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im +2
We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number ()…
Smoothed Analysis in Unsupervised Learning via Decoupling
Aditya Bhaskara, Aidao Chen, Aidan Perreault +1
Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in unsupervised learning and high-dimensional data analysis. While polynomial time smoothed analysi…
Low Rank Approximation in the Presence of Outliers
Aditya Bhaskara, Srivatsan Kumar
We consider the problem of principal component analysis (PCA) in the presence of outliers. Given a matrix () and parameters , the goal is to remove a set of a…
Sublinear Algorithms for MAXCUT and Correlation Clustering
Aditya Bhaskara, Samira Daruki, Suresh Venkatasubramanian
We study sublinear algorithms for two fundamental graph problems, MAXCUT and correlation clustering. Our focus is on constructing core-sets as well as developing streaming algorith…
Greedy Column Subset Selection: New Bounds and Distributed Algorithms
Jason Altschuler, Aditya Bhaskara, Gang Fu +3
The problem of column subset selection has recently attracted a large body of research, with feature selection serving as one obvious and important application. Among the technique…
On Binary Embedding using Circulant Matrices
Felix X. Yu, Aditya Bhaskara, Sanjiv Kumar +2
Binary embeddings provide efficient and powerful ways to perform operations on large scale data. However binary embedding typically requires long codes in order to preserve the dis…
Expanders via Local Edge Flips
Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi +2
Designing distributed and scalable algorithms to improve network connectivity is a central topic in peer-to-peer networks. In this paper we focus on the following well-known proble…
Sparse Solutions to Nonnegative Linear Systems and Applications
Aditya Bhaskara, Ananda Theertha Suresh, Morteza Zadimoghaddam
We give an efficient algorithm for finding sparse approximate solutions to linear systems of equations with nonnegative coefficients. Unlike most known results for sparse recovery,…
More Algorithms for Provable Dictionary Learning
Sanjeev Arora, Aditya Bhaskara, Rong Ge +1
In dictionary learning, also known as sparse coding, the algorithm is given samples of the form where is an unknown random sparse vector and is an…
Smoothed Analysis of Tensor Decompositions
Aditya Bhaskara, Moses Charikar, Ankur Moitra +1
Low rank tensor decompositions are a powerful tool for learning generative models, and uniqueness results give them a significant advantage over matrix decomposition methods. Howev…
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
We give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: we prove that given a tensor whose decomposition satisfies a robust form of…
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami +2
The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significan…
Approximating Matrix p-norms
Aditya Bhaskara, Aravindan Vijayaraghavan
We consider the problem of computing the q->p norm of a matrix A, which is defined for p,q \ge 1, as |A|_{q->p} = max_{x !=0 } |Ax|_p / |x|_q. This is in general a non-convex optim…