Information-theoretic lower bounds for distributed statistical estimation with communication constraints
We establish minimax risk lower bounds for distributed statistical estimation given a budget $B$ of the total number of bits that may be communicated. Such lower bounds in turn reveal the minimum amount of communication required by any procedure to achieve the classical optimal rate for statistical estimation. We study two classes of protocols in which machines send messages either independently or interactively. The lower bounds are established for a variety of problems, from estimating the mean of a population to estimating parameters in linear regression or binary classification.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationGeneral ClassificationregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Over-the-Air Statistical Estimation
We study schemes and lower bounds for distributed minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss, in a framework combining statistical estimation and wireless commun…
Settling the Communication Complexity for Distributed Offline Reinforcement Learning
We study a novel setting in offline reinforcement learning (RL) where a number of distributed machines jointly cooperate to solve the problem but only one single round of communication is allowed and there is a budget co…
Multi-Armed BanditsOffline RLreinforcement-learningReinforcement Learning+1Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression
Communication compression is an essential strategy for alleviating communication overhead by reducing the volume of information exchanged between computing nodes in large-scale distributed stochastic optimization. Althou…
Stochastic OptimizationStatistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
We describe a general technique that yields the first {\em Statistical Query lower bounds} for a range of fundamental high-dimensional learning problems involving Gaussian distributions. Our main results are for the prob…
Optimal high-dimensional and nonparametric distributed testing under communication constraints
We derive minimax testing errors in a distributed framework where the data is split over multiple machines and their communication to a central machine is limited to $b$ bits. We investigate both the $d$- and infinite-di…
Vocal Bursts Intensity Prediction