Generalization Analysis on Learning with a Concurrent Verifier
Authors: Masaaki Nishino
Kengo Nakamura
Norihito Yasuda
Venue: NeurIPS 2022 Accept (2022)
Keywords: Generalization analysis
verifier
learning theory

Abstract: Machine learning technologies have been used in a wide range of practical systems.
In practical situations, it is natural to expect the input-output pairs of a machine learning model to satisfy some requirements.
However, it is difficult to obtain a model that satisfies requirements by just learning from examples.
A simple solution is to add a module that checks whether the input-output pairs meet the requirements and then modifies the model's outputs. Such a module, which we call a {\em concurrent verifier} (CV), can give a certification, although how the generalizability of the machine learning model changes using a CV is unclear. This paper gives a generalization analysis of learning with a CV. We analyze how the learnability of a machine learning model changes with a CV and show a condition where we can obtain a guaranteed hypothesis using a verifier only in the inference time.
We also show that typical error bounds based on Rademacher complexity will be no larger than that of the original model when using a CV in multi-class classification and structured prediction settings. 

Generalization Analysis on Learning with a Concurrent Verifier
Masaaki Nishino, Kengo Nakamura, Norihito Yasuda NTT Communication Science Laboratories, NTT Corporation (masaaki mishino..... uh, kengo. nakamura. dx, norihito, parihito.yasunne yasuda. hnc ntt.co co. jp
Abstract
Machine learning technologies have been used in wide range of practical systems. In practical situations, it is natural to expect the input-output pairs of a machine learning model to satisfy some requirements. However, it is difficult to obtain a model that satisfies requirements by just learning from examples. A simple solution is to add a module that checks whether the input-output pairs meet the require- ments and then modifies the model's outputs. Such module, which we call concurrent verifier (CV), can give a certification, although how the generalizability of the machine learning model changes using CV is unclear. This paper gives generalization analysis of learning with CV. We analyze how the learnability of a machine learning model changes with CV and show a condition where we can obtain guaranteed hypothesis using a verifier only in the inference time. We also show that typical error bounds based Rademacher complexity will be no larger than that of the original model when using a CV in multi-class classification and structured prediction settings.
Introduction
As machine learning technology matures. many systems have been developed that exploit machine learning models. When developing system that uses a machine learning model, model with merely small prediction error is not satisfactory due real-field requirements. For example, an object recognition model that is sensitive to slight noise would cause security issues 4 26), or model with unexpected output would increase a system's cost for dealing with it. Thus, we want the input-output pairs of a machine learning model to satisfy some requirements. However, it is difficult to obtain model that satisfies the requirements by just learning from examples. Moreover, since the learned models tend to be complex and the input domain tends to be quite large, it is unrealistic to certify that every input-output pair satisfies the requirements. addition, even if we find an input-output pair that does not satisfy the requirements, modifying a model is difficult since we have to re-estimate it from the training examples.
This paper considers way to obtain a machine learning model whose input-output pairs satisfy the required properties. We address the following assumptions for a situation where machine learning model is used. First, we can judge whether input-output pair (æ, h(x)) satisfies the requirements, where h X' - y is machine learning model or a hypothesis. As we show below, important use cases fit this setting. Second, machine learning model already exists whose prediction error is small enough, although its input-output pairs are not guaranteed to satisfy the requirements. This second assumption is also reasonable since modern machine learning models show sufficient prediction accuracy in various tasks. Under these assumptions, a practical choice for addressing this problem isn't changing the machine learning model but adding module that checks the input-output pairs of machine learning model h. We call this module a concurrent verifier (CV). Fig. shows the system configuration of machine learning model with CV. The verifier checks whether the input-output
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Machine Learning
h(z)
Concurrent
1e(2)
Model
Verifier
Figure 1: Overview of a machine learning model with a concurrent verifier that checks whether input-output pairs of model satisfy requirements.
pair (x, h(z)) satisfies the required properties. If satisfies the requirements, it outputs h(z). If not, then it rejects (zx) and modifies or requests the learning model to modify its output. A machine learning model and verifier pair can be seen as another machine learning model whose input-output pairs are guaranteed to satisfy the required conditions.
guarantee that its input-output pairs satisfy requirements, its effect on prediction error is unclear. This paper gives theoretical analyses of the generalization errors of a machine learning model with a CV. We focus on how the learnability of the original model, denoted as hypothesis class H. can change by using the verifier. First, we consider a situation where we use CV only in the inference phase. This setting corresponds to a case where the required properties are unknown when we are in the training phase. If the hypothesis class is PAC-learnable, we can obtain a guaranteed hypothesis using a verifier only the inference time.
Although model with verifier
Second, we consider a situation where we know the requirements when learning the model. This situation corresponds to viewing the learnability of hypothesis set He. which is obtained by modifying every hypothesis h E H to satisfy the requirements. Hence we compare the generalization error upper bounds of H. with those of H. On the multi-class classification setting, we show that existing error bounds 13, 16 based on the Rademacher complexity of H are also bounds of modified hypothesis H. for any input-output requirements. Moreover, give similar analyses for structured prediction task, which is kind of multi-class classification where set of classes y can be decomposed into substructures. is worth analyzing the task since many works address the constraints in structured prediction. Some works give error bounds for structured prediction tasks, which are tighter than simply applying the bound for multi-class classification tasks [14] 6 17]. Similar to the case of multi- class classification, we show that existing Rademacher complexity-bet based bounds for the structured prediction of H are also the bounds for He.
Our main contributions are as follows: a) We introduce a concurrent verifier, which is a model- agnostic way guarantee that machine learning models satisfy the required properties. Although similar mechanism was used in some existing models, our model gives a generalization analysis that does not depend on specific model. b) We show that if hypothesis class H is PAC-learnable, then using a verifier at the inference time can give a hypothesis with a guarantee in its generalization error. Interestingly, if H is not PAC-learnable, we might fail to obtain guaranteed hypothesis even if the requirements are consistent with distribution D. c) We show that if we use CV in a learning phase of multi-class classification tasks, then the theoretical error bounds of H based on the Rademacher complexity will not increase with any input-output requirements. We also give similar results for structured prediction tasks.
1.1 Use Cases Concurrent Verifier
The following are some typical use cases for CVs.
Error-sensitive applications: A typical situation where we want to use verifier is that some prediction errors might cause severe effects, which we want to avoid. For example, a recommender system might limit the set of candidate items depending user attributes. Although such rule might degrade the prediction accuracy, practically a safer model is preferable.
Controlling outputs of structured prediction: Constraints are frequently used in structured predic- tion tasks for improving the performance or the controllability of the outputs. For example, some works [1 5 exploited the constraints sequence labeling tasks for reflecting background knowl- edge to improve the prediction results. More recently, some works [ exploited the constraints in language generation tasks, including image captioning and machine translation, and restricted

---

model to output sentence that includes given keywords. Since the constraints used in this previous work can be written as a logical formula, our CV model can represent them requirements.
Robustness against input perturbations: If machine learning model changes its output because modified its input from to x', which is very close x. then the model is described as sensitive against small change [25]. It might be a security risk if model is sensitive since its behavior unpredictable. Therefore, some methods evaluate and verify the robustness of neural networks against small perturbations [26 Existing verification methods check a machine learning model's robustness around input x by determining whether z' exists that is close to x and whether model gives different outputs, i.e., h(x)) & h(z'), for verification samples 21..... Zn. Although these verification methods can test a model, they do not directly show how to obtain robust model.
A CV can fix a model to achieve robustness around samples 21,-..,Ta Tn by setting a rule of form: "h(x") must equal h(x; if of is close xı."" Although this solution might not guarantee robustness choice.
where samples are scarce, adding enough non-labeled verification samples is often a reasonable
Related Work
Machine learning models that can exploit constraints have been investigated in many research fields, including statistical symbolic learning and structured prediction. For example, Markov logic networks (20), Problogs { and probabilistic circuit models [[T] integrate statistical models with symbolic logic formulations. Since these models can incorporate hard constraints represented by symbolic logie, they can guarantee input-output pairs. However, previous research focused on their practical performance and gave little theoretical analysis of their learnability when hard constraints are used. Morcover, previous works integrated the ability to exploit constraints into specific models. In contrast, our CV is model-agnostic and can be used in combination with wide range of machine learning models.
Recently, the verification of machine learning models has been gathering more attention. Attempts
have verfified whether machine learning model has the desired properties 4 26
10
24,
Exact
verification methods use integer programming (MIP) [26). constraint satisfaction (SAT)
[8] and
a satisfiable module theory (SMT) solver [10 to assess the robustness of a neural network model against input noise. These approaches aim to obtain models that fulfill the required properties. However, verification methods cannot help modify the models if they do not satisfy the requirements. If we want ML models to meet requirements, post-processing is needed as our concurrent verification model.
Other methods can give upper bounds on generalization error, including VC-dimension 27 and its extensions [9] Rademacher complexity [2], stability (23] and PAC-Bayes [
1 We use Rademacher complexity in the following analysis since it is among the most popular tools for giving theoretical upper bounds on generalization error. Rademacher complexity also has some extensions, including local Rademacher complexity [3] and factor graph Rademacher complexity (6. We can provide theoretical guarantees on these extended measures.
3 Preliminaries
Our notation follows previous work 222 We first introduce the notations used in the following sections. Let X' denote the domain of the inputs, let y be the domain of the labels, and let Z be the domain of the examples defined as Z : x y: Let H be hypothesis class, and let E H x Z + R., be a loss function. Training data S= (21, Zm,) E zm is finite sequence of size m drawn i.i.d. from a fixed but unknown probability distribution DD on Z. Learning algorithm A maps training data S to hypothesis h. We use notation A(S) denote the hypothesis that learning algorithm A returns upon receiving S. We represent set {1...., .....,,K K} as [K].
Given distribution D on Z, we denote by (h) the generalization error and by (s(h) the empirical error of over S, defined by
1 m
LD(h) = E =)], z>D
Ls(h)
E(h, z:).
(1)
m
3

---

PAC learnability: We introduce PAC learnability and agnostic PAC learnability as follows.
Definition 3.1. (Agnostic PAC learnability)) Hypothesis class H is agnostic PAC-learnable if there exists function mx (0, 1)2 + N and learning algorithm with the following property: For every e, E (0, 1) and distribution D over Z, if S consists of m 2 my (c, 8) ii.d. examples generated by DD then with at least probability 1 - ó, the following holds:
LD(A()) I min LD(h') +c.
(2)
WEH
Distribution D is realizable by hypothesis set H if ht E H exists such that LD(h") 0. If is realizable by agnostic PAC-learnable hypothesis H. then H. is PAC-learnable If H is PAC-learnable, then Eq. 2 becomes LD (AS)) S since minweH LD (h') = 0.
Rademacher complexity: the following sections, we use Rademacher complexity for deriving the generalization bounds. Given loss function L(h, z) and hypothesis class H. we denote G as
===6o H (= + ((h, z): : E H}.
Definition 3.2. (Empirical Rademacher complexity) Let G be family of functions mapping from Z to R. and let S = (Z1...., 2m) E 2d be the training data of size m. Then the empirical Rademacher complexity of G with respect to S is defined:
Rs( =
sup Σ ( 9E9
where σ = ( E [+1l are random variables distributed i.i.d. according to IP(o; = I] = PPao -1j= 1/2. The Rademacher complexity of G is defined as the expected value of the empirical Rademacher complexity:
Rm (m) = E [Rs(
5-Dm
4 Concurrent Verifier
Next we give a formal definition of a CV. A CV works with a machine learning model, which is function h X - + y. If x is given the model, which outputs h(x)) then the verifier checks whether (x, h(x)) satisfies the required property. We assume that the required property can be represented as requirement function e: (X' x )) + (0, 1}. If h(x)) c(z, h(x)) = 0, then it does not. Requirement function e can be represented by set of deterministic rules. For example. if X R and
1, then the pair satisfies the property; if
{0, 1). then the requirements can be in the following form: "if æ > 0, then # 0." We assume that for all possible input x E X. there exists E y such that c(x; y) for avoiding the situation where the requirements are unsatisfiable for any output y. This assumption can be easily relaxed if we allow machine learning model to reject unsatisfiable input
After checking the input-output pair, verifier modifies output h(x) depending the value of c(x, h((x). If c(x, h(x)) = 1, the verifier outputs l(()) since it satisfies the requirements. If cxx, h(x)) = 0, then the verifier modifies h(x) some y E Y that satisfies c(., 1. If we use verifier with machine learning model that corresponds to h, then the combination of the model and the verifier can be seen as function he X - V, defined as
(x) = { h(x)) if clx, A(x)) =
(3)
ye
if cf h(x)) 0
where Ve E y satisfies c(x, y.) = and is selected deterninistically. When y = [K], an example for selecting minimum i E [K] satisfying c(x, i) = 1 as ye is reasonable choice. When ) = =[K] and h(x)) is made by scoring functions h(x,,) y) : (X' x y) + R, is also reasonable to select y such that y" argmaxyey (et_))e((x.))]]_) h(x,, v). Learning model corresponds to selecting hypothesis h from hypothesis class H. Therefore, learning a model with CV corresponds to choosing a hypothesis from the modified hypothesis class: H. (he : E H). By definition, every hypothesis in H. satisfies the requirements, and thus we can guarantee that the model satisfies the condition if we select a hypothesis from H.. the following sections, we analyze the learnability of He by comparing with that of H.

---

Inference Time Verification
We first analyze the change of the generalization errors when we use a verifier only in an inference phase. In other words, requirements are unknown in the learning phase,and we estimate hypothesis h A(S) from hypothesis class H. by using training data S and algorithm A. In the inference phase, we use CV to modify h to he We call this setting the inference time verification (ITV). This class of situations contains many exciting settings: 1) pre-trained machine learning models used in wide range of applications, and 2) models that are hard replace, which might encounter different requirements from those at the learning time in the long run.
In this section,
multi-class classification setting. We set y = [K], and defined as fo.1 (h,, (ar y)) hy) where 1 is indicator function.
give analyses
hypothesis class H is set mappings h X' > [ We also assume that loss function e 0-1 loss
The following theorem shows situation where ITV works well: a situation where the generalization error of he does not exceed that of the other hypotheses in He with high probability.
Theorem 5.1. ffy [K], and hypothesis class H. PAC-learnable with 0-1 loss fo-1, training data S, and algorithm A, then suppose that h = A(S) is a hypothesis estimated form S satisfying (D(h) S for some parameter E (0, Then for any requirement c, hypothesis he obtained by modifying h with CV satisfies
Lo(he) S
min Lo(he) +E.
beEHc
We give proof in Appendix A. The proof bounds (h(h)) using the fact that it is close to Lp (ffc. where fo is obtained by modifying X Y satisfy LD(f) O. The theorem suggests that H is PAC-learnable, then inference time verification is sufficient to obtain hypothesis with small generalization error in He.
Note that the generalization error might increase with a verifier, and the amount of the increase is always larger than LD (fe). Therefore, LD(Je) represents the discrepancy between data distribution DD and requirement which is consistent with ʃ if c(x, f(x)) = for all x. If e is consistent with S. then LD(fe)= = 0, and we can certify that (D(ha) S c.
The above theorem shows that ITV works when H is PAC-leamable. However, this will not hold if D is not realizable with H. i.e, H is not PAC-learnable.
Theorem 5.2. If = [K]. the loss function is 0-1 loss la11 and hypothesis class H. is not realizable with D, and then there exists training data S, algorithm A, requirements c. and (0, 1) such that h = A(S) satisfies (h) S minkeR (h) + but (h(h)) > min (D +
We give in Appendix B proof that shows counterexample even if is consistent with ground truth f. The above thcorems show that the realizability of H. is the key factor that distinguishes among the cases where ITV works well. Moreover, unlike the realizable case, Theorem 5.2 holds even if requirement e consistent with distribution D. Let fo : X y be defined as the Bayes optimal predictor:
fo(z) = argmax Ply z). MEY
The Bayes optimal predictor is optimal, in the sense that for every other classifier g : X V, LD(fD) Lg(g). Theorem 5.2 if is consistent with fp. These results show that existing methods using constraints only in the inference time might fail to select the best hypothesis.
Using a CV increases the time needed for inference. Suppose that a verifier is an oracle that can answer the query about the value of c(z, y). To achieve previously shown modification procedure ( we need at most K queries.
Running time analysis:
Learning Time Verification
In Section 5 we show that H PAC-learnable with 0-1 1 loss, then modifying a hypothesis at the inference time is sufficient to obtain hypothesis with the smallest generalization error while
5

---

satisfying the requirements. If H. is not PAC-learnable, then the ITV scheme might fail to obtain hypothesis with small generalization error. Here we show that the generalization enror can be bounded when we use CV in the learning phase. We call this setting learning time verification (LTV).
Since the LTV scheme corresponds learning task where the hypothesis class is He, we analyze the Iearnability of H. using the standard tools for generalization analyses. This paper provides analyses based on Rademacher complexity since its a widely used tools that can give tight bounds for both data-dependent and data-independent cases. Moreover, some previous work gives bounds of structured prediction tasks using Rademacher complexity. In the literature, constraints are actively used in structured prediction tasks, including language generation and sequence labeling. Therefore, analyzing the generalization error is important when using a CV on structured prediction tasks.
In the following, we first show the upper bounds of generation error based on the Rademacher complexity of He in multi-class classification task 1, 6.2) and a structured prediction setting ($6.3). Our main finding is that the upper bounds based on the Rademacher complexity of He are always less than or equal to those of H. Therefore, adding CV a machine learning model will not degrade its learnability.
6.1 Multi-class Classification
We first give the Rademacher complexity-basee error bounds multi-class classification task, ie.. y= [K]. In this section, we show that a standard upper bound [16] based on the Rademacher complexity of H. can be used an upper bound of H. for any requirement In the next section, show that a state-of-the-arr error bound, based on local Rademacher complexity H. can also be used as upper bound of He.
Following previous works, let h : (X' y) + R be a scoring function, and define hypothesis class H as set of scoring functions. A scoring function defines mapping from X' to ):
x ト argmax 1(,, y) yEy
Let (z, y) be the margin of function of h:
Ph (r v) = h(x,,) max (x,y'). V'
Hypothesis h misclassifies the labeled example (x, y) if pn y) S O. Thus, by using a margin function, the 0-1 loss can be represented as lo-1 (h, 2) 1 (2.)) Since 0-1 loss is hard to handle during learning, we use margin loss (h, (x, u)) tb (p, where (1(() is defined as
$ (t)) = min(1, max(0, t/p))
Function f: R - R is said to be y-Lipschitz if (f( - f(t)) S p t' for any t, E R. o is an 1/p-Lipshhizz function. The empirical margin loss of hypothesis is defined
(h)
Identical the case of ITV, introducing CV to machine learning model corresponds to modifying its corresponding hypothesis class H. to hypothesis class He that is consistent with requirement c. h is score function, then define consistent function he:
ho(o, 9) = h(x, v)
if cf v) =
M
if (f(
where M is positive constant satisfying M > (ax h(,, v)]- As described in Section 4 assume that there exists y y that satisfies e(z, v) 1 for all æ E X. Therefore, we can guarantee that Ph. (x.y) v) < 0 if c(x, y) = O.
The following are the main results of the general multi-class learning problem, which is based on the margin bound shown in Theorem 9.2 Mohri al. [66. Our main finding that the generalization error of any hypothesis, ht. is bounded by the Rademacher complexity of hypothesis set H. which suggests that we have a tight bound for hypothesis class H. then we can expect to find a good hypothesis from He under any requirements c.

---

Theorem 6.1. Let H. S RxxY be a hypothesis class with y = [K] and let e be requirement. Fix p > Then for any with probability least the following bound holds for all he E Ho
LD (b((h)) S L.s + 4K
log 2m
Rm (I((H)) =1
p
where IT (H) is defined
11 11 ( h(2, EE
We give a proof in Appendix C. We obtain the results by showing that the upper bounds of the Rademacher complexity of He are bounded by some upper bounds of the Rademacher complexity of H. All the proof's of the theorems in this section use similar techniques. Parameter / sets the margin value. Following a previously shown technique [16), we obtain generalized bound that holds uniformly for all > 0. The above theorem suggests that using a CV at learning phase does not worsen the error bound for any requirement c. Intuitively, the theorem seems reasonable since requirements imposes restriction H. and thus the complexity of H. is not larger than H. However, it is not so trivial since He S H is not always true.
Running time analysis: We analyze the number of evaluations c(ar, y) required for learning with CV. Let S1 be a sub-sequence of training example S such that c(z,, yt) 1, and let So be sub-sequence such that c(2,, vi) = O. If we use 0-1 loss function, then the empirical loss of hypothesis he is
In.(a)) + SSa m
Ls(he)
Σ (x..))))
since every he misclassifies the examples in Sg. Therefore, we need at most K|Si| + |So] queries for the learning process. This is also true when we use margin loss function. On the other hand, the problem of estimating the best hypothesis might be more difficult than the original problem depending on requirement c.
6.2 Tighter Bound Based on Local Rademacher Complexity
The bound for H. shown in the previous section is relatively simple, and tighter bounds of H based on the Rademacher complexity have been developed in the literature. In this section, we show that the state-of-the-art error bound for H based on the local Rademacher complexity be used bound for H. for any requirements. c.
Definition 6.2. Let G be a family of functions from to R, and let S be training data of size m. Then for any 0, the empirical local Rademacher complexity of G is defined
Rg(G;r) Rg ((ag : a E [0, 1),9 9, (ag)) S <r)
Li et al. 13 showed tighter generalization bound for multi-class classification problem using the local Rademacher complexity when the hypothesis class is a Ep norm hypothesis space with kernel x, defined as
Hpp. {h-
(w.. o(x)) ||wl|2,0
where is represented as vector valued function (hi....,hk) with h2(z) h(,, ((z.)). vj. 1...., K. and w: X x X + IR is a Mercer kernel with associated feature map o. i.c.
is the 22,r- For any p 2 1, let 9 be the dual exponent of satisfying 1 1/p+ 1/9 = 1. Let R R be a loss function satisfying the following: 1) (t) < (tt) for all 2) (tt) is decreasing and has zero point Cp; 3) &b is {-smooth, that is, (t) 4 (t')) < Çlt -'
(o(x), ((x)). w = (wi,... wx). and ||w|| = Σ |w|6
Let Hp.n.. be the hypothesis class obtained by modifying hypothesis Hp., to satisfy requirements and L. ((x;, y) + (pph (I, v)) he E Hp.ne).. The following theorem gives a bound of the local Rademacher complexity of Lo.
7

---

y/3
f2
y1
f1
3/2
fz
ys
8/1
fi
3/2
(b)
Figure Example of factor graphs: (a) represents decomposition h(,, y) = h U1. +
h y2, ys) and (b) represents decomposition h(2, y) = h (z. vı, (2) - ( yr U2, Uz).
Theorem 6.3. Let Hp...c be the set of hypotheses obtained by modifying hypothesis h Hp. with requirement c. For any with probability least 1 6, the following bound holds:
Rm (C Ca,oE(K) log (m)
4llog !
Vm
where 1- supzex x(x,I) 00, suPiER 2()) oc, and Cd.0 is a constant. E(K) is
S(K) { Ve(4log K) + H
if 2og K, otherwise
(2q) (2q)²++ K
We give proof in Appendix D. The bound equals that of R,, (C; r) (Theorem of [3] for any requirement e and any hypothesis Hp... Therefore, the generalization error bounds based on Theorem 1 of Li et al. [3] holds for any requirement
6.3 Analyses of Structured Prediction
Structured prediction is a kind of multi-class classification task, where label set ) might be set of sequences, images, graphs, trees, or other objects admitting some possibly overlapping structure. As mentioned in Section 1 previous works try to impose constraints the output of structured prediction tasks. Thus is also useful derive error bounds for structured prediction tasks when we use CV. In the following, we show that the Rademacher complexity-basee generalization error bounds derived in a seminal work Cortes et al. [6] also hold we use a CV. Although tighter bounds given in more recent work their simplicity.
we give bounds based Cortes et al. [6] due to
We give some definitions for the structured prediction task. Following previous work, we assume that y decomposable along with substructures: y = V1 x ... 3/. Here V%s is set of possible labels that can be assigned to the k-th substructure. We denote by L / ) - IR a loss function that measures dissimilarity of two elements of output space y. L is definite, that is, L(y, s/) = iff y == y'. A typical definite loss function for structured prediction task is the Hamming loss defined by L(v, v') El=1 yu for all y (V1.-.., Wt and y' (Vi,..., vf), with yk- 2 E Vk- Other typical examples of loss functions can be in Cortes et al. (6. Using loss function L, the generalization and empirical error of are defined:
1 m
LD(h)
E L(h(x),)), (a.4)~
Ls(h)
m Σ L(h(z).v)
As with the multi-class classification task, hypothesis class H can be represented set of scor- ing function h X' x y + R. We use h(z) to represent the predictor defined by E H: h(z)= argmaxyey 1(x,, y) for all E X. Following the previous work, assume that each scoring function can be decomposed as a sum, and such decomposition follows factor graph. Factor graph G is tuple G F, E), where V is set of variable nodes, F is set of factor nodes, and is a set undirected edges between a variable node and a factor node. Every node V corresponds substructure index, where V (I,...,().
For any factor node f. we denote by W() C V a set of variable nodes connected to f and define V substructure set cross cross-product D7, II Dk. Then h admits the following decomposition as

---

sum of functions n,, each taking as an argument pair of (z. E & x D/y
h(z, v) Σ SEF
(5)
Figure 2 shows examples of decompositions based on factor graphs. We conventionally assume that the structure of the factor graphs may change depending on particular example (#i, y/): G(r; 1i) = G2 ([4), Fi, F.).. A special case of this setting is when size I of each example is allowed to vary. In such a case, the number of possible labels y is potentially infinite.
Following multi-class classification, our CV maps hypothesis to he to satisfy the requirements. The definition of he follows Eq. ( This definition does not require he to have factored representation.
For analyzing the complexity, Cortes et al. 6 introduced empirical factor graph Rademacher complexity Rg(HH of hypothesis class H. for S (Z1,..., Zm) and factor graph G:
RG(H)
1 m
sup ΣE Σ VIElesss NEH MEF:
where E = (Ei.f.y)EE ml mi..EFF..EE and every 6.f.y is i.i.d. a Rademacher random variable. Factor graph Rademacher complexity of for factor graph G' is defined as expectation
R (H)
= E S~D
(H)))
By using the factor graph Rademacher complexity, Cortes et al. (6 gives bounds for structured prediction task with the following additive and multiplicative empirical losses:
L.p (h)
=
max L(y', y:) (M(2), v6) MoZe)))) AM
P
i=1
m
max L(y yi) (1-1 (h(x). v.) h( //)) y//'
mult S.p
(h)
772
where (t) min( B, ma t)) for all t, with B = max L(y. y'). As shown in (6). these loss functions cover typical surrogate loss functions used in structured prediction tasks. We show the following bound for structured predictions.
Theorem 6.4. Fix p > O. For any 8 > 0 and requirement with probability at least 1 - over the draw of sample S of size m from distribution D, the the following holds for all he E Ho
4/2
log
Lo(he) S (ha) S andd (he) + RC (H) + BV
8
2m
4/2B R (H) + BV
log
Lo(he) < Lmmui((h)) (be)) < L (ha) +
2m
We give a proof in Appendix E. is a parameter that determines the margin. Similar to the case of multi-class classification, we can derive a bound that holds for any p > following previous derivation [6]. The above result indicates that the bound will not change if we use CV for any requirement This is interesting since the above result holds even if we do not have a factored representation of ha( y), similar to Eq. ( although the derived bound depends on the factor graph Rademacher complexity, which depends on the factored representation of h(x, y)-
We analyzed the overhead of the running time for evaluating loss function Ladd and mull (he) for hypothesis h.. Different from the multi-class classification case, both the number of queries and overhead of the running time for the loss evaluation when we use CV depend on the model and the type of requirements for structured predictions. This result is consistent with the literature, which reports that for structured prediction tasks, original tractable optimization problems can be intractable if we put additional constraints 21

---

7 Conclusion
This paper gives a generalization analysis when there are requirements that the input-oulput pairs of a machine learning model must satisfy. We introduce concurrent verifier, simple module that enables us to guarantee that the input-output pairs of a machine learning model satisfy the requirements. We show situation where the inference phase. Interestingly, if H. is not PAC-learnable we might fail to obtain a guaranteed hypothesis even if the requirements consistent with distribution D. We also give the generalization bounds based on Rademacher complexity when we use a verifier in learning phase and find that the obtained bounds are less than equal to the existing ones, independent of the machine learning model and the type of requirements.
obtain a hypothesis with small error when use verifier only in
Acknowledgements
The authors thank the anonymous reviewers for their valuable feedback, corrections, and suggestions. This work was supported by JST PRESTO (Grant Number JPMJPR20C7, Japan), JST CREST (Grant Number JPMICR22D3, Japan) and JSPS KAKENHI (Grant Number JP20H05963, Japan).
References
Pierre Alquier. User-friendly introduction to pac-bayes bounds. ArXiv, 1tbs//110.1121111 2021.
[2] Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. Guided open vocabulary image captioning with constrained beam search. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 936-945, Copenhagen, Denmark, September 2017. Association for Computational Linguistics.
[3] Peter Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482 2003.
[4] Rudy R Bunel, liker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piecewise lincar neural network verification. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[5] Ming-Wes Wei Chang, Lev Ratinow, and Dan Roth. Structured learning with constrained conditional models. Mach. Learn., 88(3):399-43 -3.199999111.00 sep 2012.
[6] Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, and Scout Yang. Structured prediction theory based factor graph complexity. Advances Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[7] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. J. Mach. Learn. Res., 16(1):2377-2404, jan 2015.
[8] Lue De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: A probabilistic prolog and its application in link discovery. In Proceedings of the 20th International Joint Conference on Artificul Intelligence, page 2468-244 2263,, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
[9] Chris Hokamp and Qun Liu. Lexically constrained decoding for sequence generation using grid beam search. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pages 1535 1546, Vancouver, Canada, July 2017. Association for Computational Linguistics.
[10] Guy Katz, Clark Barrett, David I.. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In Rupak Majumdar and Viktor Kunčak, editors, Computer Aided Verification, pages 97-117, Cham, 2017. Springer International Publishing.
[11] Doga Kisa, Guy Van Broeck, Arthur Choi, Adnan Darwiche. Probabilistic sentential decision diagrams. In Knowledge Representation and Reasoning Conference, 2014.
[12] V. Koltchinski and D. Panchenko, Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50. 2002.
10

---

[13] Jian Li, Yong Liu, Rong Yin, Hua Zhang, Lizhong Ding. and Weiping Wang. Multi-class learning: From theory to algorithm. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[14] Shaojie Li and Yong Liu. Towards sharper generalization bounds for structured prediction. In Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021.
[15] David A. McAllester. Some pac-bayesian theorems. In Proceedings of the Eleventh Annual Conference on Computational Learning Theary, page 230-234, New York, NY, USA, 1998. Association for Computing Machinery.
[16] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
[17] Waleed Mustafa, Yunwen Lei, Antoine Ledent, and Marius Kloft. Fine-grained generalization analysis of structured output prediction. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, pages 2841-2847. International Joint Conferences on Artificial Intelligence Organization, 2021. Main Track.
[18] Nina Narodytska, Hongee Zhang, Aarti Gupta, and Toby Walsh, In search for sat-friendly binarized neural network architecture. In International Conference on Learning Representations, 2020.
[19] B. K. Natarajan. learning sets functions. Mach. Learn., 4(1):67-97, 1989.
2006. [21] Dan Roth and Wen-tau Yih. Integer linear programming inference for conditional random fields. In Proceedings of the 22nd international conference Machine learning, pages 736 743, 2005.
[20] Matthew Richardson and Pedro Domingos. Markov logic networks. Mach. Learn.,
[22] Shai Shalev-Shwartz and Shai Ben-David Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014.
[23] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srehro, and Karthik Sridharan, Learnability, stability and uniform convergence. J. Mach. Learn, Res.. 11:2635--220 2172655-6670,, dec 2010.
[24] Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Pliccell, and Martin Vechev, Fast and effective robustness certification. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. R. Gamett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
and
[25] Christian Szegedy. Wajciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
[26] Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. International Conference on Learning Representations, 2019.
[27] V.N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events their prohahilities. Theory of Probability & Its Applications, 16(2):264-280, 1971.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], or [N/A] You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
11

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss conditions verifier does not work well in Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We give proof in Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "N0fzTjMnaUc", "reviewer": "Reviewer_uBfe", "summary": "This paper considers the problem of introducing a concurrent verifier either in the learning or inference phase in the setting of PAC learning.  A concurrent verifier checks if the predicted output satisfies a given requirement (represented as a constraint).  If so, it doesn't change the predicted output.  Otherwise, it forces the output to take a value that satisfies the requirement.  The authors consider the generalization error of learning with concurrent verifiers in the inference and in the learning phase, and show that (a) under the realizability assumption, learning with concurrent verifier in the inference phase doesn't suffer from too much generalization error; (b) for learning with concurrent verifier in the learning phase, the authors use the Rademacher complexity based generalization error bounds and show that these don't increase in the presence of concurrent verifier in the learning phase.  The authors also provide analysis of the running time overhead of using a concurrent verifier in the different settings.  They also describe a structured prediction setting where their theory is applicable.  This is a theoretical paper with no experimental results.", "questions": "Questions:\n1. Section 5: In the ITV setting, what happens with non 0-1 loss\nfunctions? It doesn't look like the proof of Theorem 5.1 will go\nthrough in this case in general.\n\n2. Line 194 and 199-200: This is a bit mis-leading.  You have not\nmentioned the role of the loss function being a 0-1 loss function at\nall.  Not only must D be realizable with H, but we also require the\nloss function to have special properties.\nShouldn't you change the presentation here?\n\n3. Shouldn't the statement of Theorem 5.2 also include \"Suppose\nhypothesis class H is PAC-learnable\"?  \n\n4. Lines 274-275: What is \"f\" in statement of Definition 6.2? \n\n5. The analysis of running time at the end of Section 6.3 is really\nsketchy and doesn't say much concretely.  Why can't this be explained\nbetter?\n\n\nSome typos and readability hurdles:\nLine 156: \"if we all a machine\": sounds incorrect\n\nLine 191: The notation f_c is introduced suddenly here without any\nprevious reference in the main paper.  This is inherited from Appendix\nA, so unless somebody reads the appendix, they will be confused.\n\nLine 196: Theorem 5.2 -- the statement of the theorem sounds strange.\nWe are talking about a specific distribution D that is not realizable\nwith hypothesis class H.  So why do you say \"Then, there exists D, ...\"\n\nLine 223: \"generation error\" --> \"generalization error\"\n\nTheorem 6.3 and the remainder of Section 6.2 are written in a way that\nis hard to read and understand.  This part should certainly be\nre-written.\n\nLabel of Fig. 2(b): Shouldn't we have h_{f_1}(x, y_1, y_2) instead\nof h_{f_1}(x, y_1, y_3)?\n\n", "limitations": "The authors have discussed the limitations of their approach to some extent.  There is no potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Very relevant problem\n2. The results are good and show when the use of concurrent verifiers is beneficial.\n3. The results expand our current understanding of learning/predicting with concurrent verifiers\n4. The presentation introduces the relevant theory and definitions, making it easier to read.\n\n\nWeaknesses:\n1. The paper is very dense, particularly the statement of the main technical results.  Shifting the proofs to the appendix but not providing any intuition behind the proofs makes it hard to understand the intuition behind the main theorems.\n2. The running time complexity analysis for using the concurrent verifier is a bit sketchy.  This is particularly so in Sec 6.3\n3. The math is often hard to follow for the general reader.  The paper is unnecessarily notationally heavy at places.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "92WSbPsVs9J", "reviewer": "Reviewer_PVsA", "summary": "The paper proposes a monitor that observes the input and output of a machine learning model and checks if they satisfy requirements. Two scenarios are investigated - first when the monitor is only present at inference time and the second when the requirement is known at training time.", "questions": "- What is fc in Line 191/192? A symbol table in the paper will make it more tractable specially because the theorem and proof are split between the main paper and the appendix. \n\n- Introducing the concurrent verifier can actually lead to increased generalization error based on equation 187. The surprising (and useful) result would upper bound L_D(Hc) instead of lower bound it. \n\n- Looking at the proof of Theorem 5.2, it appears we need to constrain c in some way and the degenerate choice of c is why we get negative result in Theorem 5.2. Can authors help identify a practical scenario or give some intuition where such a c would be defined over input/output?\n\n\n\n", "limitations": "There are no potential negative societal impact of the work to the best of this reviewer's understanding.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ If a hypothesis class H is PAC learning, then using the verifier at inference stage can give a hypothesis with a guarantee in its generalization error.\n\n+ When requirements are known in training phase, then the input/output requirements do not increase the Rademacher complexity. \n\n- The proofs in appendix are dense and difficult to follow while the theorem statements themselves appear to be rather unsurprising - the clarification questions will help the reviewer better understand the significance of this work. \n\n- The Rademacher bound appears to be straightforward adaption of standard result. It is not clear why one would expect Hc to have higher complexity than H.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7TRXaOGfwla", "reviewer": "Reviewer_TPUk", "summary": "The paper analyzes the generalization bounds of ML models augmented with concurrent verifiers.\nAs background it presents PAC learnability and Rademacher complexity, and then it introduces concurrent verifiers.\nIt shows how generalization changes when a verifier is applied to a model at inference time when both when the hypothesis space is realizable and when it is not: when H is PAC learnable with 0-1 loss, inference time verification (ITV) gives the minimum possible generalization error while satisfying the constraints; when H is not PAC learnable, this is not obtained. The paper also considers learning time verification (LTV), using Rademacher complexity to show that adding a concurrent verifier to a model at learning time does not reduce its learnability, giving bounds both for multiclass prediction and structured prediction.\n", "questions": "* Do you have intuitive explanations for each of the results that could enhance the clarity of the paper?\n* Are there practical settings where the Rademacher complexity based error bounds are known to be meaningful/not terribly loose, and also in which a verifier is useful?\n* You show that Rademacher complexity based error bounds will be not larger than those of the original model when a CV is added in. How does this then allow you to conclude that the CV doesn't hurt the model's generalizability (line 15)? For example in modern ML systems my understanding is that typical generalization performances can be _well_ within these bounds, and hence preserving the bounds does not directly entail preserving generalization.\n", "limitations": "The conditions in the theorems capture the limitations of the results. e.g. for ITV the generalization guarantee requires that H is PAC learnable.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\n\nThe results are original, drawing upon bounds derived in earlier work and extending them to the concurrent verifier settings.\nThe background material is both cited appropriately and explained clearly. The relevant bounds built upon are cited, and tighter bounds that are not built upon (but perhaps could be) are also referenced.\n\n### Quality\n\nAll claims are well supported, with proofs provided in the appendices. I have only verified the proofs through section 5, not those of section 6. I have not found evidence of anything unsound in my review, and the results are sensible, so I expect even the proofs I have not verified thoroughly will be sound too.\n\n### Clarity\n\nThe submission is well written and well organized. The background material is clearly explained. Most concepts are introduced prior to their use (at least up until line 280; e.g. Mercer kernels are not introduced).\n\nThe following are largely typographic suggestions, but these issues do not meaningfully degrade the overall quality of the paper.\n* nit: Line 134 consists should read \"consisting\"\n* nit: Line 156 \"all\" should be \"allow\"\n* Line 185, it should say \"sample\" rather than \"example\", yes?\n* nit: Line 185, s/be/is\n* Line 191: The notation $f$ and $f_c$ is only introduced in the Appendix, and so seems out of scope here\n* <strike>Line 237: if $\\rho_h = 0$, is this necessarily a misclassification?</strike>\n* Line 275: What does $f$ refer to in the definition of empirical local Rademacher complexity?\n\n### Significance\n\nThe new setting, machine learning with a concurrent verifier, is an important setting for many application domains. I do not know whether the bounds are relevant/meaningful in these application domains in practice, as my understanding is that in modern ML systems typical generalization performances can be well within the bounds given by Rademacher complexity. Nevertheless, the setting is an important one and the results are (to the best of my knowledge novel, and so tell us important properties of how generalizability can change / remain unchanged when a verifier is applied both during learning and at inference time to a pretrained model.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept