On Communication Complexity of Classification Problems
This work studies distributed learning in the spirit of Yao's model of communication complexity: consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of learning theory, the players can send each other examples (as well as bits) where each example/bit costs one unit of communication. This enables a uniform treatment of infinite classes such as half-spaces in $\mathbb{R}^d$, which are ubiquitous in machine learning. We study several fundamental questions in this model. For example, we provide combinatorial characterizations of the classes that can be learned with efficient communication in the proper-case as well as in the improper-case. These findings imply unconditional separations between various learning contexts, e.g.\ realizable versus agnostic learning, proper versus improper learning, etc. The derivation of these results hinges on a type of decision problems we term "{\it realizability problems}" where the goal is deciding whether a distributed input sample is consistent with an hypothesis from a pre-specified class. From a technical perspective, the protocols we use are based on ideas from machine learning theory and the impossibility results are based on ideas from communication complexity theory.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningClassificationGeneral ClassificationLearning TheorySimilar Papers 제목 키워드 기반
AI Uncertainty Based on Rademacher Complexity and Shannon Entropy
In this paper from communication channel coding perspective we are able to present both a theoretical and practical discussion of AI's uncertainty, capacity and evolution for pattern classification based on the classical…
ClassificationGeneral ClassificationDistributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approa…
Distributed OptimizationSolving a Class of Non-Convex Minimax Optimization in Federated Learning
The minimax problems arise throughout machine learning applications, ranging from adversarial training and policy evaluation in reinforcement learning to AUROC maximization. To address the large-scale data challenges acr…
Federated LearningA Theory on AI Uncertainty Based on Rademacher Complexity and Shannon Entropy
In this paper, we present a theoretical discussion on AI deep learning neural network uncertainty investigation based on the classical Rademacher complexity and Shannon entropy. First it is shown that the classical Radem…
General ClassificationAverage-Case Communication Complexity of Statistical Problems
We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-comput…