11institutetext: Institute of Data Science, National Cheng Kung University
Corporate R$\&$D, Advanced Semiconductor Engineering Group
11email<EMAIL_ADDRESS>
# OCR is All you need: Importing Multi-Modality into Image-based Defect
Detection System††thanks: This study was supported in part by ASE corporation;
partly by the National Science and Technology Council (NSTC), Taiwan, under
grants MOST 112-2221-E-006 -157 -MY3 and 111-2221-E-006 -210; partly by the
Higher Education Sprout Project of Ministry of Education (MOE) to the
Headquarters of University Advancement at National Cheng Kung University
(NCKU); partly by High Education Humanities and Social Science Subjects
Benchmark Project, Minstry of Education, Taiwan

Chih-Chung Hsu 1*1* Chia-Ming Lee 11 Chun-Hung Sun 22 Kuang-Ming Wu 221122**

###### Abstract

Automatic optical inspection (AOI) plays a pivotal role in the manufacturing
process, predominantly leveraging high-resolution imaging instruments for
scanning purposes. It detects anomalies by analyzing image textures or
patterns, making it an essential tool in industrial manufacturing and quality
control. Despite its importance, the deployment of models for AOI often faces
challenges. These include limited sample sizes, which hinder effective feature
learning, variations among source domains, and sensitivities to changes in
lighting and camera positions during imaging. These factors collectively
compromise the accuracy of model predictions. Traditional AOI often fails to
capitalize on the rich mechanism-parameter information from machines or inside
images, including statistical parameters, which typically benefit AOI
classification. To address this, we introduce an external modality-guided data
mining framework, primarily rooted in optical character recognition (OCR), to
extract statistical features from images as a second modality to enhance
performance, termed OANet (Ocr-Aoi-Net). A key aspect of our approach is the
alignment of external modality features, extracted using a single modality-
aware model, with image features encoded by a convolutional neural network.
This synergy enables a more refined fusion of semantic representations from
different modalities. We further introduce feature refinement and a gating
function in our OANet to optimize the combination of these features, enhancing
inference and decision-making capabilities. Experimental outcomes show that
our methodology considerably boosts the recall rate of the defect detection
model and maintains high robustness even in challenging scenarios.

###### Keywords:

Multi-Modality Automated Optical Inspection Feature Alignment Defect Detection
Optical Character Recognition

##  1 Introduction

In the realm of industrial manufacturing, defect detection is paramount,
serving a dual purpose: enhancing product quality and efficiency and
indirectly curbing production costs by reducing the prevalence of both false
negatives and positives. At its core, defect detection leverages a myriad of
analytical instruments to discern features rooted in the physical properties
of diverse products. Once these features are harvested, models trained on this
data are then deployed for defect detection or classification.

Among the plethora of defect detection strategies, Automatic Optical
Inspection (AOI) emerges as a predominant choice, especially in the industrial
domain. This preference is not just due to its efficacy, but also because it
incurs lower instrumentation costs compared to its analytical counterparts.
AOI harnesses the power of high-resolution imaging tools to inspect products
throughout the manufacturing phase. It taps into computer vision methodologies
to spot defects, often focusing on attributes like shape, size, color, and
product positioning. By juxtaposing the visual attributes of standard samples
with defective ones, AOI can efficiently pinpoint anomalies. The convolutional
neural network, in particular, has gained recognition for its prowess in
extracting image features pivotal for defect inspection. However, the AOI
methodology isn’t without its limitations. For instance, burgeoning internal
variability or an expanded dataset category spectrum can induce significant
image feature fluctuations, complicating the defect detection process.
Additionally, factors like unpredictable lighting conditions and even
minuscule camera shifts can undercut the reliability of defect detection
models. Even more challenges like sparse training data and sample imbalances
can yield performance that falls short of expectations.

The dawn of multimodal learning has ushered in a new era where features from
disparate modalities can be synergized, amplifying model performance. This
integration has catalyzed advancements in domains like computer vision and
natural language processing. However, training multimodal models often demands
an extensive repository of high-quality, human-annotated image-text pairings,
making the deployment of such models in AOI and defect detection less
straightforward. Prevailing research has primarily zeroed in on fusing
features from various modalities to sculpt models adept at multitasking across
multiple modalities. However, the multimodal learning framework strictly
requires multi-modality data as the input, which often becomes difficult for
the AOI field since the machines usually do not allow the intrinsic data to be
accessible. We judiciously challenge this issue. Since some statistical
information could be printed in the AOI images in most cases, it could benefit
the performance and robustness once the statistical information inside images
is available.

In response to the challenges outlined above, we harness Optical Character
Recognition (OCR) to morph external modality data within images into formats
amenable to training single-modality-aware multimodal models. A focal point of
our methodology is feature alignment prior to fusion, ensuring a harmonious
amalgamation of features derived from different modalities. We also
incorporate a gating function and feature refinement to maximize the potential
of single modality features, especially crucial when another modal feature is
compromised due to OCR malfunctions or data transmission distortions. Our
experimental evaluations, utilizing datasets from ASE Corporation, attest to
the efficacy of our approach.

  * •

Single-Modality-Aware Multimodal Learning in AOI: We challenge the
conventional multimodal learning paradigm which often necessitates data from
multiple modalities as input. Recognizing that machines in the AOI domain
often restrict access to intrinsic data, we propose a novel approach that
exploits statistical information typically embedded within AOI images. This
insight allows us to enhance the performance and robustness of defect
detection without relying on traditional multi-modality inputs.

  * •

OCR-Driven Feature Extraction: We introduce a pioneering method that employs
Optical Character Recognition (OCR) to extract external modality data from
images. This approach effectively converts such data into a format suitable
for training single-modality-aware multimodal models, addressing the challenge
of inaccessible intrinsic data in the AOI domain.

  * •

Enhanced Feature Fusion Mechanism: We present an advanced feature alignment
process that is executed before fusion, ensuring optimal integration of
features from distinct modalities. Accompanying this, we design a gating
function and a feature refinement strategy. These are particularly critical
when one modal feature might be compromised, either due to OCR errors or
disruptions in data transmission. The effectiveness of our methods is
empirically validated on the ASE Corporation dataset.

##  2 Related Work

###  2.1 Advanced Defect Detection

Defect detection has witnessed remarkable enhancements with the integration of
deep and machine learning algorithms. These algorithms stand out for their
proficiency in intricate feature extraction, managing vast data, pinpointing
anomalies, and enabling real-time detection, thereby transcending the
constraints of conventional methodologies. The realm of computer vision-based
defect detection has particularly burgeoned, owing to the evolution of models
adept at pixel-level classification.

Akcay et al. [13] offer a suite of ready-to-deploy image-based anomaly and
defect detection algorithms. Tabernik et al. [11] employ a semantic
segmentation network for surface-defect detection, paving the way for fine-
grained defect identification. Lopes et al. [12] amalgamate the AutoML
approach with various CNN-based models, aiming to bolster the robustness of
the detection system.

###  2.2 Multi-Modality Learning

While traditional deep learning typically relies on single-modality data,
recent advancements, such as CLIP [7], have pioneered the integration of
multiple modalities. Despite significant progress, challenges persist,
including variations in dimensionality and semantic content across modalities,
high costs of human annotation for paired data creation, and substantial
computational requirements.

Pioneering works, such as those by Li et al. [6], have been instrumental in
addressing these challenges. They have successfully integrated multi-modal
contrastive learning with fusion learning, thus resolving semantic
inconsistencies across different modalities. Their other contributions,
including [8, 9, 10], highlight the effectiveness of pre-training in reducing
computational demands during the fine-tuning of multi-modal models.

Our work builds upon these advancements, yet diverges by focusing on
generating new modalities from a single source. We explore the uncharted
territory of harnessing statistical data from AOI images, a novel approach
that promises to significantly advance the field of defect detection.

###  2.3 Optical Character Recognition

OCR technology, foundational in image processing and pattern recognition, is
designed to convert printed or handwritten text into machine-readable data.
While traditional OCR systems have their advantages, they face significant
challenges, including the need for high-quality images, dependence on specific
fonts and layouts, difficulties with complex backgrounds, and limitations in
processing multilingual texts.

Advancements in deep learning have revolutionized OCR by dividing the process
into distinct stages of text detection and recognition. Segmentation-based
methods, such as those detailed in [1, 2, 3], have been recognized for their
precision in detecting text shape and position, particularly in complex
layouts. Furthermore, the CNN-LSTM architecture [4, 5] has been acclaimed for
its effective balance between speed and accuracy, enhancing contextual
understanding of the text.

In our research, we utilize OCR not only for its traditional role in text
extraction but as a means to extract features from a single modality, laying
the groundwork for our OANet. This innovative approach is designed to
circumvent the typical challenges associated with OCR, particularly when
dealing with compromised modal data.

##  3 Methodology

###  3.1 Overview

This section delineates our novel method, designed to discern defects or
anomalies within 2D images. A salient aspect of our approach lies in
harnessing Optical Character Recognition (OCR) techniques to mine supplemental
numerical or textual data from the images. Depending on the modality of this
auxiliary information, we deploy appropriate sub-models for training. Post
feature alignment, a feature refinement is executed on the attributes from the
image encoder. This step amplifies the diversity and adaptability of the
feature landscape. Upon decoding, predictions pertaining to the original
images emerge. The conclusive inference draws upon the outputs of both the
sub-models and the primary image model. The model’s architecture is
graphically depicted in Figure 1.

A unique strength of our method is its ability to assimilate information
spanning diverse single modalities. The semantic richness harvested from these
individual modalities augments the encoded image features, enhancing their
robustness. At the inference stage, our model exhibits a dynamic adaptability,
recalibrating the weights of models aligned with different modalities based on
the saliency of each modality within the input. Contrasting with traditional
multi-modal training paradigms, our approach offers a more harmonious and
effective fusion of features from distinct single modalities. This synergy
culminates in our method’s elevated defect detection prowess.

Figure 1: The overall architecture of the proposed framework. It aims to
explore external modality features to comprehensively support learning better
semantic representations and decision-making. Several single modality features
are extracted and fed into corresponding models, followed by feature alignment
and refinement to enrich the feature space. Finally, we implement a gate
function to aggregate all features and adaptively adjust the weights of
different models or features, resulting in more robust and stable prediction
results.

###  3.2 External Modality-guided Data Mining

In the context of defect detection, image-based models are crucial.
Recognizing the potential inaccuracies in OCR, our multimodal approach is
designed to account for this. Specifically, we employ mask learning during
training to simulate unstable OCR conditions, thereby enhancing the robustness
of our model against OCR inaccuracies. External information, such as camera
parameters and textual inscriptions, despite variability in accuracy, is
integral to our comprehensive defect detection strategy. This information can
contain valuable insights for defect detection, often more so than the images
themselves. To leverage this, we propose an external modality-guided data
mining framework, integrating additional information to assist image-based
models in achieving higher detection accuracy.

####  3.2.1 Modality Feature Retrieval

The primary challenge lies in obtaining additional information from the
original images, which largely depends on the data format. In our dataset and
experiments, OCR is prioritized due to its simplicity, efficiency, and the
ability to process information contained within the raw images without
accessing other data sources.

####  3.2.2 External Modality Feature Intra-Bagging

In this phase, our aim is to train various models based on the obtained
feature modalities and the objectives of the task. We then use the features
from each single modality for further feature alignment. The outputs of
individual sub-models and the results of intra-bagging are taken into
consideration during the decision-making and inference stages. In typical
defect detection tasks, numerical features are often readily available.
Performing intra-bagging by building models with similar capabilities can
enhance overall performance. Gradient boosting-based decision trees, such as
LightGBM [14], XGBoost [15], and CatBoost [16], are known for their superior
performance in classification or regression tasks with numerical tabular data.
These trees are highly interpretable, facilitating the acquisition of critical
information, with criteria closer to the root of the tree playing a
significant role in decision-making and inference. When decision tree models
do not exhibit stable performance, MLP is considered as an alternative.
Depending on the task and data types, other models like LSTM [17] or
Transformer [18] may also be employed.

Figure 2: The concepts of feature alignment, refinement, and gate function are
illustrated in the following figure. External single modality data is input
into the trainable encoder branch to extract features, while image features
are processed in another branch. After aligning the features extracted by
different modality models, they are concatenated with the output from the
previous stage. Feature refinement enhances features that encompass a richer
representation. Finally, the gate function is conducted to comprehensively
boost overall model performance against defect detection task.

###  3.3 Multi-Modal Feature Fusion

We discuss the integration and enhancement of different modalities.
Integrating features from diverse modalities significantly improves zero-shot
reasoning capabilities and enables pretrained models to maintain strong
performance in downstream tasks. However, modality integration is a crucial
issue. Several studies [6, 8, 9] have indicated that performing feature
alignment before modality integration can effectively address issues related
to disparate feature distributions. By aligning and then integrating features
from different modalities, we can further refine the diversity of the feature
set.

####  3.3.1 Image-based Encoder

Convolutional Neural Networks (CNNs) are the mainstream image encoders today,
with popular examples including ResNet [21], VGG [23], and EfficientNet [24].
The choice of an appropriate encoder is contingent upon the nature of the
input data and the complexity of the task at hand. Notably, in scenarios
dealing with non-defect image data and images containing defects, the patterns
may not significantly differ. Furthermore, in cases of low-resolution images,
selecting an encoder with excessively many parameters might result in
overfitting and subsequent performance degradation on the test set.

####  3.3.2 Feature Alignment

Features from two different modalities are encoded using corresponding feature
encoders, yielding two sets of embedding vectors, as depicted in Figure 2.
Aligning these vectors involves minimizing the distance between the two sets,
thereby harmonizing their semantic representations within the feature space.
The image subnetwork, for instance, utilizes several complex convolution
layers due to the intricate nature of image features, while the other network
adopts a simpler architecture. A distance metric function, typically based on
similarity or probability-based distance, is employed for alignment; in this
work, cosine similarity is used.

####  3.3.3 Feature Refinement

Upon aligning features from multiple sub-models trained on different
modalities, we enhance the model’s performance by integrating information
across these modalities. This involves performing PCA dimension reduction on a
set of aligned vectors or embeddings encoded through image encoders, ensuring
consistent lengths and concatenating them into a single vector. This process
is iteratively performed multiple times to achieve feature enhancement, as
illustrated in Figure 2.

###  3.4 Inference and Decision Making Procedure

Enhanced image features prove effective for defect detection in untested
images. Nonetheless, outputs from a single modality and predictions from
external modality feature intra-bagging also contribute significantly to
defect detection. In certain cases, additional data may offer more crucial
insights than images, but risk being underutilized or lost during training.
For example, in complex scenarios requiring neural network inference for
defect detection, the decision boundaries of neural networks are relatively
smooth, potentially leading to false negatives. However, accessing
supplementary information, such as abnormal temperatures, could allow for
defect inference independent of the model. To address this, a gate function is
introduced during the inference stage, adaptively adjusting the model’s
weights based on the obtained information, thereby ensuring high-quality
defect detection.

####  3.4.1 Gate Function

The distribution of test data, which can often be unknown during the inference
stage, may lead to domain shifts and poor detection performance. To mitigate
this, a gate function is implemented to dynamically adjust the weights between
all trained models and their outputs during inference. This function can
selectively deactivate the outputs of certain models if their feature
information is markedly inferior to others, ensuring balanced inference
capabilities among the models. This balance is quantified by calculating the
KL-divergence between the data distributions, encompassing both image data and
external single or multi-modal data. Ultimately, a model ensemble is executed
to bolster the overall system’s robustness and achieve effective defect
detection.

##  4 Experiment

Our dataset is provided by ASE Corporation, encompassing a total of 971
images, as shown in Figure 3. These images are captured by the AOI system.
Among these images, there are 587 instances without defects, while the
remaining 384 images contain some defects in internal parameters or exhibit
defects in the objects. The lower left corner of the provided image covers the
area containing the target object. The remaining area of the image contains a
wealth of parameter information about the target object.

Figure 3: Depicted in the left image is provided by ASE corporation. From
these images, we can extract text or numerical data to gain another feature
into their content. In the middle image, a grid mask is employed to introduce
perturbations to areas of the image containing the target object, simulating a
scenario of image corruption. The right image illustrates the perturbations to
the text portion to simulate a situation where OCR may fail.

###  4.1 Implementation Details

We divided the dataset into training and testing sets using a 7:3 ratio.
During the training phase, we obtained external modal information using CnOCR
[27], an efficient OCR package. We used these external modality features to
train 4 defect detection models: LightGBM [14], Gradient Boosting Machines
[20], CatBoost [16], and RandomForest [19]. To simplify the experimental
evaluation, all hyperparameters were kept at their default values, and we also
used 5-fold validation to comprehensive evaluate model’s performance.

For the image-based encoder, we employ AlexNet [22], VGG16 [23], and ResNet18
[21]. The loss function is cross-entropy, the optimizer is SGD with a learning
rate of 0.01 and weight decay of 0.0005. The models is trained for a total of
30 epochs. Our experiments were conducted using a single NVIDIA RTX TITAN.

###  4.2 Performance Evaluation

To evaluate the effectiveness of our proposed method, we conducted ablation
experiments using three different image encoders, while varying the inclusion
of feature alignment, refinement, and gate functions. To ensure experimental
consistency and mitigate the impact of randomness, we repeated the same
experiments five times and computed the average accuracy, recall, and F1-score
of the prediction results as performance indicators.

The experimental results demonstrate that our proposed method significantly
enhances the performance of CNN models, especially in terms of the crucial
metric, recall, showing a substantial improvement, as illustrated in Table 1.

| Image
---
Encoder
| Feature
---
Alignment
| Feature
---
Refinement
| Gate
---
Function
Accuracy$\uparrow$ | Recall$\uparrow$ | F1-score$\uparrow$
Alexnet | $\times$ | $\times$ | $\times$ | 82.87 | 65.04 | 71.18
Alexnet | $\checkmark$ | $\times$ | $\times$ | 87.32 | 82.11 | 84.51
Alexnet | $\checkmark$ | $\checkmark$ | $\times$ | 90.06 | 84.55 | 87.77
Alexnet | $\checkmark$ | $\checkmark$ | $\checkmark$ | 89.38 | 85.36 | 87.13
VGG16 | $\times$ | $\times$ | $\times$ | 81.5 | 76.42 | 77.68
VGG16 | $\checkmark$ | $\times$ | $\times$ | 86.64 | 78.04 | 83.11
VGG16 | $\checkmark$ | $\checkmark$ | $\times$ | 83.56 | 87.8 | 81.81
VGG16 | $\checkmark$ | $\checkmark$ | $\checkmark$ | 87.67 | 91.05 | 86.15
Resnet18 | $\times$ | $\times$ | $\times$ | 83.56 | 78.86 | 80.16
Resnet18 | $\checkmark$ | $\times$ | $\checkmark$ | 88.01 | 83.73 | 85.47
Resnet18 | $\checkmark$ | $\checkmark$ | $\times$ | 85.95 | 85.36 | 83.66
Resnet18 | $\checkmark$ | $\checkmark$ | $\checkmark$ | 86.3 | 86.17 | 84.12

Table 1: Performance Comparison of proposed method. Our method significantly
enhances recall, which is crucial for defect detection. Feature alignment
proves to be highly effective in improving accuracy, while the implementation
of feature refinement along with the addition of a gate function significantly
enhances recall. In the table, we marked the best and the second-best metric
scores with red and blue colors, respectively.

###  4.3 Robustness Analysis

Due to our proposed method being based on varying single modality feature, it
exhibits prominent performance, even in the presence of anomalies in a certain
modality’s data. For instance, data may become corrupted due to the failure of
OCR detection or abnormalities in the data transmission process.

We made some perturbation on data by randomly replacing 60% of the data
detected by OCR with missing values and simulating data corruption in the
acquired images using a Grid mask. Ablation experiments were performed in this
context, as shown in Table 2. The results highlight the robustness of our
method, as it remains resilient to disruptions caused by data anomalies.

Method |  | Random Missing
---
| Grid Mask
---
Accuracy $\uparrow$ | Recall $\uparrow$ | F1-Score $\uparrow$
VGG16 | $\times$ | $\times$ | 81.50 | 76.42 | 77.68
VGG16 | $\times$ | $\checkmark$ | 75.68 | 49.59 | 63.21
Our+VGG16 | $\times$ | $\times$ | 87.67 | 91.05 | 86.15
Our+VGG16 | $\checkmark$ | $\times$ | 84.93 | 87.8 | 83.07
Our+VGG16 | $\times$ | $\checkmark$ | 83.56 | 86.99 | 81.67
Our+VGG16 | $\checkmark$ | $\checkmark$ | 82.87 | 84.55 | 80.62

Table 2: Regarding the analysis of simulating data corruption, the experiments
demonstrate that our proposed method maintains a strong performance even under
extreme conditions. This demonstrates its robustness and ability to deliver
consistent results in challenging scenarios.

##  5 Conclusion

In this work, we have presented OANet (OCR-AOI-Net), a framework that
leverages a single-modality-data-aware multimodal approach. At the heart of
our method is the use of Optical Character Recognition (OCR) to extract
features from various modalities, enabling the capture of a broad spectrum of
semantic information from raw images. This comprehensive approach ensures that
vital information is not overlooked, leading to more reliable and consistent
predictions in defect detection tasks. Empirical evaluations highlight the
efficacy of our method, particularly in enhancing the recall metric. Notably,
our model demonstrates resilience, maintaining robust performance even in
scenarios where some modality data is compromised. We believe that further
exploration and integration of external multi-modal features will
significantly enhance defect detection capabilities, particularly in reducing
the incidence of false negatives in detection procedures.

## References

  * [1] Zhi Tian, Weilin Huang, Tong He, Pan He, Yu Qiao: Detecting Text in Natural Image with Connectionist Text Proposal Network , arXiv preprint, arXiv:1609.03605, 2016
  * [2] Baoguang Shi, Xiang Bai, Serge Belongie: Detecting Oriented Text in Natural Images by Linking Segments, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3482-3490, 2019
  * [3] Minghui Liao, Zhaoyi Wan, Cong Yao, Kai Chen, Xiang Bai: Real-time Scene Text Detection with Differentiable Binarization, Proceedings of the AAAI conference on artificial intelligence (AAAI), pp. 11474-11481, 2020
  * [4] Baoguang Shi, Xiang Bai, Cong Yao: An End-to-End Trainable Neural Network for Image-based Sequence Recognition and Its Application to Scene Text Recognition, arXiv preprint, arXiv:1507.05717v1, 2015
  * [5] Ilya Sutskever, Oriol Vinyals, Quoc V. Le: Sequence to Sequence Learning with Neural Networks, arXiv preprint, arXiv:1507.05717v1, 2014
  * [6] Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, Steven Chu Hong Hoi: Align before Fuse: Vision and Language Representation Learning with Momentum Distillation, Advances in neural information processing systems (NeurlPS), pp. 9694-9705, 2021
  * [7] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, Ilya Sutskever: Learning Transferable Visual Models From Natural Language Supervision , International conference on machine learning (ICML), pp. 8748-8763, 2021
  * [8] Junnan Li, Dongxu Li, Caiming Xiong, Steven Hoi: BLIP: Bootstrapping Language-Image Pre-training for Unified Vision-Language Understanding and Generation, International conference on machine learning (ICML), pp. 12888-12900, 2022
  * [9] Junnan Li, Dongxu Li, Silvio Savarese, Steven Hoi: BLIP-2: Bootstrapping Language-Image Pre-training with Frozen Image Encoders and Large Language Models, arXiv preprint, arXiv:2301.12597, 2023
  * [10] Wenliang Dai, Junnan Li, Dongxu Li, Anthony Meng Huat Tiong, Junqi Zhao, Weisheng Wang, Boyang Li, Pascale Fung, Steven Hoi: BLIP-2: Bootstrapping Language-Image Pre-training with Frozen Image Encoders and Large Language Models, arXiv preprint, arXiv:2305.06500, 2023
  * [11] Domen Tabernik, Samo Šela, Jure Skvarč, Danijel Skočaj: Segmentation-Based Deep-Learning Approach for Surface-Defect Detection, Journal of Intelligent Manufacturing, 759-776, 2020
  * [12] Vasco Lopes, Luís A Alexandre: Auto-classifier: A robust defect detector based on an automl head, International Conference on Neural Information Processing (ICONIP), 137-149, 2020
  * [13] Samet Akcay, Dick Ameln, Ashwin Vaidya, Barath Lakshmanan, Nilesh Ahuja, Utku Genc: Anomalib: A Deep Learning Library for Anomaly Detection, arXiv preprint, arXiv:2202.08341, 2022
  * [14] Ke, Guolin and Meng, Qi and Finley, Thomas and Wang, Taifeng and Chen, Wei and Ma, Weidong and Ye, Qiwei and Liu, Tie-Yan: Lightgbm: A highly efficient gradient boosting decision tree, Advances in neural information processing systems (NeurlPS), pp.3146-3154, 2017
  * [15] Chen, Tianqi and Guestrin, Carlos, XGBoost: A Scalable Tree Boosting System, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 785-794, 2016
  * [16] Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, Andrey Gulin, CatBoost: unbiased boosting with categorical features, Advances in Neural Information Processing Systems (NeurIPS), 2018
  * [17] Sepp Hochreiter, Jürgen Schmidhuber, Long short-term memory, Neural computation, pp. 1735-1780, 1997
  * [18] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, Illia Polosukhin, Attention is all you need, Advances in Neural Information Processing Systems (NeurIPS), 2017
  * [19] Adele Cutler, D Richard Cutler, John R Stevens, Random forests, Ensemble machine learning: Methods and applications, 2012
  * [20] Jerome H. Friedman, Greedy function approximation: A gradient boosting machine, Ann. Statistic. 29 (5) pp. 1189-1232, 2001
  * [21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun, Deep Residual Learning for Image Recognition, Computer Vision and Pattern Recognition (CVPR), 2016
  * [22] Alex Krizhevsky, Ilya Sutskever, Geoffrey E Hinton, Imagenet classification with deep convolutional neural networks, Advances in neural information processing systems (NeurlPS), 2012
  * [23] Karen Simonyan, Andrew Zisserman, Very Deep Convolutional Networks for Large-Scale Image Recognition, arXiv preprint, arXiv:1409.1556, 2014
  * [24] Mingxing Tan, Quoc Le, Efficientnet: Rethinking model scaling for convolutional neural networks, International conference on machine learning (ICML), pp.6105-6114, 2019
  * [25] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, Ilya Sutskever: Zero-Shot Text-to-Image Generation, arXiv preprint, arXiv:2102.12092, 2021
  * [26] Pengguang Chen, Shu Liu, Hengshuang Zhao, Jiaya Jia , GridMask Data Augmentation, arXiv preprint, arXiv:2001.04086v2, 2020
  * [27] CnOCR: https://github.com/breezedeus/cnocr


# On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and
their Aggregation

Samir M. Perlaza123, Iñaki Esnaola24, Gaetan Bisson3, and H. Vincent Poor2
1INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France.  2ECE
Dept. Princeton University, Princeton, 08544 NJ, USA.  3GAATI, Université de
la Polynésie Française, Faaa, French Polynesia.  4ACSE Dept., University of
Sheffield, Sheffield, United Kingdom. This work is supported by the Inria
Exploratory Action – Information and Decision Making (AEx IDEM) and in part by
a grant from the C3.ai Digital Transformation Institute.

###### Abstract

The dependence on training data of the Gibbs algorithm (GA) is analytically
characterized. By adopting the expected empirical risk as the performance
metric, the sensitivity of the GA is obtained in closed form. In this case,
sensitivity is the performance difference with respect to an arbitrary
alternative algorithm. This description enables the development of explicit
expressions involving the training errors and test errors of GAs trained with
different datasets. Using these tools, dataset aggregation is studied and
different figures of merit to evaluate the generalization capabilities of GAs
are introduced. For particular sizes of such datasets and parameters of the
GAs, a connection between Jeffrey’s divergence, training and test errors is
established.

##  I Introduction

The Gibbs algorithm (GA) randomly selects a model by sampling the Gibbs
probability measure, which is the unique solution to the empirical risk
minimization (ERM) problem with relative entropy regularization (ERM-RER) [1].
The input of the GA is twofold. It requires a number of labeled patterns
(datasets); and a prior on the set of models in the form of a
$\sigma$-measure, e.g., the Lebesgue measure, the counting measure, or a
probability measure. One of the main features of the GA is that it does not
require an assumption on the statistical properties of the datasets [2, 3, 4].
Nonetheless, the generalization capabilities of the Gibbs algorithm are often
characterized by the generalization error, for which statistical assumptions
on the datasets must be considered, e.g., training, and unseen datasets are
identically distributed. When the prior on the set of models is a probability
measure, a closed-form expression for the generalization error is presented in
[5], while upper bounds have been derived in [6, 7, 8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27], and references therein.

In a more general setting, when the prior on the set of models is a
$\sigma$-measure, the generalization capabilities of the GA have been studied
in [28, 1], and [29], using the sensitivity of the empirical risk to
deviations from the Gibbs probability measure to another probability measure.
This method does not require any statistical assumptions on the datasets and
is chosen as the workhorse of the present analysis.

The main motivation of this work is to break away from the implicit assumption
in existing literature that all training datasets are drawn from the same
probability measure and thus, can be aggregated to improve the generalization
capabilities of a given GA. In practical settings, training data might be
acquired from multiple sources that might be subject to different impairments
during data acquisition, data storage and data transmission. For instance,
consider a GA trained upon a particular dataset and assume that a new dataset
from a different source is made available. Hence, the following questions
arise concerning the generalization capabilities of such a GA: Would such a GA
generalize over the new dataset? Should the new dataset be aggregated to the
previous dataset to build a new GA in the aim of improving generalization? How
does the GA trained upon the existing dataset compare in terms of
generalization with respect to a new GA trained upon the new dataset? The
answers to such questions are far from trivial. One of the main challenges to
answer such questions stems from the fact that the probability measures
generating each of those datasets are unknown and potentially different due to
a variety of impairments.

This paper introduces a closed-form expression for the difference of the
expected empirical risk on a given dataset induced by a GA trained upon this
dataset and the one induced by an alternative algorithm (another probability
measure). This quantity was coined _sensitivity of the GA algorithm_ in [28]
and is shown to be central to tackling the questions above. This is in part
due to the fact that it allows studying the generalization capabilities of GAs
based on actual datasets, which disengages from the assumption that both
training and unseen data follow the same probability distribution. More
specifically, by studying the sensitivity, closed-form expressions for the
difference between training error and test error can be obtained. These
expressions lead to a clearer understanding of the roles of the size of
datasets chosen for training and testing, as well as the parameters of the
GAs. As a byproduct, the difference between the expected empirical risk on the
aggregation of two datasets induced by two GAs trained upon the constituent
datasets is characterized. Similarly, the difference between the expected
empirical risk on one of the constituent datasets induced by two GAs trained
upon the aggregated dataset and the constituent dataset is also characterized.
These explicit expressions allow comparing two GAs trained upon different
datasets, which is relevant under learning paradigms such as federated
learning [30].

##  II Problem Formulation

Let $\mathcal{M}$, $\mathcal{X}$ and $\mathcal{Y}$, with
$\mathcal{M}\subseteq\mathds{R}^{d}$ and $d\in\mathds{N}$, be sets of _models_
, _patterns_ , and _labels_ , respectively. A pair
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ is referred to as a _labeled pattern_
or as a _data point_. Given $n$ data points, with $n\in\mathds{N}$, denoted by
$\left(x_{1},y_{1}\right)$, $\left(x_{2},y_{2}\right)$, $\ldots$,
$\left(x_{n},y_{n}\right)$, a dataset is represented by the tuple
$\big{(}\left(x_{1},y_{1}\right)$, $\left(x_{2},y_{2}\right)$, $\ldots$,
$\left(x_{n},y_{n}\right)\big{)}$
$\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n}$.

Let the function $f:\mathcal{M}\times\mathcal{X}\rightarrow\mathcal{Y}$ be
such that the label $y$ assigned to the pattern $x$ according to the model
$\boldsymbol{\theta}\in\mathcal{M}$ is

$y=f(\boldsymbol{\theta},x).$ (1)

Let also the function

$\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow[0,+\infty]$ (2)

be such that given a data point $(x,y)\in\mathcal{X}\times\mathcal{Y}$, the
risk induced by a model $\boldsymbol{\theta}\in\mathcal{M}$ is
$\ell\left(f(\boldsymbol{\theta},x),y\right)$. In the following, the risk
function $\ell$ is assumed to be nonnegative and for all $y\in\mathcal{Y}$,
$\ell\left(y,y\right)=0$.

Given a dataset

$\boldsymbol{z}=\big{(}\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right),\ldots,\left(x_{n},y_{n}\right)\big{)}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n},$
(3)

the _empirical risk_ induced by the model $\boldsymbol{\theta}$, with respect
to the dataset $\boldsymbol{z}$ in (3), is determined by the function
$\mathsf{L}_{\boldsymbol{z}}:\mathcal{M}\rightarrow[0,+\infty]$, which
satisfies

$\displaystyle\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\ell\left(f(\boldsymbol{\theta},x_{i}),y_{i}\right).$
(4)

Using this notation, the ERM problem consists of the following optimization
problem:

$\min_{\boldsymbol{\theta}\in\mathcal{M}}\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right).$
(5)

Let the set of solutions to the ERM problem in (5) be denoted by
$\mathcal{T}\left(\boldsymbol{z}\right)\triangleq\arg\min_{\boldsymbol{\theta}\in\mathcal{M}}\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)$.
Note that if the set $\mathcal{M}$ is finite, the ERM problem in (5) always
possesses a solution, and thus,
$\left|\mathcal{T}\left(\boldsymbol{z}\right)\right|>0$. Nonetheless, in
general, the ERM problem might not necessarily possess a solution. Hence, for
some cases, it might be observed that
$\left|\mathcal{T}\left(\boldsymbol{z}\right)\right|=0$.

###  II-A Notation

The _relative entropy_ is defined below as the extension to $\sigma$-finite
measures of the relative entropy usually defined for probability measures.

######  Definition 1 (Relative Entropy)

Given two $\sigma$-finite measures $P$ and $Q$ on the same measurable space,
such that $Q$ is absolutely continuous with respect to $P$, the relative
entropy of $Q$ with respect to $P$ is

$D\left(Q\|P\right)\triangleq\int\frac{\mathrm{d}Q}{\mathrm{d}P}(x)\log\left(\frac{\mathrm{d}Q}{\mathrm{d}P}(x)\right)\mathrm{d}P(x),$
(6)

where the function $\frac{\mathrm{d}Q}{\mathrm{d}P}$ is the Radon-Nikodym
derivative of $Q$ with respect to $P$.

Given a measurable space $\left(\Omega,\mathscr{F}\right)$, the set of all
$\sigma$-finite measures on $\left(\Omega,\mathscr{F}\right)$ is denoted by
$\triangle\left(\Omega,\mathscr{F}\right)$. Given a $\sigma$-measure
$Q\in\triangle\left(\Omega,\mathscr{F}\right)$, the subset of
$\triangle\left(\Omega,\mathscr{F}\right)$ including all $\sigma$-finite
measures absolutely continuous with $Q$ is denoted by
$\triangle_{Q}\left(\Omega,\mathscr{F}\right)$. Given a subset $\mathcal{A}$
of $\mathds{R}^{d}$, the Borel $\sigma$-field on $\mathcal{A}$ is denoted by
$\mathscr{B}\left(\mathcal{A}\right)$.

###  II-B The ERM-RER Problem

The _expected empirical risk_ is defined as follows.

######  Definition 2 (Expected Empirical Risk)

Let $P$ be a probability measure in
$\Delta\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$. The
expected empirical risk with respect to the dataset $\boldsymbol{z}$ in (3)
induced by the measure $P$ is

$\mathsf{R}_{\boldsymbol{z}}\left(P\right)=\int\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)\mathrm{d}P(\boldsymbol{\theta}),$
(7)

where the function $\mathsf{L}_{\boldsymbol{z}}$ is in (4).

The following lemma follows immediately from the properties of the Lebesgue
integral.

###### Lemma 1

Given a dataset
$\boldsymbol{z}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n}$ and two
probability measures $P_{1}$ and $P_{2}$ over the measurable space
$\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$, for all
$\alpha\in[0,1]$, the function $\mathsf{R}_{\boldsymbol{z}}$ in (7) satisfies

$\displaystyle\mathsf{R}_{\boldsymbol{z}}\left(\alpha
P_{1}+(1-\alpha)P_{2}\right)$ $\displaystyle=$
$\displaystyle\alpha\mathsf{R}_{\boldsymbol{z}}\left(P_{1}\right)+(1-\alpha)\mathsf{R}_{\boldsymbol{z}}\left(P_{2}\right).$
(8)

The ERM-RER problem is parametrized by a $\sigma$-finite measure on
$\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$ and a positive
real, which are referred to as the _reference measure_ and the _regularization
factor_ , respectively. Let $Q$ be a $\sigma$-finite measure on
$\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$ and let
$\lambda>0$ be a positive real. The ERM-RER problem, with parameters $Q$ and
$\lambda$, consists in the following optimization problem:

$\min_{P\in\triangle_{Q}\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)}\mathsf{R}_{\boldsymbol{z}}\left(P\right)+\lambda
D\left(P\|Q\right),$ (9)

where the dataset $\boldsymbol{z}$ is in (3); and the function
$\mathsf{R}_{\boldsymbol{z}}$ is defined in (7). For the ease of presentation,
the parameters of the ERM-RER problem in (9) are chosen such that

$Q\left(\left\\{\boldsymbol{\theta}\in\mathcal{M}:\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)=+\infty\right\\}\right)=0.$
(10)

The case in which the regularization is $D\left(Q\|P\right)$ (instead of
$D\left(P\|Q\right)$) in (9) is left out of the scope of this work. The
interested reader is referred to [31].

###  II-C The Solution to the ERM-RER Problem

The solution to the ERM-RER problem in (9) is presented by the following
lemma.

######  Lemma 2 (Theorem $2.1$ in [28])

Given a $\sigma$-finite measure $Q$ and a dataset
$\boldsymbol{z}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n}$, let the
function
$K_{Q,\boldsymbol{z}}:\mathds{R}\rightarrow\mathds{R}\cup\\{+\infty\\}$ be
such that for all $t\in\mathds{R}$,

$\displaystyle K_{Q,\boldsymbol{z}}\left(t\right)$ $\displaystyle=$
$\displaystyle\log\left(\int\exp\left(t\;\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)\right)\mathrm{d}Q(\boldsymbol{\theta})\right),$
(11)

where the function $\mathsf{L}_{\boldsymbol{z}}$ is defined in (4). Let also
the set $\mathcal{K}_{Q,\boldsymbol{z}}\subset(0,+\infty)$ be

$\displaystyle\mathcal{K}_{Q,\boldsymbol{z}}$ $\displaystyle\triangleq$
$\displaystyle\left\\{s>0:\;K_{Q,\boldsymbol{z}}\left(-\frac{1}{s}\right)<+\infty\right\\}.$
(12)

Then, for all $\lambda\in\mathcal{K}_{Q,\boldsymbol{z}}$, the solution to the
ERM-RER problem in (9) is a unique measure on
$\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$, denoted by
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$,
whose Radon-Nikodym derivative with respect to $Q$ satisfies that for all
$\boldsymbol{\theta}\in\mathrm{supp}\,Q$,

$\displaystyle\frac{\mathrm{d}P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}}{\mathrm{d}Q}\left(\boldsymbol{\theta}\right)$
$\displaystyle=$
$\displaystyle\exp\left(-K_{Q,\boldsymbol{z}}\left(-\frac{1}{\lambda}\right)-\frac{1}{\lambda}\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)\right).$
(13)

Among the numerous properties of the solution to the ERM-RER problem in (9),
the following property is particularly useful in the remainder of this work.

###### Lemma 3

Given a $\sigma$-finite measure $Q$ over the measurable space
$\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$, and given a
dataset $\boldsymbol{z}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n}$, for
all $\lambda\in\mathcal{K}_{Q,\boldsymbol{z}}$, with
$\mathcal{K}_{Q,\boldsymbol{z}}$ in (12), the following holds:

$\displaystyle\mathsf{R}_{\boldsymbol{z}}\left(P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\right)+\lambda
D\left(P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\|Q\right)$
$\displaystyle=$ $\displaystyle-\lambda
K_{Q,\boldsymbol{z}}\left(-\frac{1}{\lambda}\right),$ (14)

where the function $\mathsf{R}_{\boldsymbol{z}}$ is defined in (7); the
function $K_{Q,\boldsymbol{z}}$ is defined in (11); and the probability
measure
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$
is the solution to the ERM-RER problem in (9).

###### Proof:

The proof is presented in [29]. ∎

##  III Sensitivity of the ERM-RER Solution

The sensitivity of the expected empirical risk $\mathsf{R}_{\boldsymbol{z}}$
to deviations from the probability measure
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$
towards an alternative probability measure $P$ is defined as follows.

######  Definition 3 (Sensitivity [28])

Given a $\sigma$-finite measure $Q$ and a positive real $\lambda>0$, let
$\mathsf{S}_{Q,\lambda}:\left(\mathcal{X}\times\mathcal{Y}\right)^{n}\times\triangle_{Q}\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)\rightarrow\left(-\infty,+\infty\right]$
be a function such that

$\displaystyle\mathsf{S}_{Q,\lambda}\left(\boldsymbol{z},P\right)=\left\\{\begin{array}[]{cl}\mathsf{R}_{\boldsymbol{z}}\left(P\right)-\mathsf{R}_{\boldsymbol{z}}\left(P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\right)&\text{
if }\lambda\in\mathcal{K}_{Q,\boldsymbol{z}}\\\ +\infty&\text{
otherwise,}\end{array}\right.\quad$ (17)

where the function $\mathsf{R}_{\boldsymbol{z}}$ is defined in (7) and the
measure
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$
is the solution to the ERM-RER problem in (9). The sensitivity of the expected
empirical risk $\mathsf{R}_{\boldsymbol{z}}$ when the measure changes from
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$
to $P$ is $\mathsf{S}_{Q,\lambda}\left(\boldsymbol{z},P\right)$.

The following theorem introduces an exact expression for the sensitivity in
Definition 3.

###### Theorem 1

Given a $\sigma$-finite measure $Q$ over the measurable space
$\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$ and a
probability measure
$P\in\triangle_{Q}\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$,
it holds that for all datasets
$\boldsymbol{z}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n}$ and for all
$\lambda\in\mathcal{K}_{Q,\boldsymbol{z}}$, with
$\mathcal{K}_{Q,\boldsymbol{z}}$ in (12),

$\displaystyle\mathsf{S}_{Q,\lambda}\left(\boldsymbol{z},P\right)$
$\displaystyle=$
$\displaystyle\lambda\Big{(}D\left(P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\|Q\right)+D\left(P\|P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\right)-D\left(P\|Q\right)\Big{)},$

where the probability measure
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$
is the solution to the ERM-RER problem in (9).

###### Proof:

The proof uses the fact that, under the assumption in (10), the probability
measure
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$
in (13) is mutually absolutely continuous with respect to the $\sigma$-finite
measure $Q$; see for instance [1]. Hence, the probability measure $P$ is
absolutely continuous with respect to
$P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}$,
as a consequence of the assumption that $P$ is absolutely continuous with
respect to $Q$.

The proof follows by noticing that for all
$\boldsymbol{\theta}\in\mathcal{M}$,

$\displaystyle\log\left(\frac{\mathrm{d}P}{\mathrm{d}P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}}\left(\boldsymbol{\theta}\right)\right)=\log\left(\frac{\mathrm{d}Q}{\mathrm{d}P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}}\left(\boldsymbol{\theta}\right)\frac{\mathrm{d}P}{\mathrm{d}Q}\left(\boldsymbol{\theta}\right)\right)\qquad$
(18) $\displaystyle=$
$\displaystyle-\log\left(\frac{\mathrm{d}P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}}{\mathrm{d}Q}\left(\boldsymbol{\theta}\right)\right)+\log\left(\frac{\mathrm{d}P}{\mathrm{d}Q}\left(\boldsymbol{\theta}\right)\right)$
(19) $\displaystyle=$ $\displaystyle
K_{Q,\boldsymbol{z}}\left(-\frac{1}{\lambda}\right)+\frac{1}{\lambda}\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)+\log\left(\frac{\mathrm{d}P}{\mathrm{d}Q}\left(\boldsymbol{\theta}\right)\right),$
(20)

where the functions $\mathsf{L}_{\boldsymbol{z}}$ and $K_{Q,\boldsymbol{z}}$
are defined in (4) and in (11), respectively; and the equality in (20) follows
from Lemma 2. Hence, the relative entropy
$D\left(P\|P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\right)$
satisfies

$\displaystyle
D\left(P\|P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\right)=\int\log\left(\frac{\mathrm{d}P}{\mathrm{d}P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}}\left(\boldsymbol{\theta}\right)\right)\mathrm{d}P\left(\boldsymbol{\theta}\right)$
(21) $\displaystyle=$ $\displaystyle
K_{Q,\boldsymbol{z}}\left(-\frac{1}{\lambda}\right)+\int\left(\frac{1}{\lambda}\mathsf{L}_{\boldsymbol{z}}\left(\boldsymbol{\theta}\right)+\log\left(\frac{\mathrm{d}P}{\mathrm{d}Q}\left(\boldsymbol{\theta}\right)\right)\right)\mathrm{d}P\left(\boldsymbol{\theta}\right)\quad$
$\displaystyle=$ $\displaystyle
K_{Q,\boldsymbol{z}}\left(-\frac{1}{\lambda}\right)+\frac{1}{\lambda}\mathsf{R}_{\boldsymbol{z}}\left(P\right)+D\left(P\|Q\right)$
(23) $\displaystyle=$
$\displaystyle-D\left(P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\|Q\right)+\frac{1}{\lambda}\left(\mathsf{R}_{\boldsymbol{z}}\left(P\right)-\mathsf{R}_{\boldsymbol{z}}\left(P^{\left(Q,\lambda\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}}\right)\right)$
$\displaystyle+D\left(P\|Q\right),$

where the function $\mathsf{R}_{\boldsymbol{z}}$ is defined in (7), the
equality in (21) follows from (20), and the equality in (23) follows from
Lemma 3. Finally, the proof is completed by re-arranging the terms in (23). ∎

##  IV Validation of Gibbs Algorithms

Consider the dataset
$\boldsymbol{z}_{0}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n_{0}}$ that
aggregates dataset
$\boldsymbol{z}_{1}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n_{1}}$ and
dataset
$\boldsymbol{z}_{2}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n_{2}}$ as
constituents. That is,
$\boldsymbol{z}_{0}=\left(\boldsymbol{z}_{1},\boldsymbol{z}_{2}\right)$, with
$n_{0}=n_{1}+n_{2}$. Datasets $\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}$
are referred to as _constituent datasets_ , whereas, the dataset
$\boldsymbol{z}_{0}$ is referred to as the _aggregated dataset_. For all
$i\in\\{0,1,2\\}$, the empirical risk function in (4) and the expected
empirical risk function in (7) over dataset $\boldsymbol{z}_{i}$ are denoted
by $\mathsf{L}_{\boldsymbol{z}_{i}}$ and $\mathsf{R}_{\boldsymbol{z}_{i}}$,
respectively. Such functions exhibit the following property.

###### Lemma 4

The empirical risk functions $\mathsf{L}_{\boldsymbol{z}_{0}}$,
$\mathsf{L}_{\boldsymbol{z}_{1}}$, and $\mathsf{L}_{\boldsymbol{z}_{2}}$,
defined in (4) satisfy for all $\boldsymbol{\theta}\in\mathcal{M}$,

$\displaystyle\mathsf{L}_{\boldsymbol{z}_{0}}\left(\boldsymbol{\theta}\right)$
$\displaystyle=$
$\displaystyle\frac{n_{1}}{n_{0}}\mathsf{L}_{\boldsymbol{z}_{1}}\left(\boldsymbol{\theta}\right)+\frac{n_{2}}{n_{0}}\mathsf{L}_{\boldsymbol{z}_{2}}\left(\boldsymbol{\theta}\right).$
(24)

Moreover, the expected empirical risk functions
$\mathsf{R}_{\boldsymbol{z}_{0}}$, $\mathsf{R}_{\boldsymbol{z}_{1}}$, and
$\mathsf{R}_{\boldsymbol{z}_{2}}$, defined in (7), satisfy for all
$\sigma$-finite measures
$P\in\triangle\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$,

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{0}}\left(P\right)$ $\displaystyle=$
$\displaystyle\frac{n_{1}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{1}}\left(P\right)+\frac{n_{2}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{2}}\left(P\right).$
(25)

###### Proof:

The proof is presented in [29]. ∎

For all $i\in\\{0,1,2\\}$, let
$Q_{i}\in\triangle\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)$
and $\lambda_{i}\in\mathcal{K}_{Q_{i},\boldsymbol{z}_{i}}$, with
$\mathcal{K}_{Q_{i},\boldsymbol{z}_{i}}$ in (12), be the $\sigma$-finite
measure acting as the reference measure and regularization factor for the
learning task with dataset $i$, respectively. Each dataset induces a different
ERM-RER problem formulation of the form

$\min_{P\in\triangle_{Q_{i}}\left(\mathcal{M},\mathscr{B}\left(\mathcal{M}\right)\right)}\mathsf{R}_{\boldsymbol{z}_{i}}\left(P\right)+\lambda_{i}D\left(P\|Q_{i}\right),$
(26)

where $\mathsf{R}_{\boldsymbol{z}_{i}}$ is the expected empirical risk defined
in (7). For all $i\in\\{0,1,2\\}$, the solution to the ERM-RER problem in (26)
is the probability measure denoted by
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$.
In particular, from Lemma 2, it holds that the probability measure
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
satisfies for all $\boldsymbol{\theta}\in\mathrm{supp}\,Q_{i}$,

$\displaystyle\frac{\mathrm{d}P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}}{\mathrm{d}Q_{i}}\left(\boldsymbol{\theta}\right)$
$\displaystyle=$
$\displaystyle\exp\left(-K_{Q_{i},\boldsymbol{z}_{i}}\left(-\frac{1}{\lambda_{i}}\right)-\frac{1}{\lambda_{i}}\mathsf{L}_{\boldsymbol{z}_{i}}\left(\boldsymbol{\theta}\right)\right).$
(27)

For all $i\in\\{0,1,2\\}$, the probability measure
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
in (27) represents a GA trained upon the dataset $\boldsymbol{z}_{i}$ with
parameters $\left(Q_{i},\lambda_{i}\right)$. In the following, such an
algorithm is denoted by $\mathsf{GA}_{i}$ and the dataset $\boldsymbol{z}_{i}$
is often referred to as the _training dataset_ of $\mathsf{GA}_{i}$. The
dataset $\boldsymbol{z}_{j}$, with $j\in\\{0,1,2\\}\setminus\\{i\\}$, which
might contain datapoints that are not in $\boldsymbol{z}_{i}$, is referred to
as the _test dataset_ for $\mathsf{GA}_{i}$.

###  IV-A Gibbs Algorithms Trained on Constituent Datasets

The expected empirical risk induced by $\mathsf{GA}_{i}$ on the training
dataset $\boldsymbol{z}_{i}$ is the _training expected empirical risk_ , which
is denoted by
$\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$
and often referred to as the _training error_ [32]. Alternatively, the
expected empirical risk induced by $\mathsf{GA}_{i}$ on the test dataset
$\boldsymbol{z}_{j}$ is the _test expected empirical risk_ , which is denoted
by
$\mathsf{R}_{\boldsymbol{z}_{j}}\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$
and often referred to as the _test error_ [32]. The following theorem provides
explicit expressions involving the training and test errors of
$\mathsf{GA}_{1}$ and $\mathsf{GA}_{2}$.

###### Theorem 2

Assume that the $\sigma$-finite measures $Q_{1}$ and $Q_{2}$ in (26) are
mutually absolutely continuous. Then, for all $i\in\\{1,2\\}$ and
$j\in\\{1,2\\}\setminus\\{i\\}$,

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{j},\lambda_{j}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{j}}\right)-\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)=\lambda_{i}\Big{(}D\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\|Q_{i}\right)$
$\displaystyle+D\left(P^{\left(Q_{j},\lambda_{j}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{j}}\|P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)-D\left(P^{\left(Q_{j},\lambda_{j}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{j}}\|Q_{i}\right)\Big{)},\quad$
(28)

where the function $\mathsf{R}_{\boldsymbol{z}_{i}}$ is defined in (7) and the
measure
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
satisfies (27).

###### Proof:

The proof is immediate from Theorem 1 by noticing that for all $i\in\\{1,2\\}$
and for all $j\in\\{1,2\\}\setminus\\{i\\}$, the differences
$\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{j},\lambda_{j}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{j}}\right)-\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$
can be written in terms of the sensitivity
$\mathsf{S}_{Q_{i},\lambda_{i}}\left(\boldsymbol{z}_{i},P^{\left(Q_{j},\lambda_{j}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{j}}\right)$.
∎

A reasonable figure of merit to compare two machine learning algorithms
trained upon two different training datasets is the difference between the
expected empirical risk they induce upon the aggregation of their training
datasets. The following theorem provides an explicit expression for this
figure of merit for the case of the algorithms $\mathsf{GA}_{1}$ and
$\mathsf{GA}_{2}$.

###### Theorem 3

Assume that the $\sigma$-finite measures $Q_{1}$ and $Q_{2}$ in (26) are
mutually absolutely continuous. Then,

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)=\frac{n_{1}}{n_{0}}\lambda_{1}\bigg{(}D\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|Q_{1}\right)$
$\displaystyle+D\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)-D\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|Q_{1}\right)\bigg{)}\quad$
$\displaystyle-\frac{n_{2}}{n_{0}}\lambda_{2}\bigg{(}D\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|Q_{2}\right)+D\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)$
$\displaystyle-D\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|Q_{2}\right)\bigg{)},\quad$
(29)

where the function $\mathsf{R}_{\boldsymbol{z}_{0}}$ is defined in (7) and,
for all $i\in\\{1,2\\}$, the measure
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
satisfies (27).

###### Proof:

The proof uses the following argument:

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)$
(30) $\displaystyle=$
$\displaystyle\frac{n_{1}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{1}}\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)+\frac{n_{2}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{2}}\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)$
$\displaystyle-\left(\frac{n_{1}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{1}}\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)+\frac{n_{2}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{2}}\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)\right)$
$\displaystyle=$
$\displaystyle\frac{n_{1}}{n_{0}}\mathsf{S}_{Q_{1},\lambda_{1}}\left(\boldsymbol{z}_{1},P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\frac{n_{2}}{n_{0}}\mathsf{S}_{Q_{2},\lambda_{2}}\left(\boldsymbol{z}_{2},P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right),\qquad$
(31)

where the equality in (30) follows from Lemma 4; and the equality in (31)
follows from Definition 3. The proof is completed by Theorem 1. ∎

###  IV-B Averaging Gibbs Measures

In practical scenarios, building GAs on the aggregated dataset might be
difficult or impossible due to limited computational power or due to the fact
that dataset aggregation at one location is not allowed due to privacy
constraints. In these cases, a common practice is to average the output of
machine learning algorithms trained on constituent datasets, e.g., federated
learning [30]. In this case, a figure of merit to validate such an approach is
to study the difference of the expected empirical risk induced on the
aggregated dataset by $\mathsf{GA}_{0}$ and a convex combination of
$\mathsf{GA}_{1}$ and $\mathsf{GA}_{2}$. The following theorem provides an
explicit expression for this quantity.

###### Theorem 4

Assume that the $\sigma$-finite measures $Q_{0}$, $Q_{1}$ and $Q_{2}$ in (26)
are pair-wise mutually absolutely continuous. Then, for all $\alpha\in[0,1]$,

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{0}}\left(\alpha
P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}+\left(1-\alpha\right)P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)$
(32) $\displaystyle=$
$\displaystyle\lambda_{0}\Bigg{(}D\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\|Q_{0}\right)$
$\displaystyle+\alpha\left(D\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-D\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|Q_{0}\right)\right)$
$\displaystyle+\left(1-\alpha\right)\left(D\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-D\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|Q_{0}\right)\right)\Bigg{)},\hskip
15.0694pt$

where the function $\mathsf{R}_{\boldsymbol{z}_{0}}$ is defined in (7) and,
for all $i\in\\{1,2\\}$, the measure
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
satisfies (27).

###### Proof:

The proof uses the following argument:

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{0}}\left(\alpha
P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}+\left(1-\alpha\right)P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)$
(34) $\displaystyle=$
$\displaystyle\alpha\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)+\left(1-\alpha\right)\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)$
$\displaystyle-\alpha\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-\left(1-\alpha\right)\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)$
$\displaystyle=$
$\displaystyle\alpha\left(\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)-\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)\right)$
$\displaystyle+\left(1-\alpha\right)\left(\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)\right)$
$\displaystyle=$
$\displaystyle\alpha\mathsf{S}_{Q_{0},\lambda_{0}}\left(\boldsymbol{z}_{0},P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)+\left(1-\alpha\right)\mathsf{S}_{Q_{0},\lambda_{0}}\left(\boldsymbol{z}_{0},P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right),\qquad$
(35)

where the equality in (34) follows from Lemma 1, and the equality in (35)
follows from Definition 3. The proof is completed by Theorem 1. ∎

The following corollary of Theorem 4 is obtained by subtracting the equality
in (32) with $\alpha=1$ from the equality in (32) with $\alpha=0$.

###### Corollary 1

Assume that the $\sigma$-finite measures $Q_{0}$, $Q_{1}$ and $Q_{2}$ in (26)
are pair-wise mutually absolutely continuous. Then, for all $i\in\\{0,1,2\\}$,
the probability measure
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
in (27) satisfies

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\mathsf{R}_{\boldsymbol{z}_{0}}\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)$
(36) $\displaystyle=$
$\displaystyle\lambda_{0}\Bigg{(}D\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-D\left(P^{\left(Q_{2},\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|Q_{0}\right)\Bigg{)}$
$\displaystyle-\lambda_{0}\Bigg{(}D\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-D\left(P^{\left(Q_{1},\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|Q_{0}\right)\Bigg{)},$

where the function $\mathsf{R}_{\boldsymbol{z}_{0}}$ is defined in (7).

Corollary 1 is an alternative to Theorem 3 involving the GA trained upon the
aggregated dataset, i.e., $\mathsf{GA}_{0}$.

###  IV-C Gibbs Algorithms Trained on Aggregated Datasets

Training a GA upon the aggregation of datasets does not necessarily imply
lower expected empirical risk on the constituent datasets. As argued before,
datasets might be obtained up to different levels of fidelity. Hence, a
validation method for $\mathsf{GA}_{0}$ is based on the expected empirical
risk induced by $\mathsf{GA}_{0}$ on a constituent dataset
$\boldsymbol{z}_{i}$, with $i\in\\{1,2\\}$, which is denoted by
$\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)$.
A pertinent figure of merit is the difference
$\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$.
The following theorem provides an explicit expression for such quantity.

###### Theorem 5

Assume that the $\sigma$-finite measures $Q_{0}$, $Q_{1}$ and $Q_{2}$ in (26)
are pair-wise mutually absolutely continuous. Then, for all $i\in\\{0,1,2\\}$,

$\displaystyle\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)=\lambda_{i}\bigg{(}D\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\|Q_{i}\right)$
$\displaystyle+D\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\|P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)-D\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\|Q_{i}\right)\bigg{)},\quad$
(37)

where, the function $\mathsf{R}_{\boldsymbol{z}_{i}}$ is defined in (7) and
the measure
$P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
satisfies (27).

###### Proof:

The proof is immediate from Theorem 1 by noticing that for all
$i\in\\{1,2\\}$, the differences
$\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)-\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q_{i},\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$
can be written in terms of the sensitivity
$\mathsf{S}_{Q_{i},\lambda_{i}}\left(\boldsymbol{z}_{i},P^{\left(Q_{0},\lambda_{0}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{0}}\right)$.
∎

###  IV-D Special Cases

Consider a given $\sigma$-finite measure $Q$ and assume that for all
$i\in\\{0,1,2\\}$ and for all
$\mathcal{A}\in\mathscr{B}\left(\mathcal{M}\right)$,
$Q\left(\mathcal{A}\right)=Q_{i}\left(\mathcal{A}\right)$. Assume also that
the parameters $\lambda_{0}$, $\lambda_{1}$, and $\lambda_{2}$ in (26) satisfy
$\lambda_{1}=\frac{n_{0}}{n_{1}}\lambda_{0}$ and
$\lambda_{2}=\frac{n_{0}}{n_{2}}\lambda_{0}$. These assumptions are referred
to as the case of _homogeneous priors_ with measure $Q$, and the case of
_proportional regularization_ , respectively. The term “proportional” stems
from the fact that the regularization factor decreases proportionally to the
size of the data set in the optimization problem in (26). Under these
assumptions, the following corollary of Theorem 2 unveils an interesting
connection with the Jeffrey’s divergence [33].

###### Corollary 2

Consider the case of homogeneous priors with a $\sigma$-finite measure $Q$ and
proportional regularization with parameter $\lambda_{0}$. Then, for all
$i\in\\{1,2\\}$, the probability measure
$P^{\left(Q,\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
in (27), satisfies

$\displaystyle\Big{(}\frac{n_{1}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{1}}\left(P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)-\frac{n_{2}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{2}}\left(P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)\Big{)}$
$\displaystyle+\Big{(}\frac{n_{2}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{2}}\left(P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)-\frac{n_{1}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{1}}\left(P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)\Big{)}$
$\displaystyle=\lambda_{0}\Bigg{(}D\left(P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)+D\left(P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)\Bigg{)}.$
(38)

Note that
$D\left(P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)+D\left(P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)$
is the Jeffrey’s divergence between the measures
$P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}$
and
$P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}$.
For all $i\in\\{1,2\\}$ and $j\in\\{1,2\\}\setminus\\{i\\}$, the difference
$\frac{n_{j}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{j}}\left(P^{\left(Q,\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)-\frac{n_{i}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q,\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$
is reminiscent of a _validation_ [32, Section $11.2$]. This follows from
noticing that
$\mathsf{R}_{\boldsymbol{z}_{j}}\left(P^{\left(Q,\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$
is the testing error of $\mathsf{GA}_{i}$ over the test dataset
$\boldsymbol{z}_{j}$, while
$\mathsf{R}_{\boldsymbol{z}_{i}}\left(P^{\left(Q,\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}\right)$
is the training error of $\mathsf{GA}_{i}$.

In (38), it holds that
$D\left(P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\|P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)$
and
$D\left(P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\|P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)$
are both nonnegative, which leads to the following corollary of Theorem 2.

###### Corollary 3

Consider the case of homogeneous priors with a $\sigma$-finite measure $Q$ and
proportional regularization. Then, for all $i\in\\{1,2\\}$, the probability
measure
$P^{\left(Q,\lambda_{i}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{i}}$
in (27), satisfies

$\displaystyle\Big{(}\frac{n_{1}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{1}}\left(P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)+\frac{n_{2}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{2}}\left(P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)\Big{)}$
(39) $\displaystyle\geqslant$
$\displaystyle\Big{(}\frac{n_{1}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{1}}\left(P^{\left(Q,\lambda_{1}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{1}}\right)+\frac{n_{2}}{n_{0}}\mathsf{R}_{\boldsymbol{z}_{2}}\left(P^{\left(Q,\lambda_{2}\right)}_{\boldsymbol{\Theta}|\boldsymbol{Z}=\boldsymbol{z}_{2}}\right)\Big{)}.$

Corollary 3 highlights that the weighted-sum of the test errors induced by
$\mathsf{GA}_{1}$ and $\mathsf{GA}_{2}$ is not smaller than the weighted sum
of their training errors when the weights are proportional to the sizes of the
datasets.

## References

  * [1] S. M. Perlaza, G. Bisson, I. Esnaola, A. Jean-Marie, and S. Rini, “Empirical risk minimization with generalized relative entropy regularization,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Tech. Rep. RR-9454, Feb. 2022.
  * [2] O. Catoni, _Statistical Learning Theory and Stochastic Optimization: Ecole d’Eté de Probabilités de Saint-Flour, XXXI-2001_ , 1st ed. New York, NY, USA: Springer Science & Business Media, 2004, vol. 1851.
  * [3] L. Zdeborová and F. Krzakala, “Statistical physics of inference: Thresholds and algorithms,” _Advances in Physics_ , vol. 65, no. 5, pp. 453–552, Aug. 2016.
  * [4] P. Alquier, J. Ridgway, and N. Chopin, “On the properties of variational approximations of Gibbs posteriors,” _Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 8374–8414, Dec. 2016.
  * [5] G. Aminian, Y. Bu, L. Toni, M. Rodrigues, and G. Wornell, “An exact characterization of the generalization error for the Gibbs algorithm,” _Advances in Neural information Processing Systems_ , vol. 34, pp. 8106–8118, Dec. 2021.
  * [6] T. Zhang, “From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation,” _The Annals of Statistics_ , vol. 34, no. 5, pp. 2180–2210, 2006.
  * [7] ——, “Information-theoretic upper and lower bounds for statistical estimation,” _IEEE Transactions on Information Theory_ , vol. 52, no. 4, pp. 1307–1321, Apr. 2006.
  * [8] J. Jiao, Y. Han, and T. Weissman, “Dependence measures bounding the exploration bias for general measurements,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Aachen, Germany, Jun. 2017, pp. 1475–1479.
  * [9] A. Xu and M. Raginsky, “Information-theoretic analysis of generalization capability of learning algorithms,” _Advances in Neural information Processing Systems_ , Dec. 2017.
  * [10] H. Wang, M. Diaz, J. C. S. Santos Filho, and F. P. Calmon, “An information-theoretic view of generalization via Wasserstein distance,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Paris, France, Jul. 2019, pp. 577–581.
  * [11] I. Issa, A. R. Esposito, and M. Gastpar, “Strengthened information-theoretic bounds on the generalization error,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Paris, France, Jul. 2019, pp. 582–586.
  * [12] D. Russo and J. Zou, “How much does your data exploration overfit? Controlling bias via information usage,” _IEEE Transactions on Information Theory_ , vol. 66, no. 1, pp. 302–323, Jan. 2019.
  * [13] Y. Bu, S. Zou, and V. V. Veeravalli, “Tightening mutual information-based bounds on generalization error,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 1, pp. 121–130, 2020.
  * [14] A. Asadi, E. Abbe, and S. Verdú, “Chaining mutual information and tightening generalization bounds,” _Advances in Neural information Processing Systems_ , pp. 7245–7254, Dec. 2018.
  * [15] A. T. Lopez and V. Jog, “Generalization error bounds using Wasserstein distances,” in _Proceedings of the IEEE Information Theory Workshop (ITW)_ , Guangzhou, China, Nov. 2018, pp. 1–5.
  * [16] A. R. Asadi and E. Abbe, “Chaining meets chain rule: Multilevel entropic regularization and training of neural networks.” _Journal of Machine Learning Research_ , vol. 21, pp. 139–1, 2020.
  * [17] H. Hafez-Kolahi, Z. Golgooni, S. Kasaei, and M. Soleymani, “Conditioning and processing: Techniques to improve information-theoretic generalization bounds,” _Advances in Neural information Processing Systems_ , pp. 16 457–16 467, Dec. 2020.
  * [18] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite, “Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms,” _Advances in Neural information Processing Systems_ , pp. 9925–9935, Dec. 2018.
  * [19] B. Rodríguez Gálvez, G. Bassi, R. Thobaben, and M. Skoglund, “Tighter expected generalization error bounds via Wasserstein distance,” _Advances in Neural information Processing Systems_ , pp. 19 109–19 121, Dec. 2021.
  * [20] A. R. Esposito, M. Gastpar, and I. Issa, “Generalization error bounds via Rényi-, f-divergences and maximal leakage,” _IEEE Transactions on Information Theory_ , vol. 67, no. 8, pp. 4986–5004, 2021.
  * [21] G. Aminian, L. Toni, and M. R. Rodrigues, “Jensen-Shannon information based characterization of the generalization error of learning algorithms,” in _Proceedings of the IEEE Information Theory Workshop (ITW)_ , Kanazawa, Japan, Oct. 2021, pp. 1–5.
  * [22] G. Aminian, Y. Bu, L. Toni, M. R. D. Rodrigues, and G. W. Wornell, “Information-theoretic characterizations of generalization error for the Gibbs algorithm,” _ArXiv Preprint 2210.09864_ , 2022.
  * [23] G. Aminian, Y. Bu, G. W. Wornell, and M. R. Rodrigues, “Tighter expected generalization error bounds via convexity of information measures,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Aalto, Finland, Jun. 2022, pp. 2481–2486.
  * [24] J. Shawe-Taylor and R. C. Williamson, “A PAC analysis of a Bayesian estimator,” in _Proceedings of Tenth Annual Conference on Computational Learning Theory_ , July 1997, pp. 2–9.
  * [25] D. A. McAllester, “PAC-Bayesian stochastic model selection,” _Machine Learning_ , vol. 51, no. 1, pp. 5–21, 2003.
  * [26] M. Haddouche, B. Guedj, O. Rivasplata, and J. Shawe-Taylor, “PAC-Bayes unleashed: Generalisation bounds with unbounded losses,” _Entropy_ , vol. 23, no. 10, Oct. 2021.
  * [27] B. Guedj and L. Pujol, “Still no free lunches: The price to pay for tighter PAC-Bayes bounds,” _Entropy_ , vol. 23, no. 11, Nov. 2021.
  * [28] S. M. Perlaza, G. Bisson, I. Esnaola, A. Jean-Marie, and S. Rini, “Empirical risk minimization with relative entropy regularization: Optimality and sensitivity,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Espoo, Finland, Jul. 2022.
  * [29] S. M. Perlaza, I. Esnaola, G. Bisson, and H. V. Poor, “Sensitivity of the Gibbs algorithm to data aggregation in supervised machine learning,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Research Report RR-9474, Jun. 2022.
  * [30] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS)_ , Fort Lauderdale, Florida, Apr. 2017, pp. 1273–1282.
  * [31] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, “Analysis of the relative entropy asymmetry in the regularization of empirical risk minimization,” in _Proceedings of the IEEE International Symposium on Information Theory (ISIT)_ , Taipei, Taiwan, Jun. 2023.
  * [32] S. Shalev-Shwartz and S. Ben-David, _Understanding Machine Learning: From Theory to Algorithms_ , 1st ed. New York, NY, USA: Cambridge University Press, 2014.
  * [33] H. Jeffreys, “An invariant form for the prior probability in estimation problems,” _Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences_ , vol. 186, no. 1007, pp. 453–461, 1946.