Learning with Explanation Constraints
Authors: Rattana Pukdee
Dylan Sam
J Zico Kolter
Nina Balcan
Pradeep Kumar Ravikumar
Venue: NeurIPS 2023 poster (2023)
Keywords: Interpretable ML
Semi-supervised learning
Learning theory
TL;DR: We provide a learning theoretic framework to understand the benefits of incorporating explanation constraints in the standard supervised learning setting.

Abstract: As larger deep learning models are hard to interpret, there has been a recent focus on generating explanations of these black-box models. 
In contrast, we may have apriori explanations of how models should behave. In this paper, we formalize this notion as learning from explanation constraints and provide a learning theoretic framework to analyze how such explanations can improve the learning of our models.  One may naturally ask, "When would these explanations be helpful?"
Our first key contribution addresses this question via a class of models that satisfies these explanation constraints in expectation over new data. We provide a characterization of the benefits of these models (in terms of the reduction of their Rademacher complexities) for a canonical class of explanations given by gradient information in the settings of both linear models and two layer neural networks. In addition, we provide an algorithmic solution for our framework, via a variational approximation that achieves better performance and satisfies these constraints more frequently, when compared to simpler augmented Lagrangian methods to incorporate these explanations. We demonstrate the benefits of our approach over a large array of synthetic and real-world experiments.

Learning with Explanation Constraints
Rattana Pukdee' Carnegie Mellon University rpukdee@cs. cmu. edu
Dylan Sam' Carnegie Mellon University dyl arlaansa@@andre cmu. edu
J. Zico Kolter
Carnegie Mellon University Bosch Center for AI zkolterêcs, cmu, edu
Maria-Florina Balean Carnegie Mellon University ninamf@cs cmu. edu
Pradeep Ravikumar
Carnegie Mellon University pkrocs. cmu. edu
Abstract
As larger deep learning models are hard interpret, there has been recent focus on generating explanations of these black-box models. In contrast, we may have apriori explanations of how models should behave. In this paper, formalize this notion as learning from explanation constraints and provide a learning theoretic framework to analyze how such explanations models. One may naturally ask, "When would these explanations be helpful?" Our first key contribution addresses this question via class of models that satisfies these explanation constraints in expectation over new data. We provide a characterization of the benefits of these models (in terms of the reduction of their Rademacher complexities) for a canonical class of explanations given by gradient information in the settings of both linear models and two layer neural networks. In addition, we provide an algorithmic solution for our framework, via variational approximation that achieves better performance and satisfies these constraints more frequently, when compared to simpler augmented Lagrangian methods to incorporate these explanations. We demonstrate the benefits of our approach over large array of synthetic and real-world experiments.
improve the learning of
Introduction
There has been considerable recent focus generating explanations of complex black-box models so that humans may better understand their decisions. These can take the form feature importance [31, 35), counterfactuals [31, 35], influential training samples [18, 43], etc. But what if humans were able to provide explanations for how these models should behave? We are interested in the question of how to learn models given such apriori explanations. A recent line of work incorporates explanations as a regularizer, penalizing models that do not exhibit apriori given explanations [33, 32, 15, 36]. For example, Rieger et al. [32] penalize the feature importance of spurious patches on a skin-cancer classification task. These methods lead to models that inherently satisfy "desirable" properties and, thus, are more trustworthy. In addition, some of these empirical results suggest that constraining models via explanations also leads to higher accuracy and robustness to changing test environments. However, there is no theoretical analysis to explain this phenomenon.
We note that such explanations can arise from domain experts and domain knowledge, but also other large "teacher" models that might have been developed for related tasks. An attractive facet of the latter is that we can automatically generate model-base explanations given unlabeled data points. For instance, we can segmentation models to select the background pixels of images solely
Equal contribution
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Labeled deta
fx
f
DO sTptrial oxplatation
H
Hqg
Untabaled
Sasiayy canso
data
Pxplonetion ion Constraints
Teache model
f
Figure 1: A restricted hypothesis class Ho.a (left). Our algorithmic solution to solve a proposed variational objective in Section 5 (right).
unlabeled data, which we can in model training. We thus view incorporating explanation constraints from such teacher models as a form of knowledge distillation into our student models [13].
In this paper, we provide an analytical framework for learning from explanations to reason when and how explanations can improve the model performance. We first provide mathematical framework for model constraints given explanations. Casting explanations as functionals that take in a model h and input æ (as is standard in explainable AI), we can represent domain knowledge of how models should behave as constraints on the values of such explanations. We can leverage these to then solve constrained ERM problem where additionally constrain the model to satisfy these explanation constraints. Since the explanations and constraints are provided on randomly sampled inputs, these constraints are random. Nevertheless, via standard statistical learning theoretic arguments [38], any model that satisfies the set of explanation constraints on the finite sample can be shown to satisfy the constraints in expectation up to some slack with high probability. In our work, we term model that satisfies explanations constraints in expectation, an CE model (see Definition 1). Then, we can capture the benefit of learning with explanation constraints by analyzing the generalization capabilities of this class of CE models (Theorem 3.2). This analysis builds off of learning theoretic framework for semi- semi-supervised learning of Balcan and Blum [1. 2]. We remark that if the explanation constraints arbitrary, it is not possible reason if model satisfies the constraints in expectation based on a finite sample. We provide a detailed discussion on when this argument is possible in Appendix B,D. In addition, note that work also has connection with classical approaches in stochastic programming [16, 4] and is worth investigating this relationship further.
Another key contribution of our work is concretely analyzing this framework for a canonical class of explanation constraints given by gradient information for linear models (Theorem 4.1) and two layer neural networks (Theorem 4.2). We focus on gradient constraints as we can represent many different notions of explanations, such as feature importance and ignoring spurious features. These corollaries clearly illustrate that restricting the hypothesis class via explanation constraints can lead to fewer required labeled data. Our results also provide a quantitative measure of the benefits of the explanation constraints terms of the number of labeled data. We also discuss when learning these explanation constraints makes sense or is possible (i.e., with a finite generalization bound). We note that our framework allows for the explanations to noisy, and not fully satisfied by even the Bayes optimal classifier. Why then would incorporating explanation constraints help? As our analysis shows, this by reducing the estimation error (variance) by constraining the hypothesis class, at the expense of approximation error (bias). We defer the question of how to explicitly denoise noisy explanations future work.
Now that we have provided a learning theoretic framework for these explanation constraints, we next consider the algorithmic question: how do we solve for these explanation conitionnnontraineed models? In general, these constraints are not necessarily well-behaved and are difficult to optimize. One can use augmented Lagrangian approaches [33, 7], or simply regularized versions of our constrained problems [32] (which however do not in general solve the constrained problems for non-convex parameterizations but is more computationally tractable). We draw from seminal work in posterior regularization [9], which has also been studied in the capacity of model distillation [14], provide a variational objective. Our objective is composed of two terms; supervised empirical risk and the discrepancy between the current model and the class of CE models. The optimal solution of our objective is also the optimal solution of the constrained problem which is consistent with our theoretical analysis. Our objective naturally incorporates unlabeled data and provides simple way to

---

control the trade-off between explanation constraints and the supervised loss (Section 5), We propose tractable algorithm that iteratively trains a model on the supervised data, and then approximately projects this learnt model onto the class of CE models. Finally, we provide an extensive array of experiments that capture the benefits of learning from explanation constraints. These experiments also demonstrate that the variational approach improves over simpler augmented Lagrangian approaches and can lead models that indeed satisfy explanations more frequently.
2 Related Work
Explainable AI. Recent advances in deep learning have led to models that achieve high performance but which are also highly complex [20, 11]. Understanding these complex models crucial for safe and reliable deployments of these systems in the real-world. One approach to improve our understanding of a model is through explanations. This can take many forms such as feature importance [31, 35, 23, 37J, high level concepts [17, 44], counterfactual examples [39, 12, 25], robustness of gradients [41]. or influential training samples [18, 43].
In contrast to generating post-hoc explanations of a given model, we aim to learn models given apriori explanations. There has been some recent work along such lines. Koh et al. [19], Zarlenga et al. [45] incorporates explanations within the model architecture by requiring a conceptual bottleneck layer.
Ross et al. [33]. Rieger et al. [32], Ismail et al. [15], Stacey et al. [36] use explanations to modify the learning procedure for any class of models: they incorporate explanations as regularizer, penalizing models that do not exhibit apriori given explanations; Ross et al. [33] penalize input gradients, while
Rieger al. [32] penalize Contextual Decomposition score [26]. Some of these suggest that constraining models via explanations leads to higher accuracies and more robustness to spurious correlation, but do not provide analytical guarantees. On the theoretical front, Li et al. [22] show that models that are easier to explain locally also generalize well. However, Bilodeau et al. [3] show that common feature attribution methods without additional assumptions on the learning algorithm or data distribution do no better than random guessing at inferring counterfactual model behavior.
Learning Theory. Our contribution is to provide an analytical framework for learning from expla- nations that quantify the benefits of explanation constraints. Our analysis is closely related to the framework of learning with side information. Balcan and Blum [2] shows how unlabeled data can help in semi-superviee
learning through notion of compatibility between the data and the target model. This work studies classical notions of side information (e.g., margin, smoothness, and co- training). Subsequent papers have adapted this learning theoretic framework to study the benefits of representation learning [10] and transformation invariance [34]. On the contrary, our paper focuses on the more recent notion of explanations. Rather than focus on the benefits of unlabeled data, we characterize the quality of different explanations. We highlight that constraints here are stochastic, as they depend on data points which differs from deterministic constraints that have been considered in existing literature, such constraints on the norm of weights (i.e., 1.2 regularization).
Trainiran Our work can also be connected to the self-training literature [5, 42, 40, 8), where we could view our variational objective comprising regularized (potentially simpler) teacher model that encodes these explanation constraints into a student model. Our variational objective (where we use simpler teacher models) is also related to distillation, which has also been studied in terms of gradients [6].
3 Learning from Explanation Constraints
Let X' be the instance space and y be the label space. We focus on binary classification where y = [-1,1,, 13. but which can be naturally generalized. Let D be the joint data distribution over (XY and Dx the marginal distribution over X. For any classifier / X + V, we are interested in its classification error err(h) := P((z.))>(((h())) + y). though one could also use other losses to define classification error. Our goal is to learn classifier with small error from family of functions H. this work, we use the words model and classifier interchangeably. Now, we formalize local explanations as functionals that take in a model and test input, and output vector:
Definition (Explanations). Given an instance space X, model hypothesis class H. and an explana- tion functional g : H. x X' + R", we say g(h, x)) is explanation of h on point x induced by g.
3

---

For simplicity, we consider the setting when g takes a single data point and model as input, but this can be naturally extended to multiple data points and models. We can combine these explanations with prior knowledge on how explanations should look like at sample points in term of constraints,
Definition 2 (Explanation Constraint Set). For any instance space X. hypothesis class H. an explanation functionaal g H x X - RR, and a family of constraint sets {C(x) S R x 2}, we say that h E H satisfies the explanation constraints with respect to iff:
(h, x) E Cx)),, Vx E X.
In our definition, (xx) represents values that we believe our explanations should take at a point x. For example, "an input gradient of feature must be larger than feature 2" be represented by g(h, 2) = Va)(fr) and C(x)= be able to provide the constraint set C(x') for random sample l data points SE = { {.i......0 z.4] drawn i.idd. from Dx. We then say that any E H. Sg-satisfies the explanation constraints with respect C' iff gh,, E C(x), Vr Sg. We note that the constraints depends on random samples s and therefore are random. To tackle this challenge, we can draw from the standard learning theoretic arguments to reason about probably approximately satisfying the constraints in expectation. Before doing so, we first consider the notion of explanation surrogate losses, which will allow us to generalize the setup above to a form that is amenable to practical estimators.
Idd E IRd x > 22). In practice, human annotators will
Definition 3. (Explanation surrogate loss) An explanation surrogate loss 6 H x X + R quantifies how well model h satisfies the explanation constraint g(h,,) x) E C(r). For any h H E X:
1. ((h,))20 O.
2. If (h) x)) E C(x) then 6(h,,)) 0.
For example, could define x)) 1 ((g( x) E C(x)). Given such surrogate loss, we can substitute the explanation constraint that g( ) E C(z) with the surrogate ((h, .) S 0. We now have the machinery to formalize how to reason about the random explanation constraints given random set of inputs. First, denote the expected explanation loss Φ(h, D) Ez= plo(h, z)]. We are interested in models that satisfy the explanation constraints up to some slack T (i.e. approximately) in expectation. We define a learnability condition of this explanation surrogate loss as EPAC (Explanation Probably Approximately Correct learnability.
Definition (EPAC learnability). For any 8 E (0, 1), learning of H with respect to surrogate loss d, denoted m(T, 5; H, ②) is defined the smallest m E for which there exists a learning rule A such that every data distribution Dx over X, with probability at least 1 - 8 over S ~ Dmm
the sample complexity of -EPT)-PPAC
EPAC
)(A(S),))
I inf @hh, D) + T. hEH
no such m exists, define mlT, 6; setting with respect to a surrogate loss & if V8 E 1), T > 0, m(T, 6: H. Φ) is finite.
6) 00. We say that H. is EPAC learnable in the agnostic
Furthermore, for a constant T, we denote any model h E H with r-Apprxximately Correct Explanation where (h, D) S T, with a CE models. We define the class of T CE models as
HoDD, (h E H ((h, D) T)
We simply use Ho.r to denote this class of CE models. From natural statistical learning theoretic arguments, model that satisfies the random constraints in Sg might also be CE model. Proposition 3.1. Suppose a model h S Sg-satisfies the explanation constraints then
o(h, Dx) S (9) In(4/0)
2k
with probability at least 1 8, when k | and G (o(h,)) h H).
We use (-) to denote Rademacher complexity; please see Appendix where we review this and related concepts. Note that even when h satisfies the constraints exactly S, we only guarantee a bound on the expected surrogate loss Φ(h, Dx) ..We can achieve a bound similar to that in Proposition 3.1 via single and simpler constraint on the empirical expectation o(h, Sg)

---

1. EvESe @(h,x). x). We can then extend the above proposition to show that if o(h, Sg) S [88]
(i((///) with probability least - 8. Another advantage of
then @hh, Dx) S 7 (G) such a constraint that the explanation constraints could be noisy, or it may be difficult to satisfy them exactly, so also serves as a slack. The class G contains all surrogate losses of any h E H. Depending the explanation constraints, 9 can be extremely large. We remark that the surrogate loss & allows us to reason about satisfying an explanation constraint on a new data point and in expectation. However, for many constraints, & does not have closed-form unseen data point. The question of which types explanation constraints are generalizable may be of independent interest, and we further discuss this in Appendix B and provide further examples of learnable constraints in Appendix D.
is unknown
EPAC- MPAC-ERM Objective. Let us next discuss combining the two sources of information: the explana- tion constraints that set up in the previous section, together with the usual set of labeled training samples S = { y1),.... (In, Un)) drawn i.i.d. from that informs the empirical risk. Combin- ing these, get what we call EPAC-ERM objective:
&
Σ (1, s.t. T.
1
(0, ST. ST.
min =
NEW
1=1
We provide a learnability condition for a model that achieve both low average error and surrogate loss in Appendix F.
3.1 Generalization Bound
We assume that we are in a doubly agnostic setting. Firstly, we are agnostic in the usual sense that there need be no classifier in the hypothesis class H that perfectly labels (zr, y); instead, we hope to achieve the best error rate in the hypothesis class, h" = arg min errp (h). Secondly, we are also agnostic with respect to the explanations, so that the optimal classifier h may not satisfy the explanation constraints exactly, so that it incurs nonzero surrogate explanation loss @(h", D) O.
Theorem 3.2 (Generalization Bound for Agnostic Setting). Consider a hypothesis class H. distri- bution D, and explanation loss 6. Let S = {((I,,))) (1),, ..... (In, yn)} be drawn i.i.d. from D and SE = {x/,... .., [kk drawn i.i.d. from Dx. With probability least 1 6, for l H that minimizes empirical risk (h) and has ohh, Sp) I T, we have
In(4/8)
errp(h) (hrp(h; 2ww.H..HH.HH...... (Ho. ) +2
2n
E = -2) + (n((4/))
2k
when G = (((h,x) | h H. E X3 and h = arg minne (h)
Proof. The proof largely follows the arguments in Balcan and Blum [2], but we use Rademacher complexity-based deviation bounds instead of VC-entropy. We defer the full proof to Appendix E. O
Our bound suggests that these constraints help with our learning by shrinking the hypothesis class H to Harrtea, reducing the required sample complexity. However, there is also a trade-off between reduction and accuracy. In our bound, we compare against the best classifier h Ho.r-sn instead of A.. Since we may have s(h", D) > 0, if 7 is too small, we may reduce H to a hypothesis class that does not contain any good classifiers. Recall that the generalization bound for standard supervised learning - in the absence of explanation constraints - is given by
In(2/8)
chr S crrp(h") + (H) + 2/
2n
We can see the difference between this upper bound and the upper bound in Theorem 3.2 here as a possible notion of the goodness of an explanation constraint. We further discuss this in Appendix C.
5

---

Figure 2: Visualization of the piecewise constant function of V h(a) vzh((z) when is a two layer NNs with node. Background colors represent regions with non-zero value.
Gradient Explanations for Particular Hypothesis Classes
In this section, further quantify the usefulness of explanation constraints different concrete examples and characterize the Rademacher complexity of the restricted hypothesis classes. In particular, consider explanation constraint of a constraint the input gradient. For example, we may want our model's 's gradient to be close to that some h' E H. This translates to g(h, x) = Vzh(z) and C(x) {ar e I || V (x)]l S r for some T > 0.
4.1 Gradient Explanations for Linear Models
We now consider the case of a uniform distribution on sphere, and we use the symmetry this distribution to derive upper bound the Rademacher complexity (full proof to Appendix H).
Theorem 4.1 (Rademacher complexity of linear models with a gradient constraint, uniform distri- bution sphere). Let Dx be a uniform distribution a unit sphere in Rdd, let H (h : x (Wh, z) wh IRd [|m la S B} be class of linear models with weights bounded by constant B. Let o), = O(wn, wp)) be a surrogate loss where (uu, v) is an angle between u, v. We have
B
1 1-p)
Rn(Ho,))
S (si(())
/n
where = erf (Vasiulr) and erf( -2
2 / 10e e dt the standard error function.
The standard upper bound on the Rademacher complexity of linear models is B Our bound has v
nice interpretation; we shrink our bound by a factor of ('-P + sin(r)p). We remark that d increases, we observe that p > 1, so the term sin(r)p dominates this factor. As a consequence, we get that our bound is now scaled by sin(r) This implies that given labeled data, to achieve fast rate OL)), need to be good O
and the the Rademacher complexity scales down by factor of
4.2 Gradient Explanations for Two Layer Neural Networks
Theorem 4.2 (Rademacher complexity of two layer neural networks (m hidden nodes) with gradient constraint), Let X' be an instance space and Dx be a distribution over X with a large enough support. Let H = {h : +> Σ Wyr(M (u, r)|w; E IR, Uj E Rdd, ", |wyl < B, ||ulll2 1} be a class of two layer neural networks with ReLU activation function and bounded weight. Assume that there exists some constant C' > 0 such that Ez-Dxx [[| s C²2 Consider an explanation loss given by
Φ(h, a[(>) vah'(x))la + xo
V,M
for some Then, we have that R2 (Ho,))
< 3rmC
vn
Proof. (Sketch) The key ingredient is to identify the impact of the gradient constraint and the form of class Ho.T. We provide an idea when we have node. We write h(xx) wo (u x) and
h'(z) = w' ou' æ). Note that V v²h(2)- vzh((z) urulfu² 0} w' 1/''111 (dl((())) 0} is

---

piecewise constant function (Figure 2). Assume that the probability mass of each region is non- negative, our gradient constraint implies that the norm of each region cannot be larger than 7.
1. If u, of have different directions, we have regions in Vzh(x) =2,h(xr) and can conclude that |w]] < T, |w|| 7.
2. If u = v' have the same direction, we only have 2 regions in V Vzh(z) V hh' (2) and can conclude that | w'u'l w w'|
The gradient constraint enforces a model to have the same node boundary (u= n') with small weight difference |/ w'1 < T or that node would have small weight |w] < T. This finding allows us determine the restricted class H..r. and we can use this bound the Rademacher complexity accordingly. For full details, see Appendix I.
We compare this with the standard Rademacher complexity of a two layer neural network [24).
2BC
RA (H)) S
Vn
We can do better than this standard bound if 2B
3m One interpretation for this is that have a budget at most 7 to change the weight of each node and for total m nodes, we can change the weight by at most 7m. We compare this to B which is upper bound on the total weight Σy= m0 < B. Therefore, we can do better than a standard bound when we can change the weight by most thirds of the average weight 2B for each node. We would like to point that bound does not depend on the distribution D because we choose a specific explanation loss that guarantees that the gradient constraint holds almost everywhere. Extending to weaker loss such x=h((x)) is a future research direction. In contrast, our result for linear models uses weaker explanation loss and depends on D (Theorem H. We also assume that there exists with positive probability density any partition created by vzr()). This is not a strong assumption, and it holds for any distribution where the support is the Rd e.g., Gaussian distributions.
3m
as ohh, x) = |V~h(a
5 Algorithms for Learning from Explanation Constraints
Although we have analyzed learning with explanation constraints, algorithms to solve this con- strained optimization problem are non-trivial. In this setting, assume that have access to n labeled data 9:)), m unlabeled data { and & data with explanations {(nn-m+i, o(,, + We argue that in many cases, n labeled data are the most expensive to annotate. The & data points with explanations also have non-trivial cost; they require expert to provide the annotated explanation or provide surrogate loss Φ. If the surrogate loss is specified then we can evaluate it on any unlabeled data, otherwise these data points with explanations could be expensive. On the other hand, the m data points can cheaply be obtained as they are completely unlabeled. We now consider existing approaches to incorporate this explanation information.
EPAC-ERM: Recall our EPAC-ERM objective from (2):
n2 Σ
n-m-+ Σ j=R+m+1
min WCH
(h(a))) # vi
o(h,2z) ST
for some constant т. This constraint in general requires more complex optimization techniques (e.g., running multiple iterations and comparing values of 7) to solve algorithmically. We could also consider the case where т O, which would entail the hypotheses satisfy the explanation constraints exactly, which however is in general too strong constraint with noisy explanations.
Augmented Lagrangian objectives:
12 +
min Σ [[(():) + NEW TI
Σ
@(h, xz))
As is done in prior work [32], we can consider an augmented Lagrangian objective. A crucial caveat with this approach is that the explanation surrogate loss is in general much more complicated
7

---

functional of the hypothesis than the empirical risk. For instance, it might involve the gradient of the hypothesis when we use gradient- based explanations. Computing the gradients of such a surrogate loss can be more expensive compared to the gradients of the empirical risk. For instance, in our experiments, computing the gradients of the surrogate loss that involves input gradients is 2.5 times slower than that of the empirical risk. With the above objective, however, we need to compute the same number of gradients of both the explanation surrogate loss and the empirical risk. These computational difficulties have arguably made incorporating explanation constraints not as popular as they could be.
5.1 Variational Method
To alleviate these aforementioned computational difficulties, we propose a new variational objective min A) E [((h(z).v) (a.w)~D
+
inf SEHo, x~Dx
E [e(h(s), f(x)),
RER
where l some loss function and & 2 some threshold. The first term is the standard expected risk of h while the second term can be viewed as a projection distance between h and 7-CE models. It can be seen that the optimal solution of EPAC-ERM would also be an optimal solution of our proposed variational objective. The advantage of this formulation however is that it decouples the standard expected risk component from the surrogate risk component. This allows to solve this objective with the following iterative technique, drawing inspiration from prior work in posterior regularization [9, 14]. More specifically, let h2 be the learned model at time and at each timestep t,
We project he to the class of T-CE models.
a+m++ Σ
fet1. argmin NEW
Σ
(e(aa) + +Amax
0,
)7)-
M.
i=++++1
The first term is the difference between h2 and f on unlabeled data. The second term is the surrogate loss, which we want to be smaller than r is a regularization hyperparameter.
2. We calculate he+1 that minimizes the empirical risk of labeled data and matches pseudolabels from fi+1.6
n (1)
a+mm
h4+1 = argmin REH
m Σ (((22)).
71
Here, the discrepancy between h and f++1, is evaluated on the unlabeled data foy D
The advantage of this decoupling is that we could use a differing number of gradient steps and learning rates for the projection step that involves the complicated surrogate loss when compared to the empirical risk minimization step. Secondly, we can simplify the projection iterate computation by replacing Ho.r with a simpler class of teacher models Fø.r for greater efficiency. Thus, the decoupled approach solving the EPAC-ERM objective in general more computationally convenient.
We initialize this procedure with some model fn-- We remark that could see this as a constraint regularized self-training where h4 is a student model and ft is teacher model. At each timestep, we project a student model the closest teacher model that satisfies the constraint. The next student model then learns from both labeled data and pseudo labels from the teacher model. In the standard self-training, we do not have any constraint and have fr h4-
6 Experiments
We provide both synthetic and real-world experiments to support our theoretical results and clearly illustrate interesting tradeoffs of incorporating explanations. In experiments, we compare our method against 3 baselines: (1) a standard supervised learning approach, (2) a simple Lagrangian- regularized method (that directly penalizes the surrogate loss Φ), and (3) self-training, which propa- gates the predictions of (1) and matches them on unlabeled data. We remark that (2) captures the essence of the method in Ross et al. [33], except there is no & regularization term.
Our experiments demonstrate that the proposed variational approach is preferable to simple La- grangian methods and other supervised methods in many cases. In particular, the variational ap- proach leads to higher accuracy under limited labeled data settings. In addition, our method leads
8

---

Superisse Legiung
laglannge Solfirunn Var adonnal
10
10
40
50
Number of Libels Data uo
Figure 3: Comparison of MSE on regressing a linear model. Results are averaged over 5 seeds. 1000. k- 20.
Supersises Laprengton
Supervised Lagrongten Lagrangben Seildratt Uertecionnl
Laprangtin- Selltrain Verterional
3.-
2.-
2.0-
Number
Figure 4: Comparison of MSE on regressing a two layer neural network (left) and & distance over input gradients as we vary the amount of labeled data n (right). Left is task performance and right explanation constraint satisfcation. Results are averaged over 5 seeds. m = 1000, k = 20.
to models that satisfy the explanation constraints much more frequently than other baselines. We also compare to Lagrangian-regularizz
self- self-training baseline (first, we use the model (2) to generate pseudolabels for unlabeled data and then train a new model on both labeled and unlabeled data) in Appendix L. We remark that this baseline isn't 't a standard method in practice and does not fit nicely into a theoretical framework, although it seems to be the most natural approach to using unlabeled data in this procedure. More extensive ablations are deferred to Appendix N, and code to replicate experiments will be released with the full paper.
6.1 Regression Task with Exact Gradient Information
In our synthetic experiments, we focus on a regression task where we try to learn some model contained in our hypothesis class. Our data is given by X' = Rdd and we try to learn target function h=: > TR. Our data distribution given by X (0,001) where / a d identity matrix. We generate h² by randomly initializing model in the specific hypothesis class H. We assume that we have labeled data, m unlabeled data, and & data with explanations.
We first present a synthetic experiment for learning with a perfect explanation, meaning that 6(h", S) = O. We consider the case where we have the exact gradient of h² Here, let H. be linear classifier and note that the exact gradient gives us the slope of the linear model, and we only need to learn the bias term. Incorporating these explanation indeed helps as both methods that include explanation constraints (Lagrangian and ours) perform much better (Figure 3).
We also demonstrate incorporating this information for two layer neural networks. We observe a clear difference between the simpler Lagrangian approach and our variational objective (Figure 4 - left). Our method clearly the best in the setting with limited labeled data and matches the performance of the strong self-training baseline with sufficient labeled data. We note that this is somewhat expected, as these constraints primarily help in the setting with limited labeled data; with enough labeled data, standard PAC bounds suffice for strong performance.
We also analyze how strongly the approaches enforee these explanation constraints new data points that are seen at test time (Figure 4 - right) for two layer NNs. We observe that our variational objective approaches have input gradients that more closely match the ground-trun target network's s

---

Supervsed Lograngion
0.825
0.65
Vh Maraioonn
Legnangien SwilAraii
0.775
0.64
0.62
0.72
Supervisd
Lagrangian
Lagranglan Selfermh
0.675
Verietionnl
0.6
Figure 5: Comparison of accuracy on the YouTube (left) and the Yelp (right) datasets. Here, we let m 500, k 150, T 2, 0.0. Results are averaged over 40 seeds.
input gradients. This demonstrates that, in the case two layer NNs with gradient explanations, our approach best achieves both good performance and satisfying the constraints. Standard self- training achieves similar performance in terms of MSE but has no notion of satisfying the explanation constraints. The Lagrangian method does not achieve the same level of satisfying these explanations as it unable to generalize and satisfy these constraints on new data.
6.2 Tasks with Imperfect Explanations
Assuming access to perfect explanations may be unrealistic in practice, so we present experiments when explanations are imperfect. We present classification tasks (Figure 5) from weak supervi- sion benchmark [46]. In this setting, we obtain explanations through the approximate gradients of a single weak labeler, is done in [ More explicitly, weak labelers heuristics designed by do- main experts; one example is functions that check for the presence of particular words in a sentence (e.g., checking for the word "delicious" in a Yelp comment, which would indicate positive sentiment). We can then access gradient information from such weak labelers, which gives us notion of feature importance about particular features in our data. We note that these examples of gradient information are rather easy obtain, as we only need domain experts to specify simple heuristic functions for particular task. Once given these functions, we can apply them easily over unlabeled data without requiring any example-level annotations.
We observe that our variational objective achieves better performance than other baseline ap- proaches on the majority of settings defined by the number of labeled data. We remark that the ex- planation in this dataset a noisy gradient explanation along two feature dimensions, yet this still improves upon methods that do not incorporate this explanation constraint. Indeed, our method out- performs the Lagrangian approach, showing the benefits of iterative rounds of self-training over the unlabeled data. In addition to our real-world experiments, we present synthetic experiments with noisy gradients in Appendix K.
7 Discussion
Our work proposes new learning theoretic framework that provides insight into how apriori explanations of desired model behavior can benefit the standard machine learning pipeline. The statistical benefits explanations arise from constraining the hypothesis class: explanation samples serve to better estimate the population explanation constraint, which constrains the hypothesis class. This is be contrasted with the statistical benefit of labeled samples, which serve to get better estimate of the population risk. We provide instantiations of our analysis for the canonical class of gradient explanations, which captures many explanations in terms of feature importance. It would be of interest to provide corollaries for other types of explanations in future work. As mentioned before, the generality of our framework has larger implications towards incorporating constraints that not considered as "standard" explanations. For example, this work can be leveraged to incorporate more general notions of side information and inductive biases. We also discuss the societal impacts of our approach in Appendix O. As a whole, our paper supports using further information (c.g., explanation constraints) in the standard learning setting.
10

---

8 Acknowledgements
This work was supported in part by DARPA under cooperative agreement HR001 12020003, FA8750- 23-2-1015, ONR grant N00014-23-1-2366 NSF grant IIS-1909816, Bloomberg Data Science PhD fellowship and funding from Bosch Center for Artificial Intelligence and the ARCS Foundation.
References
[1] M.-F. Balcan and A. Blum. A pac-style model for learning from labeled and unlabeled data. In International Conference on Computational Learning Theory, pages 111-126. Springer, 2005.
[2] M.-F. Balcan and A. Blum. A discriminative model for semi-supervised learning. Journal of the ACM (JACM), 57(3):1-46, 2010. 2, 5, 20
[3] B. Bilodeau, N. Jaques, P. W. Koh, and B. Kim. Impossibility theorems for feature attribution.
arXiv preprini 2rXiv:22/2. 1870, 2022. 3
[4] J. R. Birge and F. Louveaux. Introduction to stochastic programming. Springer Science & Business Media, 2011.
[5] O. Chapelle, Scholkopf, and Zien. Semi-supervised learning (chapelle, o. al., eds.; 2006)[book reviews]. JEEE Transactions on Neural Networks, 20(3):542-55) 552, 2009. 3
[6] W. M. Czarnecki, S. Osindero, M. Jaderberg, G. Swirszez, and R. Pascanu. Sobolev training for neural networks. Advances neural information processing systems, 30, 2017.
[7] Fioretto, P. Van Hentenryck, T. W. Mak, C. Tran, F. Baldo, and M. Lombardi. Lagrangian duality for constrained deep learning. In Joint European Conference Machine Learning and Knowledge Discovery Databases, pages 118-135. Springer, 2021.
[8] S. Frei, D. Zou, Z. Chen, and Q. Gu. Self-training converts weak learners to strong learners in mixture models. In International Conference Artificial Intelligence and Statisties, pages 8003-80211 PMLR, 2022. 3
[9] K. Ganchev, J. Graça, J. Gillenwater, and B. Taskar. Posterior regularization for structured latent variable models. The Journal of Machine Learning Research, 11:2001-2049, 2010. 2,
[10] Garg and Y. Liang. Functional regularization for representation learningg A unified theoretical perspective. Advances in Neural Information Processing Systems, 33:17187-17199 2020. 3
[11] I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. MIT press, 2016. 3
[12] Y. Goyal, Z. Wu, J. Ersst, D. Batra, D. Parikh, and S. Lee. Counterfactual visual explanations.
In International Conference on Machine Learning, pages 2376-2384. PMLR, 2019.
[13] G. Hinton, O. Vinyals, and Dean. Distilling the knowledge a neural network. arXiv preprint 2015. 2
arXiv:
[14] Z. Hu, X. Ma, Z. Liu, E. Hovy, and E. Xing. Harnessing deep neural networks with logic rules. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2410-244 2420, 2016. 8
[15] A. A. Ismail, H. Corrada Bravo, and S. Feizi. Improving deep learning interpretability by saliency guided training. Advances in Neural Information Processing Systems, 34:26726-26739, 2021. 1,3
[16] Kall, S. W. Wallace, and P. Kall. Stochastic programming, volume 6. Springer, 1994. 2
[17] B. Kim, M. Wattenberg, J. Gilmer, C. Cai, Wexler, F, Viegas, et al. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav). In International conference on machine learning, pages 1668-2677. PMLR, 2018. 3
[18] W. Koh and P. Liang. Understanding black-box predictions via influence functions. In International conference machine learning, pages 1885-1894 PMLR, 2017. 1,3

---

[19] P. W. Koh, T. Nguyen, Y. S. Tang, S. Mussmann, E. Pierson, B. Kim, and P. Liang. Concept bottleneck models. In International Conference on Machine Learning, pages 5338-5348
PMLR, 2020. 3
[20] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning, nature, 521(7553))4336 444, 2015. 3
[21] M. Ledoux and M. Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991. 15
[22] Li, V. Nagarajan, G. Plumb, and A. Talwalkar. learning theoretic perspective on local explainability. In International Conference on Learning Representations, 2020. 3
[23] S. M. Lundberg and S.-I. Lee. A unified approach to interpreting model predictions. Advances
in neural information processing systems, 30, 2017. 3
[24] T. Ma. Lecture notes from machine learning theory, 2022. htw.ttt:://eee.stttt.oooo edu/
class/stats214/. 7, 14, 26
[25] R. K. Mothilal, A. Sharma, and C. Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 607-617, 2020. 3
[26] W. J. Murdoch, P. J. Liu, and B. Yu. Beyond word importance: Contextual decomposition to extract interactions from lstms. In International Conference on Learning Representations, 2018.
3
[27] N. Natarajan, I. S. Dhillon, P. K. Ravikumar, and A. Tewari. Learning with noisy labels. Advances in neural information processing systems, 26, 2013. 17
[28] R. Pukdee, D. Sam, P. K. Ravikumar, and N. Balcan. Label propagation with weak supervision. In The Eleventh International Conference Learning Representations, 2022. 17
[29] A. Ratner, S. H. Bach, H. Ehrenberg, J. Fries, S. Wu, and C. Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the VLDB Endowment. International Conference Very Large Data Bases, volume 11, page 269. NIH Public Access, 2017. 17
[30] A. J. Ratner, C. M. De Sa, S. Wu, D. Selsam, and C. Ré. Data programming: Creating large training sets, quickly. Advances in neural information processing systems, 29, 2016. 17, 35
[31] M. T. Ribeiro, S. Singh, and C. Guestrin." " why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference knowledge discovery and data mining, pages 1135-1144 1144, 2016. 1,3
[32] L. Rieger, C. Singh, W. Murdoch, and B. Yu. Interpretations are useful: penalizing explanations to align neural networks with prior knowledge. In International conference machine learning, pages 81 8116-811 11166126. PMLR, 2020. 1, 3,7
[33] A. S. Ross, M. C. Hughes, and F. Doshi-Velez. Right for the right reasons: training differentiable models by constraining their explanations. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 2662-2670, 2017. 2, 3, 8, 16
[34] H. Shao, O. Montasser, and A. Blum. A theory of PAC learnability under transformation invari- ances. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors. in Neural Informa- tion Processing Systems, 2022. URL https: http///ppp//eeeeeeeeeeeeeeee wwt.eerrrrieeeeeefforriiiii...a. wett//formmidd:1111.. 3
[35] D. Smilkov, N. Thorat, B. Kim, F. Viégas, and M. Wattenberg. Smoothgrad: removing noise by adding noise. ICML Workshop on Visualization for Deep Learning, 2017, 2017. 1,
[36] J. Stacey, Y. Belinkov, and M. Rei. Supervising model attention with human explanations for robust natural language inference. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11349-11357, 2022. 1,3
[37] M. Sundararajan, A. Taly, and Q. Yan. Axiomatic attribution for deep networks. In International conference machine learning, pages 3319-3328. PMLR, 2017. 3
12

---

[38] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11): -142, 1984.
2
[39] S. Wachter, B. Mittelstadt, and C. Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech., 31:841, 2017. 3
[40] C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical analysis of self- self-training with deep networks on unlabeled data. In International Conference on Learning Representations, 2020. 3
[41] M. Wicker, Heo, L. Costabello, and Weller. Robust explanation constraints for neural networks. In The Eleventh International Conference on Learning Representations, 2022.
[42] Q. Xie, M.-T. Luong, E. Hovy, and Q. V. Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages 10687-10698, 2020.
[43] C.-K. Yeh, J. Kim. I. E.-H. Yen, and P. K. Ravikumar. Representer point selection for explaining deep neural networks. Advances in neural information processing systems, 31, 2018. 1,3
[44] C.-K. Yeh, B. Kim, S. Arik, C.-L. Li, T. Pfister, and P. Ravikumar. On completeness-aware concept-based explanations deep neural networks. Advances in Neural Information Process- ing Systems, 33:20554-205555 2020. 3
[45] M. E. Zarlenga, P. Barbiero, G. Ciravegna, G. Marra, F. Giannini, M. Diligenti, F. Precioso, Melacci, A. Weller, P. Lio, et al. Concept embedding models. In NeurIPS 2022-36th Conference Neural Information Processing Systems, 2022.
[46] J. Zhang, Y. Yu, Y. Li, Y. Wang, Y. Yang, M. Yang, and A. Ratner. Wrench: A comprehensive benchmark for weak supervision. Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. 10, 38
13

---

A Uniform Convergence via Rademacher Complexity
standard tool for providing performance guarantees supervised learning problems is a gener- alization bound via uniform convergence. We will first define the Rademacher complexity and its corresponding generalization bound.
Definition 5. Let F be famity of functions mapping X -R. Let S {aI..... 2m be set of examples drawn ii.dd from a distribution Dx. Then, the empirical Rademacher complexity of F defined as
m _
Rs(F)
E
sup fEF
1=1
where om,...,om are independent random variables uniformly chosen from {-1,1}.
Definition 6. Let F be family of functions mapping X - R. Then, the Rademacher complexity of F is defined
(z)
IE
[R((F))
S~DR
The Rademacher complexity is the expectation of the empirical Rademacher complexity, samples drawn i.i.d. from the distribution Dx-
Theorem A.1 (Rademacher-basee uniform convergence). Let Dx be a distribution over X, and F family of functions mapping X' + [0, 1}. Let S = (x1,..., Tn) be a set of samples drawn i.i.d. from Dx, then with probability at least 5 over draw S.
ln(2/5)
[p[[(x) (Bs [x))] S (F)
2n
This holds for every function F, and (slf(x)) is expectation over uniform distribution over S.
This bound on the empirical Rademacher complexity leads to the standard generalization bound for supervised learning.
Theorem A.2. For binary classification setting when {+1} with zero-one loss, for H. C {h: : X [-1,1]} be a family of binary classifiers, let S (I1, y1.,.... (Ins 3n)} } drawn i.i.d.
from D then with probubility at least - 6, we have
In ln(2/8)
(errp(h) - erts & (H) +
2n
for every h E H when
crrp(h) Pr (h(x) + y) (u.y)~/
and
1 1[h(x:) # vil
s n
the empirical error S.
For linear model with bounded weights in l norm, the Rademacher complexity is O (2) We refer to the proof from Ma [24] for this result.
Theorem A.3 (Rademacher complexity of a linear model ([24])). Let X' be an instance space in Rtd, let Dx be a distribution X, let H {h - (wh, x) Wp Rdd ||wall2 B} be class of linear model with weights bounded by some constant B > 0 in Ea norm. Assume that there exists constant O such that Ey-Dx [|]]||]] C2, For any S (I1,..., Fn. is drawn i...d. from Dx. we have
B
Rs(H) <
and
BC
R2 (H) <
Vn.
14

---

Many of our proofs require the usage of Talgrand's ' lemma, which we now present. Lemma A.4 (Talgrand's Lemma [21]) Let Φ : R + be a k-Lipschitz function. Then for hypothesis class H = {h: R + R), we have that
Rs(ø H) s kR.(H)
where & H= (s: :/:24/ (((())) H).
B Generalizable Constraints
We know that constraints C(x) capture human knowledge about how explanations at point z should behave. For any constraints C(x) that are known apriori for all X, we can evaluate whether model satisfies the constraints at point E X. This motivates us to discuss the ability of models generalize from any finite samples Sz satisfy these constraints over X' with high probability. Having access to ((x) is equivalent to knowing how models should behave over all possible data points in terms of explanations, which may be too strong of assumption. Nevertheless, many forms of human knowledge can be represented by a closed-form function (()). For example,
1. An explanation has to take value in a fixed range can be represented by C(a.) - [ay, be], Vx X.
2. An explanation has to stay ball around æ can be represented by C(z) = {u E Rd || 2 I r).
3. An explanation has to stay in rectangle around 3 can be represented by C(x) {u E TRd
5 I 2 b, = b...,dJ.
rectangle around
fixed interval
ball around
Figure 6: Illustration of examples of explanation constraints, given from some learnable class C(x).
In this case, there always exists surrogate loss that represents the explanation constraints C(x); for example, we can set ((h, .) = (g .)) C(x) On the other hand, directly specifying explanation constraints through surrogate loss would also imply that C(x) is known apriori for all unseen data is well-defined in this
X. The task of generalization setting. Furthermore, if a surrogate loss ó is specified, then we can evaluate o(h, x) on any unlabeled data point without the need for human annotators which is a desirable property.
satisfy the constraint
On the other hand, we usually do not have knowledge over data points x E X:; rather, we may only know these explanation constraints over random sample of & data points Sg = {2/,... 2/.) If we do know the constraint set C(x), unclear what satisfying the constraint an unseen data point z means. Indeed, without additional assumptions, it may not make sense to think about generalization. For example, if there is relationship between C(x) for different values of x, then is not possible to infer about C(x) from C(a)) for = 1,.... k. In this case, we could define
Φ(h,2) x))(,,)) C(x))1fx e SE).
15

---

where we are only interested in satisfying these explanation constraints over the finite sample Sg. For other data points, we have o(h.x) O. This guarantees that any model with low empirical explanation loss would also achieve loss expected explanation loss, although this does not have any particular implication on any notion of generalization new constraints. Regardless, our explanation constraints still reduce the size of the hypothesis class from H to Ho,7, leading to an improvement in sample complexity.
note that
The more interesting setting, however, is when we make an additional assumption that the true (unknown) surrogate loss & exists and, during training, we only have access to instances of this surrogate loss evaluated on the sample o(;,))). We can apply uniform convergence argument to achieve
In(4/6) 2k
@hh, Dx) S ((h, +2)
with probability at least 1 - over Sg. drawn i.i.d. from Dx and g= (dbh, 314 E Although the complexity term RG) is unknown (since á is unknown), we can upper bound this by the complexity of a class of functions approximate any ((h, -) E G, meaning that (g) < (&)) Comparing to the former case when C(r) is known for all x E X' apriori, the generalization bound has a term that increases from R& (9) to R& (Φ), which may require more explanation -an--nannneddd data to guarantee generalization to new data points. We note that the simpler constraints lead simpler surrogate loss, which in turn implies a less complex upper bound Φ. This means that simpler constraints are easier to learn.
(e.g., neural networks) that is large enough to well-
Nonetheless, this is a more realistic setting when explanation constraints are hard to acquire and we do not have the constraints for all data points in X'. For example, Ross et al. [33] considers an image classification task on MNIST, and imposes an explanation constraint in terms of penalizing the input gradient of the background of images. In essence, the idea that the background should be less important than the foreground for the classification task. In general, this constraint does not have closed-form expression, and do even have access the constraint for unseen data points. However, if we assume that a surrogate loss o(h,") :) can be well--pppo by two layer neural networks, then our generalization bound allows to reason about the ability of model to generalize and ignore background features on new data.
C Goodness of an explanation constraint
Definition 7 (Goodness of an explanation constraint). For a hypothesis class H. a distribution D and an explanation loss &. the goodness of & with respect to a threshold t and labeled examples is:
G H) = (Rn (H) - Po, (Ho,))))) + (err (hrr -erp((())
h ===nm arg min (h), hCH
h = arg min errp(h).
hEH
Here, assume access to infinite explanation data so that E - 0. The goodness depends the number of labeled examples n and a threshold t. our definition, a good explanation constraint leads to reduction in the complexity of H. while still containing classifier with low error. This suggests that the benefits from explanation constraints exhibit diminishing returns as n becomes large. In fact, as n. + oc, we have R., (H) - 0, R., (Ho.r) - O which implies G., (á. H) + errp (h*) err (h;) ) S O. On the other hand, explanation constraints help when small. For t large enough, we expect err (h²) crrp(h;) (ht) to be small, so that our notion of goodness is dominated by the first term: R, (H) R., (Ho.r). which has the simple interpretation of reduction in model complexity.
D Examples for Generalizable constraints
In this section, we look at the Rademacher complexity of G for different explanation constraints to characterize how many samples with explanation constraints required in order generalize to satisfying the explanation constraints on unseen data. We remark that this is a different notion of sample complexity; these unlabeled data require annotations of explanation constraints, not standard labels. In practice, this can be casier and less expertise might be necessary if define the surrogate loss directly. First, analyze the case where our explanation is given by the gradient of linear model.
16

---

Proposition D.1 (Learning gradient constraint for linear models), Let 'D be distribution over IR.. Let H. {h + (wh, 2) wn RR I| ll2 S B} be class of linear models that pass through the origin. Let 6(h, x) = (ww,, ww) ) be surrogate explanation loss. Let g = {o(h,-) -) H.}.
then have
(9) 2/m
Proof. For a linear separator, ((b,-) is a constant function over X'. The Rademacher complexity is given by
1 m
R.
E 2~ D
E
sup ((6,))E
oho(h, 24)
m
m
E
sup
Ts
0 why WN)
2~D
NEW
m
m
E
E
sup hcH
0 Wk, wN)
RND
M11
i=1
m
π
E
2
m
2/m
We compare this with the Rademacher complexity of linear models which is given by Rm (H) S B The upper bound does not depend the upper bound on the weight B. In practice, know that the gradient a linear model is constant for any data point. This implies that knowing a gradient of a single point is enough to identify the gradient of the linear model.
We consider another type of explanation constraint that given by a noisy model. Here, could observe either a noisy classifier and noisy regressor, and the constraint could be given by having similar outputs this noisy model. This reminiscent of learning with noisy labels [27] weak supervision [30, 29, 28]. In this case, our explanation is simply the hypothesis element h itself, and our constraint is the values that h(x) can take. We first analyze this in the classification setting.
Proposition D.2 (Learning a constraint given by a noisy classifier). Let D be a distribution over Rd. Consider binary classification task with y = 11,, Let H be hypothesis class. Let é(h, .) = 1[((x)) f h/ (x:) be a surrogate explanation loss. Let G (0(h,) -) H), then we have
R2, } (H).
1
Proof.
(G)
E
E
sup
(h, x.))
I~D
1=1
1
h(x))((z))
E
E
sup
z~D
NEH.
m
1
h(z))/(x))
E
E
sup
z>D
hEH
m
2
E z>D
E
sup
1
Σ 05
h(xz)
hER
m i=1
2
1
(H).
Rr
2
17

---

Here, to learn the restriction of G is on the same order of (H). For given noisy regressor, we observe slightly different upper bound.
Proposition D.3 (Leariing constraint given by noisy regressor). Let 'D be distribution over R... Consider a regression task with y = R. Let H be a hypothesis class that Yh E HH E H. Let Φ(h,x)) = [h(x) ht' (x)] be surrogate explanation loss. Let G (o(h, h E H). then we have
R, (9) S (H).
Proof.
1 m m
(9)
sup JEG
ok xi)
zm 1)
sup NEH
011h(x;)) - 11(())))
2nD D
m
m
1 m
E
E
sup NEH
0 .max(0,((2))) hxxx))
Σ m
or (0 h(2x1)
20D D
m71
m
og mmx h(x;) h' nx(x)))
sup NEH
2~ 13
171
m
E
sup
3 max max (0,h((x)))
h (xxi))
B> D
m
E
E
sup KEH
m
(h(x)) - 11' (xx))))
]
+ IE
E
sup
1 m
Σ
m
0, (2:) - h(xx))
2
M7
z
hEH
where in the last line, we apply Talgrand's lemma A.4 and note that the max function max(0, (x)) is I-Lipschitz; in the third line, note that we break up the supremum as both terms by definition of the max function are non-negative. Then, noting that we do not optimize over h' (z)x we further simplify this as
]]
R, (G) <
E
sup
E a~ D
sup
Σ o.l (((.)()x)) i=1
z~D
h
hER
i=1
< 2RR, (H).
As mentioned before, knowing apriori surrogate loss ó might be too strong. In practice, we may only have access to the instances d(., on a set of samples S {ZI..... , .+ We also consider the case when o(h, .r) [h(x) h' (x)) when h is unknown and h' belongs to a learnable class C.
Proposition D.4 (Learning a constraint given by a noisy regressor from some learnable class C). Assume D is distribution over Rd. Let H and D be hypothesis classes. Let oi (h,, = 11(x)) (x(x) be a surrogate explanation loss of a constraint corresponding to h². Let Ge = {Øw (h, 1/ E H. R C), then have
RA (Gc) 22, + 22R,
18

---

Proof.
1
(9c(
E
sup (E
wm D
m
m Σ p((((x))) - (x(z))
IE
sup b hh' EC
m>D D
m i=
-((E))) -
$ IE
sup KEH, ECEC
or max(0,
+
m 1=1
1
E
sup hEH, EC
max (x; h(xx))))))))
1=1
m Σ (h(x);))))))))))))))))){)))))( - (h(2)))) h1(xx))
<
E
sup MEH, EC
m
1 m
E
sup
Σ
o, (h'(s;) - k(xx))
z
KEH, k'EC
m
where the lasts line again holds by an application of Talgrand's lemma. In this case, we indeed are optimizing over N', get that
m Σ o on (x;))
)
(9c))) 2.
E
sup
(h(z.))
+2. E 2>D
E
sup k'EC
hEW
m
1=1
m
22R, + (C).
We remark that while this value is much larger than that of (H), we only need information about o(h, æ) and not the true label. Therefore, in many cases, this is preferable and not expensive to learn.
E Proof of Theorem 3.2
We consider the agnostic setting of Theorem 3.2. Here, we have two notions of deviations; one is deviation a model's s ability to satisfy explanations, and the other is a model's 's ability to generalize to correctly produce the target function.
Proof. From Rademacher-based uniform convergence, for any h H. with probability at least 1 - 8/2 over SE
In(4/8)
(0(h, D) Shh, (G) +
E
2
Therefore, with probability least 1 5//2, for any h Ho,t-ea also have Φ(h, SF) < l and for any h with Φ(h, S5) I f, we have h E Hos In addition, by a uniform convergence bound, with probability least 1 5/2, for any h E Ho.tts.
In In(4/))
(errp(h) crrs(h)) & R2 (Hs.4te)) + V
2n
19

---

Now, let h be the minimizer of errs(h) given that (hh, Sg) S t. By previous results, with probability
1 6, we have h E Hopetes and
In(4/8)
crrD(h) & crrs(h') Rn (Ho.tee))
2n
In(4/5)
eers(hiiee)) + Rn (Ho.te))
2n
[n(4//)
S (erd((ii-a)) + 2 R...Httttt + 2//
2n
F EPAC-PAC learnability
We note that in our definition of EPAC learnability, we are only concerned with whether model achieves lower surrogate loss than т. However, the objective of minimizing the EPAC-ERM objective is to achieve both low average error and low surrogate loss. We characterize this property as EPAC-PAC learnability.
Definition 8 (EPAC-PAC lcarnability). For any ò E T), O, the sample complexity of (6, 7) EPAC learning of H with respect to a surrogate loss o. denoted m(6, T, ",; H. o) is defined as the smallest E M for which there exists a learning rule A such that every data distribution Dx over X, with probability least over S Dm
((A(S).)) inf (hh D) + NER
and
err((A(S) & inf er) (h) KEH
If no such m exists, define m(ō, T, H;H, H, x. We say that H is EPAC-PAC learnable in the agnostic setting with respect to a surrogate loss i8 E (0, 1), 0 m(6, T, 7; H. @) is finite.
G A Generalization Bound in the Realizable Setting
In this section, we assume that we are in the doubly realizable [2] setting where there exists h H such that errp ehrp(h") )- = O and @(h". D) = O. The optimal classifier h" lies H and also achieve zero expected explanation loss. In this case, want output hypothesis h that achieve both zero empirical risk and empirical explanation risk.
Theorem G.1 (Generalization bound for the doubly realizable setting). For hypothesis class H. distribution 'D and an explanation loss 6. Assume that there exists ht E H that errp (h") 0 and o(h", D) 0. Let S = {211, .i),..., (Ins yn)} is drawn i..dd. from D and Sg { [4 drawn i.i.d. from Dx. With probability at least 1 - 8, for any E H that errs(h) = and @h, Sg) we have
Im(2/8)
cr & R2 (Ho.ee)) +
2n
when
ln(2/5)
E = 2Rx
2k
when G = (((h, | E H, X).
Proof. We first consider only classifiers than has low empirical explanation loss and then perform standard supervised learning. From Sademacher-basee uniform convergence, for any h E H. with probability least 1 8/2 over SE
ln(2/8)
$(h, +
2k
20

---

when G = (o(h, h H. E X). Therefore, for any h E H. with o(h, Sg) 0, we have E Ho.se with probability least 1 8/2. Now, we can apply the uniform convergence on Ho.s.
For any h E Ho.e with (h) = 0, with probability at least 1 5/2, we have
In ln(2/5)
ehr - Rn (Ho.er)
2n
Therefore, for h E that @(h, Sg) = 0, e = O, we have our desired guarantee.
We remark that, since our result relies on the underlying techniques of the Rademacher complexity, result is the order of O (-)) In the (doubly) realizable setting, this is somewhat loose, and more complicated techniques are required to produce tighter bounds. We leave this as an interesting direction for future work.
H Rademacher Complexity of Linear Models with Gradient Constraint
We calculate the empirical Rademacher complexity of linear model under a gradient constraint.
f(u)
f(o) cos(O(1, w²) +)
f(v)=
Figure 7: Illustration of different value of a function f(v).
Theorem H.1 (Empirical Rademacher complexity of linear models with gradient constraint). Let {h x + (wh, .)) wyp
X be an instance spuce in IRd,, let Dx be distribution on X, Rd ||wallz S B} be a class of linear model with weights bounded by some constant B 0 in l2 norm. Assume that there exists a constant C' > 0 such that EzzDx |0||||] I C Assume that have explanation constraint in terms of gradient constraint;
want the gradient of our linear model to be close to the gradient of some linear model W. Let @(h, x) = 0(wn, wh/ be an explanation surrogate loss when O(u, v) is angle between u, For any S (#1,... , Fn is drawn i..dd from Dx, we have
B EE [[l]]](())] Rs(Ho.)) n
when U Ei Tio; and
when (v, w/) ST
f(v) = cos(O(u, (') -))
when < 0vv w/) < +r when (vv w/) > +T.
For the proof, refer Appendix H for full proof. We compare this with the standard bound linear models which given by
B [[le]]] Rs (H))
n
21

---

Figure 8: Benefits an explanation constraint also depend on the data distribution. We represent data points H; with red squares (Left). The possible regions for > 2,σ; are the shaded areas (Right). When the data is highly correlated with w', o would lie in a region where f(v) is large (Top) and this implies that the gradient constraints provide less benefits. On the other hand, when the data almost orthogonal to w', would lie in region with a small value f(v) (Bottom) which leads to more benefits from the gradient constraints
The benefits of the explanation constraints depend on the underlying data distribution; the case of linear models with gradient constraint, this depends The explanation constraint reduces the term inside the expectation by a factor of f(v) depending on 0(v, w'). When (v, w') S 7 then f(v) = which implies that there is no reduction. The value of f(v) decreases the angle between (v, w') increases and reaches f(v
angle between > 320 and w'.
0 when 0(v, w') _ +r. When the data is concentrated around the area of w', the possible regions for would be close to w' or or-w' (Figure 8 (Top)). The value of (v) in this region would be either 1 or 0 and the reduction would be 1 on average. In essence, this means that not actually tell much information beyond the information from the data distribution. On the other hand, when the data points are nearly orthogonal to w'. the possible regions for would lead a small f(v) (Figure 8 (Bottom)). This can lead to a large reduction in complexity. Intuitively, when the data nearly orthogonal to w', there many valid linear models including those not close in angle to w'. The constraints allows us to effectively shrink down the class of linear models that are close to w'.
gradient constraint being close to w' does
Proof. (Proof of Theorem H.1) Recall that Ha.r {h + (wn,x) | wA R |wpk 112 S B, (wi, ww) ) S T). For a set of sample S, the empirical Rademacher complexity of Horr is given by
1
Rs Rs(Ho.))
Er
sup he Ho..r aml
Σ h(zz)o
E2
sup || 1|a5B 7m1 0(w.,.w))
Wh, 2i)o;
1 Eg
sup || lla
(whhs
24055)
n
For vector w' E Rdd with ||w'||2 1. and vector E Rd we will claim the following,
22

---

1. If ((v w') S T, we have
sup (w, v) B||u||-
|e 1 mwww )ST
2. If 2 + S 0(0, w') S we have
sup
(u,, u) = 0.
wllls ((w)ww)
3. Ifr < 0(v, w() < 2 + have
sup
(w, = BBleel cos(f(e,, (') - 7)
| S 0(w,w)))
For the first claim, we can see that if ((v, w') T, we can pick [ee] and achieve the optimum value. For the second claim, we use the fact that ((-,)) satisfies a triangle inequality and for any w that ((w, w²) T, have
0(v, w) + -(w, w/) 2 0(v. w')
( w) 2 0(v w 0(w, w')
0(0, w) 2 +
π
π
2
This implies that for any that 0(w, w') S T. we have (w, v) = |w|||||| cos(O(v, w)) S 0 and the supremum given by where we can set ||l||| O. For the third claim, we know that (w, v) is maximum when the angle between w is the smallest. From the triangle inequality above, we must have (ww, w') = т to be the largest possible value so that we have the smallest lower bound 0(v, w) 2 (vv w') - 0(w, w'). In addition, the inequality holds when v w', lie on the same plane. Since we do not have further restrictions on w. there exists such and we have
sup | ((w,w))
(w, v) B [ cos(O(v, w') - 7)
required. One can calculate closed form formula for w by solving quadratic equation. Let Bi when t + Xwo for some constant À >> O such that ((w, w/) With this we have an |+||||
equation
(w, w²) COs(T)
|
(o + Xun, w(²)
cos(T)
a1 + Aw''l
Let (u, w'), solving for X, we have
#+ X
M 2λμz + x2 cOs(T)
2 + 2 + X2
cos (r))(1) 2Aμ + 23)
sin2(r)>² + (r) + 11² cos
(7)11=112 c7)
0
112
X2 + 2pA +
sin? cot (7) O
Solve this quadratic equation, we have
X = + cot(T)
( n22
23

---

Since A > O, we have À = - + cot()) - 2². We have
1 = v + Awo
v + (-u + col(() 112)
= v - (u, "om""""i col(T)w' V Voul2 n.
With these claims, we have
Rg(H4,))
Eg
sup
(wn,
Σ x,Or)
11
8(w),Ner)
B
Eg
|10|110(00 +T) [1]||(T s 0(u, w²) = + cos,,,((,, - -7)
n
B E, [[]]]][w)]]
n
Theorem H.2 (Rademacher complexity of linear models with gradient constraint, uniform distribution on sphere). Let X be an instance space Rd, let xx be uniform distribution on unit sphere in IR", let H = {h: + (Wh. 2) Wh,, E IRd, 1|wkll l2 S B} be a class of linear model with weights bounded by some constant B in ε2 norm. Assume that there exists a constant C >> 0 such that Ez=Dx ||| < C² Assume that we have an explanation constraint in terms of gradient constraint; we want the gradient our linear model to be close to the gradient of some linear model h'. Let o(h, x) = (wh, ww) be an explanation surrogate loss when ((u, v) is an angle between u, v. We have
B (in(T) +
1 1-P)
(M,,))
Vn
where
erf vdsin(T))
V2
Proof. From Theorem H.I, we have that
Rn, (Ho,)) E
Rss
( (H..))
B
||||| w0' <T + ||]]|1(F= < (u, - π + r) cos(O(u, (') - -
Ep
Eg
B
ED
E.
[100] w/) < π
1|0|11111 π
< 0lv, w') < π + cos(O(v,, - []]
when Σn i=1 T, Because is drawn uniformly from unit sphere, in expectation 0(v, w') has a uniform distribution over [0, T and the distribution |||| for a fixed value of 0(v, w') are the same for all 0(v, w') [0, T.. From Trigonometry, we note that
π cos π - 2r + a) + cos
2 a.) = =sin2rr (2n a) + sin(a) < sin
2
24

---

By the symmetry property and the uniformity of the distribution of 0(v, w/) and |||||-
|1:111 2 - - 0 w') < " - 7 cos(f(e, w') []]
Ep
Es
Ep
E,
||=|110= <
2r) cos(
+ 0(u, w/) -)]
2
Ep
B
(v](1(00500,, 5 >) cos
+ 0(0, w') -) + 1(T S ((,,w') - 27] cosl 2 :
+ +Ou,,'') w') - -
Ep
E.
101(110 < 7) cos
2 f0, w/) + 140 - 0(v, w/) S 7 cos 2 (2T ((v,
Ep
E.
001011050(10 w/) i r) cos(
+ 0(e, w/) -))+ 140 - 8(e, S 7) cos(
2 - =((e, w w')i)|
2
Ep
E.
[|0((100 5 (1. w 5 <) cos
+ ((e w/) 7) 100 (e, S 7) cos ạ
0c, w)))))
2
ED
E
|101111 s 0(e, w/) - 2
} sin(T)
when H(v,, w/)
2 u. w'). We have
R., (n _ -
B
En Err ||li|] (0(e, w') s
2 - S 0(v, ((u,'))= s " + + + sin(r)] 2 [E [||il]] (Pr(O(u, w²) - 7) + Pr( - - 0(v, w0) $ 2 + sin(T))
π
7] + |||||| x
2
B
ED
2
The last equation follows from the symmetry and uniformity properties. We can bound the first expectation
Ep E
[[0l]]
ED
E.
i=1
Y3 3. |
< EEl
E
n
EDly
Eg
c 1120
S CVVo.
Next, we can simply note that, since data is distributed over unit sphere, each data has norm no greater than 1. Therefore, we know that C = 1 is indeed an upper bound on Ex [|]=]|]]] For the probability term, note that in expectation has the same distribution a random vector drawn uniformly from a unit sphere. We let this be some probability p.
Pr _
π - T < (w, -
+ = Pr (l<u, w')l S sin(T))
We know that the projection (u, w²) N (O, 4). Normal Distribution, which has CDF given by
Then, we have that (u, w")l is given by a Folded
1
(vdsi((T)
+ erf (Vasin(T)
Pr (K w'll S sin(T)) 2 erf
V2
v2
Vddii(()) \/2 V2
eef
We then observe that
Pr (0(u, (') < π
--)= 1
1
0(0, w/) >5 - x
Pr
<
-2
1 1 p
2
25

---

Plugging this in yields the following bound
B
(in(()) +p 1- p)
Rn(Hor))
vn
where
p erf vdsin(T)
v2
I Rademacher Complexity for Two Layer Neural Networks with Gradient Constraint
Here, we present the full proof of the generalization bound for two layer neural networks with gradient explanations. our proof, we use two results from Ma [24]. One result is technical lemma, and the other is bound on the Rademacher complexity of two layer neural networks.
Lemma 1.1. Consider a set fa1, "i,,..,, Fn and hypothesis class F {f R2 +R. If
n2
sup FEF
f(xi)o; 2 for any o, E {=1}, I,..,n.
then, we have that
Eg
sup
faz)oss
S 2
sup FEF
f(z;)o
JEF
Theorem 1.2 (Rademacher complexity for two layer neural networks (24]). Lef X be an instance space and Dx be a distribution over X. Let H {h x + Eie W 2))w, E R, u, E R.d 5m |wm||l [us]||us]|a S B} be a class of two layer neural networks with m hidden nodes with ReLU activation function (I) = max(0, .). Assume that there exists some constant C > 0 such that Ex [|]=||]]] S C2. Then, for any S {21,..., In) is drawn i.d. from x, we have that
2B
RH) S
| 1
and
2BC
RA (H) <
Vn.
We defer interested readers to [24] for the full proof of this result. Here, the only requirement of the data distribution is that Eg-Da [||= [ < C². We now present our result in the setting of two layer neural networks with one hidden node m = to provide clearer intuition for the overall proof.
Theorem 1.3 (Rademacher complexity for two layer neural networks (m 1) with gradient con- straints). Let be an instance space and Dxx be a distribution over X. Let H = (h x + wo [w E R, u E Rd, |w| < B, ||u|| = 1}. Without loss of generality, we assume that ||u||| = Assume that there exists straint is given by a constraint on the gradient of our models, where we want the gradient of our learnt model to be close to particular target function h' E H. Let this be represented by expla- nation loss given by
constant C. > 0 such that Ex [=>=>|||== < C², Our explanation con-
o(h, x) [V)((x) Vzh'())l2 to 1[1v,((2) V2N(=)) 7)
for some T > 0. Let (z = T'o((u')) x) the target function, then we have
TC
Rn (Ho.)) <
if ww > T,
Vn
37C
R2 (Ho.))
if S T
Vn.
26

---

Vzh(z)
(x)
Vah(a) - V v'
w u
wt 'u'
uz'
0
w '''
Figure 9: Visualization of the piecewise constant function of V,h(z)) [z)((z) over 4 regions.
Proof. Our choice of =)),,)) guarantees that, for any h E Ha.r. we have that [V,h(v>) [=))) I т almost everywhere. We note that for h(x) = wo a)) the gradient is given by V h()) = wu > 0}, which is piecewise constant function over two regions (i.e., TT x > 0, u S 0), captured by Figure I.
We now consider V,h(x)) (z)) and we have 3 possible cases.
Case 1: (u,, u²)
This implics that the boundarics of V (h) and (=)((z) are different. Then, we have that Vzh(z) V v=''(x) is piecewise constant function with regions, taking values
wu w'u wu
when Jx > 0, (u') x>>0>>000
when T > 0, (u') x
Vah(r) - v+h(
w'u'
when u TT < 0, (u')Tx>
when u x 0, (u') <
If assume that each region has probability mass greater than 0 then our constraint [/,hh(z)
V v,,' (z))(2)l22 I 7 implies that |w| = | S T, / = [w|[[u'|| S т, ||w ''ll I T.
Case 2: f(u, u') = O This implies that the boundary of Vzh(x) and v=''(x)) are the same. Then, Vah(z) (ah((a) is piecewise constant over two regions
Vah(z) vzh((z) wou w'nd when TTx
when uT <
This gives that Iw w/| ww w'u'l S Case 3: 0(u, u') π Here, we have that the decision boundaries V h(x))) and vzh(()) are the same but the gradients non-zero on different sides. Then, V.h(z) V (.h((x) is piecewise constant two regions
Vah(w) Vzh((x) = wu
when u Tx > 0 -w'r! when u T r < 0
This gives us that [w] < 5 and |w/ ST.
These different cases tell us that the constraint V2h(2)- v.h(2))I < reduces into a class of models follows either
27

---

1. u = v' and |w- w/1 <. T.
2. u + wf and |w| r. However, this case only possible when |wo| < T.
If [w|| > T, we know that we must only have the first case. Now, we can calculate the Rademacher complexity of our restricted class H We will again do this in separate cases.
Case 1: |ur| > T
For any h E Ha.r. we have that u = u' and wl w'1 < T. For sample S = {o1, Inh.
(. =
Eeg
sup he Hoo i=1
E,7
sup w
wor (u')) (1'))x:)o
( as v')
2m
sup Σ ((u')) ((u')'22)0s) ].
Eg
Since, |w w'l < T,
w' r < w < w +
Then, we can compute the supremum over W as
w r
if (E= ( x2))ss <0
w
w + (E o ((u)) (u'))xz)oss) 20
Therefore, we have
n Σ Ea(lu))ani) ao)
-
(w' + sign
n Σ Ea((n')Tan (((o))))))o)) 1)
n Ea(l'') mo)os))
sup W
Now, we can calculate the Rademacher complexity as
Rs Rs(Ho.)) =
- w
1
Eo
a((u') [a((u)T2z)o) T2:)0s + r Σ ((u') x2)0y]
n2
T
E
Ca((l)) T x:)0s1
n
i=1
IF
a ((w') ((u')Tx,)) To
(Jensen's inequality)
17
E,
((u')T 2: 2=))o??
(since oi, oy are independent with mean 0)
n
((w/)xx2))
12
|,,112
n
28

---

Combining this with the fact that E [||x11]]
I C², we have
(H. = IE Rs (Ho,r))
E
| ||
mm
7
E
|amal??]
(Jensen's 's inequality)
TC
vn
Case 2: |w'lll <.
We know that Hz.
H!!! 6.r
UH (2) J 0,7 when
H Ø,r
H(1) {he E H/h a + wo x)) u = u', ml w'1 < <T
H(2) 0,5
= { E H/h x + worw T 2), |||||| = u u', |wl < r}
We have
1 -E Eg
Rs(Ho,))
sup heH
n
1 - Eg
sup
M(x))a; +
sup b(xs)o
11
hEH
NEH! i=1
Rs
(M (.t) + Rs (7
The second line holds as SUPRCAUB I (xx S sup [(x + suP fx) when suP f(x) 2 0 and sup.eB fxx) 2 O. We know that both of these supremums be greater than zero, we can recover the value of with w = O. From Case 1, we know that
TC
VT
We also note that (x(2) is class of two layer neural networks with weights with norms bounded by our T, From Theorem I.2, we have that
27C
Ru (H) < vn
Therefore, in Case 2,
3rC
Ra (n 5 Vn
as required.
Now, we consider in the general setting (i.c., no restriction on m).
Theorem I.4 (Rademacher complexity for two layer neural networks with gradient constraints ) Let X be an instance space and Dx be a distribution over X' with large enough support. Let H. (h x EØ= wrr(u,) x) 2)] E R. uj Rd ||ulll E, wyy < B}. Assume that there exists some constant C >> O such that EnnDx [||=|]]]] & C Our explanation constraint is given by a constraint on the gradient of our models, where want the gradient of our learnt model be close to a particular target function h' E H. Let this be represented by an explanation loss given by
δ(h,z) Vah(z)) v,h'(z)l12 xo 1 h(()) vah((x)] 7}
29

---

for some T >> O. Then, we have that
3rmC
Rn (Hor))
Vni
To be precise,
(2m + q)TC
Ry (Ho.)) S
Vn
when is the number of node j of h' such that luo') < T.
We note that this result indeed depends on the number of hidden dimensions m; however, we note that in the general case (Theorem I.2), the value of B is O(m) as it over the values of each hidden node. We now present the proof for the more general version our theorem.
Proof. For simplicity, we first assume that any h E H has that |uyl| 1, Vj. Consider h E H. write h -i=1 ((f)( x) and let h (((x) Σjn ((f)) xx) be function for our gradient constraint. The gradient of hypothesis h is given by
V vzh(a)
Σ wyu 1u21 0},
which is piecewise constant function over most 2 regions. Then, consider that
Vah(z) (
- maa Mu, x> 03 Σ 1((f) 0}.
which is a piecewise constant function over at most 2 regions. We again make an assumption that each of these regions has non-zero probability mass. Our choice of 6(h, guarantees that the norm of the gradient in each region less than т. Similar the case with m = 1, we will show that the gradient constraint leads to class of functions with the same decision boundary or neural networks that have weights with small norm.
Assume that among u1,-.., 4m there are vectors that have the same direction as u',-.., V Without loss of generality, let u = u/, for j l,.., k. In this case, we have that Vzh(z)- h,h'(z) (z) is a piecewise function over 22m-k regions. As each region has non-zero probability mass, for each j E {1,..., k), we know that Er such that
u x - (w') > O, uT x for f
(u/) < +
In other words, we can observe a data point from each region that uniquely defines the value of a particular Wjy Ug- In this case, have that
Vah(x) - -.h())))N()))>> wjuj wdjul
=(w, ww/)u,
From our gradient constraint, we know that 1/V v2N(2))l S T, Va, which implies that (wj - wo/1 < for I,....k.
On the other hand, for the remaining j = ks 1,..., m, we know that there exists æ such that
4 x > O, u4 x < 0 for j,
(it) x < 0 for = 1, 1,..., m.
Then, we have that V (x()))) WyUj. and constraint implies that [wy] ||u |wy| S r. Similarly, we have that (w]) | = | < <, for j = k + 1, l,.., m. can conclude that Ho.r a class of two layer neural networks with m hidden nodes (assuming |u = 1) that for each node w x) satisfies
1. There exists / E [m]] that uy us and jwy wil <
30

---

2. wyl <T
We further note that for node wfo((u)) x)) in (x)) that has that a high weight |uy] > there must be node wyo (u] z) in h with the same boundary U Otherwise, there is a contradiction with w/ll for all nodes in h without node in h with the same boundary. We can utilize this characterization of the restricted class Hø,r bound the Rademacher complexity of the class. Let
H' (h:
w Ta)ay as {0,1} and for that |u/] a, = 1}.
This is class of two layer neural networks with most m nodes such that each node is from h', We also have condition that if the weight of the j-th node in h is greater than the j-th node must be present in any member of this class. Let
H(- = (h: + Σ ( x))s my ER E |wys < <T, ا|اl = 1}. ==1
be a class of two layer neural networks with nodes such that the weight of each node is at most T. We claim that for any E Ha.r there exists In E H', h2 E H(()) that h = /n - l12 For any Ha.r. let Pa [m]] + [m]] U {0) be function that match node in h with the node with the same boundary in h.. Formally,
pa( = {
when uj = of otherwise.
The function maps j to 0 if there is no node in ht' with the same boundary. Let w/ = 0, 26 = [0, (0..... 0]. we can write
h(x)= = Σ
( x)
==1
Σ 1=1
woj x) ((1)))((())pp00)))) +
( x))()))))
Σ (wi w// (()))))(('')
Σ wn x)+ PaG]=O
Σ w/ (n (())p p))))))
Ph #0
pli3f
EHG)
The first term member of H() because we know that [uy whin) term also a member of H' since for any that |wf] > r, there exists j that pı.() = l. Therefore, we can write terms of a sum between a member of 7t' and H(r), This implies that
|wyl The second
R., (H.. < Rx() + R2 (T))
From Theorem 1.2, have that
R2 (H(T)) <
2rmC
/n
31

---

Now, we will calculate the Rademacher complexity of H'. For S = fII,.... F
1
Rs(H')
- Es
sup NEW
Σ
h(xz)oo
71
i=1
1 -
((f(( (()a))) 2i)ay)os
Eo
sup
11
hEW!
i=1
1
E.
sup
w/)(((u)) xz))a + [[1))
Σ (((o((u)Tx:)))
hEW!
F=1 luz
leg
1 Feg
sup
n
0, 10.1) i=1 luf
1 - Ex
n aj(uo Σ
Σ 1u0/lcT
sup (,E(0,1)
π1
To achieve the supremum, if u Ei=1 x2)0; > 0 we need to set a 1, otherwise, we need to set = 0. Therefore,
Rs(H() = - E,
sup E (,E(0,1)
as(2oz [o(())) x2:)oo)
|u/]er
1=1
Eg
Σ awu)
Σ (((u)) (((()))a))o)))
1=1
n Σ (w/) Σ ((()))2a))0))) |etT
|a| (a(x)
ES
21)0;) + ww Σ (((u)) xz)ool
2n
=
Eg
Σ
Iw/
o ((1))) 23)0;1
2n
ICT
i=1
< 2n
lu'sl
E
sup
Σ
ol x2)os1
||||==
1=1
lue'l
E
Σ alu Cu(uTani 22)0s ||a||=1 1=1
sup
(Lemma I.1)
|ur
n TTT.O
luu'l
E
sup 12 |=||=1
(Talagrand's Lemma).
|urgl s
Empirical Rademacher complexity of linear model
From Theorem 4.1, we can conclude that
qrC mtC Vn
RA R,(H!)) S Σ
w/
S
S
Vn
Vn
luyler
when g is the number of nodes j of h' such that w < T. Therefore,
32

---

(2m + g)TC
3mrC
Rx( <
I
Vn
Vn
tighter bound is given by (2m++g)CC when is the number w/y that |uy] <.. As + O, we also have q -> This implies that we have an upper bound of 2mrC if r is small enough. When vn
vn
comparing this the original bound 2BC, we can do much better if < We would like to point vn
out that our bound does not depend on the distribution because we choose a strong explanation loss
@hh, Vah(z)) V2h'(=)l22 + [()Vv,(()) -anee)--Ahiia (2)( 7}
which guarantees that [V V=N((=)ll2 S r almost everywhere. We also assume that we are in high-dimensional setting d >> m and there exists x with a positive probability density at any partition created by (.h(
J Algorithmic Results for Two Layer Neural Networks with a Gradient Constraint
Now that have provided generalization bounds for the restricted class of two layer neural networks, we also present an algorithm that can identify the parameters of a two layer neural network (up to a might solve this via variational objective other
permutation of the weights). In practice, simpler regularized techniques. However, we also provide a theoretical result for the required amount of data (given some assumptions about the data distribution) and runtime for algorithm to exactly recover the parameters of these networks under gradient constraints.
We again know that the gradient of two layer neural networks with ReLU activations can be written as
V va
Σ way 1 1u, x:
0},
where we consider ||u,|| = 1. Therefore, an exact gradient constraint given of the form of pairs (z, vxf(x)) produces system of equations.
Proposition J.1. If the values of us 's are known, we can identify the parameters w, with exactly m fixed samples.
Proof. We can select m datapoints, which each achieve value I for the indicator value in the gradient of the two layer neural network. This would give us equations, which each are of the form
VzJw,u = Witf-
Therefore, we can easily solve for the values of ws, given that u, is known.
To make this more general, we now consider the case where u, are not known but are at least linearly independent.
Let the u, 's be linearly independent. Assume that each region of the data (when partitioned by the values of u;) has non non-trividl support >> p. Then, with probability 1 - 5, we can identify the parameters Ws, us with O (2TT + log(
Proposition J.2.
m++lg(()) data points and in O(22m)) time.
Proof. Let us partition X' into regions satisfying unique values of the binary vector (1 x > 0}.-. .., Hu > 0}), which by our assumption each have at least some probability mass First, calculate the probability that we observe one data point with explanation from each region in this partition. This is equivalent to sampling from a multinomial distribution with probabilities (P1 ... P2n)) where p. p, Vi. Then,
Proobrerve all regions in n draws) = Pr(3i s.t. we do not observe region i)
1 2 p)"
33

---

Algorithm 1 Algorithm for identifying parameters of a two layer neural network, given exact gradient
constraints
1: Input: We are given M {x 2/C P(fx1, ...... Zm })), with {21,..., Fm linearly inde-
pendent
2: Output: The set of basis elements {I1,..., 2m
3: function
4: B =0 (3.5
0 5: for x E M do
{Set for basis vectors and set for a current sum of at least 2 elements}
6:
x E S then
7:
pass else
8:
9:
B B U [2}
10:
if = 2 then
11:
S {yı + 12). where B 191.021
12:
else
13:
S SU (y +
[Updating sums from adding æ:)
end
15:
0 BnS
[Computing overlap between current basis and sums) {Removing elements contained in pairwise span (Updating sums S from removing set O}
B
17:
5= (v Voly E 8,30 E O
end if
19:
end for
20:
return B
21:
end function
Setting this as no less than 1 leads to that m++log +) log( (-p))
Given 0 + m log(()
logl r-p ) pairs of data and gradients, we will observe least one pair from each
region of the partition. Then, identifying the values of u, and w, is equivalent identifying the datapoints that correspond to value of the binary vector where only one indicator value is 1. These values can be identified O(23m) time; the algorithm given Algorithm J. These results demonstrate that we can indeed learn the parameters (up to a permutation) of a two layer neural network given exact gradient information.
J.1 Algorithm for Identifying Regions
We first note that identifying the parameters u, 's and wt 's of two layer neural network is equivalent
identifying the values {.. Fm from the set (Eesc z/C' E Fm, mm)) where P denotes the power set. We also assume that 21. .... are linearly independent, so we cannot create F; from any linear combination of x, 's with j o i. Then, Algorithm This algorithm runs in ((23m) time as it iterates through each point in M and computes the overlapping set and resulting updated sum S, which takes ((22m) time. From the resulting set B, exactly compute values ut and w; up to permutation.
can identify the set {.1,,.., -..; Fm
in
K Additional Synthetic Experiments
We now present additional synthetic experiments that demonstrate the performance our approach under settings with imperfect explanations and compare the benefits of using different types of explanations.
K.1 Variational Objective is Better with Noisy Gradient Explanations
Here, we present the remainder of the results from the synthetic regression task of ?? under more settings noise added to the gradient explanation.
Again, we observe that our method does better than that of the Lagrangian approach and the self- training method. Under high levels of noise, the Lagrangian method does poorly. On the contrary,
34

---

Epsiion ; 0.0001
Epsilon 0.1
0.5
0.-
-05
-0.
-1.
-1.0-
-2.
20-
60
20
60
Number of Labeled Data
Number Labe ec Data
Epsilon:
Epsilon:
0.9
Dog
-1.0
NosE -1-
-15-
-25
db
20
Fpsilon :2
Sapersierd
3.
Lagiang
Lagiang Suffiiin
1-
-2-
40
80
Number Labwaet Data (7)
Figure 10: Comparison of MSE regressing layer neural network with explanations of noisy gradients. m = 1000, 1: = 20, = 10. For the iterative methods, T 10. Results are averaged over 5 seeds.
our method is resistant to this noise and also outperforms self-training significantly in settings with limited labeled data.
K.2 Comparing Different Types of Explanations
Here, we present synthetic results to compare using different types of explanation constraints. We focus comparing noisy gradients as before, as well noisy classifiers, which are used in the setting of weak supervision [30]. Here, we generate our noisy classifiers as h² (a)) + e, where e ~ N/ o²). We omit the results of self-training as it does not use any explanations, and we keep the supervised method as a baseline, Here, 0.25.
We observe different trends in performance as we vary the amount of noise in the noisy gradient noisy classifier explanations. With any amount of noise and sufficient regularization (A), this influences the overall performance the methods that incorporate constraints. With few labeled data, using noisy classifiers helps outperform standard supervised learning. With larger amount
35

---

Epsiion: ; 0.0001
Epsilon: 0.1
1.-
10-
05-
05-
0.-
10g 83300
-1.0-
-10-
-15
-15
-0--
-25
3.0
30-
20
Number of Labeled Data
Number Labe ot Data
Epsilon:
Epsilon: 0,0001
1.0
10-
0.0
-0.5
-05
-1.
NS2 Dog
-10
-2.
-2.
25-
-30
-30-
d0
20
Labeled
Libe
Epeilon 0.1
Epsilon:
1.0
Supersiset
0.5
0.-
Lagronglan Sofiiriis
Lagrongian
facional
0.0-
0.--
-0.5
-1.
-1.-
-24
-20
-2.
20
40
50
80
20 Number of Data (n)
90
Number of steled Data (r)
Figure 11: Comparison of MSE on regressing two layer neural network with explanations noisy classifier (top) and noisy gradients (bottom). m = 1000, = 20. For the iterative methods, T 10. Results averaged over 5 seeds. represents the variance of the noise added to the noisy classifier or noisy gradient.
of labeled data, this leads to no benefits (if not worse performance of the Lagrangian approach). However, with the noisy gradient, under small amounts of noise, the restricted class of hypothesis will still capture solutions with low error. Therefore. in this case, we observe that the Lagrangian approach outperforms standard supervised learning in the case with few labeled data and matches it with sufficient labeled data. Our method outperforms or matches both methods across all settings.
We consider another noisy setting, where noise has been added to the weights of copy of the target two layer neural network. Here, we compare how this information impacts learning from the direct outputs (noisy classifier) or the gradients (noisy gradients) of that noisy copy (Figure 12).
36

---

Epsilon:
Epsilon: 0.5
-2-
20
65
26
69
Number Labeled Data
Number Labeles Data
Epsilon: 0.7
Epsilon: 0.3
M52 log scaee
Number Labeind Data
Number Labe
Super Lagrongian Lagranglan
MSE Log scae
0-
Labdded Data (r)
Labeteed
Figure 12: Comparison of MSE regressing two layer neural network with explanations noisy classifier (top) and noisy gradients (bottom), m 1000, 20. For the iterative methods, 10. Results are averaged over 5 seeds. represents the variance of the noise added to the noisy classifier or noisy gradient.
37

---

L
Additional Baselines
We compare against an additional baseline of Lagrangiia-rreullatzed model + self-training on unlabeled data. We again note that this is not a standard method in practice and does not naturally fit into theoretical framework, although present compare against method that uses both explanations and unlabeled data.
Variotional
Ma2 (og Etwal
Ve oetionl
-2-
20
20
0.850
0.70
Lagranglan
Va-lational
0.000
0.64
0.750
Supervised Lagrangian
0.700
Lagranglen Selferwn
0.6
Voriadonnl
10
15
20
25
30
35
40
45
50
10
15
20
30 Number Laba and Data
25
35
40
45
30
Number Labe led Data (r))
Figure 13: Comparison of MSE regressing linear model (top left) and two layer neural network (top right) with gradient explanations. m = 1000, A: = 20. For the iterative methods, T = 2. Results averaged over 5 seeds. Comparison of classification accuracy on the YouTube dataset (bottom left) and the Yelp dataset (bottom right). m = 500, 150. Results are averaged over 40 seeds.
We observe that our method outperforms this baseline (Figure 13), again especially in the settings with limited labeled data. We observe that although this new method indeed satisfies constraints, when performing only single round of self-training, it no longer satisfies these constraints as much. Thus, this supports the use of our method perform multiple rounds of projections onto set of EPAC models.
M Experimental Details
values of 1000, 20, 0, A = 1, unless otherwise noted. For our synthetic experiments, we use d = 100, o2 layer neural networks have hidden dimensions of size 10. They trained with learning rate of 0.01 for 50 epochs. We evaluate all networks on a (synthetic) test set of size 2000.
For all of our synthetic and real-world experiments,
= 5. Our two
For our real-world data, our two layer neural networks have a hidden dimension of size 10 and are trained with learning rate of 0.1 (YouTube)) and 0.1 (Yelp) for 10 epochs. À 0.01 and gradient values computed by the smoothed approximation in [? has e = 1. Test splits are used as follows from the YouTube and Yelp datasets in the WRENCH benchmark [46].
We choose the initialization of our variational algorithm hg as the standard supervised model, trained using gradient descent.
38

---

N
Ablations
We also perform ablation studies in the same regression setting as Section 6. We vary parameters that determine either the experimental setting or hyperparameters of our algorithms.
N.1 Number of Explanation-amnottted Data
First, vary the value of k to illustrate the benefits of our method over the existing baselines.
k:
k:
Haz the seais
-1-
Number Labeled Data
Number Labe
-2-
k 100
k: 200
Superibed Lagranglan
Lagrongian Sofirrls
Veriee
scaka
80
Numbee Labeled Data (r)
Number Labade Data (r)
Figure 14: Comparison of MSE on regressing a two layer neural network over different amounts of explanation-annote annotated data k. 1000. For the iterative methods, T = 10. Results are averaged over seeds.
We observe that our variational approach performs much better than simple augmented Lagrangian method, which in turn does better than supervised learning with sufficiently large values of k. Our approach is always better than the standard supervised approach.
We also provide results for how well these methods satisfy these explanations varying values of k.
39

---

N.2 Simpler Teacher Models Can Maintain Good Performance
As noted before, subspace. This can lead to overall easier optimization problems, and we synthetically verify the impacts the overall performance. In this experimental setup, network with a hidden dimension size of 100, which is much larger than in our other synthetic experiments. Here, vary over simpler teacher models by changing their hidden dimension size.
simpler teacher models be regularized into the explanation-constraineed
regressing a two layer neural
-05
Variational Hidden Dimensiors
Variatione Hodden Bimensior:
Variational Hidden Dimension:
-10
Varistional Hidden Dimension:
Variational Hidden Dimension. 10
-15
40
60
Number Labeled Data Inl
Figure 15: Comparison of MSE on regressing two layer neural network over simpler teacher models (hidden dimension). Here, k = 20, m = 1000, T = 10. Results are averaged over 5 seeds.
We observe no major differences as we shrink the hidden dimension size by a small amount. For significantly smaller hidden dimensions (e.g.. 2 or 4), we observe large drop in performance as these simpler teachers can no longer fit the approximate projection onto our class of EPAC models accurately, However, slightly smaller networks (e.g.. 6, 8) can fit this projection as well, if not better in some cases. This is useful finding, meaning that our teacher can be smaller model and get comparable results, showing that this simpler teacher can help with scalability without much or any drop in performance.
N.3 Number of Unlabeled Data
As main benefit of our approach is the ability to incorporate large amounts of unlabeled data, provide study as we vary the amount of unlabeled data that is available. When varying the amount of unlabeled data, we observe that the performance of self-tran alf-training and our variational objective improves similar rates.
40

---

250
MSE 00g caI
NOE
Supervised
Lagression
Lapranginn Sei-ral
20
60
80
Number stated Data (r)
Number Lftabeeed Data (n)
Figure 16: Comparison MSE on regressing two layer neural network over different values of m. k = 20, T = 10. Results are averaged over 5 seeds.
41

---

N.4 Data Dimension
We also provide ablations as we vary the underlying data dimension d. As we increase the dimension d, we observe that the methods seem to achieve similar performance, due to the difficulty in modeling the high-diman -igh-siiennional data. Also, here gradient information is much harder to incorporate, the input gradient itself is dd-imensiionll, so we do not see as much of a benefit of our approach as grows.
0.5
1-
0.0
-10
15-
+
2.0
:5
1:000
Supersbed Lagrengion Lagranginn Vartacionnl
(10 scald
20
80
Numbee Labaled Dasa (r)
Number Labade Data (r)
Figure 17: Comparison of MSE on regressing layer neural network over different underlying data dimensions d. m 1000, k 20. For the iterative methods, T' = 10. Results are averaged over 5 seeds.
42

---

N.5 Hyperparameters
First, we compare the different approaches over different values regularization (X) towards satisfying the explanation constraints. Here, compare the augmented Lagrangian approach, the self-training approach, and our variational approach.
lambda 0.1
lambda
Not 10S toaee
-1-
Number Labelse Data
Number Labe Date
lambda
Supersised Lagrongian Lagrongian
Mose (ug
-1-
Data
Figure 18: Comparison of MSE regressing a two layer neural network over different values of X. m 1000, For the iterative methods, T 10. Results are averaged over seeds.
We observe that there not a significant trend as we change the value À across the different methods. Since know that explanation is perfect (our restricted EPAC class contains the target classifier), increasing the value should help, until this constraint met.
-150
Veraioon:
Vae eiiondl
Varationa.T 5
Varistionl,
-1.75
Varasenal T
Var adtonaaaaa. 0.2
Verwional 10
Vie ationel.t 0.3
MSE Dog Sca0
2200
voristional. 0.4
-225
2.50
-275
40
60
Number of Data
Numberaf Labe
Figure 19: Comparison of MSE on regressing a two layer neural network over different values of T (left) and (right) in our variational approach. 1000, h: 20, 7 10, T = 10, unless noted otherwise. Results are averaged over seeds.
Next, we compare different hyperparameter settings for our variational approach. Here, we analyze trends as vary the values of I"' (number of iterations) and (threshold before adding hinge penalty).
43

---

We note that the value of 7 does not significantly impact the performance of our method while increasing values of T seems to generally benefit performance on this task.
Social Impacts
While our proposed method has the potential to improve performance and efficiency in variety of applications, our method could introduce new biases reinforce existing biases in the data used to train the model. For example, if our explanations constraints are poorly specified and reflect biased behavior, this could lead inaccurate discriminatory predictions, which could have negative impacts on individuals or groups that are already marginalized. Therefore, it is important to note that these explanation constraints must be properly analyzed and specified to exhibit the desired behavior of our model.
44


Reviews:
[{"review_id": "GOZg71AiHy", "reviewer": "Reviewer_3fR6", "summary": "This paper presents the concept of learning from explanations and theoretically shows that learning from explanations can improve the standard excess risk bounds in the agnostic setting. They treat explanations as constraints in the ERM procedure and introduce an extension of PAC model referred to as EPAC model. The paper introduces formal notions of explanations, EPAC learnability, explanation constraint sets etc. The study analyzes the impact of explanations on model learning using standard learning theoretic tools and characterizes the constraints for linear models and two-layer neural networks. The statistical advantages of explanations stem from their role in constraining the hypothesis class: explanation samples improve the estimation of the population explanation constraint, thereby further restricting the hypothesis class. Further, the paper provides an algorithmic solution based on variational approximation to solve the problem of learning with explanation constraints. The proposed solution works better than other methods like augmented Lagrangian.\n", "questions": "Please see above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "\nStrengths:\n-------------\n\n1. The paper provides a theoretical framework for studying learning with explanations by formalizing various key notions like explanation functionals, explanation constraint set, EPAC model and EPAC learnability etc. \n\n\n2. Their analysis provides insights into why learning with explanations could improve the overall excess error of the ERM solution. The key insight is that having explanation constraints in the ERM procedure effectively reduces the size of the model class leading to smaller excess risk upper bounds. \n\n\n3. The paper also provides an algorithm solution to solve the ERM objective while satisfying the explanation constraints and the empirical results show that the proposed method works better than augmented Lagrangian and other baselines. \n", "weaknesses": "Weaknesses and Questions:\n---------------------------------\n\n1. Overall I like the ideas presented in the paper but it was a bit tedious to get exactly what is being done. It first appeared that the paper is proposing a method to learn the explanation functionals i.e. learning a model that can generate explanations by learning from some labeled explanation data. However, the goal is to study how using the explanation information improves the model performance. It would be helpful to improve the presentation to make it clear early.\n\n\n2. I am not convinced about the notion of explanations introduced. It is assumed that explanations are some vectors. Shouldn’t explanations be human-readable and be in natural language? Then how do you pose the constraint sets in natural language? I might be missing something here as I have not followed explainability research. \n\n\n3. I didn't quite get why explanation constraints are special? In general, one could put some constraints (e.g. regularization, etc.)  along with the ERM objective to reduce the size of the hypothesis class, which will lead to a reduction in the upper bound of the excess risk. Could you please provide some justification or motivation for why the explanation constraints are special? \n\n\n4. Figure 2. could be improved with some annotations and markers instead of just colors alone. The figures in experiments might  be better when run with more random seeds. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. Overall I like the ideas presented in the paper but it was a bit tedious to get exactly what is being done. It first appeared that the paper is proposing a method to learn the explanation functionals i.e. learning a model that can generate explanations by learning from some labeled explanation data. However, the goal is to study how using the explanation information improves the model performance. It would be helpful to improve the presentation to make it clear early.\n\n**Our response:** Our paper does address both of these topics: (1) we provide a mathematical framework to analyze how explanation information improves model performance and (2) we propose a variational objective that can learn explanations through explanation-labeled data. We would also like to point out that other reviewers thought that “the paper is organized and well-written”(Reviewer zYz5), “The paper is very easy to follow as it is well written”(Reviewer o4F1), “Well written and easy to follow”(Reviewer w12b), and “The presentation of this paper is clear” (Reviewer 9kMr).\n\n> 2. I am not convinced about the notion of explanations introduced. It is assumed that explanations are some vectors. Shouldn’t explanations be human-readable and be in natural language? Then how do you pose the constraint sets in natural language? I might be missing something here as I have not followed explainability research.\n\n**Our response:**  While some explanations may be in natural language, in this work, we focus on the notion of local explanations considered in explainability research where explanations indeed take a vector form. For example, feature attribution methods [1,2,3] indicate how much each feature contributed to the model predictions, and these are all represented via real-valued vectors not in language.\n\n\n[1] Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. \"\" Why should i trust you?\" Explaining the predictions of any classifier.\" Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 2016. \n\n[2] Lundberg, Scott M., and Su-In Lee. \"A unified approach to interpreting model predictions.\" Advances in neural information processing systems 30 (2017). \n\n[3] Sundararajan, Mukund, Ankur Taly, and Qiqi Yan. \"Axiomatic attribution for deep networks.\" International conference on machine learning. PMLR, 2017.\n\n> 3. I didn't quite get why explanation constraints are special? In general, one could put some constraints (e.g. regularization, etc.) along with the ERM objective to reduce the size of the hypothesis class, which will lead to a reduction in the upper bound of the excess risk. Could you please provide some justification or motivation for why the explanation constraints are special?\n\n**Our response:**  We completely agree that our framework is much more general and can handle other notions of constraints - please see our Discussion section (line 326 - 329).\n\nIn our work, we have drawn inspiration from the field of explainability where such constraints are used to train models [4,5]. The explanation constraints are provided by domain experts for which the constraint depends on the instance. For example, if we want to ignore the background of images, different images would have different constraints. This differs from standard constraints such as L2 regularization which depends only on the model parameters. We provide a specific bound for a gradient constraint which is a canonical class of explanations in the field. \n\nAs you mentioned (and as we also say in our Discussion section), this framework and the result from Theorem 2.2 holds for any notion of constraints. It is important, however, that there are models that satisfy these constraints that are also able to achieve high standard accuracy.\n\n[4] Ross, Andrew Slavin, Michael C. Hughes, and Finale Doshi-Velez. \"Right for the right reasons: training differentiable models by constraining their explanations.\" Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017.\n\n[5] Rieger, Laura, et al. \"Interpretations are useful: penalizing explanations to align neural networks with prior knowledge.\" International conference on machine learning. PMLR, 2020.\n>4. Figure 2. could be improved with some annotations and markers instead of just colors alone. The figures in experiments might be better when run with more random seeds.\n\n**Our response:**  Thank you for your suggestion. We will update the figure in the camera ready with some more descriptive annotations."}, {"review_id": "LyhEAOi8O6", "reviewer": "Reviewer_zYz5", "summary": "Disclaimer: I am not an expert in Learning Theory, but I come from a background of interpretability and explanation model’s decision making. So I am familiar with the methods that this work is trying to describe and some related works. I will review this paper modestly, and hope authors and AC can understand.  \n\n\nIn the papers, the authors studied recent methods in regularization of prediction models using explanations. An example of explanation constraints would be enforcing certain properties of the gradients of the objective w.r.t. to the data. Another would be requiring a separate teacher model that takes in the prediction model and data and require the teacher model to have specific desired outputs. Authors analyze these explanation constraints from a statistical learning perspective, such as presenting two different explanation constraints and the analysis of their learnability and generalization bounds. Then, the authors proposed the algorithm for learning with explanation constraints, and a variational method for solving the objective.  Experiments performed on synthetic data and simple real-world data demonstrates that their variational approach achieves better performance than standard approach. \n", "questions": "1. The authors claim that in Line 29 “An attractive facet of the latter is that we can automatically generate model-based explanations given unlabeled data points.” Can the authors cite works that generate model-based explanations given unlabeled data or clarify what this means? ", "limitations": "The authors did not address any limitation of their work, but addressed its social impact. One limitation could be that in this work, authors seem to focus on restricting gradients as a explanation constraints. It will be great if future work can also address other versions of explanation constraints, and potential to extensions such as feature selection methods as explanation methods. Analysis of models beyond two-layer neural network regime could potentially be discussed. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well-organized and well-written. The notation seems clear and not cluttered. The formulation and definitions are also not difficult to follow, and the writing describes most of the motivation of formulations well. Since I am not an expert, I cannot comment on the novelty of the work. Nonetheless theoretical analysis of explanation methods or methods that incorporate explanations into training are rare. So this work could potentially be a start to introducing theory in explanation methods. The authors have cited sufficient related works in the appendix. The experiments in this work are solid, where authors compared with multiple baselines and sufficiently discussed the results. The setup of the experiments also seem fair and complete. Appendix also supplies a range of ablation study such as hyperparameters. ", "weaknesses": "I do not observe any major weaknesses in this work. Although, in terms of writing, the transition into section 4.1 was a bit of a jump. It was not immediately clear to me why there is a need for variational method. Although in experiments it shows to obtain better performance that non-variational approaches, it wasn’t immediately obvious what prompted the authors to develop a variational approach, hence there seems to be a gap between going from Line 234 to line 236. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I do not observe any major weaknesses in this work. Although, in terms of writing, the transition into section 4.1 was a bit of a jump. It was not immediately clear to me why there is a need for variational method. Although in experiments it shows to obtain better performance that non-variational approaches, it wasn’t immediately obvious what prompted the authors to develop a variational approach, hence there seems to be a gap between going from Line 234 to line 236.\n\n**Our response:** Thank you for the feedback, we will provide an additional discussion in the transition into section 4.1. The main idea is that, especially in instances where computing the surrogate loss function is computationally intensive, the Lagrangian penalized objective may be expensive to optimize. Therefore, we can consider a different objective, through a projection onto a regularized class of models. \nWhile at first, this projection indeed requires computing the surrogate loss as well, the crucial advantage of this is that we can solve the projection step (this is step 1 in Section 4.1) with a **simpler class** of teacher models for which the explanation surrogate gradients are more tractable, thus resolving much of the computationally difficulty of the Lagrangian objective. We could also use different learning rates and tolerances for the projection step, again with the aim of making the optimization problem more tractable.\n\n> The authors claim that in Line 29 “An attractive facet of the latter is that we can automatically generate model-based explanations given unlabeled data points.” Can the authors cite works that generate model-based explanations given unlabeled data or clarify what this means?\n\n**Our response:** By “automatically generate model-based explanations given unlabeled data points”, we refer to the case when we can evaluate an explanation loss function phi without a domain expert. For example, if we want to encourage the model to not rely on the background features of an image and we have access to an image segmentation model. We can use this segmentation model to segment an image, giving us the background pixels in an image, which then we can penalize the feature importance of the background without the need for a human annotator. Another example presented in the paper is when we want to match the gradient of the model with the gradient of weak labelers (see Section 5.2). Since we have access to these weak labelers apriori, we can evaluate the explanation loss on any unlabeled data.\n\n"}, {"review_id": "SyWPdn5RUp", "reviewer": "Reviewer_o4F1", "summary": "In this work, the authors theoretically investigate learning with constraints on the gradient of the model. Like other works in a similar vein, this paper focuses on gradient-based explanations and on neural networks. Unlike  related works, however, this paper formulates explanation constraints as being over the data distribution rather than locally to a single input. In this setting, the authors key contributions come from their focus on a learning theoretic analysis of models that satisfy their constraints (called EPAC models) which I find to be significant contribution.\n\nThis paper is timely given the current focus on trustworthy AI and an emphasis on explainable AI in proposed legislation. I feel the analysis is simplistic in some places. Additionally, it is unused in the experimental section, and a few key prior works are not mentioned. I do believe this work provides a solid learning theoretic foundation for the budding sub-field of machine learning from explanations (MLX) and for works studying different kinds of learning constraints (e.g., adversarial certification). \n\nI will note that though I have given the paper a borderline score, I will happily update my score to an accept if the authors can substantially address my comments during the rebuttal period.", "questions": "See the above section.", "limitations": "See the weaknesses section", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "\nThe paper tackles a considerably interesting problem that will certainly have impact on future works and can serve as an important basis for understanding a budding sub-field of machine learning research.\n\nThe formulations all appear sound and correct to the best of my knowledge. \n\nThe paper is very easy to follow as it is well written. I raise a few minor points about the writing below, but in general I appreciate the high-quality of the paper’s presentation.\n\n", "weaknesses": "The main drawback of the paper is that the theory and experiments are almost wholly disjointed. The first portion of the paper focuses specifically on theoretical guarantees using standard learning theoretic tools; however, I do note see where any of these tools are experimentally evaluated even in the toy experiments. Moreover, machine learning from explanation (MLX) papers and even robust explanation constraint papers focus on datasets and models that are considerably more sophisticated than what is proposed in this paper.  \n\n* EPAC-ERM objective is exactly the same as what is proposed in prior machine learning from explanation (MLX) works, but no discussion is given. \n* For completeness the work should cite and at least discuss if not experimentally compare to papers [1][2] and [3] There are several scientifically vague sentences which I find inappropriate without further discussion of formalization. Three in particular come to mind: \n\nAnother part of the paper I find lacking is the existence of several vague scientific statements that are not backed up by formal argument or good intuition. I give three examples and my issues below: \n\n“We argue that in many cases, n labeled data are the most expensive to annotate. The k data points with explanations also have non-trivial cost; they require an expert to provide the annotated explanation or provide a surrogate loss.” - Page 6. It seems that for images at least, eliciting explanation annotations from humans is considerably more costly. Moreover, the authors claim that they “argue” the case of having a loss function, the k data points with explanations would be less costly, but I see no such argument. It is not obvious to me that eliciting a high-quality loss function $\\phi$ would be any less expensive than eliciting annotations themselves. Happy to hear an argument to the contrary, but on its own this statement feels unscientific and needs to be buttressed with an actual argument. To this end, I would find it very interesting, and I think it would also be interesting to the community working on these problems if a query/sample complexity was explicitly modeled and compared (i.e., the sample complexity of learning a loss function versus the sample complexity of learning a EPAC model from concretely provided labels) \n\n“Computing the gradients of this surrogate loss  in turn is much more expensive compared to gradients of the empirical risk.“ - Page 7. Again, I feel this is a vague and unjustified statement. The gradient of the surrogate loss for explanations is of course more expensive than the standard classification loss, but in previous papers regularization of explanations based on gradients has been done for even ResNet-50 sized models without any hint of computational strain. So, while the general case of the loss might be considerably more difficult to differentiate, in the case of studying gradient-based explanations and their losses dont seem “much more expensive” \n\n“Thus, the decoupled approach to solving the EPAC-ERM objective is in general more computationally convenient. “ - Page 7. I feel this statement would be easy enough to back up experimentally in the experimental setting put forward in this work. One can simply provide the numbers showing this. However, I am curious if this remains the case when the method is scaled up.  \n\n[1] Ross et. Al., 2017 https://arxiv.org/abs/1703.03717 (this one is cited but not compared experimentally which I think it ought to be)\n[2] Wicker et. Al. 2022 https://arxiv.org/abs/2212.08507 (this ought to be cited, but is in a different vein so no experimental comparison needed) \n[3] Czarnecki et. Al. 2017 https://arxiv.org/pdf/1706.04859.pdf (Similar aim, ought to be discussed again perhaps not experimentally compared)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. The main drawback of the paper is that the theory and experiments are almost wholly disjointed. The first portion of the paper focuses specifically on theoretical guarantees using standard learning theoretic tools; however, I do note see where any of these tools are experimentally evaluated even in the toy experiments. \n\n**Our response:** We believe that our theory and experiments are complementary. These standard learning theoretic tools are supported by our experiments - we illustrate in Figure 4 that the gradient constraint helps with performance, especially in settings with limited labeled data. This supports our theoretical result, that such models that include an explanation loss achieve lower sample complexity. \n\n> 2. Moreover, machine learning from explanation (MLX) papers and even robust explanation constraint papers focus on datasets and models that are considerably more sophisticated than what is proposed in this paper.\nEPAC-ERM objective is exactly the same as what is proposed in prior machine learning from explanation (MLX) works, but no discussion is given. For completeness the work should cite and at least discuss if not experimentally compare to papers [1][2] and [3] There are several scientifically vague sentences which I find inappropriate without further discussion of formalization. Three in particular come to mind:\n\n**Our response:**  Thank you for pointing this out. We will certaintly provide a more detailed discussion with the MLX literature.\n\n> 3. Another part of the paper I find lacking is the existence of several vague scientific statements that are not backed up by formal argument or good intuition. I give three examples and my issues below:\n“We argue that in many cases, n labeled data are the most expensive to annotate. The k data points with explanations also have non-trivial cost; they require an expert to provide the annotated explanation or provide a surrogate loss.” - Page 6. It seems that for images at least, eliciting explanation annotations from humans is considerably more costly. Moreover, the authors claim that they “argue” the case of having a loss function, the k data points with explanations would be less costly, but I see no such argument. It is not obvious to me that eliciting a high-quality loss function would be any less expensive than eliciting annotations themselves. \n\n**Our response:** Thank you for your great point. The cost of explanation annotations highly depends on how fine-grained you want your explanation constraint to be. \n\nFor example, in [1], we just want the model to ignore the background on an image. This is a relatively simple constraint and it is possible to provide a closed-form explanation loss function. For example, if we have access to an image segmentation model. We can use this segmentation model to segment an image and then penalize the feature importance of the background pixel without the need for a human annotator. \n\nHowever, if we want more complex explanation constraints such as identifying the most important features of each image then we agree that the cost of annotation will be considerably more than the cost of labeled data, and providing a high-quality loss function in this case can be difficult. This would be an interesting venue for future research.\n\nWe will provide a better clarification of this in the camera-ready version.\n\n\n> 4. To this end, I would find it very interesting, and I think it would also be interesting to the community working on these problems if a query/sample complexity was explicitly modeled and compared (i.e., the sample complexity of learning a loss function versus the sample complexity of learning a EPAC model from concretely provided labels)\n\n**Our response:** We do provide some discussion about this in Appendix C; here we discuss what types of explanation loss functions are learnable (given finite unlabeled data and “concretely provided labels” in the form of the value of this loss on those data). We also believe that this is an interesting question and that our work provides a preliminary discussion of this. We agree that modeling the complexity of designing/generating this surrogate loss is an interesting question for future work.\n\n> 5. “Computing the gradients of this surrogate loss in turn is much more expensive compared to gradients of the empirical risk.“ - Page 7. ...\n\n**Our response:** We agree that this is computable in practice for ResNet-50 sized models. That being said, the regularization of explanations based on the input gradients still take a comparatively longer time to run than learning with a standard (cross-entropy) loss.  For instance, on synthetic data with 2 layer neural networks, differentiating with respect to the norm of the input gradients is 2.5x slower than using the standard CE loss (for 10 examples over 100 epochs).\n\n> 6. “Thus, the decoupled approach to solving the EPAC-ERM objective is in general more computationally convenient. “ - Page 7... \n\n**Our response:** We provide experimental results in Appendix N.2 that show that smaller teacher models (e.g., smaller number of hidden dimensions) do not degrade the performance of our EPAC-ERM objective, which supports that this decoupled approach can be more computationally convenient. We agree that scaling this up to larger models is indeed an interesting future research agenda.\n\n> 7. [1] Ross et. Al., 2017 (this one is cited but not compared experimentally which I think it ought to be)...\n\n**Our response:** We want to point out that the method in Ross et. al. [1] is the same as the standard Lagrangian baseline in our paper; the explanation surrogate loss function here is the l2 norm of the input gradients (along the features defined in the paper), which exactly matches the second term in the objective of [1]. The only difference is the third term of Ross et. al.’s objective, which is a standard L2 regularization. We will make this clearer in the main text of our paper.\n\n\n\n\n\n"}, {"review_id": "qHLeTD1j5X", "reviewer": "Reviewer_w12b", "summary": "Traditionally, learning from labelled examples has been well studied. However, with the advent of large models (and few-shot learning) and risk of misspecifications (spurious correlations), need for augmenting supervision such as with example explanations is gaining wider interest.\nThis paper deals with this timely topic of analysing when and how learning from explanations can improve sample efficiency.\nAlthough learning from explanations is also promising in reducing systematic biases, this paper focusses on sample efficiency.\nThey also propose an interesting learning algorithm to accommodate explanation constraints.\n\nI believe the topic and analysis is timely but I have a few concenrns regarding evaluation and analysis.", "questions": "Please see weaknesses above.", "limitations": "Addressed.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Important practical problem.\n- Well written and easy to follow.\n- The proposed variational method is smart, which can exploit both labelled, unlabelled data along with explanations.", "weaknesses": "Disclaimer: I have not checked the proofs. But the statements seem correct.\n\nConsider the following also as questions.\n\n*How are explanations different?* Fundamentally, I did not understand why explanation constraints are given a status different from example labels. Can we not simply consider them to be additional labels and minimize the joint risk such as in the Lagrangian method or Rieger et.al. and handle the error bound using the classical analysis as shown between L161 and L162?\nEspecially since the explanations are imposed only approximately through objective functions. \n\n*Clarification regarding Theorem 2.2.* From L 156: \"... help with our learning by shrinking the hypothesis class $H$ to $H_{\\phi,\\tau+\\epsilon_k}$\". Although this sounds intuitively correct, from the definition of $H$, isn't $H_{\\phi, \\tau+\\epsilon_k}$ larger than $H$?\nMoreover, I do not see how constraints help improve the sample complexity since both $R_n(H_{\\phi,\\tau+\\epsilon_k})$ and $err_D(h^*_{\\tau-\\epsilon_k})$ increase for a non-zero value of $\\epsilon_k$?\n\n*Motivation for variational method.* The need for variational method is motivated to avoid evaluating gradients of a potentially complicated surrogate loss: $\\phi$, however even the variational method needs to evaluate the same when optimizing for $f$ in the first step.\n\n*Evaluation concern*. Lagrangian method may have performed poorly because it is not exposed to unlabelled data unlike variational. What happens if we add an additional term to lagrangian objective on unlabelled data that is similar to self-training?\nOtherwise, I do not see why lagrangian may poorly perform when compared with variational at least when we can compute gradient of gradients well (which is not much of a problem these days). \n\n*Real world performance gains are unimpressive*. (Section 5.2 and Figure 5). I cannot clearly see the observation noted in L312-L313: \"We observe that our variational objective achieves better performance than all other baseline approaches, across varying amounts of labeled data.\"\nThe weak labellers and the task should be better defined. How are the gradients (of $\\phi$) computed (for say largrangian method) when weak learners are used for imposing constraints? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. How are explanations different? Fundamentally, I did not understand why explanation constraints are given a status different from example labels. Can we not simply consider them to be additional labels and minimize the joint risk such as in the Lagrangian method or Rieger et.al. and handle the error bound using the classical analysis as shown between L161 and L162? Especially since the explanations are imposed only approximately through objective functions.\n\n**Our response:** While you can do something like Rieger et.al., this does not fit into a standard learning theoretic framework, which analyzes when we only have class labeled examples. To theoretically analyze this setup, we need to use a learning theoretic framework that handles the classification loss and explanation loss separately. Explanation constraints here can be information that aren’t standard class labels for our data, e.g. ignoring the background. Since the explanations and labels are different, the classification loss and the explanation loss are different objects. \n\n>2. Clarification regarding Theorem 2.2. From L 156: \"... help with our learning by shrinking the hypothesis class $H$ to $H_{\\phi,\\tau + \\epsilon_k}$ \". Although this sounds intuitively correct, from the definition of $H$, isn't $H_{\\phi,\\tau + \\epsilon_k}$ larger than $H$ ? Moreover, I do not see how constraints help improve the sample complexity since both $R_n(H_{\\phi,\\tau + \\epsilon_k})$ and $err_D(h^*_{\\tau - \\varepsilon_k})$ increase for a non-zero value of  $\\varepsilon_k$?\n\n**Our response:** No, $H_{\\phi, \\tau + \\epsilon}$ is a subset of $H$ and therefore is smaller than that of $H$. We recall the definition of $H_{\\phi, \\tau + \\epsilon_k}$ as any function in $H$ that the expected explanation loss is at most $\\tau + \\epsilon_k$. In fact, we can think of $H$ as $H_{\\phi, \\infty}$. Consequently, the complexity term $R_n(H_{\\phi, \\tau + \\epsilon_k})$ is smaller than that of $R_n(H)$ - and we give bounds on how much smaller this is for 2 layer NNs and linear models in Thoerems 3.1 and 3.2. \n\n>3. Motivation for variational method. The need for variational method is motivated to avoid evaluating gradients of a potentially complicated surrogate loss: $\\phi$, however even the variational method needs to evaluate the same when optimizing for $f$ in the first step.\n\n**Our response:** This is an astute observation; the underlying motivation for the variational method is to potentially achieve more efficient solutions to complicated constrained optimization problems. When compared to the standard Lagrangian penalized method, as is done in [1], the variational objective simplifies the Lagrangian objective even further by a sum of two terms, one of which is the empirical risk, and the other is a projection error onto the set of hypotheses that satisfy a bound on the explanation surrogate risk. A crucial advantage of such a decoupling is that we can reduce this to two steps (these are steps 1 and 2 in Section 4.1): a projection step of projecting current model onto the set of those with bounded explanation risk, and a synthesis step where we use the training labels as well as pseudo-labels from the projected model. \nThe crucial advantage of this decoupling is that we can solve the projection step (this is step 1 in Section 4.1) with a **simpler** class of models for which the explanation surrogate gradients are more tractable, thus resolving a critical caveat with the Lagrangian objective. We could also use different learning rates and tolerances for the projection step, again with the aim of making the optimization problem more tractable.\n> 4. Evaluation concern. Lagrangian method may have performed poorly because it is not exposed to unlabelled data unlike variational. What happens if we add an additional term to lagrangian objective on unlabelled data that is similar to self-training? Otherwise, I do not see why lagrangian may poorly perform when compared with variational at least when we can compute gradient of gradients well (which is not much of a problem these days).\n\n**Our response:** We already have this comparison in the Appendix section L (additional baselines)! We also observe that a lagrangian with a single round of self-training afterwards is also worse in satisfying constraints on new test data, which in turn leads to worse performance in limited labeled data settings. This supports our method’s use of multiple rounds of incorporating these explanation constraints.\n\n>5. Real world performance gains are unimpressive. (Section 5.2 and Figure 5). I cannot clearly see the observation noted in L312-L313: \"We observe that our variational objective achieves better performance than all other baseline approaches, across varying amounts of labeled data.\" The weak labellers and the task should be better defined. How are the gradients (of $\\phi$) computed (for say largrangian method) when weak learners are used for imposing constraints?\n\n**Our response:** We will make this claim a bit less strong, but we still observe the following: “Our variational objective achieves better performance than all other baselines, on the majority of settings defined by the number of labeled data”\nThe procedure for generating gradients is taken from a prior work [4]. The high level idea is that we can consider random inputs into these weak learners, and differentiate with respect to the parameters of this distribution to get a proxy for the gradient of these weak learners. In the case for weak learners that are hand-engineered lookup functions or regular expressions for language tasks, this corresponds to extracting feature indices for particular words or characters in the regular expression pattern.\n\n[4] D. Sam and J. Z. Kolter. Losses over labels: Weakly supervised learning via direct loss construction. https://arxiv.org/abs/2212.06921\n\n\n"}, {"review_id": "ePko7EXQ9v", "reviewer": "Reviewer_9kMr", "summary": "This paper tries to answer an important and fundamental question: why can interpretability constraints on model parameters improve model performance. The authors developed an analytic framework. They first define constraints as a functional on a model function and a data point, and the model satisfying the constraint is hence represented as the functional value lies in a set. Following this setup, they defined the surrogate loss based on the constraint violation, and showed the generalization bound on this constraint violation loss. They showed that the constraints helped shrink the hypothesis class. They also showed that with gradient constraints, linear and 2-layer NN models could benefit in requiring fewer labeled data. They also discussed optimization algorithms through projections that could make the model satisfy the constraints.", "questions": "Please address the comments in the weakness section.", "limitations": "This paper doesn't have potential negative societal impact. The authors are encouraged to discuss the plausibility of the conditions of their theorems.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper tries to answer an important and fundamental question: why can interpretability constraints on model parameters improve model performance. The presentation of this paper is clear, techniques sound, and contributions good. ", "weaknesses": "The paper lacks a discussion on the stringency of their conditions in theorems, which makes it more difficult to judge the significance of the contribution.\nThe paper focus on gradient constraints and lacks a discussion and related work on model shape constraints, such as monotonicity and convexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper lacks a discussion on the stringency of their conditions in theorems, which makes it more difficult to judge the significance of the contribution. The paper focus on gradient constraints and lacks a discussion and related work on model shape constraints, such as monotonicity and convexity.\n\n**Our response:** Our result presents the reduction in the Rademacher complexity of an EPAC model for a class of linear models and two-layer neural networks. (Theorem 3.1, 3.2). We have already provided a short discussion on the assumption of the gradient constraints for neural networks between lines 205-210. Our results apply to a general data distribution (see Theorem H.1 for linear models) and distributions where samples from this have a bounded norm in expectation (Theorem 3.2 for neural networks). This assumption on the bounded norm (in expectation) of data samples for NNs is a standard assumption in practice and is not restrictive of particular tasks; for example, a Gaussian distribution satisfies this assumption.\nWe also make the assumption for our proof for neural networks that the support is large enough, or more specifically, that each partition of the input space (partitions being defined by values of the hidden layer of the neural network) has a positive probability mass. This is not a strong assumption, and it holds for any distribution where the support is the $R^d$, for example, Gaussian distributions. We will add these clarifications to our revision.\n\n\nWe focus on gradient constraints since our work is motivated by a line of works in the field of explainability where such explanation constraints are used to train models [1,2], and input gradients are one of the canonical classes of explanations. We will discuss the other notions of constraints that you have mentioned in the camera-ready version. \n\n[1] Ross, Andrew Slavin, Michael C. Hughes, and Finale Doshi-Velez. \"Right for the right reasons: training differentiable models by constraining their explanations.\" Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017.\n\n[2] Rieger, Laura, et al. \"Interpretations are useful: penalizing explanations to align neural networks with prior knowledge.\" International conference on machine learning. PMLR, 2020.\n"}]

Author rebuttal:
**General response**


We would like to thank all the reviewers for their efforts in providing thoughtful and attentive examinations of our work. We are glad to see that the reviewers highlighted a number of strengths, including:
1. The paper tries to answer an “interesting”(o4F1) and “important” problem (9kMr, w12b)
2. The paper has a “good contribution” (9kMr) and could potentially be “a start to introducing theory” in explanation methods (zYz5) and can “serve as an important basis” for understanding the subfield (o4F1)
3. The paper is “well-written” (zYz5, o4F1, w12b) and has a “clear presentation” (9kMr)
4. The proposed method “works better than other baselines” (3fR6) and the setup of the experiments also seems “fair and complete” (zYz5).

We respond to individual reviewer comments in the individual threads. Thank you again for your hard work and consideration.


Meta-review: This paper joins an interesting area where additional information can be used on top of a labeled dataset for supervised learning. It proposes a framework for learning from information in the form of a type of explanation---here mathematically modeled as functionals. It provides learning-theoretic results, algorithms, and reasonably varied and convincing empirical results. 

This paper formalizes notions that are often used casually and provides a comprehensive analysis. Such papers are often useful to clarify concepts and approaches that are only touched on intuitively. The reviewers agreed and largely found the work compelling.
Decision: Accept (poster)