On Communication Cost of Distributed Statistical Estimation and Dimensionality
Authors: Ankit Garg, Tengyu Ma, Huy Nguyen
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that in this setting, the communication cost scales linearly in the number of dimensions i.e. one needs to deal with different dimensions individually. Applying this result to previous lower bounds for one dimension in the interactive setting [1] and to our improved bounds for the simultaneous setting, we prove new lower bounds of (md/ log(m)) and (md) for the bits of communication needed to achieve the minimax squared loss, in the interactive and simultaneous settings respectively. To complement, we also demonstrate an interactive protocol achieving the minimax squared loss with O(md) bits of communication, which improves upon the simple simultaneous protocol by a logarithmic factor. Given the strong lower bounds in the general setting, we initiate the study of the distributed parameter estimation problems with structured parameters. |
| Researcher Affiliation | Academia | Ankit Garg Department of Computer Science, Princeton University garg@cs.princeton.edu Tengyu Ma Department of Computer Science, Princeton University tengyu@cs.princeton.edu Huy L. Nguy ˆen Simons Institute, UC Berkeley hlnguyen@cs.princeton.edu |
| Pseudocode | Yes | Protocol 1: Protocol for Ps; Protocol 2: i |
| Open Source Code | No | No mention of open-source code release or repository links for the methodology described. |
| Open Datasets | No | The paper deals with theoretical analysis of statistical estimation on sampled data from unknown Gaussian distributions, not empirical studies on publicly available datasets. Therefore, it does not specify any public dataset access information. |
| Dataset Splits | No | The paper is theoretical and focuses on proving bounds and analyzing protocols; it does not involve empirical experiments with training, validation, or test data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and analyzes algorithms and protocols; it does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and presents proofs and protocol analyses, not empirical experimental setups with hyperparameters or training configurations. |