Nicholas Asher
email: asher@irit.fr

Soumya Paul
email: soumya.paul@telindus.lu

Chris Russell

Fair and Adequate Explanations

Recent efforts have uncovered various methods for providing explanations that can help interpret the behavior of machine learning programs. Exact explanations with a rigorous logical foundation provide valid and complete explanations, but they have an epistemological problem: they may be too complex for humans to understand and too expensive to compute even with automated reasoning methods. Interpretability requires good explanations that humans can grasp and can compute. We take an important step toward specifying what good explanations are by analyzing the epistemically accessible and pragmatic aspects of explanations. We characterize sufficiently good, or fair and adequate, explanations in terms of counterfactuals and what we call the conundra of the explainee, the agent that requested the explanation. We provide a correspondence between logical and mathematical formulations for counterfactuals to examine the partiality of counterfactual explanations that can hide biases; we define fair and adequate explanations in such a setting. We then provide formal results about the algorithmic complexity of fair and adequate explanations.

Introduction

Explaining the predictions of sophisticated machine-learning algorithms is an important issue for the foundations of AI. Recent efforts [START_REF] Ribeiro | Explaining the predictions of any classifier[END_REF][START_REF] Ribeiro | Anchors: High-precision model-agnostic explanations[END_REF][START_REF] Wachter | Counterfactual explanations without opening the black box: Automated decisions and the gpdr[END_REF][START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF][START_REF] Bachoc | Entropic variable projection for explainability and intepretability[END_REF] have shown various methods for providing explanations. Among these, model-based, logical approaches that completely characterise one aspect of the decision promise complete and valid explanations.

Such logical methods are thus a priori desirable, but they have an epistemological problem: they may be too complex for humans to understand or even to write down in human-readable form. Interpretability requires epistemically accessible explanations, explanations humans can grasp and compute. Yet what is a sufficiently complete and adequate epistemically accessible explanation, a good explanation still needs analysis [START_REF] Murdoch | Definitions, methods, and applications in interpretable machine learning[END_REF]. We propose to characterize sufficiently good, or fair and adequate, explanations in terms of counterfactuals-explanations, that is that are framed in terms of what would have happened had certain conditions (that do not obtain) been the case-and what we call the conundrum and fairness requirements of the explainee, the person who requested the explanation or for whom the explanation is intended). It is this conundrum that makes the explainee request an explanation. Counterfactual explanations, as we argue below, are a good place to start for finding accessible explanations, because they are typically more compact than other forms of explanation.

We argue that a fair and adequate explanation is relative to the cognitive constraints and fairness requirements of an explainee E [START_REF] Bromberger | An approach to explanation[END_REF][START_REF] Achinstein | The Nature of Explanation[END_REF][START_REF] Miller | Explanation in artificial intelligence: Insights from the social sciences[END_REF]. E asks for an explanation for why π when she wasn't expecting π. Her not expecting π follows from beliefs that must now be revised-how to specify this revision is the conundrum of E. An adequate explanation is a pragmatic act that should solve the conundrum that gave rise to the request for explanation; solving the conundrum makes the explanation useful to E [START_REF] Holzinger | Measuring the quality of explanations: the system causability scale (scs)[END_REF]. In addition, an adequate explanation must lay bare biases that might be unfair or injurious to E (the fairness constraint). In effect, this pragmatic act is naturally modelled in a game theoretic setting in which the explainer must understand explainee E's conundrum and respond so as to resolve it. A cooperative explainer will provide an explanation in terms of the type he assigns to E, as the type will encode the relevant portions of E's cognitive state. On the other hand the explainee will need to interpret the putative explanation in light of her model of the explainer's view of his type. Thus, both explainer and explainee have strategies that exploit information about the other-naturally suggesting a game theoretic framework for analysis.

In developing our view of fair and adequate explanations, we will exploit both the logical theory of counterfactuals [START_REF] Lewis | Causation[END_REF] and mathematical approaches for adversarial perturbation techniques [START_REF] Kusner | Counterfactual fairness[END_REF][START_REF] Younes | Diffeomorphic learning[END_REF][START_REF] Peyré | Computational optimal transport: With applications to data science[END_REF][START_REF] Kurakin | Adversarial examples in the physical world[END_REF][START_REF] Dube | High dimensional spaces, deep learning and adversarial examples[END_REF][START_REF] Bachoc | Entropic variable projection for explainability and intepretability[END_REF]. We provide a correspondence between logical and mathematical formulations for counterfactuals, and we analyze how counterfactual explanations can hide biases. We then formalize conundra and fair and adequate explanations, and we develop a game theoretic setting for proving computational complexity results for finding fair and adequate explanations in non cooperative settings.

Background on explanations

Following [START_REF] Bromberger | An approach to explanation[END_REF][START_REF] Achinstein | The Nature of Explanation[END_REF], we take explanations to be answers to why questions. Consider the case where a bank, perhaps using a machine learning program, judges E's application for a bank loan and E is turned down. E is in a position to ask a why question like, [START_REF] Achinstein | The Nature of Explanation[END_REF] why was I turned down for a loan? when her beliefs would not have predicted this. Her beliefs might not have been sufficient to infer that she wouldn't get a loan; or her beliefs might have been mistaken-they might have led her to conclude that she would get the loan. In any case, E must now revise her beliefs to accord with reality. Counterfactual explanations, explanations expressed with counterfactual statements, help E do this by offering an incomplete list of relevant factors that together with unstated properties of E entail the explanandum-the thing E needs explained, in this case her not getting the loan. For instance, the bank might return the following answer to (1):

(2) Your income is e50K per year.

(3) If your income had been e100K per year, you would have gotten the loan.

The counterfactual statement [START_REF] Asher | Strategic conversation under imperfect information: epistemic Message Exchange games[END_REF] states what given all of E's other qualities would have been sufficient to get the loan. But since her income is in fact not e100K per year, the semantics of counterfactuals entails that E does not get the loan.

(3) also proposes to E how to revise her beliefs to make them accord with reality, in that it suggests that she mistakenly thought that her actual salary was sufficient for getting the loan and that the correct salary level is e100K per year. 4Counterfactual explanations, we have seen, are partial, because they do not explicitly specify logically sufficient conditions for the prediction. They are also local, because their reliance on properties of a particular sample makes them valid typically only for that sample. Had we considered a different individual, say D, the bank's explanation for their treatment of D might have differed. D might have had different, relevant properties from E; for instance, D might be just starting out on a promising career with a salary of e50K per year, while E is a retiree with a fixed income.

The partiality and locality of counterfactuals make them simpler and more epistemically accessible than other forms of explanation. Moreover, the logical theory of counterfactuals enables us to move from a counterfactual to a complete and logically valid explanation. So in principle counterfactual explanations can provide both rigour and epistemic accessibility. But not just any partiality will do, since partiality makes possible explanations that are misleading, that hide injurious or unfair biases. To show how the partiality of counterfactual explanations can hide unfair biases, consider the following scenario. The counterfactual in (2) might be true but it also might be misleading, hiding an unfair bias. ( 1)-( 2) can be true while another, more morally repugnant explanation that hinges on E's being female is also true. Had E been male, she would have gotten the loan with her actual salary of e50K per year. A fair and adequate explanation should expose such biases.

We now move to a more abstract setting. Let f : X n → Y be a machine learning algorithm, with X n an n-dimenstional feature space encoding data and Y the prediction space. Concretely, we assume that f is some sort of classifier. When f = π, an explainee may want an explanation, an answer to the question,"why π?" We will say that an explanation is an event by an explainer, the provider of the explanation, directed towards the explainee (the person requesting the explanation or to whom the explanation is directed) with a conundrum. An explanation will consist of of an explanandum, the event or prediction to be explained, an explanans, the information that is linked in some way to the explanandum so as to resolve the explainee's conundrum. When the explanation is about a particular individual, we call that individual the focal point of the explanation.

Explanations have thus several parameters. The first is the scope of the explanation. For a global explanation of f , the explainee wants to know the behavior of f over the total space X n . But such an explanation may be practically uncomputable; and for many purposes, we might only want to know how f behaves on a selection of data points of interest or focal points, like E's bank profile in our example. 5 Explanations that are restricted to focal points are local explanations.

Explanations of program behavior also differ as to the nature of the explanans. In this paper, we will be concerned with external explanations that involve an explanatory link between features of input or feature space X and the output in Y without considering any internal states of the learning mechanism [START_REF] Friedrich | A taxonomy for generating explanations in recommender systems[END_REF]. These are attractive epistemically, because unpacking the algorithms' internal states and assigning them a meaning can be a very complicated affair.

A third pertinent aspect of explanations concerns the link between explanans and the explanandum. [START_REF] Hempel | Aspects of scientific explanation[END_REF][START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF][START_REF] Ignatiev | On relating "why?" and "why not?" explanations[END_REF] postulate a deductive or logical consequence link between explanans and explanandum. [START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF] represent f as a set of logic formulas M( f ). By assuming features with binary values6 , an instance is then a set of literals that assigns values to every feature in the feature space. An abductive explanation of why π is a subset minimal set of literals I such that M( f ), I |= π. Abductive explanations exploits universal generalizations and a deductive consequence relation. They explain why any instance x that has I is such that f (x) = π and hence are known as global explanations [START_REF] Molnar | Interpretable machine learning[END_REF].

Counterfactuals offer a natural way to provide epistemically accessible, partial explanations of properties of individuals or focal points. The counterfactual in (3) gives a sufficient reason for E's getting the loan, all other factors of her situation being equal or being as equal as possible (ceteris paribus) given the assumption of a different salary for E. Such explanations are often called local explanations [START_REF] Doshi-Velez | Towards a rigorous science of interpretable machine learning[END_REF][START_REF] Molnar | Interpretable machine learning[END_REF], as they depend on the nature of the focal point; they are also partial [START_REF] Wachter | Counterfactual explanations without opening the black box: Automated decisions and the gpdr[END_REF], because the antecedent of a counterfactual are not by themselves logically sufficient to yield the formula in the consequent. Deductive explanations, on the other hand, are invariant with respect to the choice of focal point. But because counterfactual explanations exploit ceteris paribus conditions, factors that deductive explanations must mention can remain implicit in a counterfactual explanation. Thus, counterfactual explanations are typically more compact and thus in principle easier to understand. 7 Counterfactuals are also intuitive vehicles for explanations as they also encode an analysis of causation [START_REF] Lewis | Causation[END_REF].

Counterfactual explanations for learning algorithms

The canonical semantics for a counterfactual language L, which is a propositional language to which a two place modal operator → is added, as outlined in [START_REF] Lewis | Causation[END_REF] exploits a possible worlds model for propositional logic, A = W, ≤, [[.]] , where: W is a non-empty set (of worlds), ≤ is a ternary similarity relation (w ≤ w w ), and [[.]] : P → W → {0, 1} assigns to elements in P , the set of proposition letters or atomic formulas of the logic, a function from worlds to truth values or set of possible worlds. Then, where |= represents truth in such a model, we define truth recursively as usual for formulas of ordinary propositional logic and for counterfactuals ψ → φ, we have:

Definition 1. A, w |= ψ → φ just in case: ∀w , if A, w |= ψ and ∀w (A, w |= ψ → w ≤ w w ), then: A, w |= φ
What motivates this semantics with a similarity relation? We can find both epistemic and metaphysical motivations. Epistemically, finding a closest or most similar world in which the antecedent φ of the counterfactual φ → ψ is true to evaluate its consequent ψ follows a principle of belief revision [START_REF] Gärdenfors | Revisions of knowledge systems using epistemic entrenchment[END_REF], according to which it is rational to make minimal revisions to one's epistemic state upon acquiring new conflicting information. A metaphysical motivation comes from the link Lewis saw between counterfactuals and causation; ¬φ → ¬ψ implies that if φ hadn't been the case, ψ wouldn't have been the case, capturing much of the semantics of the statement φ caused ψ. The truth of such intuitive causal statements, however, relies on the presence of a host of secondary or enabling conditions. Intuitively the statement that if I had dropped this glass on the floor, it would have broken is true; but in order for the consequent to hold after dropping the glass, there are many elements that have to be the same in that counterfactual situation as in the actual world-the floor needs to be hard, there needs to be a gravitational field around the strength of the Earth's that accelerates the glass towards the floor, and many other conditions. In other words, in order for such ordinary statements to be true, the situation in which one evaluates the consequent of a counterfactual has to resemble very closely the actual world.

Though intuitive, as this logical definition of counterfactuals stands, it is not immediately obvious how to apply it to explanations of learning algorithm behavior. We need to adapt it to a more analytical setting. We will do so by interpreting the similarity relation appealed to in the semantics of counterfactuals as a distance function or norm as in [START_REF] Williamson | First-order logics for comparative similarity[END_REF] over the feature space X n , an n-dimensional space, used to describe data points. To fill out our semantics for counterfactuals in this application, we identify instances in X n as the relevant "worlds" for the semantics of the counterfactuals. We now need to specify a norm for X n . A very simple norm assumes that each dimension of X n is orthogonal and has a Boolean set of values; in this case, X n has a natural L 1 norm or Manhattan or edit distance [START_REF] Salzberg | Distance metrics for instance-based learning[END_REF]. 8 While this assumption commits us to the fact that the dimensions of X n capture all the causally relevant factors and that they are all independent-both of which are false for typical instances of learning algorithms, it is simple and makes our problem concrete. We will indicate below when our results depend on this simplifying assumption.

A logic of counterfactuals can now exploit the link between logic formulas, features of points in X n , and a learning algorithm f described in [START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF][START_REF] Karimi | Model-agnostic counterfactual explanations for consequential decisions[END_REF]. Suppose a focal point x is such that f (x) = η. A counterfactual A → π that is true at the point x, where π is a prediction incompatible with η, has an antecedent that is a conjunction of literals, each literal defining a feature value, and that provides a sufficient and minimal shift in the features of x to get the prediction π. Each counterfactual that explains the behavior of f around a focal point x ∈ X n thus defines a minimal transformation of the features of x to change the prediction. We now define the transformations on X n that counterfactuals induce.

Definition 2. Let i ⊂ n. A fixed transformation ∆ i is a function ∆ i : X n → X n such that for x ∈ X n , if ∆ i (x) = y,
then x and y differ only in the dimensions in i. We write x = i x to mean that x and x share the same values along dimensions i. Given x ∈ X n , and f (x) = η and where . X n is a natural norm on X n , we shall be interested in the following types of transformations.

(i) ∆ i (x) is appropriate if f (∆ i (x)) = π where η and π are two incompatible predictions in Y . (ii) ∆ i (x) is minimally appropriate if it is appropriate and in addition, ∀x ∈ X such that ∆ i (x) = i x and f (x ) = π, x -x X n ≥ ∆ i (x) -x X n . (iii) ∆ i (x)
is sufficiently appropriate if it is appropriate and in addition, for any j i, ∆ j (x) is not appropriate. (iv) ∆ i (x) is sufficiently minimally appropriate if it is both sufficiently and minimally appropriate.

Note that when X is a space of Boolean features, then conditions (ii) and (iv) of Def. 2 trivially hold. Given a focal point x in X n , minimally appropriate transformations represent the minimal changes necessary to the features of x to bring about a change in the value predicted by f . Let f : X n → Y and consider now a counterfactual language L f with a set of formulas Π that describe the predictions in Y of f .

Definition 3. A counterfactual model C X n , f for L f with f : X n → Y is a triple W, ≤, [[.]] with W a set of worlds W = X n , ≤ defined by a norm ||.|| on X n and [[.]] : P ∪ {Π} → W → {0, 1} such that for A ∈ P , [[A]] w = 1 iff w has feature A and for π ∈ Π, [[π]] w = 1 iff f (w) = π. Given a counterfactual model C X n , f for L f with norm ||.|| on X n , we say that ||.|| is L f definable just in case for worlds w, w 1 ∈ X n , there is a formula φ of L f that separates w 1 from all w 2 ∈ X n such that w 2 -w < w 1 -w -i.e. for all w 2 , w 2 -w < w 1 -w , C X n , f , w 1 |= φ and C X n , f , w 2 |= φ.
and logic [START_REF] De Raedt | From statistical relational to neuro-symbolic artificial intelligence[END_REF], we can have probability estimates on literals and so encode continuous feature spaces.

Proposition 1. . Let f : X n → Y and let C X n , f be a counterfactual model for L f with an L f definable norm. Suppose also that f (w) = η. Then:

C X n , f , w |= φ → π,
where π ∈ Π and φ is a separating formula iff there is a minimally appropriate transformation, ∆ i :

X n → X n , where f (∆ i (w)) = π, and C X n , f , ∆ i (w) |= A.
Proposition 1 follows easily from Definitions 1, 2 and 3. Proposition 1 is general and can apply to many different norms and languages. We will mostly be concerned here with a special and simple case:

Corollary 1 Let L f be a propositional language with a set P of propositional letters, where P is the set of Boolean valued features of X n , and let C X n , f be a counterfactual model for L f with an L 1 norm. Then: C X n , f , w |= A → π, where π ∈ Π and A is a conjunction of literals in P iff there is a minimally appropriate transformation over the dimensions i fixed by A, ∆ i :

X n → X n , where f (∆ i (w)) = π, and C X n , f , ∆ i (w) |= A.
We can generate minimally appropriate transformations via efficient (polytime) techniques like optimal transport or diffeomorphic deformations [START_REF] Younes | Diffeomorphic learning[END_REF][START_REF] Peyré | Computational optimal transport: With applications to data science[END_REF][START_REF] Kurakin | Adversarial examples in the physical world[END_REF][START_REF] Dube | High dimensional spaces, deep learning and adversarial examples[END_REF][START_REF] Bachoc | Entropic variable projection for explainability and intepretability[END_REF] for computing adversarial perturbations [START_REF] Kusner | Counterfactual fairness[END_REF]. In effect all of these diverse methods yield counterfactuals or sets of counterfactuals given Proposition 1. A typical definition of an adversarial perturbation of an instance x, given a classifier, is that it is a smallest change to x such that the classification changes. Essentially, this is a counterfactual by a different name. Finding a closest possible world to x such that the classification changes is, under the right choice of distance function, the same as finding the smallest change to x to get the classifier to make a different prediction. 9The great advantage of Proposition 1 is that marries efficient techniques to generate counterfactual explanations with the logical semantics of counterfactuals that provides logically valid (LV) explanations from counterfactual explanations, unlike heuristic methods [START_REF] Ribeiro | Anchors: High-precision model-agnostic explanations[END_REF][START_REF] Lundberg | A unified approach to interpreting model predictions[END_REF][START_REF] Ribeiro | Anchors: High-precision model-agnostic explanations[END_REF]. Thus, counterfactual explanations build a bridge between logical rigour and computational feasibility. Proposition 2. A counterfactual explanation given by a minimally appropriate ∆ i (x) in C X n , f , with an L 1 norm and X n with Boolean valued features, yields a minimal, LV explanation in at worst a linear number of calls to an NP oracle.

Proof sketch. The atomic diagram [START_REF] Chang | Model theory[END_REF] of C X n , f in which each world is encoded as a conjunction of literals (Boolean values of the features P of X n together with predictions from Y ), encodes M( f ). Further, given Corollary 1 and Definition 3, each minimally appropriate ∆ i defines a set of literals L ∆i describing ∆ i (x) such that ∆ i (x), M( f ) |= π. [START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF][START_REF] Ignatiev | On relating "why?" and "why not?" explanations[END_REF] provide an algorithm for finding a subset minimal set of literals E ⊆ L ∆i with E, M( f ) |= π in a linear number relative to |L ∆i | of calls to an NP oracle [START_REF] Junker | Preferred explanations and relaxations for over-constrained problems[END_REF].

We have observed that counterfactual explanations are intuitively simpler than deductive ones, as they typically offer only a partial explanation. In fact there are three sorts of partiality in a counterfactual explanation. First, a counterfactual explanation is deductively incomplete; it doesn't specify the ceteris paribus conditions and so doesn't specify what is necessary for a proof of the prediction π for a particular focal point. Second, counterfactual explanations are also partial in the sense that they don't specify all the sufficient conditions that lead to π; they are hence globally incomplete. Finally, counterfactuals are partial in a third sense; they are also locally incomplete. To explain this sense, we need a notion of overdetermination.

Definition 4. A prediction π ∈ Y by f : X → Y is overdetermined for a focal point x ∈ X if the set of minimally sufficiently appropriate transformations of x O(x, π, f ) = {∆ i : ∆ i (x)
is minimally sufficiently appropriate} contains at least two elements.

Locally incomplete explanations via counterfactuals can occur whenever f 's counterfactual decisions are over-determined for a given focal point. Many real world applications like our bank loan example will have this feature.

Locally incomplete explanations can, given a particular ML model M f , hide implicitly defined properties that show f to be unacceptably biased in some way and so pose a problem for fair and adequate explanations. Local incompleteness allows for several explanatory counterfactuals with very different explanans to be simultaneously true. This means that even with an explanation, f may act in ways unknown to the agent E or the public that is biased or unfair. Worse, the constructor or owner of f will be able to conceal this fact if the decision for E is overdetermined, by offering counterfactual explanations using maps ∆ that don't mention the biased feature.

Definition 5. A prejudicial factor P is a map, P : X n → X n and f exhibits a biased dependency on prejudicial factor P just in case for some i = 0, ∆ i , and for some incompatible predictions η and π,

f (x) = f (∆ i (x)) = η and f (P (x)) = f (P (∆ i (x))) = π
Dimensions of the feature space that are atomic formulas in L f can provide examples of a prejudicial factor P . But prejudical factors P may be also implicitly definable in M f . Assume that . is a map from real individuals x to their representation as data points x ∈ X. Then: P is M f implicitly definable just in case:

for all x such that x ∈ X, x ∈ P iff for some boolean combination E of atoms of L f , M f |= E(x). We've just described some pitfalls of locally incomplete counterfactual explanations. We now show how to move from a partial picture of the behavior of f to a more complete one using counterfactuals. Imagine that at a focal point x, f (x) = η and we want to know why not π. Definition 6. In a counterfactual model C X n , f with a set of Boolean valued features P , the collection of counterfactuals S C,x,π = {φ → π : C X n , f , x |= φ → π with φ a Boolean combination of values for atoms in P } true at x gives the complete explanation for why π would have occurred at x. Appropriate transformations ∆ i on X n in a counterfactual model C X n , f to produce π associated with counterfactuals via Proposition 1 can capture S C,x,π and permit us to plot the local complete explanation of f around a focal point x with regard to prediction π.

Definition 7. B C,x,π = {∆ i (x) : ∆ i is a minimal appropriate transformation for some i ⊂ n} Proposition 3. In a counterfactual model C X n , f , B C,x,π = {y ∈ X n : ∃ (φ → ψ) ∈ S C,x,π such that y is a closest φ world to x where C X n , f , y |= ψ}.
For the remainder of this section we will fix a counterfactual model C X n , f to simplify notation.

We are interested in the space N f ,x,π around x with boundary B x,π .

Definition 8. 1. N f ,x,π is the subspace of X n such that (i) x ∈ N f ,x,π and

(ii) N f ,π,x includes in its interior all those points z for which f (z) = f (x) and (iii) the boundary of

N f ,x,π is given by B x,π . 2. N d f ,π,x is a subspace of N f ,x,π with boundary B d x,π , where B d x,π = B x,π ∩ B d (x), where B d (x) = {y ∈ X n : y -x ≤ d}.

S d

x,π = {y : ∃(φ → ψ) ∈ S x,π ∧ C X n , f , y |= ψ ∧ y -x ≤ d}. The set S x,π can have a complex structure in virtue of the presence of ceteris paribus assumptions. Because strengthening of the antecedent fails in semantics for counterfactuals, the counterfactuals in (4) relevant to our example of Section 2 are all satisfiable at a world without forcing the antecedents of (4)b or (4)c to be inconsistent: [START_REF] Bachoc | Entropic variable projection for explainability and intepretability[END_REF] a. If I were making e100K euro, I would have gotten the loan. b. If I were making e100K or more but were convicted of a serious financial fraud, I would not get the loan. c. If I were making e100K or more and were convicted of a serious financial fraud but then the conviction was overturned and I was awarded a medal, I would get the loan.

The closest worlds in which I make e100k do not include a world w in which I make e100k but am also convicted of fraud. Counterfactuals share this property with other conditionals that have been studied in nonmonotonic reasoning [START_REF] Ginsberg | Counterfactuals[END_REF][START_REF] Pearl | System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning[END_REF]. However, if the actual world turns out to be like w, then by weak centering (4)a turns out to be false, because the ceteris paribus assumption in (4)a is that the actual world is one in which I'm not convicted of fraud.

In S x,π we can count how many times the value of the consequent changes as we move from one antecedent to a logically more specific one (e.g., does the prediction flip from A to A ∧ C or from A ∧ C to A ∧ C ∧ D). For generality, we will also include in the number of flips, the flips that happen when we change the Boolean value of a feature-going from A to ¬A for example. We will call the number of flips the flip degree of S x,π .

There is an important connection between the flip degree of S x,π and the geometry of N f ,x,π . In a counterfactual model, the move from one antecedent φ 1 of a counterfactual c 1 a to logically more specific antecedent φ 2 of c 2 , with c 1 , c 2 ∈ S x,π will, given certain assumptions about the underlying norm yield x < y < z, with y being a closest to x point verifying φ 1 and z a closest point verifying φ 2 . In fact we generalize this property of norms. Definition 9. A norm ||.|| in a counterfactual model C X n , f respects the logical specificity of the model iff for any z ∈ X n such that C X n , f , z |= ψ and for counterfactual antecedents φ 1 , φ 2 , . . . , φ n describing features of X n such that C X n , f , z |= φ 1 → ¬ψ, φ 2 → ψ, . . . , φ n → ¬ψ such that φ i+1 |= φ i and φ i |= φ i+1 , there are collinear x 1 , ...x n ∈ X n such that for each i, x i is a closest point to z such that C X n , f , x i |= φ i and ||x i+1 -z|| > ||x i -z||.

Remark 1 An L1 norm for a counterfactual model is a logical specificity respecting norm.

In addition, a flip (move from a point verifying φ 1 to a point verifying φ 2 corresponds to a move from a transformation ∆ i to a transformation ∆ j with i ⊂ j. Thus, flips determine a partial ordering under ⊆ over the shifted dimensions i: thus ∆ i ≤ ∆ j , if i ⊆ j. We are interested in the behavior of f with respect to the partial ordering on ∆ i . Definition 10. f is nearly constant around x, if for every sufficiently minimally appropriate ∆ i for all ∆ j ⊃ ∆ i , f (∆ j (x)) = f (∆ i (x)).

A nearly constant f changes values only once for each combination of features/dimensions d i moving out from a focal point x. So at some distance d, nearly constant f becomes constant f . For a nearly constant f around x, S x,π , has flip degree 1. A complete local explanation for f 's prediction of π within d, S d

x,π , is a global explanation f 's behavior with respect to π.

We can generalize this notion to define an n-shifting f . If f flips values n times moving out from x, S x,π has flip degree n. Proof sketch. Assume S x,π has flip degree ≥ 3. Then S x,π will contain counterfactuals with antecedents φ, χ, δ such that φ |= χ |= δ but, say, φ and δ counterfactually support π but not χ. As the underlying norm respects |=, there are collinear points x, y, and z, where x is a closest point to x where φ is true, y is a closest χ world, and z is a closest δ world such that x < z < y < x. But x, y χ ∈ N f ,x,π , while x φ , z δ ∈ B x,π and ∈ N f ,x,π , which makes N f ,x,π non convex. Conversely, suppose N f ,x,π is non convex. Using the construction of counterfactuals from the boundary B x,π of N f ,x,π will yield a set with flip degree 3 or higher.

The flip degree of S x,π gives a measure of the degree of non-convexity of N f ,x,π , and a measure of the complexity of an explanation of f 's behavior. A low flip degree for S d

x,π with minimal overdeterminations provides a more general and comprehensive explanation. With Proposition 4, a low flip degree converts a local complete explanation into a global explanation, which is a priori preferable. It is also arguably closer to our prior beliefs about basic causal processes. The size of S d

x,π gives us a measure to evaluate f itself; a large S d x,π doesn't approximate very well a good scientific theory or the causal structures postulated by science. Such a f lacks generality; it has neither captured the sufficient nor the necessary conditions for its predictions in a clear way. This could be due to a bad choice of features determining f 's input X n [START_REF] Dube | High dimensional spaces, deep learning and adversarial examples[END_REF]; too low level or unintuitive features could lead to lack of generality with high flip degrees and numerous overdeterminations. Thus, we can use S d

x,π to evaluate f and its input representation X n .

The flip degree of S x,π and the topology of N f ,x,π can also tell us about the relation between counterfactual explanations based on some element in X and ground truth instances provided during training. Our learning algorithm f is trying to approximate or learn some phenomenon, which we can represent as a function f : X → Y ; the observed pairs (z, f (z)) are ground truth points for f . Ideally, f should fit and converge to f -i.e., with the number of data points N f is trained on lim N →∞ f N → f ; in the limit explanations of the behavior of f will explain f , the phenomenon we want to understand. Given that we generate counterfactual situations using techniques used to find adversarial examples, however, counterfactual explanations may also be based on adversarial examples that have little to no intuitive connection with the ground truth instances f was trained on. While these can serve to explain the behavior of f and as such can be valuable, they typically aren't good explanations of the phenomenon f that f is trying to model. [START_REF] Laugel | Unjustified classification regions and counterfactual explanations in machine learning[END_REF] seek to isolate good explanations of f from the behavior of f and propose a criterion of topological connectedness for good counterfactual explanations. This idea readily be implemented as a constraint on N f ,x,π : roughly, f as an approximation of f will yield good counterfactual explanations relative to a focal point x only if for any point y outside of N f ,x,π , there is a region C where f returns the same value and a path of points y 1 , ...y n ∈ C between y and a ground truth data point p such that f (p) = f (p) = f (y i ) = f (y). 10While we have clarified the partiality of counterfactual explanations, AI applications can encode data via hundreds even thousands of features. Even for our simple running example of a bank loan program, the number of parameters might provide a substantial set of counterfactuals in the complete local explanation given by S x,π . This complete local explanation might very well involve too many counterfactuals for humans to grasp. We still to understand what counterfactual explanations are pragmatically relevant in a given case.

Pragmatic relevance relies on two observations. First, once we move out a certain distance from the focal point, then the counterfactual shifts intuitively cease to be about the focal point; they cease to be counterparts of x and become a different case. Exactly what that distance is, however, will depend on a variety of factors about the explainee E and what the explainer believes about E. Second, appropriate explanations must respond to the particular conundrum or cognitive problem that led E to ask for the explanation [START_REF] Bromberger | An approach to explanation[END_REF][START_REF] Achinstein | The Nature of Explanation[END_REF][START_REF] Miller | Explanation in artificial intelligence: Insights from the social sciences[END_REF]. On our view, the explainee E requires an explanation when her beliefs do not lead her to expect the observed prediction π. When E's beliefs suffice to predict f (x) = π, she has a priori an answer to the question Why did f (x) = π? In our bank example from Section 2, had E's beliefs been such that she did not expect a loan from the bank, she wouldn't have needed to ask, why did the bank not give me a loan? 11The conundrum comes from a mismatch between E's understanding of what f was supposed to model (our function f ) and f 's actual predictions. So E, in requesting an explanation of f 's behavior, might also want an explanation of f itself (see the previous section for a discussion). Either E is mistaken about the nature of f , or her grasp of f is incomplete..12 More often than not, E will have certain preconceptions about f , and then many if not most of the counterfactuals in S x,π may be irrelevant to E. A relevant or fair and adequate explanation for E should provide a set C d E of appropriate ∆ i with ∆ i (x) -x ≤ d showing which of E's assumptions were faulty or incomplete, thus solving her conundrum.

Suppose that the explainee E requests an explanation why f (x) = η, and that x is decomposed into x d1 , x d2 .

CI Suppose E's conundrum based on incompleteness; i.e., the conundrum arises from the fact that for E f only pays attention to the values of dimensions d 1 in the sense that for her f (

x d1 , x d2 ) = f ( x d1 , x d2 ), for any values x d2 . Then there is a ∆ ∈ C d E such that ∆( x d1 , x d2 ) = x d1 , y d2 and f (∆(x)) = f ( x d1 , y d2 ) = π while f (x) = f ( x d1 , x d2 ) = η. CM Suppose E's conundrum is based on a mistake. Then there is a ∆ ∈ C d E such that ∆( x d1 , x d2 ) = y d1 , x d2 such that f ( y d1 , x d2 ) = f (∆(x)) = π. I.e.,
∆ must resolve E's conundrum by providing the values for the dimensions d 2 of x on which E is mistaken.

A fair and adequate explanation must not only contain counterfactuals that resolve the explainee's conundrum. It must make clear the biases of the system which may account for 0's incomplete understanding of f ; it must lay bare any prejudicial factors P that affect the explainee and thus in effect all overdetermining factors as in Definition 4. An explainee might reasonably want to know whether such biases resulted in a prediction concerning her. E.g., the explanation in (3) might satisfy CM or CI, but still be misleading. Thus:

CB ∀ prejudicial factors P , there is a ∆ ∈ C d E such that f (∆(x)) = π and P (∆(x)) = ∆(x).
In our bank loan example, if the bank is constrained to provide an explanation obeying CB, then it must provide an explanation according to which being white and having E's salary would have sufficed to get the loan. Definition 11. A set of counterfactuals provides a fair and adequate explanation of f for E at x just in case they together satisfy CM, CI and CB within a certain distance d of x.

The counterfactuals in C d E jointly provide a fair and adequate explanation of f for E, though individually they may not satisfy all of the constraints. We investigate how hard it is to find an adequate local explanation in the next section.

The algorithmic complexity of finding fair and adequate explanations

In this section, we examine the computational complexity of finding a fair and adequate explanation. To find an appropriate explanation, we imagine a game played, say, between the bank and the would-be loan taker E in our example from Section 2, in which E can ask questions of the bank (or owner/ developer of the algorithm) about the algorithm's decisions. We propose to use a two player game, an explanation game to get appropriate explanations for the explainee. The pragmatic nature of explanations already motivates the use of a game theoretic framework. We have argued fair and adequate explanations must obey pragmatic constraints; and in order to satisfy these in a cooperative game the explainer must understand explainee E's conundrum and respond so as to resolve it. Providing an explanation is a pragmatic act that takes into account an explainee's cognitive state and the conundrum it engenders for the particular fact that needs explaining. A cooperative explainer will provide an explanation in terms of the type he assigns to E, as the type will encode the relevant portions of E's cognitive state. On the other hand the explainee will need to interpret the putative explanation in light of her model of the explainer's view of his type. Thus, both explainer and explainee naturally have strategies that exploit information about the other. Signaling games [START_REF] Spence | Job market signaling[END_REF] are a well-understood and natural formal framework in which to explore the interactions between explainer and explainee; the game theoretic machinery we develop below can be easily adapted into a signaling game between explainer and explainee where explanations succeed when their strategies coordinate on the same outcome.

Rather than develop signaling games however for coordinating on successful explanations, we look at non-cooperative scenarios where the explainer f may attempt to hide a good explanation. For instance, the bank in our running example might have encoded directly or indirectly biases into its loan program that are prejudicial to E, and it might not want to expose these biases. The games below provide a formal account of the difficulty our explainee has in finding a winning strategy in such a setting.

To define an explanation game, we first fix a set of two players {E, A}.

The moves or actions V E for explainee E are: playing an ACCEPT move-in which E accepts a proposed ∆ i if it partially solves her conundrum; playing an N-REQUEST move-i.e. requesting a ∆ j where j differs from all i such that ∆ i has been proposed by A in prior play; playing a P-REQUEST move-i.e. for some particular i, requesting ∆ i . E may also play a CHALLENGE move, in which E claims that a set of features A 1 , . . . A n of the focal point that entails π in the counterfactual model associated with f . We distinguish three types of ME explanation games for E based on the types of moves she is allowed: the Forcing ME explanation games, in which E may play ACCEPT, N-REQUEST, P-REQUEST; the more restrictive Restriction ME explanation games, in which E may only play ACCEPT, N-REQUEST; and finally Challenge ME explanation games in which CHALLENGE moves are allowed. Adversary A's moves V A consists of the following: producing ∆ i and computing f (∆ i (x)) in response to N-REQUEST or P-REQUEST by E; if G is a forcing game, A must play ∆ i at move m in ρ, if E has played P-REQUEST ∆ i at m -1. In reacting to a N-REQUEST, player A may offer any new ∆ i ; if he is noncooperative, he will offer a new ∆ i that is not relevant to E's conundrum, unless he has no other choice. On the other hand, A must react to a CHALLENGE move by E by playing a ∆ i that either completes or corrects the Challenge assumption. A CHALLENGE demands a cooperative response; and since it can involve any implicitly definable prejudicial factor as in Definition 5, it can also establish CB, as well as remedy CI or CM.

We now specify a win-lose, generic explanation game.

Definition 12. An Explanation game, G, concerning a polynomially computable function f : X n → Y , where X n is a space of boolean valued features for the data and Y a set of predictions, is a tuple [START_REF] Johnson | How easy is local search?[END_REF][START_REF] Papadimitriou | On the complexity of local search[END_REF]. On the other hand if G is only a Restriction game, then the worst case complexity for finding her strategy is exponential.

((V E ∪ V A ) * , E, A, f : X n → Y, x, d, C d E ) where: i. C d E ⊆ B d x,
Proof sketch. Finding C d E is a search problem using f . C d E is finite with, say, m elements. These elements need not be unique; they just need jointly to solve the conundrum. This search problem is PLS just in case every solution element is polynomially bounded in the size of the input instance, f is poly-time, the cost of the solution is poly-time and it is possible to find the neighbors of any solution in poly-time. Let x be the input instance. By assumption, f is polynomial; and given the bound d, the solutions y for f (y) = π and y ∈ C The fact that forcing explanation games are PLS complete makes getting an appropriate explanation computationally difficult. Worse, if G is a Restriction Explanation game,then A can force E to enumerate all possible ∆ i within radius d of x to find C d E .

Proposition 6. Suppose G is a Challenge explanation game. Then E has a winning strategy in G that is linear time computable.

Proof sketch. A must respond to E's CHALLENGE moves by correcting or completing E's proposed list of features. E can determine C d E in a number of moves that is linear in the size of C d E .

A Challenge explanation game mimics a coordination game where A has perfect information about C d E , because it forces cooperativity and coordination on the part of A. Suppose E in our bank example claims that her salary should be sufficient for a loan. In response to the challenge, the bank could claim the salary is not sufficient; but that's not true-the salary is sufficient provided other conditions hold. That is, E's conundrum is an instance of CI. Because of the constraint on CHALLENGE answers by the opponent, the bank must complete the missing element: if you were white with a salary of e50K,... Proposition 6 shows that when investigating an f in a challenge game, exploiting a conundrum is a highly efficient strategy.

The flip degree of S d x,π and the number of overdetermining factors O(x, π) (Definition 4) typically affect the size of C and thus the complexity of the conundrum and search for fair and adequate explanations and their logical valid associates. More particularly, when |O(π, x)| = n and the cost of the prediction is as in the proof of Proposition 5, E's conundrum and the explanations resolving it may require n local minima. When the flip degree of S d

x,π is m, E may need to compute m local minima.

To develop practical algorithms for fair and adequate explanations for AI systems, we need to isolate E's conundrum. This will enable us to exploit the efficiencies of Challenge explanation games. Extending the framework to discover E's conundrum behind her request for an explanation is something we plan to do using epistemic games from [START_REF] Asher | Strategic conversation under imperfect information: epistemic Message Exchange games[END_REF] with more developed linguistic moves. In a more restricted setting where Challenge games are not available, our game framework shows that clever search algorithms and heuristics for PLS problems will be essential to providing users with relevant, and provably fair and adequate counterfactual explanations. This is something current techniques like enumeration or finding closest counterparts, which may not be relevant [START_REF] Ignatiev | On relating explanations and adversarial examples[END_REF][START_REF] Ignatiev | On relating "why?" and "why not?" explanations[END_REF][START_REF] Karimi | Model-agnostic counterfactual explanations for consequential decisions[END_REF]-do not do.

Conclusion

We have shown that counterfactual explanations can deliver partial, but epistemically accessible and adequate explanations. We have also shown that any counterfactual explanation can be extended to a valid deductive one. We have shown that pragmatic factors dramatically affect the complexity of finding adequate explanations, and we introduced Explanation Games, which provided to represent finding fair and adequate counterfactual explanations as a PLS complete search problem. In addition, we explored how the complexity of the set of counterfactuals describing a local neighborhood around the focal point can affect both the complexity of fair and adequate explanations and our evaluation of the learning algorithm as a model.

Our paper fills in part of the gap for finding fair and adequate explanations in a computationally reasonable way. Nevertheless moving from an explanation provided by an explanation game to a proof from a minimal set of sufficient premises as in Proposition 2 is still computationally difficult. In future work we will look at efficient heuristics for this step. In future work, we will alo look at how explanation games help us to formally explore interactive machine learning, in particular "human in the loop" or interactive explainability for machine learning function behavior [START_REF] Amershi | Power to the people: The role of humans in interactive machine learning[END_REF][START_REF] Holzinger | Interactive machine learning: experimental evidence for the human in the algorithmic loop[END_REF]. Such game theoretic investigations may have special relevance in medical domains [START_REF] Holzinger | Towards multi-modal causability with graph neural networks enabling information fusion for explainable ai[END_REF].

Proposition 4 .

 4 Suppose A counterfactual model has a logical specificity respecting norm, then: S x,π , has a flip degree ≤ 2 iff N f ,x,π forms a convex subspace of f [X].

  d E are polynomially bounded in the size of the description of x. Now, finding a point y ∈ C d E that solves at least part of E's conundrum, as well as finding neighbors of y is polytime, since E can use P-REQUEST moves to direct the search. To determine the cost c of finding C d E for |C d E | = m in poly-time: we set for y ∈ C d E the jth element of C computed as c(y) = m -j; if y ∈ C, c(y) = m. Finding C d E thus involves determining m local minima and is PLS. In addition, determining C d E encodes the PLS complete problem FLIP[START_REF] Johnson | How easy is local search?[END_REF]: the solutions y in G have the same edit distance as the solutions in FLIP, f encodes a starting position, and our cost function can be recoded over the values of the Boolean features defining y to encode the cost function of FLIP and the function that compares solutions in FLIP is also needed and constructible in G. So finding C d E is PLS complete in G as it encodes FLIP.

  π resolves E's conundrum and obeys CB. ii. x ∈ X n is the starting position, d is the antecedently fixed distance parameter. iii. A, but not E has access to the behavior of f and a fortiori C d E . iv. E opens G with a REQUEST or CHALLENGE move v. A responds to E's requests by playing some ∆ i , i ≤ d. vi. E may either play ACCEPT, in which case the game ends or again play a REQUEST or CHALLENGE move. E wins G just in case in G she can determine C d E . The game terminates when (a) 0 has determined C d E (resolved her conundra) or gives up. E always has a winning strategy in an explanation game. The real question is how quickly E can compute her winning condition. An answer depends on what moves we allow for E in the Explanation game; we can restrict E to playing a Restriction explanation game, a Forcing game or a Forcing game with CHALLENGE moves. Proposition 5. Suppose G is a forcing explanation game. Then the computation of E's winning strategy in G is Polynomial Local Search complete (PLS)

[START_REF] Fan | On computing explanations in argumentation[END_REF] provide a superficially similar picture to the pragmatic one we present, but their aim is rather different, to provide a semantics for argumentation frameworks. For us the pragmatic aspect of explanations is better explained via a game theoretic framework; see below.

We are implicitly assuming that f is too complex or opaque for its behaviour to be analyzed statically.

By increasing the number of literals we can simulate non binary values, so this is not really a limitation as long as the features are finite.

See[START_REF] Ignatiev | On relating "why?" and "why not?" explanations[END_REF] for some experimental evidence of this.

In fact, we only assume a finite set of finitely valued features, since an n-valued feature is definable with n Boolean valued features. By complicating the language

Such minimal perturbations may not reflect the ground truth, the causal facts that our machine learning algorithm is supposed to capture with its predictions, as noted by[START_REF] Laugel | Unjustified classification regions and counterfactual explanations in machine learning[END_REF]. We deal with this in Section 4.

We note that our discussion and constraint make clear the distinction between f and f which is implicit in[START_REF] Laugel | Unjustified classification regions and counterfactual explanations in machine learning[END_REF][START_REF] Holzinger | Measuring the quality of explanations: the system causability scale (scs)[END_REF].

Of course E might want to know whether her beliefs matched the bank's reasons for denying her a loan, but that's a different question-and in particular it's not a why question.

Perhaps E is also mistaken about or has an incomplete grasph of f or if not, she is mistaken about how f differs from f ). But we will not pursue this here.

Acknowledgement

We thank the ANR PRCI grant SLANT, the ICT 38 EU grant COALA and the 3IA Institute ANITI funded by the ANR-19-PI3A-0004 grant for research support. We alo thank the reviewers for their insightful comments.


Boris Muzellec
email: boris.muzellec@inria.frfrancis.bach@inria.fralessandro.rudi@inria.fr

Francis Bach

Alessandro Rudi

A Note on Optimizing Distributions using Kernel Mean Embeddings

Kernel mean embeddings are a popular tool that consists in representing probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. When the kernel is characteristic, mean embeddings can be used to define a distance between probability measures, known as the maximum mean discrepancy (MMD). A well-known advantage of mean embeddings and MMD is their low computational cost and low sample complexity. However, kernel mean embeddings have had limited applications to problems that consist in optimizing distributions, due to the difficulty of characterizing which Hilbert space vectors correspond to a probability distribution. In this note, we propose to leverage the kernel sums-of-squares parameterization of positive functions of Marteau-Ferey et al. [2020] to fit distributions in the MMD geometry. First, we show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. Then, we provide algorithms to optimize such distributions in the finite-sample setting, which we illustrate in a density fitting numerical experiment.

Introduction

Mean embeddings [START_REF] Muandet | Kernel mean embedding of distributions: A review and beyond[END_REF] are a way of representing probability distributions through the moments of a potentially infinite-dimensional feature vector, usually corresponding to the feature map φ(x) of a reproducing kernel Hilbert space (RKHS) H. When this RKHS is large enough (i.e., when the kernel is characteristic [START_REF] Bharath | Universality, characteristic kernels and rkhs embedding of measures[END_REF]) this embedding is injective, i.e., a distribution is uniquely characterized by its mean embedding. From there, one may define a distance between probability distributions as the distance between their embeddings in the Hilbert space, known as the maximum mean discrepancy (MMD) [START_REF] Gretton | A kernel two-sample test[END_REF].

MMD benefits from a low computational cost and a favorable sample complexity. More precisely, given two distributions µ, ν on R d , one may get a estimate of the MMD distance based on n samples from µ and ν with a precision O(n -1/2 ), independently from the dimension d, at a O(dn 2 ) computational cost. For those reasons, MMD has become a popular distance in the machine learning community that has had applications to testing [START_REF] Gretton | A kernel two-sample test[END_REF][START_REF] Sejdinovic | Equivalence of distance-based and rkhs-based statistics in hypothesis testing[END_REF] and generative modeling [START_REF] Li | Generative moment matching networks[END_REF][START_REF] Bińkowski | Demystifying mmd gans[END_REF], among others.

However, numerous machine learning applications such as density fitting [START_REF] Parzen | On estimation of a probability density function and mode[END_REF][START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF]] or distributionally robust optimization (DRO) [START_REF] Rahimian | Distributionally robust optimization: A review[END_REF] place the focus on optimizing distributions themselves. Despite its practical advantages, MMD has had limited applications to those tasks, due to the difficulty of characterizing which functions in a RKHS are the mean embeddings of a probability distribution. Indeed, while H corresponds to the space spanned by {φ(x), x ∈ R d }, the set of mean embeddings M is only the convex hull of this set, whose extreme points are the feature vectors φ(x), x ∈ R d . This can be related to the pre-image problem [Kwok and [START_REF] Kwok | The pre-image problem in kernel methods[END_REF]: given an element v of H, the pre-image problem consists in finding a point x whose feature vector φ(x) is equal or close to v. In comparison, we aim here at finding a distribution µ such that E µ [φ(x)] is close to v.

As a workaround, [START_REF] Staib | Distributionally robust optimization and generalization in kernel methods[END_REF] propose to relax such problems by optimizing over any function in H, instead of restricting to those in M. As a result, the output of those methods are not guaranteed to correspond to probability distributions: they may correspond to measures that do not have unit mass, or that take negative values. Alternatively, in some settings it is possible to obtain a tractable exact problem by deriving the dual [START_REF] Zhu | Kernel distributionally robust optimization: Generalized duality theorem and stochastic approximation[END_REF].

Contributions. In this short note, we leverage the kernel sum-of-squares representation for positive functions proposed by Marteau-Ferey et al. [2020] to design a method to optimize over probability distributions in the MMD distance. In the finite-sample setting, this parameterization can be approximated with a finiterank positive-semidefinite (PSD) matrix. Based on this fact, we provide algorithmic tools to solve optimization problems over distributions in the MMD geometry. Finally, we illustrate our methods on a density fitting example.

Background and notation

Notation. For n ∈ N, [n] denotes the set {1, ..., n}. We use lower-case fonts for vectors (e.g., v), and bold upper-case fonts for matrices (e.g., B). We denote inner products •, • to which we add a subscript: F for the Frobenius product between matrices, H for the Hilbert inner product on H, HS for the Hilbert-Schmidt product between bounded operators on H. For a set X , P(X ) denotes the space of probability distributions on X , and when applicable AC(X ) is the subset of absolutely continuous probability distributions (i.e., that admit a density w.r.t. the Lebesgue measure on X ). C 0 (X ) denotes the set of real-valued continuous functions on X that vanish at infinity. Kernels and reproducing kernel Hilbert spaces (RKHS). We refer to [START_REF] Steinwart | Support Vector Machines[END_REF] and [START_REF] Paulsen | An Introduction to the Theory of Reproducing Kernel Hilbert Spaces[END_REF] for a more complete covering of the subject. Let X be a set and k : X × X → R. k is a positive-definite kernel if and only if for any set of points x 1 , ..., x n ∈ X , the matrix of pairwise evaluations K ij = k(x i , x j ), i, j ∈ [n] is positive semi-definite. Given a kernel k, there exists a unique associated reproducing kernel Hilbert space (RKHS) H, that is, a Hilbert space of functions from X to R satisfying the two following properties:

• For all x ∈ X , k x def = k(x, •) ∈ H; • For all f ∈ H and x ∈ X , f (x) = f, k x H . In particular, for all x, x ∈ X it holds k x , k x H = k(x, x ).
A feature map is a bounded map φ : X → H such that ∀x, x ∈ X , φ(x), φ(x ) H = k(x, x ). A particular instance is x → k x , which is referred to as the canonical feature map. Many practical applications of RKHS theory can be cast as minimization problems of the form

min f ∈H L(f (x 1 ), ..., f (x n )) + Ω( f H ), (1)
where Ω : R + → R is a strictly increasing function. In that case, the representer theorem [see, e.g., [START_REF] Steinwart | Support Vector Machines[END_REF]Christmann, 2008, Paulsen and[START_REF] Paulsen | An Introduction to the Theory of Reproducing Kernel Hilbert Spaces[END_REF]references therein] shows that solutions of (1) admit the following finite representation:

f = n i=1 α i k xi for some α ∈ R n .
Kernel mean embeddings and maximum mean discrepancy (MMD). Given a probability measure µ, we define its kernel mean embedding as the element w µ of H that satisfies ∀f ∈ H, E X∼µ [f (x)] = f, w µ H , which may be expressed as w µ = X φ(x)dµ(x). When the kernel is characteristic [START_REF] Bharath | Universality, characteristic kernels and rkhs embedding of measures[END_REF] -such as the Gaussian kernel -the embedding µ → w µ is injective. Note that mean embeddings are a strict subset of H: as mentioned in Section 1, an element of H is the kernel mean embedding of a distribution if and only if it lies in M def = Conv({φ(x) : x ∈ H}), whereas H = Span({φ(x) : x ∈ H}). Using kernel mean embeddings, we may define a distance between probability measures, called the maximum mean discrepancy [START_REF] Gretton | A kernel two-sample test[END_REF]:

MMD(µ, ν) def = w µ -w ν H .
When ν admits a density p, we write by abuse MMD(µ, p) for MMD(µ, ν).

2.1 Relaxing mean embedding constraints: a counter-example Note that the relaxed adversary (left) is not the mean embedding of a probability distribution (it is the embedding of a Dirac in 0 with a negative mass). The solution of the unrelaxed problem is evaluated by discretizing the support interval [-2, 2], for which we obtain θ ≈ -0.4. A equivalent symmetrical saddle point with θ ≈ 0.4 also exists.

We conclude this section with a simple example to illustrate how replacing MMD constraints over distributions with RKHS norm constraints over vectors can be detrimental. Let μ denote a distribution of observed data points, and K a positive-definite translation-invariant kernel (e.g., the Gaussian kernel

K(x, y) = e -x-y 2 σ 2
) with corresponding RKHS H. Assume the convolution (K * μ) of μ by K denotes a "return function", that a player wants to maximize by picking the highest mode:

max θ∈R d (K * μ)(θ).
(2)

The player knows that an adversary might have perturbed the data μ that they have observed, compared to a true underlying distribution µ from which the player will get their returns. To hedge themselves against the adversary, the player decides to optimize θ over the worst distribution in a MMD ball around the observed distribution μ:

max θ∈R d min µ∈P(R d ) (K * µ)(θ) s.t. MMD(µ, μ) ≤ ε. (3)
As mentioned in the introduction, problems of this form are generally intractable. As an example, [START_REF] Staib | Distributionally robust optimization and generalization in kernel methods[END_REF] are confronted to this issue in applications to distributionally robust optimization, and propose to circumvent the difficulty by relaxing the problem: instead of restricting to distributions in the MMD distance, they optimize over H in the RKHS norm. Observing that the objective of eq. ( 3) can be rewritten as the inner product (K * µ)(θ) = w µ , φ(θ) H , this yields the following relaxed problem:

max θ∈R d min v∈H v, φ(θ) H s.t. v -w μ H ≤ ε. (4)
Equation ( 4) is a saddle point problem, in which the inner minimum a is convex problem. Writing the optimality conditions for the min, we get that the optimal adversary is v (θ) = w μ -ε φ(θ) φ(θ) . Plugging this back in eq. ( 4), the problem becomes

max θ∈R d (K * μ)(θ) -ε K(θ, θ).
(5)

Let us observe two things: first, in general v (θ) is not the mean embedding of a probability distribution, and may even take negative values. Second, given that K is a translation-invariant kernel, the solution θ of eq. ( 5) is the same as the non-robust version (2) and does not depend on ε: only the value of the objective does. Hence, the relaxed version (4) fails at guaranteeing adversarial robustness. On the other hand, the original adversarial problem over distributions in eq. ( 3) does not admit a simple analytical expression, but does guarantee robustness against adversarial perturbations. This is illustrated in Figure 1 in a 1D case where μ is a Dirac centered in 0 and K is the Gaussian kernel. The discrepancy between the MMD geometry over distributions and the RKHS norm over general functions is already visible in this toy example. This suggests that the RKHS norm relaxation is ill-suited to more complex, higher-dimensional tasks and settings, and calls for better ways of dealing with optimization problems on distributions with MMD.

3 Optimizing over distributions using kernel sums-of-squares

As mentioned in Section 1, problems of the form

inf µ∈P(X ) F (v) s.t. v = φ(x)dµ(x) (6)
are notoriously difficult to tackle. In this note, we introduce a parametric model for smooth distributions that is compatible with MMD, that can be plugged in eq. ( 6). We focus on measures that admit a smooth density p w.r.t. to a reference measure ρ ∈ M(X ) (e.g., for X ⊂ R d we may consider the Lebesgue measure), and propose to represent such densities using the kernel sum-of-squares (SoS) representation of non-negative functions of Marteau-Ferey et al. [2020]:

p A (x) = φ(x), Aφ(x) H , x ∈ X , (7)
with A ∈ S + (H). The following lemma (which is a particular case of Proposition 4 of Marteau-Ferey et al.

[2020]) characterizes the operators S + (H) that lead to a valid density p A (i.e., with total mass equal to 1). Its proof is deferred to the appendix.

Lemma 1. Let A ∈ S + (H) and ρ ∈ M(X ). Define Σ ρ def = X φ(x) ⊗ φ(x)dρ(x).
The function p A defined in eq. ( 7) is a density w.r.t. ρ if and only if A, Σ ρ HS = 1.

From there, we propose to handle problems of the form (6) using the parameterization in eq. ( 7), i.e., to solve inf

A∈S+(H) F (w p A ) s.t. Tr(AΣ ρ ) = 1. ( 8
)
We will denote

F ρ def = = {p A : A ∈ S + (H), TrAΣ ρ = 1}
. This representation has the double advantage of being parametric -and thus amenable to learning, as we will show in the remainder of this work -and universal. Indeed, as proved by Marteau-Ferey et al. [2020], any continuous positive function can be approximated arbitrarily well in maximum norm over compact subsets by a function of the form of eq. ( 7) provided H is large enough: this is referred to as universality [START_REF] Charles A Micchelli | Universal kernels[END_REF].

Proposition 1 (Marteau-Ferey et al. [2020]). Let H be a RKHS with a universal feature map φ : X → R d . Then {p A : A ∈ S + (H), TrA < ∞} is a universal approximator of continuous non-negative functions on X .

In particular, this representation allows to approximate continuous density functions on X arbitrarily well. However, depending on the choice of topology, Proposition 1 alone does not guarantee that any distribution can be approximated by a distribution with a density in F ρ . For instance, in the total variation distance such densities may approach distributions with continuous density functions, but may not approach Dirac distributions. We show in the following theorem that distributions with densities in F ρ are dense in the set of probability distributions for the weak topology. When the kernel is continuous (like most usual kernels) and when H ⊂ C 0 , this implies in turn that F ρ is dense for the MMD distance [Simon-Gabriel et al., 2020, Lemma 2.1].

Theorem 1. Let X be a compact subset of R d , H be a RKHS with a universal feature map φ : X → R d , and assume ρ is absolutely continuous. Then distributions with densities w.r.t. ρ in F ρ are dense in P(X ) for the topology of the weak convergence.

Examples. Kernels and RKHS satisfying the hypothesis of Proposition 1 and Theorem 1 include (but do not limit to):

• the Gaussian kernel k(x, x ) = e -x-x 2 σ 2 ;

• the Laplace kernel k(x, x ) = e -x-x σ ;

• more generally, the Sobolev kernels k s (x, x ) ∝ x -x s-d/2 K s-d/2 ( x -x ) with s > d/2 and where K s-d/2 is the Bessel function of the second kind, whose corresponding RKHS are the Sobolev spaces of smoothness s [START_REF] Adams | Sobolev Spaces[END_REF].

Finally, Hilbert space distances of mean embeddings with densities of the form eq. ( 7) (and MMD in particular) can be expressed as functions of φ-tensors of order 4:

Lemma 2. Let A ∈ S + (H), TrA < ∞ and v ∈ H. It holds v -w p A 2 H = v 2 H + A, T (A) HS -2 A, V HS , (9)
with

V def = v(x)φ(x) ⊗ φ(x)dρ(x)
and T (A) def = φ(x) ⊗ φ(x) φ(y), Aφ(y) HS k(x, y)dρ(x)dρ(y) ∈ S + (H).

Low-rank representations

As recalled in Section 2, a key benefit of working in an RKHS is the existence of the representer theorem, which allows to learn functions from samples in a finite-dimensional representation. Marteau-Ferey et al.

[2020] prove an extension of the representer theorem for kernel SoS of the form (7). More precisely, the solution of a problem of the form min

A∈S+(H) L(p A (x 1 ), ..., p A (x n )) + λTrA (10) admits a representation of the form A = n ij B ij φ(x i ) ⊗ φ(x j ) with B ∈ S + (R n ).
However, unless Σ ρ admits a finite-rank parameterization, this result does not hold under the additional constraint A, Σ ρ HS = 1 that is required to ensure that p A is a density (Lemma 1).

As a workaround, we make an approximation and consider problems between vectors that are projected on a finite-dimensional subspace H m = Span{φ(x 1 ), ..., φ(x m )} where x1 , ..., xm are a set of supporting points, and consider the case where A ∈ S + (H m ). In that case, we can write

A = m i=1 B ij φ(x i ) ⊗ φ(x j ) with B ∈ S + (R m ), and we define p B (x) = m ij=1 B ij k(x, xi )k(x, xj ). From Lemma 1, p B is a valid density if and only if Tr(BW) = 1 with W ij def = X k(x, xi )k(x, xj )dρ(x), i, j ∈ [m]. Let P m denote the orthogonal projection onto H m , i.e. P m (φ(x)) = m i=1 c i φ(x i ) with c = K-1k x where Kij = k(x i , xj ), i, j ∈ [m] and ( kx ) i = k(x, xi ), i ∈ [m].
In particular, for a function that admits a finite representation

v = n i=1 a i φ(x i ), we have P m (v) = m i=1 b i φ(x i ) with b = K-1 K( X, X)a and K( X, X) ij = k(x i , x j ), i ∈ [m], j ∈ [n].
The following lemma gives a closed-form expression of the RKHS distance between a vector in H that admits a finite representation, and the mean embedding w p B . Its proof is deferred to Appendix A.

Lemma 3. Let B ∈ S + (R m ) and v = n i=1 a i φ(x i ), and W ij def = X k(x, xi )k(x, xj )dρ(x), i, j ∈ [m]. For p, q ∈ [m], denote u pq = k(x, xp )k(x, xq ) kx dρ(x) ∈ R m .
Then, p B is a density function if and only if Tr(BW) = 1, and it holds

P m (v -w p B ) 2 H = U(B) T K-1 U(B) -2 B, V F + P m (v) 2 H , ( 11
)
with ∀p, q ∈ [m], V pq = u T pq K-1 K( X, X)a, and U is the map from R m×m to R m such that U(B) = 1≤p,q≤m B pq u pq .
In particular, whenever the vectors u pq , p, q ∈ [m] are available in closed form (see examples in Appendix B),

P m (v -w p B ) 2
H can be computed in O(m 3 + nm 2 ) time.

Algorithms

We now provide algorithmic tools to optimize distributions with densities in F ρ . We illustrate those techniques on the sample problem of fitting a distribution with a kernel SoS density to observed data, with an optional trace regularization term:

inf

A∈S+(Hm) P m (v -w p A ) 2 H + λTrA s.t. Tr(AΣ ρ ) = 1. ( 12
) Writing A = ij B ij φ(x i ) ⊗ φ(x j ), we have TrA = ij B ij k(x i , xj ).
Hence, from Lemma 3 and ignoring terms that do not depend on B, eq. ( 12) can be reformulated as 13) is a smooth convex optimization problem, and can therefore be solved using (accelerated) gradient descent. However, the projection on the set

inf B 0 U(B) T K-1 U(B) -B, 2 Ṽ -λ K F s.t. Tr(BW) = 1, ( 13
) with W ij def = X k(x, xi )k(x, xj )dρ(x), i, j ∈ [m]. Equation (
A def = {M ∈ S + (R m ) : Tr(MW) = 1}
is computationally expensive (it is an instance of the covariance adjustment problem [Malick, 2004, Boyd and[START_REF] Boyd | Least-squares covariance matrix adjustment[END_REF]). We circumvent this issue by changing the parameterization to C = RBR T , where R satisfies W = R T R (e.g., the Cholesky factor of W). With this parameterization, we have

B ∈ A ⇐⇒ C ∈ B def = {M ∈ S + (R m ) : Tr(M) = 1},
with the advantage that the projection on B is much easier to compute: see Algorithm 1. This projection relies on computing the eigenvalue decomposition of C (in O(m 3 ) time) followed by the projection of its eigenvalues on the simplex in O(m) time [START_REF] Maculan | A linear-time median-finding algorithm for projecting a vector on the simplex of R n[END_REF]. With this parameterization, eq. ( 13) becomes

inf C 0 U(R -1 CR -T ) T K-1 U(R -1 CR -T ) + C, R -T (λ K -2V)R -1 F s.t. Tr(C) = 1. (14)
We may optimize this objective using projected gradient descent, or FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]. The initial formation of V, R -1 and u pq , p, q ∈ [m] has a O(mn + m 3 ) computational cost, and O(mn + m 3 ) memory footprint. From then, each (accelerated) projected gradient iteration has complexity O(m 3 ) and O(m 3 ) memory footprint (since storing K( X, X) is not necessary once V is formed). Hence, using FISTA eq. ( 13) can be minimized to precision ε with a total O mn + m 3 ε 2 computational cost [Beck and Teboulle, 2009, Theorem 4.4].

Algorithm 1 Projection on B Require: X ∈ Sym(R n ) Compute the EVD of X: X = U diag(λ 1 , ..., λ n )U T .
Project on the simplex:

(λ 1 , ..., λ n ) + ← proj ∆n (λ 1 , ..., λ n ), ∆ n def = {x ∈ R n + : n i=1 x i = 1} Ensure: X + = U diag(λ 1 , ..., λ n ) + U T
Remark 1. Depending on the choice of kernel parameters, eq. (13) and eq. ( 14) may have poor conditioning. In particular, forming the Cholesky decomposition W = R T R and inverting R may suffer from numerical stability issues. While a classical way of dealing with such issues is to use pre-conditioning [START_REF] Rudi | Falkon: an optimal large scale kernel method[END_REF] on B, this approach is not compatible with the projection strategy described in Algorithm 1. As an alternative, when the conditioning is problematic we propose to add a small diagonal term to W and to apply the constraint Tr(B(W + λI)) = 1, and then renormalize B to satisfy Lemma 1: B ← B 1-λTrB .

Applications and numerical experiments

Motivated by Theorem 1, we propose to handle problems of the form (6) using our parameterization, i.e., to solve inf

A∈S+(H) F (w p A ) s.t. Tr(AΣ ρ ) = 1. ( 15
)
Example 1: density fitting. Given n points x 1 , ..., x n sampled from an unknown distribution µ, density fitting [START_REF] Parzen | On estimation of a probability density function and mode[END_REF] aims at estimating a parametric model µ θ for µ based on its samples. Motivated by Theorem 1, we propose to fit a density estimator p B ∈ F ρ using MMD, with an optional regularization term:

min B 0 MMD( 1 n n i=1 δ xi , p B ) + λTrBK such that Tr(BW) = 1. ( 16
)
Example 2: distributionally robust optimization. Kernel distributionally robust optimization (DRO) [START_REF] Staib | Distributionally robust optimization and generalization in kernel methods[END_REF]Jegelka, 2019, Zhu et al., 2021] consists in minimizing a loss function f over f ∈ H under bounded adversarial perturbations of the input data μ = n i=1 δ xi :

min f ∈H max µ∈P(X ) E x∼µ [ f (x)] s.t. MMD(µ, μ) ≤ ε. (17)
Due to the difficulty of optimizing under the constraint MMD(µ, μ) ≤ ε, several relaxations of this problem have been proposed, leading to problems that do not respect the MMD geometry, as illustrated in Section 2.1. We propose instead to perform DRO with the parameterization (15). Problem (17) then becomes

min f ∈H max B∈S+(R n ) n i,j=1 B ij f (x)k(x, x i )k(x, x j )dρ(x)
subject to Tr(BW) = 1 and MMD(μ, p B ) ≤ ε.

(

) 18
Provided f is convex in f , ( 17) is a convex-concave min-max problem. Hence, whenever the integral f (x)k(x, x i )k(x, x j )dρ(x) can be computed in closed form (e.g., for the square loss with a Gaussian kernel), eq. ( 17) can be solved using standard min-max optimization techniques.

Numerical experiments. We provide numerical results of a 2D density fitting task. We leave to future work the implementation of more complex applications, such as the DRO problem described above. In Section 4 and figs. 2b and 2c, we sample n = 100 points from a "two moons" distribution, out of which m we then have that p An dx converges in distribution to µ, which implies weak convergence. This concludes the proof.

A.3 Proof of Lemma 2

Proof. Let A ∈ S + (H), TrA < ∞ and v ∈ H. It holds v -w p A 2 H = v 2 H + w p A 2 H -2 v, w p A H .
Since w p A = φ(x) φ(x), Aφ(x) H dρ(x), we have

w p A 2 H = φ(x) φ(x), Aφ(x) H dρ(x), φ(y) φ(y), Aφ(y) H dρ(y) H = φ(x), φ(y) H φ(x), Aφ(x) H φ(y), Aφ(y) H dρ(x)dρ(y) = k(x, y) A, φ(x) ⊗ φ(x) HS A, φ(y) ⊗ φ(y) HS dρ(x)dρ(y) = A, T (A) HS with T (A) def = φ(x) ⊗ φ(x) φ(y), Aφ(y) H k(x, y)dρ(x)dρ(y).
Likewise, we have

v, w p A H = v, φ(x) φ(x), Aφ(x) H dρ(x) H = v, φ(x) H φ(x), Aφ(x) H dρ(x) = v(x) A, φ(x) ⊗ φ(x) HS dρ(x) = A, v(x)φ(x) ⊗ φ(x) HS dρ(x) = A, V HS with V def = v(x)φ(x) ⊗ φ(x)dρ(x).
A.4 Proof of Lemma 3

Proof. Let H m = Span{φ(x 1 ), ..., φ(x m )} and A ∈ S + (H m ), there exists Further, we have where U : R m×m → R m is the tensor of order 3 defined as U(B) = pq B pq u pq .

B ∈ S + (R m ) such that A = n i,j=1 B ij φ(x i ) ⊗ φ(x j ). From Lemma 1, p A (and therefore p B ) is a density function if and only if TrAΣ ρ = 1. Since TrAΣ ρ = i,j=1 B ij φ(x i ) ⊗ φ(x j ), φ(x) ⊗ φ(x)dρ(x) HS = i,j=1 B ij φ(x i ) ⊗ φ(x j ), φ(x) ⊗ φ(x) HS dρ(x) = i,j=1 B ij φ(x i ), φ(x) H φ(x j ), φ(x) H dρ(x) = i,j=1 B ij k(x i , x)k(x j , x)dρ(x), this yields the equivalent condition TrBW = 1 with W ij = k(x i , x)k(x j , x)dρ(x), i, j ∈ [m]. Let now v = n i=1 a i φ(x i ), let us derive a finite-dimensional expression of P m (v -w p A ) 2 H , where P m is the projection operator on H m . Let Ki,j = k(x i , xj ), i, j ∈ [m], K( X, X) ij = k(x i , x j ), i ∈ [m], j ∈ [n] and kx = [k(x, xi )] m i=1 . P m satisifies P m (φ(x)) = n i=1 α i φ(x i ) with α = K-1k x . For p, q ∈ [m], let u pq = k(x, xp )k(x,
P m (v) 2 H = a T K( X, X) T K-1 K( X,

B Closed forms in the Gaussian kernel

In this section, we provide as an example closed forms for W and u pq , p, q, ∈ [m] in the case where X = R d , ρ

is the Lebesgue measure and k(x, x ) = e -x-x 2 σ 2

. Closed-forms for different kernels, supports and reference measures can be obtained in a similar way. .

Likewise, for p, q, r ∈ [m] we have

x -x p 2 + x -x p 2 + x -x r 2 = 3 x -x p + x q + x r 3 2 -1 3

x p + x q + x r 2 + x p 2 + x q 2 + x r 2 .

Hence, it holds

Figure 1 :

 1 Figure1: RKHS norm relaxation (left) vs. MMD solution (right). Note that the relaxed adversary (left) is not the mean embedding of a probability distribution (it is the embedding of a Dirac in 0 with a negative mass). The solution of the unrelaxed problem is evaluated by discretizing the support interval[-2, 2], for which we obtain θ ≈ -0.4. A equivalent symmetrical saddle point with θ ≈ 0.4 also exists.

  xq ) kx dρ(x) ∈ R m . Since A ∈ S + (H m ), A can be written as A = ij B ij φ(x i ) ⊗ φ(x j ) with B ∈ S + (R m ). Hence, it holds P m (v) = i=1 c i φ(x i ) with c = K-1 K( X, X)a,andP m (w p A ) = pq B pq P m (φ(x))k(x, xp )k(x, xq )dρ(x) = i,p,q B pq φ(x i ) K-1 k(x, xp )k(x, xq ) kx dρ(x) i = i=1 β i φ(x i ) with β = pq B pq K-1 u pq .

  X)a, andP m (v), P m (w p A ) H = c T Kβ = B, Ṽ F with Ṽpq = a T K( X, X) T K-1 u pq = c T U(B),and finallyP m (w p A ) 2 H = β T Kβ = pqrs B pq B rs u T pq K-1 u rs = U(B) T K-1 U(B),

Lemma 4 .

 4 Let X = R d , ρ be the Lebesgue measure on R d and ∀x, x ∈ R d , k(x, x ) = e -x-x 2 2 + xq 2 + xr 2 -1 3 xp+xq+xr 2 . Proof. Let p, q ∈ [m]. Since x -x p 2 + x -x p 2 = 2 x -

  , x p )k(x, x q )k(x, x r )dx =

Note that the weaker assumption x∈X k(x, x)

dρ(x) < ∞ would be enough.

Acknowledgments

This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001(PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grants SEQUOIA 724063 and REAL 947908), and support by grants from Région Ile-de-France.

points are used as support points x1 , ..., xm , and minimize eq. ( 16) using the Gaussian kernel. In Section 4 and fig. 2b, we fix m = 50 and we illustrate the effect of bandwidth v.s. trace regularization, while in Figure 2c we show the impact of varying the support size m. The code to reproduce these figures is available at https://github.com/BorisMuzellec/kernel-SoS-distributions.

Conclusion and future work

In this note, we proposed to represent smooth probability distributions using kernel sums-of-squares as a way to address the intractability of optimizing distributions in the MMD geometry. We showed that this representation is dense for the weak topology, and can therefore be used to approximate arbitrarily well the solution of such problems on the whole space of probability measures. Finally, we provided efficient algorithms to fit kernel sum-of-squares densities. We leave to future work the application of this model to more complex tasks, such as distributionally robust optimization.

A Appendix

A.1 Proof of Lemma 1

Proof. By definition it holds ∀x ∈ X , p A (x) ≥ 0. Hence, p A is a density if and only if X p A (x)dρ(x) = 1. We have

where •, • HS denotes the Hilbert-Schmidt inner product, and the operator

A.2 Proof of Theorem 1

Proof. We consider w.l.o.g. the case where ρ is the Lebesgue measure on X . Since AC(X ) is dense in P(X ) for the weak topology, it suffices to show that absolutely continuous probability measures with densities in F ρ are dense in AC(X ).

Let µ ∈ AC(X ) with density function f . By compacity of X , using Proposition 1 we may construct a sequence (A n ) n∈N ∈ S + (H) N with finite trace such that p An converges to f almost-everywhere. Further, since f is a density function, we may assume w.l.o.g. that ∀n ∈ N, TrA n Σ ρ = 1. By Scheffé's lemma [START_REF] Scheffé | A useful convergence theorem for probability distributions[END_REF],