Computational Implications of Reducing Data to Sufficient Statistics
Given a large dataset and an estimation task, it is common to pre-process the data by reducing them to a set of sufficient statistics. This step is often regarded as straightforward and advantageous (in that it simplifies statistical analysis). I show that -on the contrary- reducing data to sufficient statistics can change a computationally tractable estimation problem into an intractable one. I discuss connections with recent work in theoretical computer science, and implications for some techniques to estimate graphical models.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Linear-Time User-Level DP-SCO via Robust Statistics
User-level differentially private stochastic convex optimization (DP-SCO) has garnered significant attention due to the paramount importance of safeguarding user privacy in modern large-scale machine learning application…
Computational EfficiencyPrivacy PreservingComputationally sufficient statistics for Ising models
Learning Gibbs distributions using only sufficient statistics has long been recognized as a computationally hard problem. On the other hand, computationally efficient algorithms for learning Gibbs distributions rely on a…
Trimming the Independent Fat: Sufficient Statistics, Mutual Information, and Predictability from Effective Channel States
One of the most fundamental questions one can ask about a pair of random variables X and Y is the value of their mutual information. Unfortunately, this task is often stymied by the extremely large dimension of the varia…
Motor Learning Mechanism on the Neuron Scale
Based on existing data, we wish to put forward a biological model of motor system on the neuron scale. Then we indicate its implications in statistics and learning. Specifically, neuron firing frequency and synaptic stre…
Reducing Neural Architecture Search Spaces with Training-Free Statistics and Computational Graph Clustering
The computational demands of neural architecture search (NAS) algorithms are usually directly proportional to the size of their target search spaces. Thus, limiting the search to high-quality subsets can greatly reduce t…
ClusteringGraph ClusteringNeural Architecture Search