Non-Asymptotic Performance of Social Machine Learning Under Limited Data

Aug 4, 2026

Upload by Ezra

This paper studies the probability of error in the social machine learning (SML) framework, which uses an independent training phase followed by cooperative decision-making over a graph. The classification setting considers limited observations during the decision stage, requiring a non-asymptotic performance analysis. A condition for consistent training is established, and an upper bound on the probability of classification error is derived. The results reveal how data statistical properties and the graph combination policy shape performance, and they show exponential decay of error with the number of unlabeled samples.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages36

Reading Time1 h 31 min

AccessFree to download

Introduction

SML framework and motivation

Two-phase learning: training and prediction

Performance guarantees and problem setting

arXiv :2306 .09397v2 [ cs .LG] 9 Jul 2024 Non-Asymptotic Performance of Social Machine Learning Under Limited Data ⋆ Ping Hua,∗, Virginia Bordignona , Mert Kayaalpa , Ali H. Sayeda a School of Engineering, EPFL, CH-1015, Lausanne, Switzerland Abstract This paper studies the probability of error associated with the social machine learning framework, which involves an independent training phase followed by a cooperative decision-making phase over a graph. This framework addresses the problem of classifying a stream of unlabeled data in a distributed manner. In this work, we examine the classification task with limited observations during the decision-making phase, which requires a non-asymptotic performance analysis. We establish a condition for consistent training and derive an upper bound on the probability of error for classification. The results clarify the dependence on the statistical properties of the data and the combination policy used over the graph. They also establish the exponential decay of the probability of error with respect to the number of unlabeled samples. Keywords: Social machine learning, probability of error, classification, non-asymptotic analysis 1. Introduction Social learning is a useful paradigm for addressing decision-making tasks involving a group of agents. Practical applications arise in various scenarios, such as detection and object recognition using autonomous robots, as well as statistical inference and learning across multiple processors [2] . In this paper, we focus on the social machine learning (SML) framework introduced in [3], which is a data-driven cooperative decisionmaking paradigm. The main motivation for the introduction of this framework is to address a critical limitation of traditional social learning solutions [4–11] . These solutions allow a group of agents to interact over a graph to arrive at consensus decisions about a hypothesis of interest. However, a limiting assumption in all these studies is the requirement that the likelihood models for data generation are known beforehand. The SML strategy removes this requirement, thus opening up the door for solving classification tasks in a distributed manner with performance guarantees by relying solely on a data-driven implementation. ⋆ A preliminary short conference version of this work was previously published in [1] . ∗ Corresponding author Email addresses: [ping.hu@epfl.ch](ping.hu@epfl.ch) (Ping Hu), [virginia.bordignon@epfl.ch](virginia.bordignon@epfl.ch) (Virginia Bordignon), [mert.kayaalp@epfl.ch](mert.kayaalp@epfl.ch) (Mert Kayaalp), [ali.sayed@epfl.ch](ali.sayed@epfl.ch) (Ali H. Sayed) Preprint submitted to Signal Processing July 10, 2024 Prediction phase Training phase h6,i 1 h1,i h2,i Each agent k learns an applorog-xliimationkelihookra(htio) fockr(thh)e Each agent k removes the bias frdoe-mbiked(h)loagn-ldikgeneliheoraotedsrtahtieo estimates ck (h) . e h4,i e Figure 1: SML architecture. (Left panel) The independent training process where each agent k finds an optimal model fk based on its training set and constructs a classifier k involving a debiasing operation. (Right panel) The cooperative classification process where each agent k receives a sequence of streaming observations hk,i and implements a social learning protocol to enhance the prediction performance. The neighboring set Nk of agent k is marked by the area highlighted in gray. The SML strategy involves two learning phases, as depicted in Fig. 1. In the training phase on the left, each agent trains a classifier independently using a finite set of labeled samples within a supervised learning framework (such as logistic regression, neural networks, or other convenient frameworks) . The purpose of this phase is to learn some discriminative information that allows agents to distinguish different hypotheses. The output of each trained classifier is used to form a local decision statistic for inference in

FAQs

What are the two learning phases in the social machine learning (SML) framework?

SML uses an independent training phase followed by a cooperative prediction phase over a graph. During training, agents learn classifiers from labeled data; during prediction, they use streaming unlabeled observations and a social learning protocol to infer the true state.

Why is a non-asymptotic analysis needed in this work?

The paper studies classification under limited observations during the decision-making phase, which is common in practice. This setting requires performance guarantees without relying on asymptotic (infinite-sample) behavior.

What theoretical results does the paper provide about classification error?

It establishes a condition for consistent training and derives an upper bound on the probability of error for the classification task. The analysis also shows exponential decay of error probability as the number of unlabeled samples increases.

Aug 4, 2026

Upload by Ezra