252 citations · 435 across the 19 of their papers we have counts for
23 papers
Understanding the Effect of the Long Tail on Neural Network Compression
Harvey Dam, Vinu Joseph, Aditya Bhaskara +3
Network compression is now a mature sub-field of neural network research: over the last decade, significant progress has been made towards reducing the size of models and speeding…
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 ()…
Logarithmic Regret from Sublinear Hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We consider the online linear optimization problem, where at every step the algorithm plays a point in the unit ball, and suffers loss for some cost…
Going Beyond Classification Accuracy Metrics in Model Compression
Vinu Joseph, Shoaib Ahmed Siddiqui, Aditya Bhaskara +5
With the rise in edge-computing devices, there has been an increasing demand to deploy energy and resource-efficient models. A large body of research has been devoted to developing…
Online Linear Optimization with Many Hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We study an online linear optimization (OLO) problem in which the learner is provided access to "hint" vectors in each round prior to making a decision. In this setting, we dev…
Fair clustering via equitable group representations
Mohsen Abbasi, Aditya Bhaskara, Suresh Venkatasubramanian
What does it mean for a clustering to be fair? One popular approach seeks to ensure that each cluster contains groups in (roughly) the same proportion in which they exist in the po…
Online Learning with Imperfect Hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We consider a variant of the classical online linear optimization problem in which at every step, the online player receives a "hint" vector before choosing the action for that rou…
Approximate Guarantees for Dictionary Learning
Aditya Bhaskara, Wai Ming Tai
In the dictionary learning (or sparse coding) problem, we are given a collection of signals (vectors in ), and the goal is to find a "basis" in which the signals have…
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…
Provable Bounds for Learning Some Deep Representations
Sanjeev Arora, Aditya Bhaskara, Rong Ge +1
We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an node multi…
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…
Optimal Hitting Sets for Combinatorial Shapes
Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan
We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2…
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…
On Quadratic Programming with a Ratio Objective
Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran +1
Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form \sum_{i \ne j} a_{ij} x_i x_j. QP captures many known combinatorial optim…
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…