Théophile Cantelobre

Benjamin Guedj

María Pérez-Ortiz

John Shawe-Taylor

A PAC-Bayesian Perspective on Structured Prediction with Implicit Loss Embeddings

Keywords: Structured-Prediction Statistical learning theory, PAC-Bayes theory, Structured output prediction, Implicit Loss Embeddings, Generalization bounds ©2020

Many practical machine learning tasks can be framed as Structured prediction problems, where several output variables are predicted and considered interdependent. Recent theoretical advances in structured prediction have focused on obtaining fast rates convergence guarantees, especially in the Implicit Loss Embedding (ILE) framework. PAC-Bayes has gained interest recently for its capacity of producing tight risk bounds for predictor distributions. This work proposes a novel PAC-Bayes perspective on the ILE Structured prediction framework. We present two generalization bounds, on the risk and excess risk, which yield insights into the behavior of ILE predictors. Two learning algorithms are derived from these bounds. The algorithms are implemented and their behavior analyzed, with source code available at https://github.com/theophilec/ PAC-Bayes-ILE

Introduction

Structured prediction (also referred to as Structured output prediction) is a widely studied problem in machine learning of great theoretical and practical interest. Broadly, we define Structured prediction as the joint prediction of interdependent or constrained decision variables.

Although we make this definition precise below, let us first present an example of a recent application of Structured prediction: Scene Graph Generation. Given an image, a goal can be to extract the semantic information that describes the depicted scene, that is, to detect objects present in the image and the semantic relationships between them. Formally, the task consists in predicting a graph of all entities and the relations between then from an image (for example, the man is wearing a hat). Note that this graph is on the instance level, so the man wearing the hat, is known to be the same one holding a bucket (which the horse is known to be eating from).

The decision variable for this task is the scene graph. Seen as a discrete object, its domain is combinatorially large. Although it would be possible to first predict instances independently, and then the relations between pairs of detected instances, this strategy clearly appears sub-optimal.

Imagine for example that the entities predicted are, for whatever reason, a dog and a lion. Jointly predicting the entities avoids predicting particularly improbable pairs. On the other hand, even if not all entity and relation triplets are represented in the training data, the correlations between objects should hopefully be taken into account. For example, even if the particular configuration of a horse eating from a bucket is not in the training data, all other domestic animal feeding situations are correlated with it (man feeding cow with a bucket, man feeding a horse with another object, etc.). We refer the interested reader to [START_REF] Liu | Visual semantic information pursuit: A survey[END_REF] which provides a complete survey of the field of Visual Semantic Information Pursuit.

Beyond practical applications, prediction of joint or constrained variables is of great theoretical interest and encompasses tasks such as ordinal regression, multiclass classification, multilabel classification, or manifold regression, to cite but a few. In fact, we will see that most machine learning problems can be formulated as a form of Structured output prediction problem, from binary classification to ordinal regression. Furthermore, many theoretical and practical challenges of statistical learning are present in Structured output prediction:

1. Both training and inference are NP-Hard in general, making large-scale (in problem size, and dataset size) problems hard to solve. Indeed, many common approaches to optimization rely on repeatedly performing inference on (part of) the training set (for example, the Structured SVM algorithm, see [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF].

2. Seen as a classification problem with a very large label space, Structured output prediction has few statistical or algorithmic guarantees with respect to standard approaches. In fact, as highlighted by Nowak-Vila et al. (2019b), many algorithms are known to be inconsistent.

In this work, we present a PAC-Bayes analysis of the Implicit Loss Embedding (ILE) approach to Structured prediction. In particular we concentrate of studying the generalization and consistency properties of the ILE approach.

Generalization. The former is a central problem in statistical learning theory and quantifies how well we can expect the performance of a predictor trained on a finite dataset to generalize to the entire data-generating distribution. There would be too many seminal contributions to the study of generalization to cite -we refer to [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF] and [START_REF] Vapnik | Statistical Learning Theory[END_REF] and references therein.

In this work, we consider the PAC-Bayes learning paradigm to study generalization. A generalization of the Probably Approximately Correct framework of [START_REF] Valiant | A theory of the learnable[END_REF], PAC-Bayes bounds originate in the seminal papers of [START_REF] Shawe-Taylor | A PAC analysis of a Bayes estimator[END_REF]; [START_REF] Mcallester | Some PAC-Bayesian theorems[END_REF][START_REF] Mcallester | PAC-Bayesian model averaging[END_REF] and further developed by [START_REF] Seeger | PAC-Bayesian Generalization Error Bounds for Gaussian Process Classification[END_REF]; Catoni (2004Catoni ( , 2007)). In this framework, instead of considering the generalization qualities of a given predictor, we study that of a distribution of predictors, learned from the training data. The bounds we aim to obtain make little to no hypotheses on the data-generating distribution. There has been a surge of interest in PAC-Bayes in the past few years, as it has re-emerged as a promising framework for assessing generalization performance in several settings, such as coherent risk measures [START_REF] Mhammedi | PAC-Bayesian Bound for the Conditional Value at Risk[END_REF], deep neural networks [START_REF] Dziugaite | Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data[END_REF][START_REF] Letarte | Dichotomize and generalize: Pac-bayesian binary activated deep neural networks[END_REF], differential privacy (Dziugaite and Roy, 2018b,a), meta-learning [START_REF] Amit | Meta-learning by adjusting priors based on extended pac-bayes theory[END_REF] or contrastive learning [START_REF] Nozawa | Pac-bayesian contrastive unsupervised representation learning[END_REF] to name but a few. We refer to [START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF] for a recent survey and to [START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF] for a recent tutorial on PAC-Bayes. We outline some contributions of PAC-Bayesian theory to Structured prediction in the Prior work paragraph below.

Consistency. In statistical learning theory, much effort has been spent solving the intractability of minimizing the empirical 0 -1 loss. We will make the definition of consistency precise in what follows. Broadly, a surrogate method is consistent for a given task (for example, minimizing the empirical 0 -1 loss) if minimizing the surrogate loss (for example, the quadratic loss) solves the task. For general treatments about consistency, see for example [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF] and [START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF].

In the rest of the paper, we introduce and reason around Fisher consistency and its implications in practice.

Prior work. There have been many attempts to tame the Structured output prediction problem, both from a statistical and an algorithmic point of view. These include for example many ad hoc approaches such as Structural Support Vector Machines [START_REF] Tsochantaridis | Support vector machine learning for interdependent and structured output spaces[END_REF] or Conditional Random Fields [START_REF] Lafferty | Conditional random fields: Probabilistic models for segmenting and labeling sequence data[END_REF][START_REF] Taskar | Max-Margin Markov Networks[END_REF]. [START_REF] Nowozin | Structured learning and prediction in computer vision[END_REF] provides a survey of applications of Structured prediction for Computer vision. [START_REF] Wainwright | Graphical models, exponential families, and variational inference[END_REF] presents a unified approach to learning and inference over graphical models. Many ensemble methods based on building efficient subgraphs over graphical models have been developed: for example, [START_REF] Rakotomamonjy | [END_REF], [START_REF] Bach | Multiple kernel learning, conic duality, and the SMO algorithm[END_REF], [START_REF] Argyriou | Convex multi-task feature learning[END_REF], Marchand et al. (2014).

Several quadratic methods have focused on (consistently) training quadratic surrogate methods for the Structured learning problem. These include Kernel Dependency Estimation (KDE, see [START_REF] Weston | Kernel dependency estimation[END_REF][START_REF] Cortes | A general regression framework for learning stringto-string mappings[END_REF], Input-Output Kernel (for example, [START_REF] Brouard | Input output Kernel regression : supervised and semi-supervised structured output prediction with operator-valued kernels[END_REF] and ILE approaches [START_REF] Buitinck | A consistent regularization approach for structured prediction[END_REF]Osokin et al., 2017;[START_REF] Rudi | Manifold structured prediction[END_REF]Nowak-Vila et al., 2019a;Ciliberto et al., 2019). Non-quadratic methods also exist [START_REF] Nowak-Vila | Consistent structured prediction with max-min margin markov networks[END_REF]. For instance, Nowak-Vila et al. (2019b) generalizes the ILE framework to a more general class of surrogates.

Several authors have proposed PAC-Bayes approaches to Structured prediction. Let us cite just three works which show the diversity of the PAC-Bayesian approach: Marchand et al. (2014) uses PAC-Bayes arguments to justify an approximation strategy for graphical models, while [START_REF] Mcallester | Generalization Bounds and Consistency for Structured Labeling[END_REF] provides generalization bounds with a focus on tasks involving language models. Finally, [START_REF] Giguère | Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction[END_REF] provides a PAC-Bayesian generalization bound for the KDE algorithm, which we will return to. For completeness we also mention recent works focusing on the decoding problem (that is, constructing a solution to the task from the surrogate solution), even though this falls outside of the scope of this paper [START_REF] Mensch | Differentiable dynamic programming for structured prediction and attention[END_REF]Blondel, 2019).

Contributions. In this work, we propose an original PAC-Bayes analysis of the ILE framework in [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF]. For most of the paper, we concentrate on the multilabel problem. In particular:

• We provide a PAC-Bayes generalization bound using classic PAC-Bayes arguments based on [START_REF] Zhang | Information-theoretic upper and lower bounds for statistical estimation[END_REF].

• We extend the Comparison inequality in [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] to propose a new bound on the expected excess risk that depends on the performance of the predictor distribution on the training set. This result holds with high probability over the training set, thanks to recent work on PAC-Bayes generalization bounds in [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF] for unbounded loss functions, such as commonly used regression losses.

• We thoroughly analyze the bound and its behavior, allowing us to illustrate the importance of using a structured loss (for example, the Hamming loss) instead of the 0 -1 loss. This yields theoretical insights as well as practical advice for Structured prediction.

• Finally, we present learning algorithms derived from our novel PAC-Bayes bound and test their performance on Structured output prediction datasets. All our experiments are reproducible from the associated GitHub repository1 .

The rest of the paper is organized as follows: in Section 2, we introduce the Structured learning formulation and the ILE framework. In Section 3, we present our PAC-Bayes classification bound for ILE Structured output prediction. In Section 4, we derive and analyze a novel PAC-Bayes generalization bound providing insights into the consistency of ILE methodology. In Section 5, we solve the multi-label classification problem on Structured output prediction datasets using the derived result, through two methods. In Section 6 we put our results into perspective with respect to the ILE framework. Finally, we gather our experimental results in Section 7.

Structured output Learning with Implicit Loss Embeddings

We now introduce our notation and the Implicit Loss Embedding (ILE) framework for Structured output prediction.

Supervised Learning & Excess risk

Let X be an input space equipped with a kernel k(x, x ) = φ(x), φ(x ) for any x, x ∈ X. Let Y be the label space for the training data, and Z denotes the output space. In many cases, Y = Z, but the distinction is necessary, for example, in information retrieval. Indeed in this setting, X can be for example the space of search engine queries with Z an ordering over documents presented in response to a query and Y a relevance score for each result for the query (instead of a ranking). Let ∆ : Z × Y → R be a non-negative loss function.

We aim to solve the supervised learning problem, i.e., given a dataset {(x i , y i )} m i=1 drawn i.i.d. from a data-generating distribution ρ over X × Y, find a measurable function f m : X → Z that minimizes the expected task risk (or Bayes risk) defined by:

F H X Z Y h d f =d•g X g ψ ∆= ψ,ϕ ϕ
E(f ) = X×Y ∆(f m (x), y)dρ(x, y). (1)
We define f * the optimal predictor given by:

f * = arg min fm:X→Z E(f m ), (2)
where X → Z denotes all measurable functions from X to Z.

We define the expected excess risk E(f m )-E(f * ) between f m and f * , which characterizes the sub-optimality of a predictor f m with respect to the task loss ∆ and data-generating distribution ρ.

In what follows, we present the ILE framework of [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] as well as some selected results. We refer to [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] and references therein for a more complete treatise.

Implicit Loss Embedding

The central idea to the ILE framework is the existence of an embedding of the output and label spaces such that the loss function ∆ is the dot product of the embedding functions to this space (similarly to the idea behind the use of kernels). Formally, we define an Implicit Loss Embedding for ∆ as follows. See Figure 1 for a summary illustration of the different involved sets and maps.

Definition 1 (Implicit Embedding, ILE). A loss function ∆ : Z × Y → R has an Implicit Loss Embedding (ILE) if there exists a Hilbert space H and two measurable maps ϕ : Y → H and ψ : Z → H such that

∀(z, y) ∈ Z × Y, ∆(z, y) = ψ(z), ϕ(y) .
(3)

Let us motivate the introduction of this definition. First, notice that most structured (and indeed unstructured) loss functions fall into this formalism. For example, if Y and Z are finite, then the ILE is the matrix formed by the values of the loss function for (y, z) pairs, encoded as one-hot encodings e y and e z . In Example 1, we show that the Hamming loss for multi-label classification has an ILE. We offer a formal definition of the -multilabel binary classification problem.

Problem 1 ( -multilabel binary classification problem). With ∈ N * , let Y = {0, 1} . Within the formalism described in Section 2.1, the problem is to learn a predictor f : X → Y from training data sampled iid from the data-generating distribution ρ over X × Y.

Some generic examples of -multilabel binary classification problems include for example detecting several characteristics of input datum x (i.e. different objects present in an image, topics of a text, presence of different defects). Using a similar example as in the introduction, detecting several objects in an image should be easier if the objects are jointly predicted.

Example 1. In binary -multi-label learning, the Hamming loss H is ILE where

H(z, y) = 1 k=1 I(z k = y k ) = 1 - 1 k=1 I(z k = 0)I(y k = 0) + I(z k = 1)I(y k = 1). (4)
Furthermore, |Y| = 2 and dim(H) = 2 + 1.

Different authors have shown that a wide variety of machine learning problems fall into the ILE framework. As a matter of fact, Ciliberto et al. (2020, Sec. 6) provide a collection of simple sufficient conditions for a learning problem to admit an ILE (the finite cardinality of Y and Z is the simplest of such conditions).

Second, the "separability" of ∆ as illustrated in Eq. ( 6) ensures that the learning problem can be (Fisher-)consistently solved by solving a more computationally efficient quadratic regression problem, approximating ϕ(y) from x. In particular, this ensures that, in structured contexts, the so-called pre-image problem is not solved during training as it is in Structured SVM methods.

In what follows, we assume that ∆ is ILE with associated maps ψ and ϕ. We also assume that Y and Z are finite sets, and that H is finite dimensional. In specific examples, we will return to the -multi-label binary classification problem with the Hamming loss, as defined in Problem 1 and Eq. (4).

Quadratic surrogate and consistency

Under the assumptions that the task loss is ILE and that the data-generating distribution ρ can be factorized as ρ(x, y) = ρ(x)ρ(y|x), [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] prove the following results, which naturally lead to a consistent surrogate method (in a sense we define below). We briefly survey this approach to set the context and demonstrate the utility of such a framework, in theory and in practice. [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] first prove that the pointwise conditionally optimal predictor is identically equal to the minimizer of Eq. (1):

Lemma 1 [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF]. Assume that the data-generating distribution ρ can be factorized as ρ(x, y) = ρ(y|x)ρ X (x), then

f * (x) = arg min z∈Z Y ∆(z, y)dρ(y|x).
(5)

From this, because ∆(z, y) = ψ(z), ϕ(y) is linear in ϕ(y), the optimal predictor f * is naturally written as a function of the conditional mean embedding of ϕ(y) given x, which we denote g * (x) = Y ϕ(y)dρ(y|x), i.e., f * (x) = arg min z∈Z ψ(z), g * (x) .

(6) Thus, in order to estimate f * , it is natural to seek to estimate g * by g and "plug-in" g to define f as ∀x ∈ X, f (x) = arg min z∈Z ψ(z), g(x) .

It can be shown, see for example [START_REF] Grünewälder | Conditional mean embeddings as regressors[END_REF], that g * is the minimizer of the following expected quadratic risk:

R(g) = X×Y ϕ(y) -g(x) 2 dρ(x, y). (8)
A consistent empirical counterpart of Eq. ( 8) for a given sample is:

R n (g) = 1 n n i=1 g(x i ) -ϕ(y i ) 2 + λ g 2 , ( 9
)
where λ is a regularization parameter. There exist α 1 , . . . , α n n functions in X → H such that g n minimizes R n where g n is defined by

g n (x) = n i=1 α i (x)ϕ(y i ). ( 10
)
The associated classifier is thus defined by:

∀x ∈ X, f n (x) = arg min z∈Z ψ(z), g n (x) (11) = arg min z∈Z n i=1 α i (x) ψ(z), ϕ(y i ) . (12)
The above computation is called the "loss trick" by [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] in analogy to the well-known "kernel trick". This proves that the existence of the ILE embedding is enough and that knowledge of ϕ and ψ are not required.

Efficiently solving the decoding problem. As we have outlined above, the general structure of the ILE learning method is to solve a quadratic surrogate regression problem, and then at inference solve a decoding problem (the arg min in Eq. ( 6)). A priori, this can be solved in O(|Z|) time. Because |Z| is combinatorial in nature (for example |Z| = 2 for the -label binary classification problem) this can be costly and even impossible at large scale.

In this work, we focus on the link between the plug-in classifier f n and the surrogate regressor g n without worrying about how the arg min is computed. The problem of efficiently solving the decoding problem is the subject of some recent work in, for example, Blondel (2019); [START_REF] Mensch | Differentiable dynamic programming for structured prediction and attention[END_REF].

Fisher consistency [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] show that estimating g is Fisher consistent, i.e., that if the optimal regressor g * is found, then the associated predictor f * is optimal for E. Formally, there exists a map d : H → Z (for example, the arg min function over Z)

such that E(f * ) = E(d • g * ).
They prove a stronger result, upper-bounding the expected excess prediction risk E(f )-E(f * ) as a function of the expected excess regression risk R(g) -R(g * ), their comparison inequality. This result will be the basis for our own analysis in Section 4. For easy crossreferencing, we present a stronger version of the inequality obtained by withholding the last step in the proof of the inequality in [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF].

Theorem 2 (Strong Comparison Inequality). Assume Z is compact and ∆ has an ILE. Let g : X → H be measurable, and f defined as in Eq. (7). Then,

(f ) -(f * ) ≤ 2c ∆ X g(x) -g * (x) dρ X (x),
where c ∆ = sup z∈Z ψ(z) and ρ X is the data-generating distribution marginalized over y.

In particular, this implies the Comparison inequality (Theorem 3).

Theorem 3 (Comparison inequality, Thm. 3, Ciliberto et al., 2020). Assume Z is compact and ∆ has an ILE. Let g : X → H be measurable, and f defined as in Eq. (7). Then,

E(f ) -E(f * ) ≤ 2c ∆ R(g) -R(g * ),
where c ∆ = sup z∈Z ψ(z) .

Note that such calibration functions exist for a wider range of surrogates, see Nowak-Vila et al. (2019b) for a more general approach. These results are analogous to the ψ-transform bounds in, for example, [START_REF] Bartlett | Convexity, classification, and risk bounds[END_REF].

In this section, we presented the supervised Structured learning problem and the ILE framework. We also introduced the relevant results for the rest of the paper. We now present the PAC-Bayes approach, as well as prove our first results.

A PAC-Bayes take on ILE classification

In this section, we offer a novel perspective on the learning problem described in Section 2 using tools from the PAC-Bayes framework. We first outline the main tenets of the PAC-Bayes approach, and a classic PAC-Bayes bound. Using these tools we prove a generalization bound for ILE classification.

Notation. In the rest of the paper, we define the empirical task risk as:

E m (f ) = 1 m m i=1 ∆(f (x i ), y i ). ( 13
)
The expectation of the measurable function f of a random variable X with domain X under distribution Q is defined as (when it exists):

E X∼Q f (x) = X f (x)dQ(x).
The Kullback-Leibler divergence between distributions Q and P is denoted K(Q, P) and defined as

K(Q, P) = log dQ(x) dP(x) dQ(x).
When there is no ambiguity, we identify linear maps between finite-dimensional vector spaces, associated matrices in the canonical bases, and the vectors of matrix coordinates. Finally, in the rest of the paper, we will make the slight notation abuse of writing f ∼ Q when f is the structured predictor associated to stochastic regressor g ∼ Q.

Canonical PAC-Bayes bounds

We introduce the PAC-Bayes setting and present a canonical PAC-Bayes generalization bound from [START_REF] Zhang | Information-theoretic upper and lower bounds for statistical estimation[END_REF]. In PAC-Bayes theory, one considers stochastic predictors sampled from a distribution Q over the space of measurable maps {f : X → Z}. Intuitively, this can be understood as sampling a different predictor from a distribution Q for each inference task, for example for each data-point in a dataset.

Thus, if learning is generally the process of estimating an optimal predictor, in the PAC-Bayes approach, learning consists in estimating an optimal distribution of predictors. Similarly to the general learning setting, the definition of "optimality" depends on the performance of the predictor (distribution) on the training set and on regularization terms.

Because the optimized distribution Q depends on the training set used for "learning": in analogy to Bayesian statistics, this distribution is called the posterior. Conversely, we consider a data-independent prior distribution over predictors P.

The result below bounds the expected risk over a posterior distribution Q of predictors from the empirical risk over the dataset, with high probability over the training set. Note that the bound holds for any data-generating distribution ρ. The generalization penalty terms contain the Kullback-Leibler divergence between Q and P. Because the Exponential information inequality presented in [START_REF] Zhang | Information-theoretic upper and lower bounds for statistical estimation[END_REF] uses an alternative so-called one-sample formulation, we refer to the corresponding result in [START_REF] Giguère | Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction[END_REF]:

Theorem 4 (Giguère et al., 2013, Thm. 10.3.). Let ζ be an arbitrary (in particular, not necessarily bounded) loss function.

For any data-independent distribution P, δ > 0, and a > 0, with probability at least 1 -δ over the training set drawn from ρ m , for any posterior distribution Q such that Q P and P Q,

-E g∼Q log E x,y∼ρ e -ζ(g(x),y) ≤ 1 m E g∼Q m i=1 ζ(g(x i ), y i ) + K(Q, P) + log 1 δ .
We use Theorem 4 to prove a first result below.

ILE generalization bound

In this section, we prove the following novel result, which applies Theorem 4 to ILE Structured prediction:

Theorem 5 (Classification bound). Assume that ∆ admits an ILE defined by ∆(z, y) = ψ(z), ϕ(y) . Let g : X → H a measurable function, and f (x) = arg min z∈Z ψ(z), g(x) .

For any data-independent distribution P, for any δ > 0, for any λ > 0, with probability at least 1 -δ over the training set sampled iid from ρ m , for any posterior distribution Q such that Q P and P Q,

E f ∼Q E(f ) ≤ ae e -1 1 -exp - 1 a E f ∼Q E m (f ) - K(Q, P) + log 1 δ m . ( 14
)
The proof of Theorem 5 is inspired by the proof of Theorem 10.4 in [START_REF] Giguère | Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction[END_REF]. We first prove an exponential bound on the identity, with a slack parameter a. Figure 2 illustrates the bound.

Proposition 6 (Exponential bound on the identity, with slack parameter). For any a > 1,

∀x ∈ [0, 1], x ≤ ae e -1 1 -e -x a . ( 15
)
Proof The function f defined by

f (x) = e e-1 (1 -e -x ) on [0, 1] is concave. Since, f (0) = 0 and f (1) = 1, ∀x ∈ [0, 1], x ≤ f (x) (f is over its chords). The result follows because 1 a [0, 1] ⊂ [0, 1] (a > 1).
Proof (Theorem 5) Let P be a prior distribution on regression functions. Let δ > 0 and Q be a distribution over regression functions.

Let a > 1. Denote:

ζ(f (x), y) = ∆(f (x),y) a .
Then, by Theorem 4, with probability at least 1 -δ on the training set sampled iid from ρ m , we have

-E g∼Q log E x,y∼D e -ζ(g(x),y) ≤ 1 m E g∼Q m i=1 ζ(g(x i ), y i ) + K(Q, P) + log 1 δ . Because x → -log x is convex, by Jensen, -log E g∼Q E x,y∼D e -ζ(g(x),y) ≤ 1 m E g∼Q m i=1 ζ(g(x i ), y i ) + K(Q, P) + log 1 δ . Because x → -exp(-x) is non-decreasing, -E g∼Q E x,y∼D e -ζ(g(x),y) ≤ -exp - 1 m E g∼Q m i=1 ζ(g(x i ), y i ) + K(Q, P) + log 1 δ . (16)
On the other hand, from Proposition 6 applied to ∆(f (x), y),

∆(f (x), y) ≤ ae e -1 1 -e -∆(f (x),y)/a . ( 17
)
We conclude by combining Eq. ( 16) and Eq. ( 17).

It is important to note that the value of the bound depends on the performance of a given distribution of predictors on the training set, independently of how the distribution is obtained. We return to this discussion in Section 6.

PAC-Bayes analysis of consistency

In the previous section, we proved a PAC-Bayes bound on the expected risk of the stochastic predictor E∆(f (x), y) (the expectation is taken with respect to f ∼ Q and x, y ∼ ρ). The bound depends on the empirical risk of the stochastic predictor f E 1 m i ∆(f (x i ), y i ) (where the expectation is taken with respect to f ∼ Q only) and a penalty term. This can give a tight estimate of the generalization properties of a supervised classification problem.

However, minimizing the upper bound is at least as hard as solving the ILE Structured prediction problem directly. Thus, it does not provide an efficient way of learning: we cannot, given a model of posterior, estimate the parameters for which we minimize the bound. Furthermore, the results introduced in Section 3 pertain to generalization and do not quantify the sub-optimality of the predictor of f (compared to f * ) as a function of the sub-optimality of g.

We propose an approach to solving the latter problem in this section. In Section 5 we use these results to learn a posterior Q over predictors from a training set (x 1 , y 1 ), . . . , (x m , y m ).

In this section, we aim to bound the expected excess risk of a (stochastic) predictor f using the empirical excess quadratic surrogate risk. Our contributions are original in several respects: first, they incorporate the finite-sample performance of the predictor distribution in true PAC-Bayes fashion, giving actionable insight into the value of a predictor distribution; second, in the case of finite-dimensional vector spaces, they formalize certain trade-offs that are important in the practice of Structured prediction.

Augmented learning problem

To this end, we introduce an augmented learning problem. Simply put, we consider the learning problem of learning from the dataset (x i , g * (x i )) instead of learning from (x i , y i ). Note that g * depends on the data-generating distribution ρ but not on the iid samples x 1 , . . . , x m . Thus, the pairs (x i , g * (x i )) are iid, just like (x i , y i ).

This allows us to absorb the intractable R(g * ) in the Comparison inequality, and decompose R(g) -R(g * ), using the Strong Comparison Inequality. We introduce the absolute deviation loss g(x) -g * (x) , naturally interpretable as the pointwise surrogate excess risk. The empirical sum of these quantities can be seen as the L 2,1 norm of the residuals of the augmented regression.

Proving a PAC-Bayes bound for this augmented learning problem requires establishing a concentration inequality over the absolute deviation regression problem (an unbounded loss). In the following section, we present and adapt a result from [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF] and establish our result.

Absolute regression bound

In this section, we prove Theorem 9, which provides a finite-sample dependent consistency guarantee with high-probability. We first state Theorem 9, then introduce and extend results from [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF] needed to prove it.

In order to handle the unbounded absolute deviation loss, recall the following definition from [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF]:

Definition 7 (Hypothesis-dependent range (HYPE) condition). Let D = X × H be the data space and G be the space of predictors. A loss function : H × G verifies the Hypothesisdependent range (HYPE) condition for a function K : G → R * + such that ∀g ∈ G, sup x,y∈D (g, z) ≤ K(g). In this case, we say that is HYPE(K)-compliant.

The following theorem is extended to vector-valued regression from Haddouche et al. (2020, Thm. 5.1.).

Theorem 8 (extended from Haddouche et al., 2020, Thm. 6.1). Let 1 ≥ α > 0 and N ≥ 6, the dimension of the regression space G. We define as:

: (h, (X(x), g * (x))) ∈ G × (F × H) → g * (x) -h • X(x) . ( 18
)
Then, is

HYPE(K) compliant for K(h) = B h F + C with C = g * 2,∞ and B = X 2,∞ . Moreover, let P = N(0, σ 2 I N ) with σ 2 = t m 1-2α B 2
with 0 < t < 1, be a Gaussian prior. We have with probability at least 1 -δ over S ∼ D m , for any posterior distribution Q such that Q P and P Q:

E h∼Q R(h) ≤ E h∼Q R m (h) + K(Q, P ) + log(2/δ) m α + C 2 2m 1-α 1 + F (t) -1 (19) + N m α log 1 + C 2F (t)m 1-2α + log 1 √ 1 -t . ( 20
)
where

F (t) = 1-t t .
Proof We first prove that is HYPE(K)-compliant for K(h) of the form

K(h) = g * 2,∞ + h op X 2,∞ . Indeed, g * (x) -h • X(x) ≤ g * 2,∞ + h op X(x) 2 .
Furthermore, we have ∀h, h op ≤ h F . Indeed, let h = U ΣV T be the singular value decomposition of h where U and V are unitary and Σ is diagonal with non-negative σ i singular values of A. Because U and V are unitary, Σ F = U T hV F = h F . Thus,

h F = Σ F = i σ i (A) 2 ≥ max i σ i (A) = h op .
Thus,

g * (x) -h • X(x) ≤ g * 2,∞ + h op X 2,∞ .
The second part of the result is a generalization of the original result. Because the HYPE condition is verified with the same form as in the scalar case. See Haddouche et al. (2020, Appendix F.2.) for a proof of the original result.

Finally, we specialize Theorem 8 into a PAC-Bayes generalization bound for the augmented regression problem:

Theorem 9 (Augmented linear regression excess risk bound). Let α > 0 and dim(H ⊗F) = N ≥ 6. Let P = N(0, σ 2 0 I N ) with σ 2 0 = t m 1-2α κ 2

= tσ 2 be a Gaussian prior with 0 < t < 1. We have with probability at least 1 -δ over the training set sampled from ρ m , for any posterior distribution

Q = N(W, σ 2 I N ), E f ∼Q E(f ) -E(f * ) ≤ 2c ∆ E g∼Q 1 m m i=1 g * (x i ) -g(x i ) + K (Q, P) + log 2 δ m α + ε (m, t, α, P) , (21) where
ε (m, t, α, P) = g * 2 2m 1-α 1 + F (t) -1 + N m α log 1 + g * 2F (t)m 1-2α + log 1 √ 1 -t , (22) and F (t) = 1-t t .
Proof Recall the Strong Comparison Inequality (Theorem 2):

E(f ) -E(f * ) ≤ 2c ∆ X g(x) -g * (x) H dρ X (x) =: R(g)
.

We can then apply the Augmented regression formulation and Theorem 8 to bound the expectation of the lower-bound, by recognizing R(g). We also specialize the result for Gaussian posteriors.

Theorem 9 expands on the general PAC-Bayes approach to learning presented in Section 3 and on the Comparison Inequality Theorem 3 by considering the consistency problem from the point of view of finite sample concentration: how suboptimal is f with respect to f * over the data-generating distribution given the suboptimality of g with respect to g * on the finite, real-world dataset at hand.

In the rest of this section we focus on the analysis of the dependencies of the bound in Theorem 9 in the different learning problem and bound parameters. By examining and discussing the influence of these parameters on the value of the bound, we show that our approach yields practical guidance on the performance of learning methods and formulations, in particular on the choice of loss for Structured prediction.

Posterior parametrization

We first examine the impact of the choice of posterior variance on the Kullback-Leibler divergence term. Different parametrizations yield different regularization behaviors, we present two alternatives here.

For completeness, we begin by recalling the Kullback-Leibler divergence of two multivariate Gaussian distributions, with a specialization for isotropic Gaussians.

Proposition 10 (Kullback-Leibler divergence of multivariate Gaussians). The Kullback-Leibler divergence of two N -dimensional multivariate Gaussians P = N(µ 2 , Σ 2 ) and Q = N(µ 1 , Σ 1 ) is:

K(Q, P) = 1 2 log det Σ 2 det Σ 1 -N + tr(Σ -1 2 Σ 1 ) + (µ 2 -µ 1 ) T Σ -1 2 (µ 2 -µ 1 ) . ( 23
)
In particular, if µ 2 = 0, Σ 2 = σ 2 2 I N and Σ 1 = σ 2 1 I N , then Eq. ( 23) can be reduced to:

K(Q, P) = 1 2 2N log σ 2 σ 1 -N + N σ 2 1 σ 2 2 + µ 1 2 σ 2 2 . ( 24
)
The proof can be found in many references, including in [START_REF] Petersen | The matrix cookbook[END_REF].

General Kullback-Leibler variations. For ease of comprehension, we consider the general case where the variance of P is fixed, and study the variations of the Kullback-Leibler divergence as the variance of Q changes. In Figure 3, we illustrate the dependence of the Kullback-Leilber divergence on posterior variance (especially relatively to the prior variance).

The main takeaway of such an illustration is that there is a global minimum of the Kullback-Leibler divergence (even though the means do not coincide), which justifies that the ensuing discussion in the section is justified.

Of course, the posterior variance can be optimized in all generality. However, simple rules are interesting because they can be applied in practice. Furthermore, in PAC-Bayes literature, it is common for the posterior variance to be fixed a priori, for example to 1. Two a priori examples are interesting because they yield insight into the impact of the problem parameters on generalization performance: the unit-variance model and the so-called, wide posterior. We first present both models then compare them. Unit variance posterior This posterior model is widely used in PAC-Bayes analysis.

Here, σ 2 1 = 1 and σ 2 2 = tσ 2 where 0 < t < 1, as defined in Theorem 9. Denote K U (t) the Kullback-Leibler divergence in this model, which has the following expression:

K U (t) = K(Q, P) = µ 1 2 2tσ 2 + n 2 log t + log σ 2 -1 + 1 tσ 2 . ( 25
)
Wide posterior In this case, we set the posterior variance to the supremum of the set of admissible variances for the prior (i.e. corresponding to t = 1 in Theorem 9). Here, σ 2 1 = σ 2 and σ 2 2 = tσ 2 , where 0 < t < 1, and the Kullback-L divergence, noted K W (t) becomes:

K W (t) = K(Q, P) = µ 1 2 2tσ 2 + n 2 log t -1 + 1 t . ( 26
)
Comparison We compare the two parametrizations, to better understand the implications of each hypothesis. The difference of the two divergences gives:

K U (t) -K W (t) = n 2 log σ 2 + 1 tσ 2 - 1 t . ( 27
)
This gap depends on t but only through the prior variance. It is positive if and only if

log σ 2 + 1 tσ 2 - 1 t > 0. ( 28
)
If σ 2 < 1, this is always verified. If σ 2 > 1, then there is a threshold behavior at t 0 (σ) =

1-1 σ 2 log σ 2 .
In Theorem 9, σ is not arbitrary, but determined by the parameters of the learning problem. Recall that σ = m 1-2α κ where κ 2 = sup x∈X k(x, x). In other words, the magnitude of σ is inversely proportional to that of κ, with coefficient m 1-2α .

In the special case of α = 1/2, the above discussion yields insight into the impact of the magnitude of the input kernel on the generalization performance of the ILE method.

• If the input kernel is bounded by 1, then σ > 1 and the choice of parametrization (and the choice of t has an impact). In this case, t should be chosen larger than the threshold value when the wide parametrization is chosen, and smaller when the unitary parametrization is selected. This remark nuances the remark in Haddouche et al. ( 2020) that the limitation on the choice of prior is not limiting: choosing a smaller prior variance helps obtain good generalization bounds with a posterior with smaller variance.

• If the input kernel cannot be bounded by 1, then σ < 1 and the gap is always positive. In this case, the wide parametrization is better, whichever the choice of t. Note however that if the known bound for a given kernel is not tight, then the practitioner may find herself in the previous case without knowing it. This highlights the importance of having informative bounds when controlling the different ingredients to the learning problem.

The analysis in more subtle with α = 1 2 , because the prior variance depends on m.

• In the case where α < 1 2 , σ → +∞ when m → ∞. So with enough data, we are in the first case above. Note that as σ becomes large, the threshold value above becomes small, meaning that the potential widening of the posterior is compensated by the choice of a small t (in the unitary posterior parametrization).

• If 1 > α > 1 2 , the prior becomes tighter as the quantity of data grows. This seems pathological in the large data limit: we want to maintain variance in the prior as the quantity of data grows.

The above discussion gives insight into the choice of posterior parametrization, giving simple rules of thumb for practical use (which eliminates a free parameter). Furthermore, we have shown that having informative bounds on the different ingredients of the learning problem has impact of the generalization guarantees we can obtain.

In the rest of this section, we qualitatively study the effect of different bound parameters on the bound value. We consider the unit-variance posterior parametrization. Furthermore, to evaluate the effects of the parameters on the bound values, we consider the mean regressor ḡ = g * . The discussion can be formulated in the following way:

If g * was known, what PAC-Bayes guarantees could we expect on the resulting stochastic predictor?

In the rest of this section, we adopt the following shorthand, where we have regrouped terms in ε = K(Q,P) m α + ε to highlight their effect on the bound:

ε = N m α log 1 + g * 2F (t)m 1-2α + log F (t) -1 + 1 2 log m 1-2α κ 2 - 1 2 + N 2m 1-α κ 2 t 1 + g * 2 2 N + g * 2 2 N 1 + F (t) -1 . ( 29
)

Penalty dependence on N

The bound's dependence on N , the dimension of the regressor space, is a key contribution of our work. It justifies the practitioner's intuition in the choice of losses for Structured output prediction is important. We can see in Eq. ( 29) that N contributes greatly to the generalization penalty, in O(N ). However, as written Eq. ( 29) does not materialize the dependence of the penalty on the "size" of the Structured output learning problem. We discuss below how the choice of loss determines the penalty value through N . Recall that N = dim(H) × dim(F) is the dimension of the regressor. Indeed, the choice of loss impacts the ILE which in turn impacts the dimension of H.

To illustrate this effect concretely, let us return to the multi-label binary classification problem in Example 1. For the 0 -1 loss, ϕ(y) is a one-hot encoding of y, and dim(H) = |Y| = 2 . For the Hamming loss, dim(H) = 2 +1

|Y|. This greatly reduces the number of samples needed to attain good generalization performance and, by Theorem 9, consistency.

In other words, the choice of a "structured loss" harnesses the power of the framework described above, instead of considering the Structured prediction problem as naïve classification.

Penalty dependence over m

Eq. ( 29) shows that apart from a light logarithmic dependence in m, the penalty decreases as O 1 m β , where β = min (α, 1 -α). This gives an indication of a rate of convergence, which we discuss more generally in Section 6, and echoes that in Section 4.3.

Penalty dependence over t

In Figure 4, we visualize the dependence of Eq. ( 29) on t for different values of κ. Note the global minimum over t.

Learning from the Augmented Regression Bound

In this section, we present and analyze learning algorithms derived from Theorem 9. In PAC-Bayes theory, learning algorithms are derived from a bound when the bound is optimized with respect to the posterior for a given set of data. Because we use a fixed-variance posterior model, we can reduce optimizing the bound in Theorem 9 to minimizing the following objective function, where Q(ḡ) is the parameterized distribution with mean ḡ:

J(ḡ) = E g∼Q(ḡ) 1 m m i=1 g * (x i ) -g(x i ) + h 2 2σ 2 0 m α . ( 30
)
Because g * is unknown, the above objective is intractable. By applying the Triangle Inequality g * (x) -g(x) ≤ g * (x) -ϕ(y) + ϕ(y) -g(x) , we separate the approximation and estimation errors respectively and can concentrate on the latter.

Thus, we consider the optimization objective in Eq. ( 31) instead of in Eq. ( 30):

Ĵ(ḡ) = E g∼Q(ḡ) 1 m m i=1 ϕ(y i ) -g(x i ) + h 2 2σ 2 0 m α . ( 31
)
Although Ĵ is convex, because a practical closed-form expression of Ĵ does not exist 2 , we present two approximate approaches: a deterministic relaxation strategy in Section 5.1, then an estimation strategy using the so-called "log-prob" trick, and apply variance reduction in Section 5.2.

2. Computing the above expectation reduces to computing the mean of the norm of an isotropic Gaussian vector. The norm of a Gaussian vector follows a Generalized Rayleigh Distribution (see for example, [START_REF] Park | Moments of the Generalized Rayleigh Distribution[END_REF] or [START_REF] Blumenson | Properties of Generalized Rayleigh Distributions[END_REF]). [START_REF] Park | Moments of the Generalized Rayleigh Distribution[END_REF] shows that there exists a closed-form expression of the moments of the Generalized Rayleigh distribution. However, these expressions depend on the confluent hypergeometric function, which is not closed for in our setting: it is worth noting that in [START_REF] Park | Moments of the Generalized Rayleigh Distribution[END_REF] the words closed-form are in quotes!

Relaxation strategy

We can upper-bound the Ĵ with an expectation-free convex objective Ĵc . In this section, after establishing the upper-bound, we discuss optimizing Ĵc .

Relaxation

In order to prove the relaxation in Eq. ( 34) we first bound the expected value of the norm of the regression residual.

Proposition 11 (Expected deviation upper-bound). Let Q = N(W, σ 2 I N ) a multivariate Gaussian distribution, where (by abuse of notation)

W ∈ R d×d and d × d = N . Let x ∈ R d and y ∈ R d . Then, (a) EV ∼Q y -V x 2 = y -W x 2 + σ 2 d x 2 , (b) EV ∼Q y -V x ≤ σ 2 d x 2 + y -W x 2
Proof (a) is a classic result: a detailed proof is given for example in Giguère et al. (2013, Appendix 10.7.2.). For (b), we successively apply Jensen's inequality (Eq. ( 32)) then use (a) (Eq. ( 33)), as detailed below:

E V ∼Q y -V x ≤ E V ∼Q y -V x 2 , ( 32
) = y -W x 2 + σ 2 d x 2 . ( 33
)
Remark 12. We note that there may in fact several interpretations of (b) in the previous lemma, such as Jensen or the positivity of the variance.

We can apply this lemma to upper-bound Ĵ(ḡ) in Eq. ( 31):

Ĵ(ḡ) ≤ Ĵc (ḡ) := 1 m m k=1 β(x k ) + ϕ(y k ) -h • X(x k ) 2 + λ α m (t) h 2 , ( 34
)
where

β(x) = σ 2 dim(H) X(x) 2 = σ 2 dim(H)k(x, x) and regularization parameter λ α m (t) = 1 2tσ 2 m α = κ 2 2tm 1-2α m α .
Remark 13 (Slackness of the relaxation). Is the upper-bound in Proposition 11 reasonable? A first remark, is that Jensen's inequality is known to be tight. However, we cannot quantify what is lost before training using the bounds (see Section 7). We evaluated the slackness of Proposition 11 (b) numerically in Figure 5. where

L(σ) = EV ∼Q y -V x and R(σ) = σ 2 d x 2 + y -W x 2 .
Notice that the bound is at least tight to 10%. The simulation methodology can be found documented at https://github.com/theophilec/PAC-Bayes-ILE-Structured-Prediction in the source code associated to this paper (see Section 7).

Learning algorithm

In this section, we present a minimization method for Ĵc (W ) over W ∈ L(F, H). The resulting algorithm, based on gradient descent, is presented in Algorithm 1.

Proposition 14 (Properties of Ĵc ). Ĵc is differentiable and µ-strongly convex for any µ > 2λ α m (t). Furthermore, ∇ Ĵc is given by

∇ Ĵc (W ) = 1 m m k=1 (ϕ(y k ) -W X(x k )) X(x k ) T β(x k ) + ϕ(y k ) -W X(x k ) 2 + 2λ α m (t)W,
thus Ĵc is twice-differentiable.

Proof Let l(x) = √ a + x 2 where a > 0. l is increasing and convex:

l (x) = 2x √ a+x 2 > 0 and l (x) = 4a 2(a+x 2 ) 3/2 > 0. Furthermore, W → y -W x is convex. Thus, W → β(x) + y -W x 2 is convex.
The result follows by convex combination. Because the regularization penalty is µ strongly convex for any µ > 2λ α m (t).

Gradient estimation

Without loss of generality, we ignore the quadratic regularization in Ĵ and focus of the expectation term, using the following notation:

Ĵ(W ) = E Q(V |W ) [L(V )] ,
where

L(V ) = 1 m m k=1 ϕ(y k ) -V X(x k ) and Q(V |W ) is the density of Q(W ) at V .
The following proposition provides an expression of ∇ Ĵ at W and derives an unbiased estimator of ∇ Ĵ.

Proposition 15 (Score-function gradient expression). ∇ Ĵ(W ) can be expressed as the expectation of a function of

V ∼ Q(W ) over Q(W ): ∇ Ĵ(W ) = E V ∼Q(W ) [L(V )∇ log Q(V |W )] . Definition 16 (Score function estimator (SFE)). Let V 1 , . . . , V M be M iid copies of V ∼ Q(W ).
The score function estimator is defined as:

η M (W ) = 1 M M k=1 L(V k )∇ log Q(V k |W ). (35)
Proposition 17. η M is an unbiased estimator of ∇ Ĵ(W ).

The proof of Proposition 17 stems directly from Proposition 15. Given the importance of the approach in our PAC-Bayes approach, we sketch out the main steps of the proof of Proposition 15.

As highlighted in [START_REF] Mohamed | Monte Carlo Gradient Estimation in Machine Learning[END_REF], proving Proposition 15 reduces essentially to interchanging the derivative and the expectation, and applying Lebesgue's dominated convergence theorem. Three conditions should be verified:

1. Q(v|W ) is continuously differentiable with respect to W 2. L(v)Q(v|W ) is integrable and differentiable with respect to W . 3. L(v)∇Q(v|W ) is dominated by an integrable function g of v.
Proof The first two points are straight-forward for the multivariate Gaussian distribution. It is enough to verify the third over all bounded open sets of the space of linear functions. Let C be such a set and C = max{ W , W ∈ C}.

Ignoring the normalization constant of Q, we have:

L(V )∇Q(V |W ) = Y -V X V -W exp - 1 2σ 2 V -W 2 . ( 36
) Noting that -V -W 2 = -V 2 -W 2 ≥ 0 +2 V, W ≤ -V 2 +2C V and V -W ≤ V + C, we have: L(V )∇Q(V |W ) ≤ Y -V X ( V + C) exp - 1 2σ 2 V 2 -2C =: γ(V ).
Algorithm 2: Naïve score estimator gradient descent, SF-GD Input : Initial posterior mean W 0 . Parameters: Step-size parameters: ν ∈ (0.5, 1], w ≥ 0.

1 Initialization W 0 ← W 0 . 2 while stopping criterion not met do 3 Sample M predictors from Q: V 1 , . . . , V M . 4 Estimate intractable gradient: η M ← 1 M k f (V k )∇ log Q(V K |W t ). 5 Compute step-size: γ t = 1 (w+t) ν . 6 Gradient step: W t+1 ← W t -γ t η M . 7 end Result: W f inal Because V 2 γ(V ) → 0 when V → ∞, γ is integrable.
Remark 18. In Proposition 15, L is not required to be differentiable.

With this estimator of the gradient of Ĵ, we can then minimize Ĵ using gradient descent. We present the associated algorithm in Algorithm 2.

The algorithm described above does not have the same theoretical guarantees as gradient descent, as the gradient estimate, while unbiased, can have large variance. There are several approaches to controlling the gradient's variance. We present an approach in Section 5.2.2.

Variance reduction

A general method of reducing the variance of an estimator is to introduce a control variate.

The main ingredient to this approach is the construction of a function B(V ) highly correlated with L(V ), so as to guarantee that B(V )∇ log Q(V |W ) and L(V )∇ log Q(V |W ) will also be correlated.

Let B(V ) be such a function, highly correlated with L. We define, for a ∈ R,

L(V ) := L(V )∇ log Q(V ) -a B(V )∇ log Q(V ) -E q B(V )∇ log Q(V ) . (37)
Note that EQ L(V ) = EQ L(V )∇ log Q. The goal is thus to choose a such that the variance of L(V ) is minimized.

Choice of a & estimation of a *

Proposition 19 (Optimal baseline coefficient, [START_REF] Paisley | Variational Bayesian Inference with Stochastic Search[END_REF]. Given L and B, define L as in Eq. (37). Then, V( L) is minimized for a * ∈ R given by:

a * = N k=1 Cov L ∂ log Q ∂W k , B ∂ log Q ∂W k N k=1 V B ∂ log Q ∂W k . ( 38
)
Of course, a * is intractable in general. We use a plug-in estimator of it â, by sampling from Q, independently from the gradient samples. As recommended in

(V ) = 1 m m i y i -V x i and B(V ) = 1 m m i y i -V x i 2 .
The correlation coefficient is given over M = 500 predictors sampled from a isotropic multivariate normal distribution. The coefficients are averaged over 100 experiments in order to estimate the variance of the estimate (which is materialized by the envelope and dotted lines). To reproduce, see https://github.com/theophilec/PAC-Bayes-ILE-Structured-Prediction.

Definition 20

(Optimal baseline coefficient estimator â). Let V 1 , . . . , V M be M iid sam- ples from Q(V |W ). Then, â = α β , (39)
where Choice of B Of course, the variance reduction virtues of this approach rely on having a function B strongly correlated with L and for which we can compute the gradient of its 3. See: https://github.com/deepmind/mc gradients/blob/master/monte carlo gradients/control variates.py expectation in closed form. [START_REF] Mohamed | Monte Carlo Gradient Estimation in Machine Learning[END_REF] present several alternative methods for choosing such a B. In particular, B does not need to be an upper-bound of L (contrary to the relaxation approach above).

α = 1 M M j=1 N k=1 Cov L ∂ log Q(V j ) ∂W k , B ∂ log Q(V j ) ∂W k , (40)
β = 1 M M j=1 N k=1 V B ∂ log Q(V j ) ∂W k . ( 41
We define B(V ) as:

B(V ) = 1 m m i=1 y i -V x 2 . ( 42
)
The intuition behind such a choice is that we have a closed-form expression of the gradient of B, and the norm and squared-norm are correlated as one is a non-trivial deterministic function of the other. Of course, L (B) are linear combinations of the norms (squared-norms) of residuals (respectively). However, the (x, y) pairs are drawn iid and because x, y → y -V x is deterministic, y -V x and y -V x are independent. Conditioned on the dataset, the correlation of L and B should remain strong.

Remark 21 (Numerical evaluation of correlation). We numerically evaluated our hypothesis that L and B as defined in Eq. ( 42) are well correlated, even when the correlation is reduced by summing over the dataset. We present the results in Figure 6. The correlation is strong, including for large datasets. The experiment is detailed in the associated codebase: https://github.com/theophilec/PAC-Bayes-ILE-Structured-Prediction.

To summarize, the different approximations are as follows (again, ignoring the regularization term):

∇ Ĵ(W ) = E q [L(V )∇ log Q(V ) + ∇ (W )] , = E q L(V )∇ log Q(V ) -a B(V )∇ log Q(V ) -∇ E q B(V ) , = E q [(L(V ) -aB(V ))∇ log Q(V )] + a∇ E q B(V ), ≈ E q [(L(V ) -âB(V ))∇ log Q(V )] Sample +â ∇ E q B(V ) Tractable , ≈ 1 M M k=1 L(V k ) -âB(V k ) ∇ log Q(V k ) ηM (W ) +â ∇ E q B(V ) η B (W ) . ( 43
)
where V 1 , . . . , V M are iid and independent from the M samples used to estimate â.

Algorithm

We present the complete algorithm using Stochastic Search Gradient Descent [START_REF] Paisley | Variational Bayesian Inference with Stochastic Search[END_REF]. To the best of our knowledge, this is a novel application of Stochastic Search Gradient Descent, the applications in the [START_REF] Paisley | Variational Bayesian Inference with Stochastic Search[END_REF] being logistic regression and Hierarchical Dirichlet processes.

Algorithm 3: Quadratic Stochastic Search Gradient Descent iteration, Q-SSGD. Input : Previous W t . Parameters: Step-size parameters: ν ∈ (0.5, 1], w ≥ 0, M , M .

1 Sample M predictors V 1 , . . . , V M from Q(W t ).
2 Estimate â according to Eq. ( 39).

3 Sample M predictors from Q(W t ), V 1 , . . . , V M . 4 Estimate intractable gradient ηM ← 1 Ms k (L(V k ) -âB(V k ))∇ log Q(V k |W t ). 5 Compute η B = ∇ E B(V ) under Q(W t
) according to Eq. ( 44). 6 Compute η P the gradient of the penalty term.

7 Compute step-size γ t = 1 (w+t) ν . 8 Update W t+1 ← W t -γ t ηM (W t ) -γ t âη B (W t ) -γ t η P .
Result: W t+1

As described above, two intractable quantities are sampled in order to estimate the gradient: the stochastic search correction ηM and â (as shown in Eq. ( 43)). Let M and M be the number of samples used for each estimation, respectively4 .

We summarize the Stochastic Search Gradient Descent algorithm with the control variate described above in Algorithm 4. It repetitively calls Algorithm 3.

Proposition 22 provide expressions of the closed form gradients that are needed in the algorithm.

Proposition 22 (Control variate gradient η B ).

∇E Q(W ) B(V ) = 2 m m k=1 (ϕ(y k ) -W X(x k )) X(x k ) T . ( 44
)
Proof

∇ E B(V ) = ∇ 1 m m k=1 ϕ(y k ) -W X(x k ) 2 + σ 2 X(x) 2 dim(H) , = 1 m m k=1 ∇ ϕ(y k ) -W X(x k ) 2 = 2 m m k=1 (ϕ(y k ) -W X(x k )) X(x k ) T .
In this section, we presented two approaches to learning with Theorem 9 -bringing additional evidence that PAC-Bayes bounds are a principled way to derive new algorithms (see e.g. the ICML 2019 tutorial [START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF]. In Section 7, we provide experimental results of to support theoretical results and discussion in Sections 3 to 5.

Discussion

In this paper, we provide a theoretical analysis of the properties of estimators in the Implicit Loss Embedding framework. Our analysis is theoretical and methodological in nature. On Algorithm 4: Quadratic Stochastic Search Gradient Descent algorithm.

Input : Initial regressor W 0 . Parameters: Step-size parameters: ν ∈ (0.5, 1], w ≥ 0, M , M . 1 while stopping criterion not met do

2 W t+1 ← Q-SSGD(W t ) 3 t ← t + 1 4 end
Result: W t one hand, we prove PAC-Bayes generalization bounds for ILE losses. These seek to upperbound the task risk and the excess task risk, from the performance of a given predictor distribution on the dataset. In turn these theoretical results yield two important methodological contributions.

In this section, we briefly summarize our main contributions at a high-level, tying together the different sections and approaches presented therein. Furthermore, we put our results into perspective with respect to those presented in [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF].

Generalization

In Theorem 5, we prove a generalization bound for the ILE problem stemming from a classic PAC-Bayes bound from [START_REF] Zhang | Information-theoretic upper and lower bounds for statistical estimation[END_REF]. It is important to note that in Theorem 5, the loss function ∆ is ILE but the bound hold irrespective of how the predictor (distribution) Q is obtained. This differs from the approach adopted in [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] which consider convergence rates of specific algorithms.

The bound offers methodological guarantees. In the case where m is very large, the generalization penalty term is small, so with probability 1 -δ, the generalization gap (i.e. the difference between EQ E(f ) and EQ E m (f )) reduces to the gap induced by exponential bound on the identity (Proposition 6). For small values of EQ E m (f ), this bound is tight (see Figure 2). This is expected: in the infinite data limit, we expect the empirical loss to be close to the distribution loss.

Furthermore, generalization performance is limited by a penalization term formed of the Kullback-Leibler divergence of the posterior and prior distributions. In practice, this yields a sound way of penalizing predictor (distributions) that do not generalize well. Indeed, in the simple multivariate normal case, if the distributions have the same variance, the penalization coincides with the widely used Tikhonov regularization. et al. (2020) offers insight into the links between the Kernel Dependency Estimation approach and the ILE framework. In this section, we tie together the PAC-Bayes approach to generalization and the ILE approach to consistency, by recalling some results from [START_REF] Giguère | Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction[END_REF].

Comparison with KDE generalization bounds

Ciliberto

We consider an output space Y associated to the reproducing kernel k Y defined by k Y (y, y ) = Y (y), Y (y ) , ∀y, y ∈ Y 2 . We assume the task loss is defined from the output kernel k Y as follows:

L(y, y ) = 1 2 Y (y) -Y (y ) 2 = 1 2 k Y (y, y) + 1 2 k Y (y , y ) -k Y (y, y ). ( 45
)
The KDE predictor f k is the decoded linear regressor, defined by:

f k (x) = arg min y∈Y Y (y) -W X(x) 2 . ( 46
)
One key insight in the KDE approach is to notice that:

L(y, f k (x)) ≤ 2 Y (y) -W X(x) 2 , ( 47
)
where W ∈ L(F, H). In this sense, the KDE framework is a quadratic surrogate approach, without any consistency guarantees as is. [START_REF] Giguère | Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction[END_REF] establishes a PAC-Bayes generalization bound in the KDE setting. The bound is based on the pointwise quadratic upper-bound of the KDE loss we presented in Eq. ( 47) and bounds the expected risk of the mean KDE predictor by the empirical regression risk of the mean regressor, R m

(ḡ) = 1 m m i=1 Y (y i ) -ḡ(x i ) 2 and ḡ = w • X where w ∈ L(F, H).
Recall that we assume F (the RKHS associated to k) and H (the Hilbert space associated to the ILE) to be finite-dimensional. We consider regressors g = w • X where w ∈ L(F, H).

Theorem 23 [START_REF] Giguère | Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction[END_REF]. Assume k is such that k(x, x) = 1, ∀x ∈ X. For any δ > 0, with probability at least 1 -δ over training set sampled iid from ρ, for any w ∈ L(F, H), with g = w • X,

E(d • g) ≤ 5e e -1 1 -exp -2R m (g) - 9 8 w 2 + log 1 δ m . ( 48
)
Notice that in the above bound, the predictors are deterministic and not stochastic. Indeed, using Gaussian distributions for w, the expectations in Theorem 4 were explicitly computed, making the bound only depend on the mean predictor associated to w = w.

As [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] point out, under certain hypotheses, we can show that KDE is a special case of ILE and transfer consistency guarantees of ILE predictors to KDE predictors. Thus the surrogate method in the ILE framework can also be seen as the minimization of a PAC-Bayes bound. Even though this is the case, minimizing the upper bound in Theorem 23 does not yield the same rate guarantees as in [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] which hold for a regularization parameter equal to 1 √ m .

Consistency

Existing approaches do not yield results about the gap between E(d • g) -E(f * ), from a given predictor and a finite sample of data.

Indeed, Theorem 24 provides tight bounds of E(f m ) -E(f * ) for finite m. However, these results depend on how f m is obtained from the data sample. For example, kernel ridge regression can be used (with regularization parameter λ m = 1 √ m , see Caponnetto and Vito, 2006). For completeness we recall the (abridged) result:

• MC-PB(α, t): minimize Eq. ( 30) with score-function gradient descent (with constant learning rate γ).

For Relaxed-PB and MC-PB, α and t are parameters of the prior P so are, in general, data-independent. See Section 7.3 for more details on the choice of α and t.

Implementation

In our work, we consider the PAC-Bayes framework: predictors f are sampled from a posterior distribution Q, itself learned from dataset S = {(x 1 , y 1 ), . . . , (x m , y m )}. Recall that prior to learning, we define a prior distribution over predictors P, which is independent from S. The main difference between the PAC-Bayes approach and more general approaches is thus that we do not learn a predictor through empirical risk minimization but seek to estimate an optimal posterior distribution which minimizes a bound. In Section 5 we showed how this can be reduced to minimizing a data-dependent penalized empirical risk objective.

Furthermore, in the ILE setting, learning a predictor f : X → Z (or predictor distribution Q) is equivalent to learning a regressor g : X → H (or Q). See Figure 1 for an overview. In Section 5, we present two alternative ways of learning Q over regressors : g : X → H.

The combination of the ILE and PAC-Bayes settings in materialized in our implementation. Indeed, two main objects are implemented:

• Regressor encodes data in X to H, akin to g (and to the mean of the posterior distribution Q). The encoding is learned using one of the three families of algorithms mentioned above: ILE, Relaxed-PB and MonteCarlo-PB. As expected, in the case where ILE is employed, Regressor coincides with a Kernel ridge regressor.

• StochasticPredictor is a complete predictor from X to Z, akin to f ∼ Q. It has a Regressor attribute and uses it to learn (stochastic predictor.regressor.fit is called) and perform inference. However, inference can be performed in one of two ways: deterministically from the mean of the posterior distribution Q (this reproduces the behavior of an ordinary predictor) or stochastically by sampling M predictors f 1 , . . . , f m from Q and returning the M corresponding predictions. Similarly, inference can be performed on regression by sampling g 1 , . . . , g m from Q. We mentioned in Section 2 that this decoder (or arg min step) can be solved efficiently in certain cases. See for example Nowak-Vila et al. (2019b); Blondel (2019); [START_REF] Mensch | Differentiable dynamic programming for structured prediction and attention[END_REF]. In our implementation, d is a naïve arg max over all possible labels in Z. Note however, that d is not used during training.

Both of these objects are implemented so as to be compatible with the popular scikit-learn library (Buitinck et al., 2013;[START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF], in order to maximize their familiarity.

In our implementations of gradient descent and score-function gradient descent, we make use of automatic differentiation and safe pseudo-random number generation from the jax library [START_REF] Bradbury | JAX: composable transformations of Python+NumPy programs[END_REF]. This presents several advantages: (i) our code is entirely written in Python, meaning it can be easily read and extended all the whilst being fast and memory efficient; (ii) reproduction is easy despite multiple, nested sampling steps that take place at training and at inference; (iii) although not currently implemented, our code can be compiled to XLA and run on a GPU.

We use the emotions dataset from scikit-multilearn, a multi-label learning library for Python [START_REF] Szymański | A scikit-based Python environment for performing multi-label classification[END_REF]. The dataset presents m = 593 examples (we concatenate the training and test folds for our experiments), dim(X) = 73 and = 6 binary labels. We use the linear kernel so F = H.

Choice of the prior P(α, t)

It is well-known that the choice of prior can help or hinder algorithm performance. In our case, the prior variance (we consider its mean to be 0), which varies with α and t determines the behaviors of the bound and derived algorithms.

Bound behavior We examined the variation of the penalty term ε in Section 4. Here we consider the behavior of empirical risk term for the PAC-Bayes predictor associated to the ILE regressor. In this case, the mean of Q is independent of α and t. However, its variance σ 2 is chosen as a function of α and t. This impacts the bound value. Note that we cannot compute it explicitly (it depends on intractable quantities such as g * ). In Figure 7, we illustrate the dependence of the empirical risk part of the risk certificate Ĵ, defined in Eq. ( 31), on α and t. Figure 7 helps to illustrate the behavior of the ILE predictor in our PAC-Bayes setting, and gives an idea of how α and t can impact the bound. Note that we are not offering this grid search experiment as a method of model selection. Indeed, the prior is assumed to be data independent and thus cannot be, without additional considerations, be optimized using bound values or predictor performance on the training set.

Algorithm behavior

The choice of prior also impacts the behavior of the algorithms presented in this work: gradient descent on a relaxed objective or Monte Carlo gradient descent. Indeed, the relaxed objective presents terms which depend on the posterior variance. In the Monte Carlo approach, predictors are sampled from the posterior in order to optimize its mean. The behavior varies when σ is large or small.

Figures 8 and9 illustrates bound surrogate values ( Ĵ is computed for all three algorithms) for different values of t and α. A complementary picture is given by the dependence of σ and λ α m (t) on α and t, see Figures 10 and11.

Figure 1 :

 1 Figure 1: Summary illustration of the different sets and maps in the ILE framework.

Figure 2 :

 2 Figure 2: Illustration of Proposition 6 (the exponential bound on the identity) for different values of a > 1.

Figure 3 :

 3 Figure 3: Kullback-Leibler divergence as a function of posterior covariance σ, where the prior covariance is unitary. Note the global minimum.

Figure 4 :

 4 Figure 4: Dependence of ε as a function of t, for different values of κ. For these curves: N = 10 2 , m = 10 4 , α = 0.3 and g * = 10. Note the global minimum over 0 < t < 1.

Figure 5 :

 5 Figure 5: Relative gap in Proposition 11 (b). We plot |L(σ)-R(σ)| R(σ)

Figure 6 :

 6 Figure 6: Numerical evaluation of correlation for L(V ) = 1

)

  This is in particular the estimator proposed by[START_REF] Paisley | Variational Bayesian Inference with Stochastic Search[END_REF] andMohamed et al. (2020, associated code) 3 .

Remark 25 .

 25 Given x ∈ X, our stochastic predictor returnsf 1 (x) = d • g 1 (x), . . . , f M (x) = d • g M (x) where g 1 , . . . , g M are sampled iid from Q. It is important to note that it does not return 1 M k f k (x) (in the structured setting, this quantity is not defined) nor d • 1 M k g k (x) .Remark 26 (Decoding). Recall that given an ILE loss ∆(z, y) = ψ(y), ϕ(y) and a regressor g, the ILE framework defines f by f = d • g where: d(g(x)) = arg min z∈Z ψ(z), g(x) .

Figure 7 :

 7 Figure 7: Ĵ as a function of α and t for the ILE algorithm. Ĵ is defined in Eq. (31). The regularization parameter λ is chosen to minimize Ĵ.

Figure 8 :

 8 Figure 8: Ĵ as a function of α and t for the Relaxed-PB algorithm. Ĵ is defined in Eq. (31).The learning rate is chosen between {10 -8 , 10 -4 , 10 -3 , 10 -2 } to minimize Ĵ.

Figure 9 :

 9 Figure 9: Ĵ as a function of α and t for the MC-PB algorithm. Ĵ is defined in Eq. (31).The learning rate is chosen between {10 -5 , 10 -4 , 10 -3 } to minimize Ĵ. M = 20 samples where used at each gradient step (with â = 0).

Figure 10 :

 10 Figure 10: σ as a function of α and t.Figure11: λ as a function of α and t.

Figure 11 :

 11 Figure 10: σ as a function of α and t.Figure11: λ as a function of α and t.

https://github.com/theophilec/PAC-Bayes-ILE-Structured-Prediction

Note that Paisley et al. (2012) consider M M .

Algorithm 1: Gradient descent, Relax-GD Input : Initial posterior mean W 0 . Parameters: Step-size parameters: ν ∈ (0.5, 1], w ≥ 0. 1 Initialization W 0 ← W 0 . 2 Pre-compute β(x k ). 3 while stopping criterion not met do 4 Compute ∇J c (W t ) (see Proposition 14).

5

Compute step-size: γ t = 1 (w+t) ν .

6

Gradient step:

where we used Tr(AB) = Tr(BA) and Tr(A T ) = Tr(A). The gradient expression follows by composition.

Because Ĵc is L-smooth (for some L > 0), it is well-known that we can minimize it by gradient descent [START_REF] Boyd | Convex Optimization[END_REF].

Stochastic Search Variational Minimization

In this section, we present a second approach to optimizing Ĵ. Instead of relaxing the optimization problem, we seek to directly estimate ∇ Ĵ. The intuition behind this approach is that Ĵ is convex, thus estimating its gradient could be sufficient to minimize it in practice. To this end, we apply the well-known "log-prob" trick. In order to reduce the variance of the resulting estimator, we apply techniques presented in [START_REF] Mohamed | Monte Carlo Gradient Estimation in Machine Learning[END_REF] and [START_REF] Paisley | Variational Bayesian Inference with Stochastic Search[END_REF] with a well-chosen control variate.

These techniques are widely-used in different fields of mathematics and in particular machine learning: stochastic optimization, reinforcement learning, extreme-value statistics, among others. The interested reader can consult the recent survey [START_REF] Mohamed | Monte Carlo Gradient Estimation in Machine Learning[END_REF] and references therein.

Theorem 24 (Ciliberto et al., 2020, from Theorem 5). If Z is compact and ∆ admits an ILE. Assume that k is continuous and bounded by κ 2 = sup x∈X k(x, x). Let ρ be a datagenerating distribution such that g * ∈ H ⊗ F where H is associated to the ILE and F to k. Let δ > 0 and m 0 large enough, then with probability at least 1 -δ over the training set sampled from ρ m for f m (KRR with the same regularization as above),

where M = 16 κ (1 + κ g * ) + κ 1 + g * 2 + g * and q ≤ 3.

In constrast, in Theorem 9, we bound a stochastic predictor analog to E(f m ) -(f * ). This approach is complementary to that of [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF]. It provides a theoretical guarantee bounding the suboptimality of a given predictor distribution, and dependent on the finite sample performance of the bound. In particular, Theorem 9 holds with high probability, independently of the learning method used.

Theorem 9 also yields methodological insight into the Structured prediction problem. Indeed, it materializes the gain obtained using "structured" losses such as the Hamming loss, over the 0 -1 loss, theoretically validating practitioner intuition. Furthermore, we show how prior information such as the bound on the input kernel κ can have an impact of the chosen learning method.

Theorem 9 is of particular interest because the upper-bound is differentiable. In Section 5, we derive two learning algorithms that minimize the bound. The experimental results of this approach is presented in Section 7.

Experimental results

In this paper, we prove a PAC-Bayes bound for Structured prediction using ILE losses. The bound provides an excess risk certificate that holds with high probability. Furthermore, we derive two learning algorithms from the bound, which both stem from minimizing a surrogate of the bound.

In this section, we present experimental results of three algorithms, on multi-label binary classification datasets. All experiments can be reproduced with source code available 5 .

Algorithms

First, we recall the different implement algorithms and their variants. We compare three families of algorithms:

• ILE(λ): minimize Eq. ( 9) by Kernel Ridge Regression with regularization parameter λ.

• Relaxed-PB(α, t): minimize Eq. ( 34) with gradient descent (with constant learning rate γ). This is described in Algorithm 1.

5. https://github.com/theophilec/PAC-Bayes-ILE-Structured-Prediction


Nouredine Oueldna

Alain Portavoce
email: alain.portavoce@im2np.fr

Maxime Bertoglio

Marion Descoins

Abdelkhalek Kammouni

Khalid Hoummada

Seebeck coefficient in multiphase thin films

Keywords: Thermoelectricity, Seebeck coefficient, Interface, Thin film, MgAgSb

Mg-Ag-Sb thin films were deposited by magnetron sputtering using a commercial Mg 1/3 Ag 1/3 Sb 1/3 target. All the films contain principally the two phases Ag 3 Sb and -MgAgSb in same proportions but exhibit different microstructures. The films have the same Seebeck coefficient despite the difference of interface density and structure. Theoretical calculations show that the film effective Seebeck coefficient S film is depending only on the volume of each phase present in the film and their Seebeck coefficients. The multiple interfaces between the different phases have no effect on S film .

2

Several solutions allowing the production of efficient thermoelectric materials were recently proposed [1]. Among them, charge carrier energy filtering is considered as one of the most promising strategy [1,2]. The principal method consists in the creation of specific interfaces in the material acting as energy filtering barriers, promoting a significant increase of the Seebeck coefficient (S) and of the thermoelectric power factor. Experimental variations of S in materials containing inclusions are regularly attributed to energy filtering. However, when several phases are present in a thermoelectric polycrystalline material, the effective Seebeck coefficient S eff is depending on S i of each present phase  i . Assuming a constant temperature (T) gradient in the film, and excluding any interface effects, S eff of a material containing n different phases can be expressed such as: (1) with f  the volume fraction of the phase  i (Fig. 1). In the present work, we investigate the interface influence on the S of a polycrystalline material containing several phases. -MgAgSb is a ternary semi-conductor [3], which usually contains inclusions of the metallic binary phase Ag 3 Sb [3]. The S of -MgAgSb was reported to significantly vary depending on the fabrication process [4][5][6]. -MgAgSb has been to date only studied in its bulk state, but -MgAgSb thin films produced by sputtering are expected to be useful for the integration of energy harvesting devices in the CMOS technology [7].

Mg-Ag-Sb thin films were deposited in a magnetron sputtering system exhibiting a base pressure of 10 -8 Torr, using a 99.9999% pure Ar gas flow to sputter in the DC mode a 99.99% pure Mg 1/3 Ag 1/3 Sb 1/3 target purchased from CODEX international. The films were deposited on glass substrates for S measurements, or on the native oxide of Si(001) substrates while the second one (#2) was ex situ annealed under vacuum (10 7 mbar) at 523 K for 30 min. The two other films were deposited at 523 K (#3) and 573 K (#4), respectively. The structure of the films was investigated using X-ray diffraction (XRD) in the Bragg-Brentano (-2) geometry using a Cu K  source ( K = 0.154 nm), as well as using scanning electron microscopy (SEM) in cross-section. The S of the films was measured using a home-made setup. T and the electrical potential were measured with the same probes at two different locations on the specimens separated by 1 cm. S was measured between T = 220 and 330 K, corresponding to the temperature range of the targeted CMOS applications. The experimental S were compared to theory, running the BoltzTraP code [8] with material bulk parameters determined from ab-initio calculations. Ab-initio calculations were carried out using the firstprinciples pseudopotential method based on the DFT and the plane-wave self-consistent field method (PWSCF) which is implemented in the QUANTUM ESPRESSO package [9]. The Generalized Gradient Approximation (GGA-PBE) [10] was used for exchange-correlation functional. The ultrasoft pseudopotential (USP) method was used to treat the valence electron configuration.

Figure 2 presents the X-ray diffractograms measured on the four specimens. Fig. 2a shows that only the binary phase Ag 3 Sb is detected in the film after deposition at RT. Seven diffraction peaks are detected corresponding to the Ag 3 Sb atomic planes (110), (002), (111), (022), (130), (023), and (132) at 2 = 34.32°, 37.24°, 39.23°, 51.56°, 61.77°, 68.44°, and 74.29°, respectively. Fig. 2b shows that annealing the same film at 523 K for 30 min allows the phase -MgAgSb as well as the phase Sb to form in the film in addition to the phase Ag 3 Sb. In addition to the same Ag 3 Sb diffraction peaks, five diffraction peaks corresponding to -MgAgSb(110), -MgAgSb(202), -MgAgSb(114), -MgAgSb(330), and -MgAgSb(006) are respectively observed in the diffractogram at 2 = 13.01°, 24.16°, 31.88°, 41.25°, and 42.06°, as well as two peaks corresponding to Sb(102) and Sb(213) at 2 = 28.69° and 48.35°. Fig. 2c and Fig. 2d show that the same diffraction peaks are observed in the samples heated at 523 K or 573 K during deposition. Only the peak Ag 3 Sb(130) is only observed in the specimen ex situ annealed. The (qualitative) volume fraction f of each phase present in the different films was determined using the integration of each detected peak of each phase. Due to the uncertainties related to the Bragg-Brentano geometry, the values of f should not be considered quantitatively. Nevertheless, the fractions corresponding to the three phases present in the films are the same in the three different films #2, #3, and #4: f  ~ 33%, f Ag3Sb ~ 60%, and f Sb ~ 7%. Fig. 3 presents cross-sectional SEM images obtained on the films #1 (Fig. 3a), #2 (Fig. 3b), #3 (Fig. 3c), and #4 (Fig. 3d). The SEM images show in the four films the coexistence of multiple grains of different phases exhibiting different contrasts.

However, the microstructures of the samples #2, #3, and #4 are different. According to the XRD analyses, the matrix should correspond to the phase Ag 3 Sb, while the inclusions should be -MgAgSb grains. The inclusions in the film #2 exhibit a higher density ( ~ 1.510 11 cm 2 ) and smaller sizes (10  l  50 nm) than in the film #3 ( ~ 8.2 10 9 cm 2 , 23  l  70 nm) and #4 ( ~ 3.5  10 9 cm 2 , 65  l  90 nm). Furthermore, the film #3 is rougher and facets are less easily observed on the inclusions compared to film #4. Fig. 4 presents S measured on the four different films versus T. S measured on the films #2 (open up triangles), #3 (solid circles), and #4 (solid squares), are similar in the considered T range. However, S measured on the as-deposited film #1 (solid down triangles) is significantly lower than the three other films. Indeed, S measured in the film #1 should correspond to the phase Ag 3 Sb, while S measured on the three other films should correspond to an effective coefficient resulting from the presence of the different phases. Fig. 4 shows also the theoretical S of the two major phases present in the samples (i.e. Ag 3 Sb and -MgAgSb) calculated using the BoltzTraP code and ab-initio calculations. The theoretical coefficient of Ag 3 Sb (solid line) is in good agreement with the experimental coefficient measured on the film #1 (solid down triangles), containing only Ag 3 Sb. Furthermore, the theoretical coefficient of -MgAgSb is in good agreement with the experimental value reported by Kirkham et al. [4] (solid diamonds).

XRD measurements suggest that the phase -MgAgSb occupies in average only 30% of the volume of the films #2, #3, and #4. Neglecting the presence of Sb in the samples, S eff of a hypothetic film containing the two phases Ag 3 Sb and -MgAgSb was calculated using the theoretical values of S Ag3Sb and S  and eq. 1, with f  = 0.3 and f Ag3Sb = 0.7. S eff (dash line in Fig. 4) is in good agreement with the S measured on the three films #2, #3, and #4. Neither nano-size effect [11][12] nor interfacial effect [1][2] are observed on S. Indeed, the microstructures of the films may be too far from the structure of superlattice-type materials, the size of -MgAgSb inclusions being too large (> 5 nm [11][12]) and exhibiting a significant size distribution. Furthermore, the nature of the Ag 3 Sb/-MgAgSb interface may not promote the suitable energy barrier (ohmic instead of Schottky contact).

In conclusion, Mg-Ag-Sb thin films were elaborated by magnetron sputtering in different conditions allowing the production of different films containing principally the phase

Ag 3 FIG. 1 .FIG. 2 .

 312 FIG. 1. Schematic showing the serial electrical circuit corresponding to the case of a

FIG. 3 .FIG. 4 .

 34 FIG. 3.Cross-sectional SEM images acquired on the four different films: a) RT as-deposited

Figure 1 N

 1 Figure 1

Figure 2 N. Oueldna et al. 10 Figure 3 Figure 4 N

 21034 Figure 2