23 citations · 94 across the 24 of their papers we have counts for
26 papers
Linear Regression using Heterogeneous Data Batches
Ayush Jain, Rajat Sen, Weihao Kong +2
In many learning applications, data are collected from multiple sources, each providing a \emph{batch} of samples that by itself is insufficient to learn its input-output relations…
Robust estimation algorithms don't need to know the corruption level
Ayush Jain, Alon Orlitsky, Vaishakh Ravindrakumar
Real data are rarely pure. Hence the past half-century has seen great interest in robust estimation algorithms that perform well even when part of the data is corrupt. However, the…
TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm
Yi Hao, Ayush Jain, Alon Orlitsky +1
Approximating distributions from their samples is a canonical statistical-learning problem. One of its most powerful and successful modalities approximates every distribution to an…
Linear-Sample Learning of Low-Rank Distributions
Ayush Jain, Alon Orlitsky
Many latent-variable applications, including community detection, collaborative filtering, genomic analysis, and NLP, model data as generated by low-rank matrices. Yet despite cons…
Profile Entropy: A Fundamental Measure for the Learnability and Compressibility of Discrete Distributions
Yi Hao, Alon Orlitsky
The profile of a sample is the multiset of its symbol frequencies. We show that for samples of discrete distributions, profile entropy is a fundamental measure unifying the concept…
A General Method for Robust Learning from Batches
Ayush Jain, Alon Orlitsky
In many applications, data is collected in batches, some of which are corrupt or even adversarial. Recent work derived optimal robust algorithms for estimating discrete distributio…
SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm
Yi Hao, Ayush Jain, Alon Orlitsky +1
Sample- and computationally-efficient distribution estimation is a fundamental tenet in statistics and machine learning. We present SURF, an algorithm for approximating distributio…
Optimal Robust Learning of Discrete Distributions from Batches
Ayush Jain, Alon Orlitsky
Many applications, including natural language processing, sensor networks, collaborative filtering, and federated learning, call for estimating discrete distributions from data col…
Unified Sample-Optimal Property Estimation in Near-Linear Time
Yi Hao, Alon Orlitsky
We consider the fundamental learning problem of estimating properties of distributions over large domains. Using a novel piecewise-polynomial approximation technique, we derive the…
The Broad Optimality of Profile Maximum Likelihood
Yi Hao, Alon Orlitsky
We study three fundamental statistical-learning problems: distribution estimation, property estimation, and property testing. We establish the profile maximum likelihood (PML) esti…
Data Amplification: A Unified and Competitive Approach to Property Estimation
Yi Hao, Alon Orlitsky, Ananda T. Suresh +1
Estimating properties of discrete distributions is a fundamental problem in statistical learning. We design the first unified, linear-time, competitive, property estimator that for…
Data Amplification: Instance-Optimal Property Estimation
Yi Hao, Alon Orlitsky
The best-known and most commonly used distribution-property estimation technique uses a plug-in estimator, with empirical frequency replacing the underlying distribution. We presen…
On Learning Markov Chains
Yi Hao, Alon Orlitsky, Venkatadheeraj Pichapati
The problem of estimating an unknown discrete distribution from its samples is a fundamental tenet of statistical learning. Over the past decade, it attracted significant research…
Maximum Selection and Ranking under Noisy Comparisons
Moein Falahatgar, Alon Orlitsky, Venkatadheeraj Pichapati +1
We consider -PAC maximum-selection and ranking for general probabilistic models whose comparisons probabilities satisfy strong stochastic transitivity and stochastic triangl…
A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation
Jayadev Acharya, Hirakendu Das, Alon Orlitsky +1
The advent of data science has spurred interest in estimating properties of distributions over large alphabets. Fundamental symmetric properties such as support size, support cover…
Maximum Selection and Sorting with Adversarial Comparators and an Application to Density Estimation
Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour +2
We study maximum selection and sorting of numbers using pairwise comparators that output the larger of their two inputs if the inputs are more than a given threshold apart, and…
Estimating the number of unseen species: A bird in the hand is worth in the bush
Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu
Estimating the number of unseen species is an important problem in many scientific endeavors. Its most popular formulation, introduced by Fisher, uses samples to predict the nu…
Universal Compression of Power-Law Distributions
Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky +2
English words and the outputs of many other natural processes are well-known to follow a Zipf distribution. Yet this thoroughly-established property has never been shown to help co…
Faster Algorithms for Testing under Conditional Sampling
Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky +2
There has been considerable recent interest in distribution-tests whose run-time and sample requirements are sublinear in the domain-size . We study two of the most important te…
Competitive Distribution Estimation
Alon Orlitsky, Ananda Theertha Suresh
Estimating an unknown distribution from its samples is a fundamental problem in statistics. The common, min-max, formulation of this goal considers the performance of the best esti…
Universal compression of Gaussian sources with unknown parameters
A. Orlitsky, N. Santhanam
For a collection of distributions over a countable support set, the worst case universal compression formulation by Shtarkov attempts to assign a universal distribution over the su…
Estimating Renyi Entropy of Discrete Distributions
Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh +1
It was recently shown that estimating the Shannon entropy of a discrete -symbol distribution requires samples, a number that grows near-line…
Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky +1
The Poisson-sampling technique eliminates dependencies among symbol appearances in a random sequence. It has been used to simplify the analysis and strengthen the performance guara…
String Reconstruction from Substring Compositions
Jayadev Acharya, Hirakendu Das, Olgica Milenkovic +2
Motivated by mass-spectrometry protein sequencing, we consider a simply-stated problem of reconstructing a string from the multiset of its substring compositions. We show that all…