Minimal Communication-Cost Statistical Learning

• URL: http://arxiv.org/abs/2406.08193v1
• Date: Wed, 12 Jun 2024 13:22:26 GMT
• Title: Minimal Communication-Cost Statistical Learning
• Authors: Milad Sefidgaran, Abdellatif Zaidi, Piotr Krasnowski,
• Abstract summary: We propose a joint training and source coding scheme with provable in-expectation guarantees. We show that by imposing a constraint on a suitable Kullback-Leibler divergence between the conditional distribution induced by a compressed learning model $widehatW$ given $W$ and the prior, one guarantees simultaneously small average empirical risk. We also consider a one-shot scenario in which the guarantees on the empirical risk and generalization error are obtained for every encoder's output message.
• Score: 14.453654853392619
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A client device which has access to $n$ training data samples needs to obtain a statistical hypothesis or model $W$ and then to send it to a remote server. The client and the server devices share some common randomness sequence as well as a prior on the hypothesis space. In this problem a suitable hypothesis or model $W$ should meet two distinct design criteria simultaneously: (i) small (population) risk during the inference phase and (ii) small 'complexity' for it to be conveyed to the server with minimum communication cost. In this paper, we propose a joint training and source coding scheme with provable in-expectation guarantees, where the expectation is over the encoder's output message. Specifically, we show that by imposing a constraint on a suitable Kullback-Leibler divergence between the conditional distribution induced by a compressed learning model $\widehat{W}$ given $W$ and the prior, one guarantees simultaneously small average empirical risk (aka training loss), small average generalization error and small average communication cost. We also consider a one-shot scenario in which the guarantees on the empirical risk and generalization error are obtained for every encoder's output message.

Related papers

• Robust Model Evaluation over Large-scale Federated Networks [8.700087812420687]
  We address the challenge of certifying the performance of a machine learning model on an unseen target network. We derive theoretical guarantees for the model's empirical average loss and provide uniform bounds on the risk CDF. Our bounds are computable in time with a number of queries to the $K$ clients, preserving client privacy by querying only the model's loss on private data.
  arXiv  Detail & Related papers  (2024-10-26T18:45:15Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  We characterize the fundamental communication cost required to obtain the best accuracy under $varepsilon$ central DP. Our results show that $tildeOleft( min(n2varepsilon2, d) right)$ bits per client are both sufficient and necessary. This provides a significant improvement relative to state-of-the-art SecAgg distributed DP schemes.
  arXiv  Detail & Related papers  (2022-03-07T22:56:09Z)
• Settling the Communication Complexity for Distributed Offline Reinforcement Learning [10.315054389907031]
  We study a novel setting in offline reinforcement learning (RL) where a number of distributed machines jointly cooperate to solve the problem. There is a budget constraint on the total number of information (in terms of bits) that each machine can send out. For value function prediction in contextual bandits, and both episodic and non-episodic MDPs, we establish information-theoretic lower bounds on the minimax risk.
  arXiv  Detail & Related papers  (2022-02-10T06:27:07Z)
• Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control [67.52000805944924]
  Learn then Test (LTT) is a framework for calibrating machine learning models. Our main insight is to reframe the risk-control problem as multiple hypothesis testing. We use our framework to provide new calibration methods for several core machine learning tasks with detailed worked examples in computer vision.
  arXiv  Detail & Related papers  (2021-10-03T17:42:03Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• Weighted Empirical Risk Minimization: Sample Selection Bias Correction based on Importance Sampling [2.599882743586164]
  We consider statistical learning problems when the distribution $P'$ of the training observations $Z'_i$ differs from the distribution $P'$ involved in the risk one seeks to minimize. We show that, in various situations frequently encountered in practice, it takes a simple form and can be directly estimated from the $Phi(z)$. We then prove that the capacity generalization of the approach aforementioned is preserved when plugging the resulting estimates of the $Phi(Z'_i)$'s into the weighted empirical risk.
  arXiv  Detail & Related papers  (2020-02-12T18:42:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.