Minimax Bounds for Distributed Logistic Regression

Abstract

We consider a distributed logistic regression problem where labeled data pairs $(X_i,Y_i)\in {\mathbb{R}}^d\times \{-1,1\}$ for $i=1,\dots ,n$ are distributed across multiple machines in a network and must be communicated to a centralized estimator using at most $k$ bits per labeled pair. We assume that the data $X_i$ come independently from some distribution $P_X$, and that the distribution of $Y_i$ conditioned on $X_i$ follows a logistic model with some parameter $\theta \in {\mathbb{R}}^d$. By using a Fisher information argument, we give minimax lower bounds for estimating $\theta$ under different assumptions on the tail of the distribution $P_X$. We consider both ${\ell }^2$ and logistic losses, and show that for the logistic loss our sub-Gaussian lower bound is order-optimal and cannot be improved.

References in corpus (7)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Protection Against Reconstruction and Its Applications in Private Federated Learning
• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints
• Lower Bounds for Locally Private Estimation via Communication Complexity
• Distributed Simulation and Distributed Inference

Cited by in corpus (1)

• A Minimax Lower Bound for Low-Rank Matrix-Variate Logistic Regression