Vivien Cabannes

Francis Bach

Alessandro Rudi

Disambiguation of Weak Supervision leading to Exponential Convergence rates

Machine learning approached through supervised learning requires expensive annotation of data. This motivates weakly supervised learning, where data are annotated with incomplete yet discriminative information. In this paper, we focus on partial labelling, an instance of weak supervision where, from a given input, we are given a set of potential targets. We review a disambiguation principle to recover full supervision from weak supervision, and propose an empirical disambiguation algorithm. We prove exponential convergence rates of our algorithm under classical learnability assumptions, and we illustrate the usefulness of our method on practical examples.

Introduction

In many applications of machine learning, such as recommender systems, where an input 𝑥 characterizing a user should be matched with a target 𝑦 representing an ordering of a large number 𝑚 of items, accessing fully supervised data (𝑥, 𝑦) is not an option. Instead, one should expect weak information on the target 𝑦, which could be a list of previously taken (if items are online courses), watched (if items are plays), etc., items by a user characterized by the feature vector 𝑥. This motivates weakly supervised learning, aiming at learning a mapping from inputs to targets in such a setting where tools from supervised learning can not be applied off-the-shelves.

Recent applications of weakly supervised learning showcase impressive results in solving complex tasks such as action retrieval on instructional videos [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF], image semantic segmentation [START_REF] Papandreou | Weakly-and semi-supervised learning of a deep convolutional network for semantic image segmentation[END_REF], salient object detection [START_REF] Wang | Learning to detect salient objects with image-level supervision[END_REF], 3D pose estimation [START_REF] Dabral | Learning 3D human pose from structure and motion[END_REF], text-to-speech synthesis [START_REF] Jia | Transfer learning from speaker verification to multispeaker text-to-speech synthesis[END_REF], to name a few. However, those applications of weakly supervised learning are usually based on clever heuristics, and theoretical foundations of learning from weakly supervised data are scarce, especially when compared to statistical learning literature on supervised learning [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF][START_REF] Boucheron | Theory of classification: a survey of some recent advances[END_REF][START_REF] Steinwart | Support vector machines[END_REF]. We aim to provide a step in this direction.

In this paper, we focus on partial labelling, a popular instance of weak supervision, approached with a structured prediction point of view [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF]. We detail this setup in Section 2. Our contributions are organized as follows.

• In Section 3, we introduce a disambiguation algorithm to retrieve fully supervised samples from weakly supervised ones, before applying off-the-shelf supervised learning algorithms to the completed dataset. • In Section 4, we prove exponential convergence rates of our algorithm, in term of the fully supervised excess of risk, given classical learnability assumptions. • In Section 5, we explain why disambiguation algorithms are intrinsically non-convex, and provide guidelines based on well-grounded heuristics to implement our algorithm.

We end this paper with a review of literature in Section 6, before showcasing the usefulness of our method on practical examples in Section 7, and opening on perspectives in Section 8.

Disambiguation of Partial Labelling

In this section, we review the supervised learning setup, introduce the partial labelling problem along with a principle to tackle this instance of weak supervision.

Algorithms can be formalized as mapping an input 𝑥 to a desired output 𝑦, respectively belonging to an input space X and an output space Y. Machine learning consists in automating the design of the mapping 𝑓 : X → Y, based on a joint distribution 𝜇 ∈ Δ X ×Y over input/output pairings (𝑥, 𝑦) and a loss function ℓ : Y × Y → R, measuring the error cost of outputting 𝑓 (𝑥) when one should have output 𝑦. The optimal mapping is defined as satisfying

𝑓 * ∈ arg min 𝑓 :X →Y E ( 𝑋,𝑌 )∼𝜇 [ℓ( 𝑓 (𝑋), 𝑌 )] . (1)
In supervised learning, it is assumed that one does not have access to the full distribution 𝜇, but only to independent samples (𝑋 𝑖 , 𝑌 𝑖 ) 𝑖 ≤𝑛 ∼ 𝜇 ⊗𝑛 . In practice, accessing such samples means building a dataset of examples. While input data (𝑥 𝑖 ) are usually easily accessible, getting output pairings (𝑦 𝑖 ) generally requires careful annotation, which is both time-consuming and expensive. For example, in image classification, (𝑥 𝑖 ) can be collected by scrapping images over the Internet. Subsequently a "data labeller" might be ask to recognize a rare feline 𝑦 𝑖 on an image 𝑥 𝑖 . While getting 𝑦 𝑖 will be hard in this setting, recognizing that it is a feline and describing elements of color and shape is easy, and already helps to determine what outputs 𝑓 (𝑥 𝑖 ) are acceptable. A second example is given when pooling a known population (𝑥 𝑖 ) to get estimation of their political orientation (𝑦 𝑖 ), one might get information from recent election of percentage of voters across the political landscape, leading to global constraints that (𝑦 𝑖 ) should verify. A supervision that gives information on (𝑦 𝑖 ) 𝑖 ≤𝑛 without giving its precise value is called weak supervision.

Partial labelling, also known as "superset learning", is an instance of weak supervision, in which, for an input 𝑥, we do not access the precise label 𝑦 but only a set 𝑠 of potential labels, 𝑦 ∈ 𝑠 ⊂ Y. For example, on a caracal image 𝑥, one might not get the label "caracal" 𝑦, but the set 𝑠 "feline", containing all the labels 𝑦 corresponding to felines. It is modelled through a distribution 𝜈 ∈ Δ X ×2 Y over X × 2 Y generating samples (𝑋, 𝑆), which should be compatible with the fully supervised distribution 𝜇 ∈ Δ X ×Y as formalized by the following definition.

Definition 1 (Compatibility, [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF]). A fully supervised distribution 𝜇 ∈ Δ X ×Y is compatible with a weakly supervised distribution 𝜈 ∈ Δ X ×Y , denoted by 𝜇 𝜈 if there exists an underlying distribution 𝜋 ∈ Δ X ×Y×2 Y , such that 𝜇, and 𝜈, are the respective marginal distributions of 𝜋 over X × Y and X × 2 Y , and such that 𝑦 ∈ 𝑠 for any tuple (𝑥, 𝑦, 𝑠) in the support of 𝜋 (or equivalently 𝜋| 𝑠 ∈ Δ 𝑠 , with 𝜋| 𝑠 denoting the conditional distribution of 𝜋 given 𝑠).

This definition means that a weakly supervised sample (𝑋, 𝑆) ∼ 𝜈 can be thought as proceeding from a fully supervised sample (𝑋, 𝑌 ) ∼ 𝜇 after loosing information on 𝑌 according to the sampling of 𝑆 ∼ 𝜋| 𝑋,𝑌 . The goal of partial labelling is still to learn 𝑓 * from Eq. ( 1), yet without accessing a fully supervised distribution 𝜇 ∈ Δ X ×Y but only the weakly supervised distribution 𝜈 ∈ Δ X ×2 Y . As such, this is an ill-posed problem, since 𝜈 does not discriminate between all 𝜇 compatible with it. Following lex parsimoniae, [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF] have suggested to look for 𝜇 such that the labels are the most deterministic function of the inputs, which they measure with a loss-based "variance", leading to the disambiguation

𝜇 * ∈ arg min 𝜇 𝜈 inf 𝑓 :X →Y E ( 𝑋,𝑌 )∼𝜇 [ℓ( 𝑓 (𝑋), 𝑌 )] , (2)
and to the definition of the optimal mapping 𝑓 * : X → Y 𝑓 * ∈ arg min

𝑓 :X →Y E ( 𝑋,𝑌 )∼𝜇 * [ℓ( 𝑓 (𝑋), 𝑌 )] . (3)
This principle is motivated by Theorem 1 of [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF] showing that 𝑓 * in Eq. ( 3) is characterized by 𝑓 * ∈ arg min 𝑓 :X →Y E ( 𝑋,𝑆)∼𝜈 inf 𝑦 ∈𝑆 ℓ( 𝑓 (𝑋), 𝑦) , matching a prior formulation based on infimum loss [START_REF] Cour | Learning from partial labels[END_REF][START_REF] Luo | Learning from candidate labeling sets[END_REF][START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization[END_REF]. In practice, it means that if (𝑆|𝑋 = 𝑥) has probability 50% to be the set "feline" and 50% the set "orange with black stripes", (𝑌 |𝑋 = 𝑥) should be considered as 100% "tiger", rather than 20% "cat", 30% "lion" and 50% "orange car with black stripes", which could also explain (𝑆|𝑋 = 𝑥). In other terms, Eq. ( 2) creates consensus between the different information provided on a label. Similarly to supervised learning, partial labelling consists in retrieving 𝑓 * without accessing 𝜈 but only samples (𝑋 𝑖 , 𝑆 𝑖 ) 𝑖 ≤𝑛 ∼ 𝜈 ⊗𝑛 .

Remark 2 (Measure of determinism). Eq. ( 2) is not the only variational way to push towards distribution where labels are deterministic function of the inputs. For example, one could minimize entropy (e.g., [START_REF] Berthelot | Mixmatch: A holistic approach to semi-supervised learning[END_REF][START_REF] Lienen | From label smoothing to label relaxation[END_REF]. However, a loss-based principle is appreciable since the loss usually encodes structures of the output space [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF], which will allow sample and computational complexity of consequent algorithms to scale with an intrinsic dimension of the space rather than the real one, e.g., 𝑚 rather than 𝑚! when Y = S 𝑚 and ℓ is a suitable ranking loss (see Section 5.4 or [START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF].

Learning Algorithm

In this section, given weakly supervised samples, we present a disambiguation algorithm to retrieve fully supervised samples based on an empirical expression of Eq. ( 2), before learning a mapping from X to Y based on those fully supervised samples, according to Eq. (3).

Given a partially labelled dataset D 𝑛 = (𝑥 𝑖 , 𝑠 𝑖 ) 𝑖 ≤𝑛 , sampled accordingly to 𝜈 ⊗𝑛 , we retrieve fully supervised samples, based on the following empirical version of Eq. ( 2), with

𝐶 𝑛 = 𝑖 ≤𝑛 𝑠 𝑖 ⊂ Y 𝑛 ( ŷ𝑖 ) 𝑖 ≤𝑛 ∈ arg min (𝑦 𝑖 ) 𝑖≤𝑛 ∈𝐶 𝑛 inf (𝑧 𝑖 ) 𝑖≤𝑛 ∈Y 𝑛 𝑛 ∑ 𝑖, 𝑗=1 𝛼 𝑗 (𝑥 𝑖 )ℓ(𝑧 𝑖 , 𝑦 𝑗 ), (4)
where (𝛼 𝑖 (𝑥)) 𝑖 ≤𝑛 is a set of weights measuring how much one should base its prediction for 𝑥 on the observations made at 𝑥 𝑖 . This formulation is motivated by the Bayes approximate rule proposed by [START_REF] Stone | Consistent nonparametric regression[END_REF], which can be seen as the approximation of 𝜇 by 𝑛 -1 𝑛 𝑖, 𝑗=1 𝛼 𝑗 (𝑥 𝑖 )𝛿 𝑥 𝑖 ⊗ 𝛿 𝑦 𝑗 in Eq. ( 2). In essence, 𝑧 𝑖 (which corresponds to 𝑓 (𝑥 𝑖 )) is likely to be 𝑦 𝑖 , although Eq. ( 4) allows for flexibility to avoid rigid interpolation. As such Eq. ( 4) should be understood as constraining 𝑦 𝑖 ∈ 𝑠 𝑖 to be similar to 𝑦 𝑗 ∈ 𝑠 𝑗 if 𝑥 𝑖 and 𝑥 𝑗 are close, with the measure of similarity defined by 𝛼 𝑖 (𝑥 𝑗 ).

Once fully supervised samples (𝑥 𝑖 , ŷ𝑖 ) have been recollected, one can learn 𝑓 𝑛 : X → Y, approximating 𝑓 * , with classical supervised learning techniques. In this work, we will consider the structured prediction estimator introduced by [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF], defined as

𝑓 𝑛 (𝑥) ∈ arg min 𝑧 ∈Y 𝑛 ∑ 𝑖=1 𝛼 𝑖 (𝑥)ℓ(𝑧, ŷ𝑖 ).
(5)

Weighting scheme 𝛼. For the weighting scheme 𝛼, several choices are appealing. Laplacian diffusion is one of them as it incorporates a prior on low density separation to boost learning [START_REF] Zhu | Semi-supervised learning using Gaussian fields and harmonic functions[END_REF][START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Bengio | Label propagation and quadratic criterion[END_REF][START_REF] Hein | Graph Laplacians and their convergence on random neighborhood graphs[END_REF]. Kernel ridge regression is another due to its theoretical guarantees [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF].

In the theoretical analysis, we will use nearest neighbors. Assuming X is endowed with a distance 𝑑, and assuming, for readability sake, that ties to define nearest neighbors do not happen, it is defined as

𝛼 𝑖 (𝑥) = 𝑘 -1 if 𝑛 𝑗=1 1 𝑑 (𝑥,𝑥 𝑗 ) ≤𝑑 (𝑥,𝑥 𝑖 ) ≤ 𝑘 0 otherwise,
where 𝑘 is a parameter fixing the number of neighbors. Our analysis, leading to Theorem 4, also holds for other local averaging methods such as partitioning or Nadaraya-Watson estimators.

Consistency Result

In this section, we assume Y finite, and prove the convergence of 𝑓 𝑛 towards 𝑓 * as 𝑛, the number of samples, grows to infinity. To derive such a consistency result, we introduce a surrogate problem that we relate to the risk through a calibration inequality. We later assume that weights are given by nearest neighbors and review classical assumptions, that we work to derive exponential convergence rates.

In the following, we are interested in bounding the expected generalization error, defined as

E ( 𝑓 𝑛 ) = E D 𝑛 R( 𝑓 𝑛 ) -R( 𝑓 * ), (6)
where

R( 𝑓 ) = E ( 𝑋,𝑌 )∼𝜇 * [ℓ( 𝑓 (𝑋), 𝑌 )]
, by a quantity that goes to zero, when 𝑛 goes to infinity. This implies convergence in probability (the randomness being inherited from D 𝑛 ) of R( 𝑓 𝑛 ) towards inf 𝑓 :X →Y R( 𝑓 ), which is referred as consistency of the learning algorithm. We first introduce a few objects.

Disambiguation ground truth (𝑦

which explains the wording of plug-in estimator [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF]. We now introduce a calibration inequality, that relates the error between 𝑓 𝑛 and 𝑓 * with surrogate error quantities.

Lemma 3 (Calibration inequality). When Y is finite, and the labels are a deterministic function of the input, i.e., when 𝜇 * | 𝑥 is a Dirac for all 𝑥 ∈ supp 𝜈 X , for any weighting scheme that sums to one, i.e., 𝑛 𝑖=1 𝛼 𝑖 (𝑥) = 1 for all 𝑥 ∈ supp 𝜈 X ,

R( 𝑓 𝑛 ) -R( 𝑓 * ) ≤ 4𝑐 𝜓 𝑔 * 𝑛 -𝑔 𝑛 𝐿 1 + 8𝑐 𝜓 𝑐 𝜑 P 𝑋 𝑔 * 𝑛 (𝑋) -𝑔 * (𝑋) > 𝛿 , ( 10
)
with 𝑐 𝜓 = sup 𝑧 ∈Y 𝜓(𝑧) , 𝑐 𝜑 = sup 𝑧 ∈Y 𝜑(𝑦) , and 𝛿 a parameter that depend on the geometry of ℓ and its decomposition through 𝜑.

This lemma, proven in Appendix A.1, separates a part reading in 𝑔 𝑛 -𝑔 * 𝑛 , due to the disambiguation error between ( ŷ𝑖 ) and (𝑦 * 𝑖 ) together with the stability of the learning algorithm when substituting ( ŷ𝑖 ) for (𝑦 * 𝑖 ), and a part in 𝑔 * 𝑛 -𝑔 * due to the consistency of the fully supervised learning algorithm. The expression of the first part relates to Theorem 7 in [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF] while the second part relates to Theorem 6 in [START_REF] Cabannes | Fast rates in structured prediction[END_REF].

Classical learnability assumptions

In the following, we suppose that the weights 𝛼 are given by nearest neighbors, that X is a compact metric space endowed with a distance 𝑑, that Y is finite and that ℓ is proper in the sense that it strictly positive except on the diagonal of Y × Y diagonal where it is zero. We now review classical assumptions to prove consistency. First, assume that 𝜈 X is regular in the following sense. Assumption 1 (𝜈 X well-behaved). Assume that 𝜈 X is such that there exists ℎ 1 , 𝑐 𝜇 , 𝑞 > 0 satisfying, with B designing balls in X ,

∀ 𝑥 ∈ supp 𝜈 X , ∀ 𝑟 < ℎ 1 , 𝜈 X (B(𝑥, 𝑟)) > 𝑐 𝜇 𝑟 𝑞 .
Assumption 1 is useful to make sure that neighbors in D 𝑛 are closed with respect to the distance 𝑑, it is usually derived by assuming that X is a subset of R 𝑞 ; that 𝜈 X has a density 𝑝 against the Lebesgue measure 𝜆 with minimal mass 𝑝 min in the sense that for any 𝑥 ∈ supp 𝜈 X , 𝑝(𝑥) > 𝑝 min ; and that supp 𝜈 X has regular boundary in the sense that 𝜆(B(𝑥, 𝑟) ∩ supp 𝜈 X ) ≥ 𝑐𝜆(B(𝑥, 𝑟) for any 𝑥 ∈ supp 𝜈 X and 𝑟 < ℎ (e.g., [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF].

We now switch to a classical assumption in partial labelling, allowing for population disambiguation. It should be noted that regularity of 𝑔 * , Assumption 3, together with determinism of 𝜇 * | 𝑥 inherited from Assumption 2 implies that classes X 𝑦 = {𝑥 | 𝑓 * (𝑥) = 𝑦} are separated in X , in the sense that there exists ℎ 2 > 0, such that for any 𝑦, 𝑦 ∈ Y and (𝑥, 𝑥 ) ∈ X 𝑦 × X 𝑦 , 𝑑 (𝑥, 𝑥 ) > ℎ 2 , which is a classical assumption to derive consistency of semi-supervised learning algorithm (e.g., [START_REF] Rigollet | Generalization error bounds in semi-supervised classification under the cluster assumption[END_REF].

Those implications results from the fact that separation in Y (hard Tsybakov condition) plus Lipschitzness of 𝑔 * implies separation of classes in X , as we details in Appendix A.2.

Exponential convergence rates

We are now ready to state our convergence result. We introduce ℎ = min(ℎ 1 , ℎ 2 ) and 𝑝 = 𝑐 𝜇 ℎ 𝑞 , so that for any 𝑥 ∈ supp 𝜈 X , 𝜈 X (B(𝑥, ℎ)) > 𝑝.

Theorem 4 (Exponential convergence rates). When the weights 𝛼 are given by nearest neighbors, under Assumptions 1, 2 and 3, the excess of risk in Eq. ( 6) is bounded by

E ( 𝑓 𝑛 ) ≤ 8𝑐 𝜓 𝑐 𝜑 (𝑛 + 1) exp - 𝑛𝑝 16 + 8𝑐 𝜓 𝑐 𝜑 𝑚 exp (-𝑘 |log(𝜂)|) , (11) as soon as 𝑘 < 𝑛𝑝/4, with 𝑚 = #Y. By taking 𝑘 𝑛 = 𝑘 0 𝑛, for 𝑘 0 < 𝑝/4, this implies exponential convergence rates E ( 𝑓 𝑛 ) = 𝑂 (𝑛 exp(-𝑛)).
Sketch for Theorem 4. In essence, based on Lemma 3, Theorem 4 can be understood as two folds.

• A fully supervised error between 𝑔 * 𝑛 and 𝑔 * . This error can be controlled in exp(-𝑛𝑝) as the non-ambiguity assumption implies a hard Tsybakov margin condition, a setting in which the fully supervised estimate 𝑔 * 𝑛 is known to converge to the population solution 𝑔 * with such rates [START_REF] Cabannes | Fast rates in structured prediction[END_REF].

• A weakly disambiguation error, that is exponential too, since, based on Assumption 2, disambiguating between 𝑧 ∈ Y and 𝑦 𝑥 from 𝑘 sets 𝑆 sampled accordingly to 𝜈| 𝑥 can be done in 𝜂 𝑘 , and disambiguating between all 𝑧 ≠ 𝑦 𝑥 and 𝑦 𝑥 in 𝑚𝜂 𝑘 = 𝑚 exp(-𝑘 |log(𝜂)|).

Appendix A.3 provides details.

Theorem 4 states that under a non-ambiguity assumption and a regularity assumption implying no-density separation, one can expect exponential convergence rates of 𝑓 𝑛 learned with weakly supervised data to 𝑓 * the solution of the fully supervised learning problem, measured with excess of fully supervised risk. Because of the exponential convergence, we could derive polynomial convergence rates for a broader class of problems that are approximated by problems satisfying assumptions of Theorem 4. The derived rates in 𝑛 exp(-𝑛) should be compared with rates in 𝑛 -1/2 and 𝑛 -1/4 , respectively derived, under the same assumptions, by [START_REF] Cour | Learning from partial labels[END_REF][START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF].

Discussion on Assumptions

While we have retaken classical assumptions from literature, those assumptions are quite strong, which allows us, by understanding their strength, to derive exponential convergence rates. Assumptions 1 and 3 are classical in the nearest neighbor literature with full supervision. If we were using (reproducing) kernel methods to define the weighting scheme 𝛼, those assumptions would be mainly replaced with "𝑔 * belonging to the RKHS". Assumption 2 is the strongest assumption in our view, that we will now discuss.

How to check it in practice ? First, for Assumption 2 to hold, the labels have to be a deterministic function of the inputs. In other words, a zero error is achievable. Finally, Assumption 2 is related to dataset collection. If dealing with images, weak supervision could take the form of some information on shape, color, or texture, etc., Assumption 2 supposes that the weak information potentially given on a specific image 𝑥, allows to retrieve the unique label 𝑦 of the image (e.g., a "pig" could be recognized from its shape and its color). This is a reasonable assumption, if, for a given 𝑥, we ask at random a data labeller to provide us information on shape, color, or texture, etc. However, it will not be the case, if for some reasons (e.g. the dataset is built from several weakly annotated datasets), in some regions of the input space, we only get shape information, and in other regions, we only get color information. In particular, it is not verified for semi-supervised learning when the support of the unlabelled data distribution is not the same as the support of the labelled input data distribution.

How to relax it and what results to expect?

Previous works used Assumption 2 to derive a calibration inequality between the infimum loss to the original loss (e.g., see Proposition 2 by [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF]. In contrast, we relate the surrogate and original problem through a refined calibration inequality (10). This technical progress allows us to derive exponential convergence rates similarly to the work of [START_REF] Cabannes | Fast rates in structured prediction[END_REF]. Importantly, in comparison with previous work, our calibration inequality Lemma 3 can easily be extended without the determinism assumption provided by Assumption 2. Essentially, in our work, Assumption 2 is used to simplify the study of ( ŷ𝑖 ) 𝑖 ≤𝑛 given by the disambiguation algorithm (4), and therefore the study of the disambiguation error in Eq. ( 10). The study of ( ŷ𝑖 ) 𝑖 ≤𝑛 without Assumption 2 would requires other tools than the one presented in this paper. It could be studied in the realm of graphical model and message passing algorithm, or with Wasserstein distance and topological considerations on measures. With much milder forms of Assumption 2, we expect the rates to degrade smoothly with respect to a parameter defining the hardness of the problem, similarly to the works of [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]; [START_REF] Cabannes | Fast rates in structured prediction[END_REF].

Optimizaton Considerations

In this section, we focus on implementations to solve Eq. ( 4). We explain why disambiguation objectives, such as Eq. ( 2) are intrinsically non-convex and express a heuristic strategy to solve Eq. ( 4) besides non-convexity in classical wellbehaved instances of partial labelling. Note that we do not study implementations to solve Eq. ( 5) as this study has already been done by [START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF]. We end this section by considering a practical example to make derivations more concrete.

Non-convexity of disambiguation objectives

For readability, suppose that X is a singleton, justifying to remove the dependency on the input in the following. Con-

sider 𝜈 ∈ Δ 2 Y a distribution modelling weak supervision. While the domain {𝜇 ∈ Δ Y | 𝜇 𝜈} is convex, a disambigua- tion objective E : Δ Y → R defining 𝜇 * ∈ arg min 𝜇 𝜈 E (𝜇),
similarly to Eq. ( 2), that is minimized for deterministic distributions, which correspond to 𝜇 a Dirac, i.e., minimized on vertices of its definition domain Δ Y , can not be convex.

In other terms, any disambiguation objective that pushes toward distributions where targets are deterministic function of the input, as mentioned in Remark 2, can not be convex.

Indeed, smooth disambiguation objectives such as entropy and our piecewise linear loss-based principle (2), reading pointwise

E (𝜇) = inf 𝑧 ∈Y E 𝑌 ∼𝜇 [ℓ(𝑧, 𝑌 )], are concave. Sim- ilarly, its quadratic variant E (𝜇) = E 𝑌 ,𝑌 ∼𝜇 [ℓ(𝑌 , 𝑌 )]
, is concave as soon as (ℓ(𝑦, 𝑦 )) 𝑦,𝑦 ∈Y is semi-definite negative. We illustrate those considerations on a concrete example with graphical illustration in Appendix C. We should see how this translates on generic implementations to solve the empirical objective (4).

Generic implementation for Eq. (4)

Depending on ℓ and on the type of observed set (𝑠 𝑖 ), Eq. ( 4) might be easy to solve. In the following, however, we will introduce optimization considerations to solve it in a generic structured prediction fashion. To do so, we recall the decomposition of ℓ (7) and rewrite Eq. ( 4) as

( ŷ𝑖 ) 𝑖 ≤𝑛 ∈ arg min (𝑦 𝑖 ) ∈𝐶 𝑛 inf (𝑧 𝑖 ) ∈Y 𝑛 𝑛 ∑ 𝑖, 𝑗=1
𝛼 𝑗 (𝑥 𝑖 )𝜓(𝑧 𝑖 ) 𝜑(𝑦 𝑗 ).

Since, given (𝑦 𝑗 ), the objective is linear in 𝜓(𝑧 𝑗 ), the constraint 𝜓(𝑧 𝑗 ) ∈ 𝜓(Y) can be relaxed with 𝜁 𝑖 ∈ Conv 𝜓(Y).

Similarly, with respect to 𝜑(𝑦 𝑗 ), this objective is the infimum of linear functions, therefore is concave, and the constraint 𝜑(𝑦 𝑗 ) ∈ 𝜑(𝑠 𝑗 ), could be relaxed with 𝜉 𝑖 ∈ Conv 𝜑(𝑠 𝑗 ).

Hence, with H 0 = Conv 𝜓(Y) and Γ 𝑛 = 𝑗 ≤𝑛 Conv 𝜑(𝑠 𝑗 ), the optimization is cast as

( ξ𝑖 ) 𝑖 ≤𝑛 ∈ arg min (𝜉 𝑖 ) ∈Γ 𝑛 inf (𝜁 𝑖 ) ∈H 𝑛 0 𝑛 ∑ 𝑖, 𝑗=1 𝛼 𝑗 (𝑥 𝑖 )𝜁 𝑖 𝜉 𝑗 . ( 12
)
Because of concavity, ( ξ𝑖 ) will be an extreme point of Γ 𝑛 , that could be decoded into ŷ𝑖 = 𝜑 -1 ( ξ𝑖 ). However, it should be noted that if only interested in 𝑓 𝑛 and not in the disambiguation ( ŷ𝑖 ), this decoding can be avoided, since Eq. ( 5) can be rewritten as 𝑓 𝑛 (𝑥) ∈ arg min 𝑧 ∈Y 𝜓(𝑧) 𝑛 𝑖=1 𝛼 𝑖 (𝑥) ξ𝑖 .

Alternative minimization with good initialization

To solve Eq. ( 12), we suggest to use an alternative minimization scheme. The output of such an scheme is highly dependent to the variable initialization. In the following, we introduce well-behaved problem, where (𝜉 𝑖 ) 𝑖 ≤𝑛 can be initialized smartly, leading to an efficient implementation to solve Eq. ( 12). We provide a real-world example of a well-behaved problem in Section 5.4 as well as a synthetic example with graphical illustration in Appendix C. On those problems, we suggest to solve Eq. ( 12) by considering the initialization

𝜉 (0) 𝑖 = E 𝑌 ∼𝜇 𝑠 𝑖 [𝜑(𝑌 )],
and performing alternative minimization of Eq. ( 12), until attaining 𝜉 (∞) as the limit of the alternative minimization scheme (which exists since each step decreases the value of the objective in Eq. ( 12) and there is a finite number of candidates for (𝜉 𝑖 )). It corresponds to a disambiguation guess ỹ𝑖 = 𝜑 -1 (𝜉 (∞)

𝑖

). Then we suggest to learn f𝑛 from (𝑥 𝑖 , ỹ𝑖 ) based on Eq. ( 5), and existing algorithmic tools for this problem [START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF]. To assert the well-groundedness of this heuristic, we refer to the following proposition, proven in Appendix A.4. Proposition 6. Under the non-ambiguity hypothesis, Assumption 2, the solution of Eq. (3) is characterized by

𝑓 * ∈ arg min 𝑓 :X →Y E ( 𝑋,𝑆)∼𝜈 E 𝑌 ∼𝜇 𝑆 [ℓ( 𝑓 (𝑋), 𝑌 )] . More- over, if the surrogate function 𝑔 • 𝑛 : X → H defined as 𝑔 • 𝑛 (𝑥) = 𝑛 𝑖=1 𝛼 𝑖 (𝑥)𝜉 𝑠 𝑖 , with 𝜉 𝑠 = E 𝑌 ∼𝜇 𝑠 [𝜑(𝑌 )], converges towards 𝑔 • (𝑥) = E 𝑆∼𝜈 | 𝑥 [𝜉 𝑆 ] in 𝐿 1 , 𝑓 •
𝑛 defined through the decoding Eq. (9) converges in risk towards 𝑓 * .

The minimization pushes towards extreme points of the definition domain.

Given that our algorithm scheme is initialized for 𝜉 (0) 𝑖 = 𝜉 𝑠 𝑖 and 𝜁 (0) 𝑖 = 𝑓 • 𝑛 (𝑥 𝑖 ) and stopped once having attained 𝜉 (∞)

𝑖

and 𝜁 (∞) 𝑖 = f𝑛 (𝑥 𝑖 ), f𝑛 is arguably better than 𝑓 • 𝑛 , which given consistency result exposed in Proposition 6, is already good enough.

Remark 7 (IQP implementation for Eq. ( 4)). Other heuristics to solve Eq. (4) are conceivable. For example, considering 𝑧 𝑖 = 𝑦 𝑖 in this equation, we remark that the resulting problem is isomorphic to an integer quadratic program (IQP). Similarly to integer linear programming, this problem can be approached with relaxation of the "integer constraint" to get a real-valued solution, before "thresholding" it to recover an integer solution. This heuristic can be seen as a generalization of the Diffrac algorithm [START_REF] Bach | DIFFRAC: a discriminative and flexible framework for clustering[END_REF][START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF]. we present it in details in Appendix B.

Remark 8 (Link with EM, [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]). Arguably, our alternative minimization scheme, optimizing respectively the targets 𝜉 𝑖 = 𝜑(𝑦 𝑖 ) and the function estimates 𝜁 𝑖 = 𝜓( 𝑓 𝑛 (𝑥 𝑖 )) can be seen as the non-parametric version of the Expectation-Maximization algorithm, popular for parametric model [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF].

Application: Ranking with partial ordering

Ranking is a problem consisting, for an input 𝑥 in an input space X , to learn a total ordering 𝑦, belonging to Y = S 𝑚 , modelling preference over 𝑚 items. It is usually approach with the Kendall loss ℓ(𝑦, 𝑧) = -𝜑(𝑦) 𝜑(𝑧), with 𝜑(𝑦) = (sign (𝑦(𝑖) -𝑦( 𝑗))) 𝑖, 𝑗 ≤𝑚 ∈ {-1, 1} 𝑚 2 [START_REF] Kendall | A new measure of rank correlation[END_REF]. Full supervision corresponds, for a given 𝑥, to be given a total ordering of the 𝑚 items. This is usually not an option, but one could expect to be given partial ordering that 𝑦 should follow [START_REF] Cao | Learning to rank: from pairwise approach to listwise approach[END_REF][START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF][START_REF] Korba | A structured prediction approach for label ranking[END_REF]. Formally, this equates to the observation of some, but not all, coordinates 𝜑(𝑦) 𝑖 of the vector 𝜑(𝑦) for some 𝑖 ∈ 𝐼 ⊂ 1, 𝑚 2 .

In this setting, 𝑠 ⊂ Y is a set of total orderings that match the given partial ordering. It can be represented by a vector 𝜉 𝑠 ∈ H, that satisfies the partial ordering observation, (𝜉 𝑠 ) 𝐼 = 𝜑(𝑦) 𝐼 , and that is agnostic on unobserved coordinates, (𝜉 𝑠 )𝑐 𝐼 = 0. This vector satisfies that 𝑧 → 𝜓(𝑧) 𝜉 𝑠 is minimized for, and only for, 𝑧 ∈ 𝑠. Hence, it constitutes a good initialization for the alternative minimization scheme detailed above. We provide details in Appendix A.5, where we also show that 𝜉 𝑠 can be formally translated in a 𝜇 𝑠 to match the Definition 5, proving that ranking with partial labelling is a well-behaved problem.

Many real world problems can be formalized as a ranking problem with partial ordering observations. For example, 𝑥 could be a social network user, and the 𝑚 items could be posts of her connection that the network would like to order 13) shown in green, with our Disambiguation Framework (DF), Eqs. ( 4) and ( 5), shown in orange; with weights 𝛼 given by kernel ridge regression. (DF) retrieves ŷ𝑖 before learning a smooth 𝑓 𝑛 based on (𝑥 𝑖 , ŷ𝑖 ), while (IL) implicitly retrieves ŷ𝑖 (𝑥) differently for each input, leading to irregularity of the consequent estimator of 𝑓 * . on her feed accordingly to her preferences. One might be told that the user 𝑥 prefer posts from her close rather than from her distant connections, which translates formally as the constraint that for any 𝑖 corresponding to a post of a close connection and 𝑗 corresponding to a post of a distant connection, we have 𝜑(𝑦) 𝑖 𝑗 = 1. Nonetheless, designing non-parametric structured prediction models that scale well when the intrinsic dimension 𝑚 of the space Y is very large (such as the number of post on a social network) remains an open problem, that this paper does not tackle.

Related work

Weakly supervised learning has been approached through parametric and non-parametric methods. Parametric models are usually optimized through maximum likelihood [START_REF] Heitjan | Ignorability and coarse data[END_REF][START_REF] Ghahramani | Learning with multiple labels[END_REF]. [START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization[END_REF] show that this approach, as formalized by [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF], equates to disambiguating sets by averaging candidates, which was shown inconsistent by [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF] when data are not missing at random. Among nonparametric models, [START_REF] Xu | Maximum margin clustering[END_REF]; [START_REF] Bach | DIFFRAC: a discriminative and flexible framework for clustering[END_REF] developed an algorithm for clustering, that has been cast for weakly supervised learning problem [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF][START_REF] Alayrac | Unsupervised learning from narrated instruction videos[END_REF], leading to a disambiguation algorithm similar than ours, yet without consistency results. More recently, half-way between theory and practice, [START_REF] Gong | A regularization approach for instance-based superset label learning[END_REF] The non-ambiguity assumption has been introduced by [START_REF] Cour | Learning from partial labels[END_REF] and is a classical assumption of learning with partial labelling [START_REF] Liu | Learnability of the superset label learning problem[END_REF]. Assumptions of Lipschitzness and minimal mass are classical assumptions to prove convergence of local averaging method [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF][START_REF] Biau | Lectures on the Nearest Neighbor Method[END_REF]. Those assumptions imply class separation in X , which has been leverage in semi-supervised learning, justifying Laplacian regularization [START_REF] Rigollet | Generalization error bounds in semi-supervised classification under the cluster assumption[END_REF][START_REF] Zhu | Semi-supervised learning using Gaussian fields and harmonic functions[END_REF].

Note that those assumptions might not hold on raw representation of the data, but with appropriate metrics, which could be learned through unsupervised [START_REF] Duda | Pattern Classification[END_REF] or self-supervised learning [START_REF] Doersch | Multi-task self-supervised visual learning[END_REF]. Indeed, [START_REF] Wei | Theoretical analysis of self-training with deep networks on unlabeled data[END_REF] provide an analysis akin ours based on such an assumption. As such, the practitioner might consider weights 𝛼 given by similarity metrics derived through such techniques, before computing the disambiguation (4) and learning 𝑓 𝑛 from the recollected fully supervised dataset with deep learning.

Experiments

In this section, we review a baseline, and experiments that showcase the usefulness of our algorithm Eqs. ( 4) and (5).

Baseline. We consider as a baseline the work of [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF], which is a consistent structured prediction approach to partial labelling through the infimum loss. Testing errors as function of the supervision corruption on real dataset corresponding to classification with partial labels. We split fully supervised LIBSVM datasets into training and testing dataset. We corrupt training data in order to get partial labels. Corruption is managed through a parameter, represented by the 𝑥-axis, that relates to the ambiguity degree 𝜂 of Assumption 2. For each methods (our algorithm (DF), the baseline (IL), and the baseline of the baseline (AC, consisting of averaging candidates 𝑦 𝑖 in sets 𝑆 𝑖 )), we consider weights 𝛼 given by kernel ridge regression with Gaussian kernel, for which we optimized hyperparameters with cross-validation on the training set. We then learn an estimate 𝑓 𝑛 that we evaluate on the testing set, represented by the 𝑦-axis, on which we have full supervision.

The figure show the superiority of our method, that achieves error similar to baseline when full supervision (𝑥 = 0) or no supervision (𝑥 = 100%) is given, but performs better when only in presence of partial supervision. See Appendix D for reproducibility specifications, where we also provide Figure 6 showcasing similar empirical results in the case of ranking with partial ordering.

Note that with our proof technique, which overcome the suboptimality of calibration inequality [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF][START_REF] Cabannes | Fast rates in structured prediction[END_REF], exponential convergence rates similar to Theorem 4 could be derived for the baseline. Yet, as we will see, our algorithm outperforms this state-of-theart baseline. This could be explained by the fact that our algorithm introduce an intrinsically smaller surrogate space (in essence, [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF] introduced surrogate functions from inputs in X to powersets represented in R 2 Y , while we look at functions from input in X to output represented in R Y ).

Disambiguation coherence -Interval regression. The baseline Eq. ( 13) implicitly requires to disambiguate ( ŷ𝑖 (𝑥)) differently for every 𝑥 ∈ X . This is counter intuitive since (𝑦 * 𝑖 ) does not depend on 𝑥. It means that ( ŷ𝑖 ) could be equal to some ( ŷ(0) 𝑖 ) on a subset X 0 of X , and to another ( ŷ(1) 𝑖 ) on a disjoint subset X 1 ⊂ X , leading to irregularity of 𝑓 𝑛 between X 0 and X 1 . We illustrate this graphically on Figure 1. This figure showcases an interval regression problem, which corresponds to the regression setup (Y = R, ℓ(𝑦, 𝑧) = |𝑦 -𝑧| 2 ) of partial labelling, where one does not observed 𝑦 ∈ R but an interval 𝑠 ⊂ R containing 𝑦. Among others, this problem appears in physics [START_REF] Sheppard | On the calculation of the most probable values of frequency constants, for data arranged according to equidistant division of a scale[END_REF] and economy [START_REF] Tobin | Estimation of relationships for limited dependent variables[END_REF].

Computation attractiveness -Ranking. Computationally, the baseline requires to solve a disambiguation problem, recovering ( ŷ𝑖 (𝑥)) ∈ 𝐶 𝑛 for every 𝑥 ∈ X for which we want to infer 𝑓 𝑛 (𝑥). This is much more costly, than doing the disambiguation of ( ŷ𝑖 ) ∈ 𝐶 𝑛 once, and solving the supervised learning inference problem Eq. ( 5), for every 𝑥 ∈ X for which we want to infer 𝑓 𝑛 (𝑥). To illustrate the computation attractiveness of our algorithm, consider the case of ranking, defined in Section 5.4. Fully supervised inference scheme (5) corresponds to solving a NP-hard problem, equivalent to the minimum feedback arcset problem [START_REF] Duchi | On the consistency of ranking algorithms[END_REF]. While disambiguation approaches with alternative minimization implied by Eq. ( 4) and Eq. ( 13) require to solve this NP-hard problem for each minimization step. In other terms, the baseline ask to solve multiple NP-hard problem every time one wants to infer 𝑓 𝑛 given by Eq. ( 13) on an input 𝑥 ∈ X . Meanwhile, our disambiguation approach asks to solve multiple NP-hard problem upfront to solve Eq. ( 4), yet only require to solve one NP-hard problem to infer 𝑓 𝑛 given by Eq. ( 5) on an input 𝑥 ∈ X .

Better empirical results -Classification. Finally, we compare our algorithm, our baseline ( 13) and the baseline considered by [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF] on real datasets from the LIBSVM dataset [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF]. Those datasets (𝑥 𝑖 , 𝑦 𝑖 ) correspond to fully supervised classification problem. In this setup, Y = 1, 𝑚 for 𝑚 a number of classes, and ℓ(𝑦, 𝑧) = 1 𝑦≠𝑧 . We "corrupt" labels in order to create a synthetic weak supervision datasets (𝑥 𝑖 , 𝑠 𝑖 ). We consider skewed corruption, in the sense that (𝑠 𝑖 ) is generated by a probability such that 𝑧 ∈Y P 𝑆 𝑖 (𝑧 ∈ 𝑆 𝑖 |𝑦 𝑖 ) depends on the value of 𝑦 𝑖 . This corruption is parametrized by a parameter that related with the ambiguity parameter 𝜂 of Assumption 2. Results on Figure 2 show that, in addition to having a lower computation cost, our algorithm performs better in practice than the state-of-the-art baseline.

Beyond Eq.

(2) -Semi-supervised learning. The main limitation of Eq. ( 2) is that it is a pointwise principle that decorrelates inputs, in the sense that the optimization of All the code is available onlinehttps://github.com/ VivienCabannes/partial_labelling.

Semi-supervision setting DF reconstruction IL reconstruction

Figure . Semi-supervised learning, "concentric circle" instance with four classes (red, green, blue, yellow). Reproducibility details provided in Appendix D. (Left) We represent points 𝑥 𝑖 ∈ X ⊂ R 2 , there is many unlabelled points (represented by black dots and corresponding to 𝑆 𝑖 = Y), and one labelled point for each class (represented in color, corresponding to 𝑆 𝑖 = {𝑦 𝑖 }). (Middle) Reconstruction 𝑓 𝑛 : X → Y given by our algorithm Eqs. ( 4) and ( 5). Our algorithm succeeds to comprehend the concentric circle structure of the input distribution and clusters classes accordingly. (Right) Reconstruction 𝑓 𝑛 : X → Y given by the baseline Eq. ( 13). The baseline performs as if only the four supervised data points where given.

𝜇 * | 𝑥 , for 𝑥 ∈ X , only depends on 𝜈| 𝑥 and not on what is happening on X \ {𝑥}. As such, this principle failed to tackle semi-supervised learning, where 𝜈| 𝑥 is equal to 𝜇| 𝑥 (in the sense that 𝜋| 𝑥,𝑦 = 𝛿 {𝑦 } ) for 𝑥 ∈ X 𝑙 and is equal to 𝛿 Y for 𝑥 ∈ X 𝑢 := X \X 𝑙 . In such a setting, for 𝑥 ∈ X 𝑢 , 𝜇 * | 𝑥 can be set to any 𝛿 𝑦 for 𝑦 ∈ Y. Interestingly, in practice, while the baseline suffer the same limitation, for our algorithm, weighting schemes have a regularization effect, that contrasts with those considerations. We illustrate it on Figure 3.

Real real-world applications.

There is a real lack of clean datasets to experiment with partial labelling. Most theoretical papers consist in synthetic corruption of fully supervised dataset (e.g., [START_REF] Korba | A structured prediction approach for label ranking[END_REF] as we did. Empirical papers are built on highly complex datasets that require skilled pre-processing and tricks beside theoretically-grounded principle (e.g., action recognition on Youtube videos). However, note that the state-of-the-art work of [START_REF] Miech | Howto100m: Learning a text-video embedding by watching hundred million narrated video clips[END_REF] is built on heuristics from the Diffrac algorithm, which we generalized (see Alayrac et al., 2016, for details). We hope that, by providing theoretical understanding of the problem, our paper could help to design powerful heuristics in practice, even though this is out of scope of the present paper.

Conclusion

In this work, we have introduced a structured prediction algorithm Eqs. ( 4) and ( 5), to tackle partial labelling. We have derived exponential convergence rates for the nearest neighbors instance of this algorithm under classical learnability assumptions. We provided optimization considerations to implement this algorithm in practice, and have successfully compared it with the state-of-the-art. Several open problems offer prospective follow-up of this works.

• Semi-supervised learning and beyond. While we only proved convergence in situation where 𝜇 * of Eq. ( 2) is uniquely defined, therefore excluding semi-supervised learning, Figure 3 suggests that our algorithm (4) could be analyzed in a broader setting than the one consid-ered in this paper. Among others, the non-ambiguity assumption could be replaced by a cluster assumption [START_REF] Rigollet | Generalization error bounds in semi-supervised classification under the cluster assumption[END_REF] together with a non-ambiguity assumption cluster-wise in Theorem 4. • Hard-coded weak supervision. Variational principles Eqs. ( 2) and ( 3) could be extended beyond partial labelling to any type of hard-coded weak supervision, which is when weak supervision can be cast as a set of hard constraint that 𝜇 should satisfy, formally written as a set of fully supervised distributions compatible with weak information. Hard-coded weak supervision includes label proportion [START_REF] Quadrianto | Estimating labels from label proportions[END_REF][START_REF] Dulac-Arnold | Deep multiclass learning from label proportions[END_REF], but excludes supervision of the type "80% of the experts say this nose is broken, and 20% say it is not". Providing a unifying framework for those problems would make an important step in the theoretical foundation of weakly supervised learning. • Missing input data. While weak supervision assumes that only 𝑦 is partially known, in many applications of machine learning, 𝑥 is also only partially known, especially when the feature vector 𝑥 is built from various source of information, leading to missing data. While we only considered a principle to fill missing output information, similar principles could be formalized to fill missing input information. This would be particularly valuable when data are not missing at random [START_REF] Rubin | Inference and missing data[END_REF][START_REF] Muzellec | Missing data imputation using optimal transport[END_REF].

A. Proofs

Mathematical assumptions. To make formal what should be seen as implicit assumptions heretofore, we consider X and Y Polish spaces, Y compact, ℓ : Y × Y → R continuous, H a separable Hilbert space, 𝜑 measurable, and 𝜓 continuous. We also assume that for 𝜈 𝑥 -almost every 𝑥 ∈ X , and any 𝜇 𝜈, that the pushforward measure 𝜑 * 𝜇| 𝑥 has a second moment. This is the sufficient setup in order to be able to define formally objects and solutions considered all along the paper.

Notations. Beside standard notations, we use #Y to design the cardinality of Y, and 2 Y to design the set of subsets of Y.

Regarding measures, we use 𝜇 X and 𝜇| 𝑥 respectively the marginal over X and the conditional accordingly to 𝑥 of 𝜇 ∈ Δ X ×Y . We denote by 𝜇 ⊗𝑛 the distribution of the random variable (𝑍

Abuse of notations.

For readability sake, we have abused notations. For a signed measure 𝜇, we denote by E 𝜇 [𝑋] the integral ∫ 𝑥 d𝜇(𝑥), extending this notation usually reserved to probability measure. More importantly, when considering 2 Y , we should actually restrict ourselves to the subspace S ⊂ 2 Y of closed subsets of Y, as S is a Polish space (metrizable by the Hausdorff distance) while 2 Y is not always. However, when Y is finite, those two spaces are equals, 2 Y = S.

A.1. Proof of Lemma 3

From Lemma 3 in [START_REF] Cabannes | Fast rates in structured prediction[END_REF], we pulled the calibration inequality

R( 𝑓 𝑛 ) -R( 𝑓 * ) ≤ 2𝑐 𝜓 E 1 𝑔 𝑛 ( 𝑋)-𝑔 * ( 𝑋) >𝑑 (𝑔 * ( 𝑋),𝐹) 𝑔 𝑛 (𝑋) -𝑔 * (𝑋) .
Where 𝐹 is defined as the set of points 𝜉 ∈ Conv 𝜑(Y) leading to two decodings

𝐹 = 𝜉 ∈ Conv 𝜑(Y) # arg min 𝑧 ∈Y 𝜓(𝑧), 𝜉 > 1 ,
and 𝑑 is defined as the extension of the norm distance to sets, for 𝜉 ∈ H

𝑑 (𝜉, 𝐹) = inf 𝜉 ∈𝐹 𝜉 -𝜉 H . Using that 𝑔 𝑛 (𝑋) -𝑔 * (𝑋) ≤ 𝑔 𝑛 (𝑋) -𝑔 * 𝑛 (𝑋) + 𝑔 * 𝑛 (𝑋) -𝑔 * (𝑋) and that, if 𝑎 ≤ 𝑏 + 𝑐, 1 𝑎>𝛿 𝑎 ≤ 1 𝑏+𝑐>𝛿 𝑏 + 𝑐 ≤ 1 2 sup(𝑏,𝑐) >𝛿 2 sup 𝑏, 𝑐 = 2 sup 𝑒 ∈𝑏,𝑐 1 𝑒>𝛿 𝑒 ≤ 21 𝑏>𝛿 𝑏 + 21 𝑐>𝛿 𝑐.
We get the refined inequality

R( 𝑓 𝑛 ) -R(𝑔 * ) ≤ 4𝑐 𝜓 E 1 2 𝑔 𝑛 ( 𝑋)-𝑔 * 𝑛 ( 𝑋) >𝑑 (𝑔 * ( 𝑋),𝐹) 𝑔 𝑛 (𝑋) -𝑔 * 𝑛 (𝑋) + 1 2 𝑔 * 𝑛 ( 𝑋)-𝑔 * ( 𝑋) >𝑑 (𝑔 * ( 𝑋),𝐹) 𝑔 * 𝑛 (𝑋) -𝑔 * (𝑋) . The first term is bounded with E 1 2 𝑔 𝑛 ( 𝑋)-𝑔 * 𝑛 ( 𝑋) >𝑑 (𝑔 * ( 𝑋),𝐹) 𝑔 𝑛 (𝑋) -𝑔 * 𝑛 (𝑋) ≤ 𝑔 𝑛 -𝑔 * 𝑛 𝐿 1 .
While for the second term, we proceed with

E 1 2 𝑔 * 𝑛 ( 𝑋)-𝑔 * ( 𝑋) >𝑑 (𝑔 * ( 𝑋),𝐹) 𝑔 * 𝑛 (𝑋) -𝑔 * (𝑋) ≤ 𝑔 * 𝑛 -𝑔 * 𝐿 ∞ P 𝑋 2 𝑔 * 𝑛 (𝑋) -𝑔 * (𝑋) > inf 𝑥 ∈supp 𝜈 X 𝑑 (𝑔 * (𝑋), 𝐹) .
When weights sum to one, that is 𝑛 𝑖=1 𝛼 𝑖 (𝑋) = 1, both 𝑔 * 𝑛 (𝑋) and 𝑔 * (𝑋) are averaging of 𝜑(𝑦) for 𝑦 ∈ Y, therefore

𝑔 * 𝑛 -𝑔 * 𝐿 ∞ ≤ 2𝑐 𝜑 .
Finally, when the labels are a deterministic function of the input, 𝑔 * (𝑋) = 𝜑( 𝑓 * (𝑋)), and 𝑑 (𝑔 * (𝑋), 𝐹) ≤ sup 𝑦 ∈Y 𝑑 (𝜑(𝑦), 𝐹). Defining 𝛿 := sup 𝑦 ∈Y 𝑑 (𝜑(𝑦), 𝐹)/2, and adding everything together leads to Lemma 3.

A.2. Implication of Assumptions 2 and 3

Assume that Assumption 2 holds, consider 𝑥 ∈ supp 𝜈 X , let us show that 𝑓 * (𝑥) = 𝑦 𝑥 and 𝜇 * | 𝑥 = 𝛿 𝑦 𝑥 . First of all, notice that 𝑆;𝑆 ∈supp 𝜈 | 𝑥 = {𝑦 𝑥 }; that 𝛿 𝑦 𝑥 𝜈| 𝑥 , as it corresponds to 𝜋| 𝑥,𝑆 = 𝛿 𝑦 𝑥 ∈ Δ 𝑆 , for all 𝑆 in the support of 𝜈| 𝑥 ; and that, because ℓ is well-behaved, inf

𝑧 ∈Y ℓ(𝑧, 𝑦 𝑥 ) = ℓ(𝑦 𝑥 , 𝑦 𝑥 ) = 0.
This infimum is only achieved for 𝑧 = 𝑦 𝑥 , hence if we prove that 𝜇 * | 𝑥 = 𝛿 𝑦 𝑥 , we directly have that 𝑓 * (𝑥) = 𝑦 𝑥 . Finally, suppose that 𝜇| 𝑥 𝜈| 𝑥 charges 𝑦 ≠ 𝑦 𝑥 . Because 𝑦 does not belong to all sets charged by 𝜈| 𝑥 , 𝜇| 𝑥 should charge an other 𝑦 ∈ Y, and therefore inf

𝑧 ∈Y E 𝑌 ∼𝜇 | 𝑥 [ℓ(𝑧, 𝑦)] ≥ inf 𝑧 ∈Y 𝜇| 𝑥 (𝑦)ℓ(𝑧, 𝑦) + 𝜇| 𝑥 (𝑦 )ℓ(𝑧, 𝑦 ) > 0.
Which shows that 𝜇 * | 𝑥 = 𝛿 𝑦 𝑥 . We deduce that 𝑔 * (𝑥) = 𝑦 𝑥 . Now suppose that Assumption 3 holds too, and consider two 𝑥, 𝑥 ∈ supp 𝜈 X belonging to two different classes 𝑓 (𝑥) = 𝑦 and 𝑓 (𝑥 ) = 𝑦 . We have that 𝑔 * (𝑥) = 𝜑(𝑦) and 𝑔 * (𝑥 ) = 𝜑(𝑦 ), therefore,

𝑑 (𝑥, 𝑥 ) ≥ 𝑐 -1 𝜑(𝑦) -𝜑(𝑦 ) H . Define ℎ 2 = inf 𝑦≠𝑦 𝑐 -1 𝜑(𝑦) -𝜑(𝑦 ) H . Let us now show that ℎ 2 > 0.
When Y is finite, this infimum is a minimum, therefore, ℎ 2 = 0, only if there exists a 𝑦 ≠ 𝑦 , such that 𝜑(𝑦) = 𝜑(𝑦 ), which would implies that ℓ(•, 𝑦) = ℓ(•, 𝑦 ) and therefore ℓ(𝑦, 𝑦 ) = ℓ(𝑦, 𝑦) which is impossible when ℓ is proper.

A.3. Proof of Theorem 4

Reusing Lemma 3, we have

E ( 𝑓 𝑛 ) ≤ 4𝑐 𝜓 E D 𝑛 ,𝑋 𝑔 * 𝑛 (𝑋) -𝑔 𝑛 (𝑋) H + 8𝑐 𝜓 𝑐 𝜑 E D 𝑛 ,𝑋 1 𝑔 * 𝑛 ( 𝑋)-𝑔 * ( 𝑋) >𝛿 .
We will first prove that

E D 𝑛 1 𝑔 * 𝑛 ( 𝑋)-𝑔 * ( 𝑋) >𝛿 ≤ exp -
𝑛𝑝 8 as long as 𝑘 < 𝑛𝑝/2. The error between 𝑔 * and 𝑔 𝑛 relates to classical supervised learning of 𝑔 * from samples (𝑋 𝑖 , 𝑌 𝑖 ) ∼ 𝜇 * . We invite the reader who would like more insights on this fully supervised part of the proof to refer to the several monographs written on local averaging methods and, in particular, nearest neighbors, such as [START_REF] Biau | Lectures on the Nearest Neighbor Method[END_REF]. Because of class separation, we know that, if 𝑘 points fall at distance at most ℎ of 𝑥 ∈ supp 𝜈 X , 𝑔 * 𝑛 (𝑥) = 𝑘 -1 𝑖;𝑋 𝑖 ∈N (𝑥) 𝜑(𝑦 𝑖 ) = 𝜑(𝑦 𝑥 ) = 𝑔 * (𝑥), where N (𝑥) designs the 𝑘-nearest neighbors of 𝑥 in (𝑋 𝑖 ). Because the probability of falling at distance ℎ of 𝑥 for each 𝑋 𝑖 is lower bounded by 𝑝, we have that P D 𝑛 (𝑔 * 𝑛 (𝑥) ≠ 𝑔 * (𝑥)) ≤ P(Bernouilli(𝑛, 𝑝) < 𝑘). This can be upper bound by exp(-𝑛𝑝/8) as soon as 𝑘 < 𝑛𝑝/2, based on Chernoff multiplicative bound (see [START_REF] Biau | Lectures on the Nearest Neighbor Method[END_REF], for a reference), meaning

E D 𝑛 ,𝑋 1 𝑔 * 𝑛 ( 𝑋)-𝑔 * ( 𝑋) ≥𝛿 ≤ exp(-𝑛𝑝/8).
For the disambiguation part in 𝑔 𝑛 -𝑔 * 𝑛 𝐿 1 , we distinguish two types of datasets, the ones where for any input 𝑋 𝑖 its 𝑘-neighbors at are distance at least ℎ, ensuring that disambiguation can be done by clusters, and datasets that does not verify this property. Consider the event

D = (𝑋 𝑖 ) 𝑖 ≤𝑛 sup 𝑖 𝑑 (𝑋 𝑖 , 𝑋 (𝑘) (𝑋 𝑖 )) < ℎ
where 𝑋 (𝑘) (𝑥) design the 𝑘-th nearest neighbor of 𝑥 in (𝑋 𝑖 ) 𝑖 ≤𝑛 . We proceed with

E D 𝑛 ,𝑋 𝑔 * 𝑛 (𝑋) -𝑔 𝑛 (𝑋) H ≤ sup 𝑋 ∈X 𝑔 * 𝑛 -𝑔 𝑛 ∞ P D 𝑛 ((𝑋 𝑖 ) ∉ D) + E D 𝑛 ,𝑋 𝑔 * 𝑛 (𝑋) -𝑔 𝑛 (𝑋) H (𝑋 𝑖 ) ∈ D , Which is based on 𝐸 [𝑍] = P(𝑍 ∈ 𝐴) E[𝑍 | 𝐴] + P(𝑍 ∉ 𝐴) E[𝑍 | 𝑐 𝐴].
For the term corresponding to bad datasets, we can bound the disambiguation error with the maximum error. Similarly to the derivation for Lemma 3, because 𝑔 * 𝑛 (𝑥) and 𝑔 * 𝑛 (𝑋), are averaging of 𝜑(𝑦), we have that sup

𝑥 ∈supp 𝜈 X 𝑔 𝑛 (𝑥) -𝑔 * 𝑛 (𝑥) ≤ 2𝑐 𝜑 .
Indeed, we allow ourselves to pay the worst error on those datasets as their probability is really small, which can be proved based on the following derivation.

P D 𝑛 ((𝑋 𝑖 ) 𝑖 ≤𝑛 ∉ D) = P ( 𝑋 𝑖 ) (sup 𝑖 𝑑 (𝑋 𝑖 , 𝑋 (𝑘) (𝑋 𝑖 )) ≥ ℎ) = P ( 𝑋 𝑖 ) ∪ 𝑖 ≤𝑛 𝑑 (𝑋 𝑖 , 𝑋 (𝑘) (𝑋 𝑖 )) ≥ ℎ ≤ 𝑛 ∑ 𝑖=1 P ( 𝑋 𝑖 ) 𝑑 (𝑋 𝑖 , 𝑋 (𝑘) (𝑋 𝑖 )) ≥ ℎ = 𝑛 P 𝑋,D 𝑛-1 𝑑 (𝑋, 𝑋 (𝑘) (𝑋)) ≥ ℎ .
This last probability has already been work out when dealing with the fully supervised part, and was bounded as

P 𝑋,D 𝑛-1 𝑑 (𝑋, 𝑋 (𝑘) (𝑋)) ≥ ℎ ≤ exp (-(𝑛 -1) 𝑝/8) .
as long as 𝑘 < (𝑛 -1) 𝑝/2. Finally we have sup

𝑋 ∈X 𝑔 * 𝑛 -𝑔 𝑛 ∞ P D 𝑛 ((𝑋 𝑖 ) 𝑖 ≤𝑛 ∉ D) ≤ 2𝑐 𝜑 𝑛 exp (-(𝑛 -1) 𝑝/8) .
For the expectation term, corresponding to datasets, D 𝑛 ∈ D, that cluster data accordingly to classes, we have to make sure that ŷ𝑖 = 𝑦 * 𝑖 is the only acceptable solution of Eq. ( 4), which is true as soon as the intersection of 𝑆 𝑗 , for 𝑥 𝑗 the neighbors of 𝑥 𝑖 , only contained 𝑦 * 𝑖 . To work out the disambiguation algorithm, notice that

𝑔 𝑛 -𝑔 * 𝑛 𝐿 1 = ∫ X 𝑛 ∑ 𝑖=1 𝛼 𝑖 (𝑥)𝜑( ŷ𝑖 ) -𝜑(𝑦 * 𝑖 ) d𝜈 X (𝑥) ≤ ∫ X 𝑘 -1 𝑛 ∑ 𝑖=1 1 𝑋 𝑖 ∈N (𝑥) 𝜑( ŷ𝑖 ) -𝜑(𝑦 * 𝑖 ) d𝜈 X (𝑥) = 𝑘 -1 𝑛 ∑ 𝑖=1 P 𝑋 (𝑋 𝑖 ∈ N (𝑋)) 𝜑( ŷ𝑖 ) -𝜑(𝑦 * 𝑖 ) ≤ 2𝑐 𝜑 𝑘 -1 𝑛 ∑ 𝑖=1 P 𝑋 (𝑋 𝑖 ∈ N (𝑋)) 1 𝜑 ( ŷ𝑖 )≠𝜑(𝑦 * 𝑖 ) .
Finally we have, after proper conditionning, considering the variability in 𝑆 𝑖 while fixing 𝑋 𝑖 first, We design D, because when this event holds, we know that the 𝑘-th nearest neighbor of any input 𝑋 𝑖 is at distance at most ℎ of 𝑋 𝑖 , meaning the because of class separation, 𝑦 𝑥 𝑖 ∈ 𝑆 𝑗 for any 𝑋 𝑗 ∈ N (𝑋 𝑖 ). This mean that outputting ( ŷ𝑖 ) = (𝑦 * 𝑖 ) and 𝑧 𝑗 = 𝑦 𝑗 , will lead to an optimal error in Eq. ( 4). Now suppose that there is an other solution for Eq. ( 4) such that ŷ𝑖 ≠ 𝑦 * 𝑖 , it should also achieve an optimal error, therefore it should verify 𝑧 𝑗 = ŷ 𝑗 for all 𝑗 as well as ŷ 𝑗 = ŷ𝑖 for all 𝑗 such that 𝑋 𝑗 is one of the 𝑘 nearest neighbors of 𝑋 𝑖 . This implies that ŷ𝑖 ∈ ∩ 𝑗;𝑋 𝑗 ∈N ( 𝑋 𝑖 ) 𝑆 𝑗 , which happen with probability

E
P (𝑆 𝑗 ) 𝑗;𝑋 𝑗 ∈N ( 𝑋 𝑖 ) (∃𝑧 ≠ 𝑦 𝑖 , 𝑧 ∈ ∩ 𝑗 𝑆 𝑗 ) ≤ 𝑚 P 𝑆 𝑗 (𝑧 ∈ 𝑆 𝑗 ) 𝑘 ≤ 𝑚𝜂 𝑘 = 𝑚 exp(-𝑘 |log(𝜂)|).
With 𝑚 = #Y the number of element in Y. We deduce that as long as 𝑘 < (𝑛 -1) 𝑝/2, which implies Theorem 4 as long as 𝑛 ≥ 2.

P (𝑆 𝑖 ) 𝜑( ŷ𝑖 ) ≠ 𝜑(𝑦 * 𝑖 ) (𝑋 𝑖 ) ≤ 𝑚 exp(-𝑘 |log(𝜂)|).

And because

B.2. Link with Diffrac and empirical risk minimization

Our IQP algorithm is similar to an existing disambiguation algorithm known as the Diffrac algorithm [START_REF] Bach | DIFFRAC: a discriminative and flexible framework for clustering[END_REF][START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF]. This algorithm was derived by implicitly following empirical risk minimization of Eq. ( 2). This approach leads to algorithms written as

(𝑦 𝑖 ) ∈ arg min (𝑦 𝑖 ) ∈𝐶 𝑛 inf 𝑓 ∈F 𝑛 ∑ 𝑖=1 ℓ( 𝑓 (𝑥 𝑖 ), 𝑦 𝑖 ) + 𝜆Ω( 𝑓 ),
for F a space of functions, and Ω : F → R + a measure of complexity. Under some conditions, it is possible to simplify the dependency in 𝑓 (e.g., [START_REF] Xu | Maximum margin clustering[END_REF][START_REF] Bach | DIFFRAC: a discriminative and flexible framework for clustering[END_REF]. For example, if ℓ(𝑦, 𝑧) can be written as 𝜑(𝑦) -𝜑(𝑧) 2 for a mapping 𝜑 : X → Y, e.g. the Kendall loss detailed in Section 5.4, and the search of 𝜑( 𝑓 ) : X → 𝜑(Y) is relaxed as a 𝑔 : X → H. With Ω and F linked with kernel regression on the surrogate functional space X → H, it is possible to solve the minimization with respect to 𝑔 as 𝑔(𝑥 𝑖 ) = 𝑛 𝑗=1 𝛼 𝑗 (𝑥 𝑖 )𝜑(𝑦 𝑖 ), with 𝛼 given by kernel ridge regression [START_REF] Ciliberto | A consistent regularization approach for structured prediction[END_REF], and to obtain a disambiguation algorithm written as arg min

𝑦 𝑖 ∈𝑆 𝑖 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 𝛼 𝑗 (𝑥 𝑖 )𝜑(𝑦 𝑗 ) -𝜑(𝑦 𝑖 ) 2 .
This IQP is a special case of the one we will detail. As such, our IQP is a generalization of the Diffrac algorithm, and this paper provides, to our knowledge, the first consistency result for Diffrac.

B.3. Link with an other determinism measure

While we have considered the measure of determinism given by Eq. ( 2), we could have considered its quadratic variant

𝜇 ★ ∈ arg min 𝜇 𝜈 inf 𝑓 :X →Y E 𝑋∼𝜈 X E 𝑌 ,𝑌 ∼𝜇 | 𝑥 [ℓ(𝑌 , 𝑌 )] .
This correspond to the right drawing of

and still derive Theorem 4 when substituting Eq. ( 4) by Eq. ( 14). When the loss is a correlation loss ℓ(𝑦, 𝑧) = -𝜑(𝑦) 𝜑(𝑧). This leads to the quadratic problem ( ŷ𝑖 ) ∈ arg min

(𝑦 𝑖 ) ∈𝐶 𝑛 - 𝑛 ∑ 𝑖, 𝑗=1
𝛼 𝑖 (𝑥 𝑗 )𝜑(𝑦 𝑖 ) 𝜑(𝑦 𝑗 ).

B.4. IQP Implementation

In order to make our implementation possible for any symmetric loss ℓ : Y × Y → R, on a finite space Y, we introduce the following decomposition. The Diffrac algorithm was first introduced for clustering, which is a classical approach to unsupervised learning. In practice, it consists to change the constraint set 𝐶 𝑛 = 𝑆 𝑖 by a set of the type 𝐶 𝑛 = arg max (𝑦 𝑖 ) ∈Y 𝑛 𝑛 𝑖, 𝑗=1 1 𝑦 𝑖 ≠𝑦 𝑗 in Eqs. ( 4) and ( 14), meaning that (𝑦 𝑖 ) should be disambiguated into different classes.

Since 𝜑(𝑦) is constant.

We . By construction, 𝜓 is of constant norm being equal to 𝐶 and that ℓ(𝑦, 𝑧) = 𝜓(𝑦) 𝑇 𝜓(𝑧) -𝜑(𝑦) 𝑇 𝜑(𝑧). Finally, because ℓ(𝑦, 𝑧) = 0, we also have 𝜑 of constant norm.

Using the decomposition Eq. ( 15), Eq. ( 14 Objective convexification. As 𝛼 𝑖 (𝑥 𝑗 ) is a measure of similarity between 𝑥 𝑖 and 𝑥 𝑗 , 𝐴 is usually symmetric positive definite, making this objective convex in Ψ and concave in Φ. However, recalling Eq. ( 15 When parametrized by 𝜉 = Ξ(y), this is an optimization problem with a convex quadratic objective and "integer-like" constraint 𝜉 ∈ Ξ(𝐶 𝑛 ), identifying to an integer quadratic program (IQP).

Relaxation. IQP are known to be NP-hard, several tools exists in literature and optimization library implementing them. The most classical approach consists in relaxing the integer constraint 𝜉 ∈ Ξ(𝐶 𝑛 ) into the convex constraint 𝜉 ∈ Conv(Ξ(𝐶 𝑛 )), solving the resulting convex quadratic program, and projecting back the solution towards an extreme of the convex set. Arguably, our alternative minimization approach is a better grounded heuristic to solve our specific disambiguation problem.

C. Example with graphical illustrations

To ease the understanding of the disambiguation principle (2), we provide a toy example with a graphical illustration, Figure 4. Since Eq. ( 2) decorrelates inputs, we will consider X to be a singleton, in order to remove the dependency to X . In the following, we consider Y = {𝑎, 𝑏, 𝑐}, with the loss given by

𝐿 = (ℓ(𝑦, 𝑧)) 𝑦,𝑧 ∈Y = 0 1 1 1 0 2 1 2 0 .
This problem can be represented on a triangle through the embedding of probability measures reading 𝜉 : Δ Y → R 3 ; 𝜇 → 𝜇(𝑎)𝑒 1 + 𝜇(𝑏)𝑒 2 + 𝜇(𝑐)𝑒 3 , and onto the triangle 𝑧 ∈ R 3 + 𝑧 1 = 1 . Note that 𝜉 can be extended from any signed measure of total mass normalized to one onto the plane 𝑧 ∈ R 3 𝑧 1 = 1 , as well as the drawings Figure 4 the affine span of the represented triangles. The objective (2) reads pointwise as Δ Y → R; 𝜇 → min 𝑖 ≤3 𝑒 𝑖 𝐿𝜉 (𝜇), while its quadratic version reads Δ Y → Y; 𝜇 → 𝜉 (𝜇) 𝐿𝜉 (𝜇). Note that while 𝐿 is not definite negative, one can check that the restriction of R 3 → R; 𝑧 → 𝑧 𝐿𝑧 to the definition domain 𝑧 ∈ R 3 𝑧 1 = 1 is concave, as suggested by the right drawing of Figure 4.

It should be noted that (ℓ, 𝜈) being a well-behaved partial labelling problem can be understood graphically, as having the intersection of the decision regions ∩ 𝑧 ∈𝑆 𝑅 𝑧 non-empty for any set 𝑆 in the support of 𝜈. As such, it is easy to see that our toy problem is well-behaved for any distribution 𝜈. Formally, to match Definition 5, we can define 𝜇 {𝑒 } = 𝛿 𝑒 for 𝑒 ∈ {𝑎, 𝑏, 𝑐} and 𝜇 {𝑎,𝑏 } = .5𝛿 𝑎 + .5𝛿 𝑏 , 𝜇 {𝑎,𝑐 } = .5𝛿 𝑏 + .5𝛿 𝑐 , 𝜇 {𝑏,𝑐 } = 𝛿 𝑏 + 𝛿 𝑐 -𝛿 𝑎 , 𝜇 {𝑎,𝑏,𝑐 } = .5𝛿 𝑏 + .5𝛿 𝑐 .

Graphically 𝜉 (𝜇 {𝑎,𝑏 } ) can be chosen as any points on the horizontal dashed line on the middle right drawing of Figure 4 (similarly for 𝜉 𝜇 {𝑎,𝑐 } ), while 𝜉 (𝜇 {𝑎,𝑏,𝑐 } ) has to be chosen has the intersection .5𝑒 2 + .5𝑒 3 , and while 𝜉 (𝜇 {𝑏,𝑐 } ) has to be chosen outside the simplex on the half-line leaving .5𝑒 2 + .5𝑒 3 supported by the perpendicular bisector of [𝑒 2 , 𝑒 3 ] and not containing 𝑒 1 .

D. Experiments

While our results are much more theoretical than experimental, out of principle, as well as for reproducibility, comparison and usage sake, we detail our experiments.

D.1. Interval regression -Figure 1

Figure 1 corresponds to the regression setup consisting of learning 𝑓 * : [0, 1] → R; 𝑥 → sin(𝜔𝑥), with 𝜔 = 10 ≈ 3𝜋. The dataset represented on Figure 1 is collected in the following way. We sample (𝑥 𝑖 ) 𝑖 ≤𝑛 with 𝑛 = 10, uniformly at random on X = [0, 1], after fixing a random seed for reproducibility. We collect 𝑦 𝑖 = 𝑓 (𝑥 𝑖 ). We create (𝑠 𝑖 ) by sampling 𝑢 𝑖 uniformly on [0, 1], defining 𝑟 𝑖 = 𝑟 -𝛾 log(𝑢 𝑖 ), with 𝑟 = 1 and 𝛾 = 3 -1 , sampling 𝑐 𝑖 uniformly at random on [0, 𝑟 𝑖 ], and defining 𝑠 𝑖 = 𝑦 𝑖 + sign(𝑦 𝑖 ) • 𝑐 𝑖 + [-𝑟 𝑖 , 𝑟 𝑖 ]. The corruption is skewed on purpose to showcase disambiguation instability of the baseline (13) compared to our method. We solve Eq. ( 4) with alternative minimization, initialized by taking 𝑦 (0) 𝑖 at the center of 𝑠 𝑖 , and stopping the minimization scheme when 𝑖 ≤𝑛 |𝑦 (𝑡+1) 𝑖 -𝑦 (𝑡) 𝑖 | < 𝜀 for 𝜀 a stopping criterion fixed to 10 -6 . For 𝑥 ∈ X , the inference Eqs. ( 5) and ( 13) is done through grid search, considering, for 𝑓 𝑛 (𝑥), 1000 guesses dividing uniformly [-6, 6] ⊂ Y = R. We consider weights 𝛼 given by kernel ridge regression with Gaussian kernel, defined as To create a ranking dataset, we sample randomly 𝑚 lines in R 2 , embedding a value, or equivalently a score, associated to each items as a function of the input 𝑥. (Left) By ordering those lines, we create preferences between items as a function of 𝑥. On the figure, when 𝑥 is small, the "red" item is prefered over the "orange" item, itself prefered over the "blue" item, itself prefered over the "green" item. While when 𝑥 is big, "green" is prefered over "blue", prefered over "orange", prefered over "red". We create a partial labelling dataset by sampling (𝑥 𝑖 ) ∈ X 𝑛 , and providing only partial ordering that the (𝑦 𝑖 ) follow. For example, for a small 𝑥, we might only give the partial information that "red" is prefered over "blue". and 𝑓 * , which is equivalent to evaluating the risk with the regression loss ℓ(𝑦, 𝑧) = 𝑦 -𝑧 2 , is done by considering 200 points dividing uniformly X = [0, 1] and evaluating 𝑓 𝑛 and 𝑓 * on it. The best hyperparameter 𝜆 is chosen by minimizing this error. It leads to 𝜆 = 10 -1 for the baseline ( 13), and 𝜆 = 10 -6 for our algorithm (4) and ( 5). This difference in 𝜆 is normal since both methods are not estimating the same surrogate quantities. The fact that 𝜆 is smaller for our algorithm is natural as our disambiguation objective (4) already has a regularization effect on the solution. Note that we used the same weights 𝛼 for Eq. ( 4) and Eq. ( 5), which is suboptimal, but fair to the baseline, as, consequently, both methods have the same number of hyperparameters.

D.2. Classification -Figure 2

Figure 2 corresponds to classification problems, based on real dataset from the LIBSVM datasets repository. At the time of writing, the datasets are available at https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ multiclass.html. We present results on the "Dna" and "Svmguide2" datasets, that both have 3 classes (𝑚 = 3), and respectively have 4000 samples with 180 features (𝑛 = 4000,𝑑 = 180) and 391 samples with 20 features (𝑛 = 391, 𝑑 = 20).

In term of complexity, when Y = 1, 𝑚 = {1, 2, • • • , 𝑚}, and weights based on kernel ridge regression with Gaussian kernel as described in the last paragraph the complexity of performing inference for Eqs. ( 5) and ( 13) can be done in 𝑂 (𝑛𝑚) in time and 𝑂 (𝑛 + 𝑚) in space, where 𝑛 is the number of training samples [START_REF] Nowak-Vila | Sharp analysis of learning with discrete losses[END_REF][START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF]. The disambiguation (4) performed with alternative minimization is done in 𝑂 (𝑐𝑛 2 𝑚) in time and in 𝑂 (𝑛(𝑛 + 𝑚)) in space, with 𝑐 the number of steps in the alternative minimization scheme. In practice, 𝑐 is really small, which can be understood since we are minimizing a concave function and each step leads to a guess on the border of the constraint domain.

Based on the dataset (𝑥 𝑖 , 𝑦 𝑖 ), we create (𝑠 𝑖 ) by sampling it accordingly to 𝛾𝛿 {𝑦 𝑖 } + 1 -𝛾𝛿 {𝑦,𝑦 𝑖 } , with 𝑦 the most present labels in the dataset (indeed we choose the two datasets because they were not too big and presenting unequal labels proportion), and 𝛾 ∈ [0, 1] the corruption parameter represented in percentage on the 𝑥-axis of Figure 2. This skewed corruption allows to distinguish methods and invalidate the simple approach consisting to averaging candidate (AC) in set to recover 𝑦 𝑖 from 𝑠 𝑖 , which works well when data are missing at random [START_REF] Heitjan | Ignorability and coarse data[END_REF]. We separate (𝑥 𝑖 , 𝑠 𝑖 ) in 8 folds, consider 𝜎 ∈ 𝑑 • [1, .1, .01], where 𝑑 is the dimension of X , and 𝜆 ∈ 𝑛 -1/2 • [1, 10 -3 , 10 -6 ], where 𝑛 is the number of data. We test the different hyperparameter setup and reported the best error for each corruption parameter on Figure 2. Those errors are measured with the 0-1 loss, computed as averaged over the 8 folds, i.e. cross-validated, which standard deviation represented as errorbars on the figure. The best hyperparameter generally corresponds to 𝜎 = .1 and 𝜆 = 10 -3 when the corruption is small and 𝜎 = 1, 𝜆 = 10 -3 when the corruption is big. Differences between cross-validated error and testing error were small, and we presented the first one out of simplicity.

In term of energy cost, the experiments were run on a personal laptop that has two processors, each of them running 2.3 billion instructions per second. During experiments, all the data were stored on the random access memory of 8GB.

Moreover, the analysis in [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF] suggests that the baseline is estimating a surrogate function in X → 2 R , while our method is estimating a function in X → R, which is a much smaller function space, hence needing less regularization. However, those reflections are based on upper bounds, that might be sub-optimal, which could invalidate those considerations.

Figure .

 . Figure . Interval regression. See Appendix D for the exact reproducible experimental setup (Left) Setup. The goal is to learn 𝑓 * : X → R represented by the dashed line, given samples (𝑥 𝑖 , 𝑠 𝑖 ), where (𝑠 𝑖 ) are intervals represented by the blue segments. (Right) We compare the Infimum Loss (IL) baseline (13) shown in green, with our Disambiguation Framework (DF), Eqs. (4) and (5), shown in orange; with weights 𝛼 given by kernel ridge regression. (DF) retrieves ŷ𝑖 before learning a smooth 𝑓 𝑛 based on (𝑥 𝑖 , ŷ𝑖 ), while (IL) implicitly retrieves ŷ𝑖 (𝑥) differently for each input, leading to irregularity of the consequent estimator of 𝑓 * .

  derived an algorithm geared towards classification, based on a disambiguation objective, incorporating several heuristics, such as class separation, and Laplacian diffusion. Those heuristics could be incorporated formally in our model.The infimum loss principle has been considered by several authors, among them[START_REF] Cour | Learning from partial labels[END_REF];[START_REF] Luo | Learning from candidate labeling sets[END_REF];[START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization[END_REF]. It was recently analyzed through the prism of structured prediction by[START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF], leading to a consistent non-parametric algorithm that will constitute the baseline of our experimental comparison. This principle is interesting as it does not assume knowledge on the corruption process (𝑆|𝑌 ) contrarily to the work of[START_REF] Cid-Sueiro | Consistency of losses for learning from weak labels[END_REF] or[START_REF] Van Rooyen | A theory of learning with corrupted labels[END_REF].

  Figure .Testing errors as function of the supervision corruption on real dataset corresponding to classification with partial labels. We split fully supervised LIBSVM datasets into training and testing dataset. We corrupt training data in order to get partial labels. Corruption is managed through a parameter, represented by the 𝑥-axis, that relates to the ambiguity degree 𝜂 of Assumption 2. For each methods (our algorithm (DF), the baseline (IL), and the baseline of the baseline (AC, consisting of averaging candidates 𝑦 𝑖 in sets 𝑆 𝑖 )), we consider weights 𝛼 given by kernel ridge regression with Gaussian kernel, for which we optimized hyperparameters with cross-validation on the training set. We then learn an estimate 𝑓 𝑛 that we evaluate on the testing set, represented by the 𝑦-axis, on which we have full supervision. The figure show the superiority of our method, that achieves error similar to baseline when full supervision (𝑥 = 0) or no supervision (𝑥 = 100%) is given, but performs better when only in presence of partial supervision. See Appendix D for reproducibility specifications, where we also provide Figure6showcasing similar empirical results in the case of ranking with partial ordering.

𝑖=1P1

  D 𝑛 ,𝑋 𝑔 * 𝑛 (𝑋) -𝑔 𝑛 (𝑋) H (𝑋 𝑖 ) ∈ D = 2𝑐 𝜑 𝑘 -1 E ( 𝑋 𝑖 ) 𝑛 ∑ 𝑋 (𝑋 𝑖 ∈ N (𝑋)) E (𝑆 𝑖 ) 1 𝜑( ŷ𝑖 )≠𝜑 (𝑦 * 𝑖 ) (𝑋 𝑖 ) (𝑋 𝑖 ) ∈ D = 2𝑐 𝜑 𝑘 -1 E ( 𝑋 𝑖 ),𝑋 𝑛 ∑ 𝑖=1 𝑋 𝑖 ∈N ( 𝑋) P (𝑆 𝑖 ) 𝜑( ŷ𝑖 ) ≠ 𝜑(𝑦 * 𝑖 ) (𝑋 𝑖 ) (𝑋 𝑖 ) ∈ D .

Figure 4 .

 4 We could arguably translate it experimentally as ( ŷ𝑖 ) ∈ arg min(𝑦 𝑖 ) ∈𝐶 𝑛 𝑛 ∑ 𝑖, 𝑗=1𝛼 𝑖 (𝑥 𝑗 )ℓ(𝑦 𝑖 , 𝑦 𝑗 ),

Proposition 10 (

 10 Quadratic decomposition). When Y is finite, any proper symmetric loss ℓ admits a decomposition with two mappings𝜑 : Y → R 𝑚 , 𝜓 : Y → R 𝑚 , for a 𝑚 ∈ N and a 𝑐 ∈ R, reading ∀ 𝑦, 𝑧 ∈ Y, ℓ(𝑦, 𝑧) = 𝜓(𝑦) 𝜓(𝑧) -𝜑(𝑦) 𝜑(𝑧) with 𝜑(𝑦) = 𝜓(𝑦) = 𝑐(15) Proof. Consider Y = 𝑦 1 , •, 𝑦 𝑚 and 𝐿 = (ℓ(𝑦 𝑖 , 𝑦 𝑗 )) 𝑖, 𝑗 ≤𝑚 ∈ R 𝑚×𝑚 . 𝐿 is a symmetric matrix, diagonalizable as 𝐿 = 𝑚 𝑖=1 𝜆 𝑖 𝑢 𝑖 ⊗ 𝑢 𝑖 , with (𝑢 𝑖 ) a orthonormal basis of R 𝑚 , and 𝜆 𝑖 ∈ R its eigen values. We have, with (𝑒 𝑖 ) the Cartesian basis of R 𝑚 , ℓ(𝑦 𝑗 , 𝑦 𝑘 ) = 𝐿 𝑗 𝑘 = 𝑒 𝑗 , 𝐿𝑒 𝑘 = 𝑚 ∑ 𝑖=1 (𝜆 𝑖 ) + 𝑒 𝑗 , 𝑢 𝑖 𝑒 𝑘 , 𝑢 𝑖 -𝑚 ∑ 𝑖=1 (𝜆 𝑖 ) -𝑒 𝑗 , 𝑢 𝑖 𝑒 𝑘 , 𝑢 𝑖 .

  ) reads, with y = (𝑦 𝑖 ) ŷ ∈ arg min y∈𝐶 𝑛 𝑛 ∑ 𝑖=1 𝛼 𝑖 (𝑥 𝑗 )𝜓(𝑦 𝑖 )𝜓(𝑦 𝑗 ) -𝑛 ∑ 𝑖=1 𝛼 𝑖 (𝑥 𝑗 )𝜑(𝑦 𝑖 )𝜑(𝑦 𝑗 ). By defining the matrix 𝐴 = (𝛼 𝑖 (𝑥 𝑗 )) 𝑖 𝑗 ≤𝑛 ∈ R 𝑛×𝑛 , Ψ(y) = (𝜓(𝑦 𝑖 )) 𝑖 ≤𝑛 ∈ R 𝑛×𝑚 and Φ(y) = (𝜑(𝑦 𝑖 )) 𝑖 ≤𝑛 ∈ R 𝑛×𝑚 , we cast it as ŷ ∈ arg min y∈𝐶 𝑛 Tr 𝐴Ψ(y)Ψ(y) -Tr 𝐴Φ(y)Φ(y) .

  ), we have Tr ΦΦ = Tr ΨΨ = 𝑛𝑐, therefore considering the spectral norm of 𝐴, we convexify the objective as ŷ ∈ arg min y∈𝐶 𝑛 Tr ( 𝐴 * 𝐼 + 𝐴)Ψ(y)Ψ(y) + Tr ( 𝐴 * 𝐼 -𝐴)Φ(y)Φ(y) .

Figure .

 . Figure . Exposition of a pointwise problem in the simplex Δ Y , with Y = {𝑎, 𝑏, 𝑐} and a proper symmetric loss defined by ℓ(𝑎, 𝑏) = ℓ(𝑎, 𝑐) = ℓ(𝑏, 𝑐)/2. (Left) Representation of the decision regions 𝑅 𝑧 = 𝜇 ∈ Δ Y 𝑧 ∈ arg min 𝑧 ∈Y E 𝑌 ∼𝜇 [ℓ(𝑧, 𝑦)] . for 𝑧 ∈ Y. (Middle Left) Representation of 𝑅 𝜈 = 𝜇 ∈ Δ Y 𝜇 𝜈 for 𝜈 = (5𝛿 {𝑎,𝑏,𝑐 } + 𝛿 {𝑐 } + 𝛿 {𝑎,𝑐 } + 𝛿 {𝑏,𝑐 } )/8 (Middle Right) Level curves of the piecewise function Δ Y → R; 𝜇 → min 𝑧 ∈Y E 𝑌 ∼𝜇 [ℓ(𝑧, 𝑌 )] corresponding to Eq. (2). (Right) Level curves of the quadratic function Δ Y → R; 𝜇 → E 𝑌 ,𝑌 ∼𝜇 [ℓ(𝑌 , 𝑌 )]. Our disambiguation (2) corresponds to minimizing the concave function represented on the middle right drawing on the convex domain represented on the middle left drawing.

Figure .

 . Figure .Ranking setting. We consider X an interval of R, and Y = S 𝑚 with 𝑚 = 4 on the figure. (Right) To create a ranking dataset, we sample randomly 𝑚 lines in R 2 , embedding a value, or equivalently a score, associated to each items as a function of the input 𝑥. (Left) By ordering those lines, we create preferences between items as a function of 𝑥. On the figure, when 𝑥 is small, the "red" item is prefered over the "orange" item, itself prefered over the "blue" item, itself prefered over the "green" item. While when 𝑥 is big, "green" is prefered over "blue", prefered over "orange", prefered over "red". We create a partial labelling dataset by sampling (𝑥 𝑖 ) ∈ X 𝑛 , and providing only partial ordering that the (𝑦 𝑖 ) follow. For example, for a small 𝑥, we might only give the partial information that "red" is prefered over "blue".

  ×Y×2 Y expressing the compatibility of 𝜇 * and 𝜈 as in Definition 1. Given samples (𝑥 𝑖 , 𝑠 𝑖 ) 𝑖 ≤𝑛 forming a dataset D 𝑛 , we enrich this dataset by sampling 𝑦 * 𝑖 ∼ 𝜋 * | 𝑥 𝑖 ,𝑠 𝑖 , which build an underlying dataset (𝑥 𝑖 , 𝑦 * 𝑖 , 𝑠 𝑖 ) sampled accordingly (𝜋 * ) ⊗𝑛 . Given D 𝑛 , while a priori, 𝑦 * 𝑖 are random variables, sampled accordingly to 𝜋 * | 𝑥 𝑖 ,𝑠 𝑖 , because of the definition of 𝜇 * (2), under basic definition assumptions, they are actually deterministic, defined as 𝑦 * 𝑖 = arg min 𝑦 ∈𝑠 𝑖 ℓ( 𝑓 * (𝑥 𝑖 ), 𝑦). As such, they should be seen as ground truth for ŷ𝑖 .

	Surrogate estimates. The approximate Bayes rule was
	successfully analyzed recently through the prism of plug-in
	estimators by Ciliberto et al. (2020). While we will not
	cast our algorithm as a plug-in estimator, we will leverage
	this surrogate approach, introducing two mappings 𝜑 and 𝜓
	from Y to an Hilbert space H such that
	∀ 𝑧, 𝑦 ∈ Y,	ℓ(𝑧, 𝑦) = 𝜓(𝑧), 𝜑(𝑦) ,	(7)
	Such mappings always exist when Y is finite, and have
	been used to encode "problem structure" defined by the loss
	ℓ (Nowak-Vila et al., 2019). Note that many losses (e.g.
	Hamming, Spearman, Kendall in ranking) can be written as
	correlation losses which corresponds to 𝜓 = -𝜑, yet Eq. (7)
	allows to model much more losses, especially asymmetric
	losses (e.g. discounted cumulative gain). We introduce
	three surrogate quantities that will play a major role in the
	following analysis, they map X to H as
					𝑛
	𝑔 * (𝑥) = E 𝜇 * [𝜑(𝑌 ) | 𝑋 = 𝑥] ,		𝑔 𝑛 (𝑥) =	∑	𝛼 𝑖 (𝑥)𝜑( ŷ𝑖 ),
					𝑖=1
		𝑛
	𝑔 * 𝑛 (𝑥) =	∑	𝛼 𝑖 (𝑥)𝜑(𝑦 * 𝑖 ).	(8)
		𝑖=1
	It is known that 𝑓 * and 𝑓 𝑛 are retrieved from 𝑔 * and 𝑔 𝑛 ,
	through the decoding, retrieving 𝑓 : X → Y from 𝑔 : X →
	H as
	𝑓 (𝑥) = arg min	𝜓(𝑧), 𝑔(𝑥) ,
	𝑧 ∈Y

* 𝑖 ). Introduce 𝜋 * ∈ Δ X

Assumption 2 (Non ambiguity

  , Cour et al. (2011)). Assume the existence of 𝜂 ∈ [0, 1), such that for any 𝑥 ∈ supp 𝜈 X , there exists 𝑦 𝑥 ∈ Y, such that P 𝜈 (𝑦 𝑥 ∈ 𝑆 | 𝑋 = 𝑥) = 1, and ∀ 𝑧 ≠ 𝑦 𝑥 , P 𝜈 (𝑧 ∈ 𝑆 | 𝑋 = 𝑥) ≤ 𝜂. | 𝑥 = 𝛿 𝑦 𝑥 , and 𝑓 * (𝑥) = 𝑦 𝑥 .

	Assumption 2 states that when given the full distribution 𝜈,
	there is one, and only one, label that is coherent with every
	observable sets for a given input. It is a classical assumption
	in literature about the learnability of the partial labelling
	problem (e.g., Liu & Dietterich, 2014). When ℓ is proper,
	this implies that 𝜇 Finally, we assume that 𝑔 * is regular. As we are considering
	local averaging method, we will use Lipschitz-continuity,
	which is classical in such a setting.
	Assumption 3 (Regularity of 𝑔

* * ). Assume that there exists 𝑐 𝑔 > 0, such that for any 𝑥, 𝑥 ∈ X , we have 𝑔 * (𝑥) -𝑔 * (𝑥 ) H ≤ 𝑐 𝑔 𝑑 (𝑥, 𝑥 ).

Its generalization through Hölder-continuity would work too.

  1 , • • • , 𝑍 𝑛 ), where the 𝑍 𝑖 are sampled independently according to 𝜇. For 𝐴 a Polish space, we consider Δ 𝐴 the set of Borel probability measures on this space. For 𝜑 : Y → H and 𝑆 ⊂ Y, we denote by 𝜑(𝑆) the set {𝜑(𝑦) | 𝑦 ∈ 𝑆}. For a family of sets (𝑆 𝑖 ), we denote by 𝑆 𝑖 the Cartesian product 𝑆 1 × 𝑆 2 × • • • , also defined as the set of points (𝑦 𝑖 ) such that 𝑦 𝑖 ∈ 𝑆 𝑖 for all index 𝑖, and by Y 𝑛 the Cartesian product 𝑖 ≤𝑛 Y. Finally, for 𝐸 a subset of a vector space 𝐸 , Conv 𝐸 denotes the convex hull of 𝐸 and Span(𝐸) its span.

  𝑛 𝑖=1 1 𝑋 𝑖 ∈N ( 𝑋) = 𝑘, we conclude that E D 𝑛 ,𝑋 𝑔 * 𝑛 (𝑋) -𝑔 𝑛 (𝑋) H (𝑋 𝑖 ) ∈ D ≤ 2𝑐 𝜑 𝑚 exp(-𝑘 |log(𝜂)|).

	Finally, adding everything together we get
	E ( 𝑓 𝑛 ) ≤ 8𝑐 𝜑 𝑐 𝜓 exp -	𝑛𝑝 8	+ 8𝑐 𝜑 𝑐 𝜓 𝑛 exp -	(𝑛 -1) 𝑝 8	+ 8𝑐 𝜑 𝑐

𝜓 𝑚 exp (-𝑘 |log(𝜂)|) .

  It satisfies ℓ(𝑦 𝑗 , 𝑦 𝑘 ) = ψ(𝑦) ψ(𝑧)φ(𝑦) φ(𝑧). We only need to show that we can consider 𝜑 of constant norm. For this, first consider𝐶 = max 𝑖 |𝜆 𝑖 |, we have ψ(𝑦 𝑘 ) 2 = 𝑚 𝑖=1 (𝜆 𝑖 ) + 𝑢 𝑖 , 𝑒 𝑘 2 ≤ 𝐶 𝑚 𝑖=1 𝑢 𝑖 , 𝑒 𝑘 2 = 𝐶 𝑒 𝑘 2 = 𝐶The last equalities being due to the fact that (𝑢 𝑖 ) is orthonormal. Now, introduce the correction vector 𝜉 : Y → R 𝑚 , 𝜉 (𝑦 𝑖 ) =

	build the decomposition
	ψ(𝑦 𝑘 ) =	√	(𝜆 𝑖 ) + 𝑒 𝑘 , 𝑢 𝑖	𝑖 ≤𝑚	,	and	φ(𝑦 𝑘 ) =	√	(𝜆 𝑖 ) -𝑒 𝑘 , 𝑢 𝑖	𝑖 ≤𝑚	.
							√ 𝐶 -ψ(𝑦)	2	𝑒 𝑖 . And consider 𝜑 = φ 𝜉 , 𝜓 = ψ 𝜉

Institut National de Recherche en Informatique et en Automatique -Département d'Informatique de l'École Normale Supérieure -PSL Research University. Correspondence to: Vivien Cabannes <vivien.cabannes@gmail.com>.

Acknowledgements

We would like to thanks anonymous referees for helpful comments. 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 of the European Research Council (grants SEQUOIA 724063, REAL 94790).

Remark 9 (Other approaches). While we have proceed with analysis based on local averaging methods, other paths could be explored to prove convergence results of the algorithm provided Eq. (4) and (5). For example, one could prove Wasserstein convergence of 𝑛 𝑖=1 𝛿 (𝑥 𝑖 , ŷ𝑖 ) towards 𝑛 𝑖=1 𝛿 (𝑥 𝑖 , ŷ * 𝑖 ) , together with some continuity of the learning algorithm as a function of those distributions. This analysis could be understood as tripartite:

• A disambiguation error, comparing ŷ𝑖 to 𝑦 * 𝑖 . • A stability / robustness measure of the algorithm to learn 𝑓 𝑛 from data when substituting 𝑦 * 𝑖 by ŷ𝑖 . • A consistency result regarding 𝑓 * 𝑛 learnt on (𝑥 𝑖 , 𝑦 * 𝑖 ). Our analysis followed a similar path, yet with the first two parts tackled jointly.

A.4. Proof of Proposition 6

Under the non-ambiguity hypothesis (Assumption 2), the solution of Eq. ( 3) is characterized pointwise by 𝑓 * (𝑥) = 𝑦 𝑥 for all 𝑥 ∈ supp 𝜈 X . Similarly under Assumption 2, we have the characterization

For the second part of the proposition, we use the structured prediction framework of [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF]. Define the signed measure 𝜇 • defined as 𝜇

and

. The first part of the proposition tells us that 𝑓 • = 𝑓 * under Assumption 2. The framework of [START_REF] Ciliberto | A general framework for consistent structured prediction with implicit loss embeddings[END_REF], tells us that 𝑓 • is obtained after decoding, Eq. ( 9), of 𝑔 • : X → H, and that if 𝑔 • 𝑛 converges to 𝑔 • with the 𝐿 1 norm, 𝑓 • 𝑛 converges to 𝑓 • in term of the 𝜇 • -risk. Under Assumption 2 and mild hypothesis on 𝜇 • , it is possible to prove that convergence in term of the 𝜇 • -risk implies convergence in term of the 𝜇-risk (for example through calibration inequality similar to Proposition 2 of Cabannes et al. ( 2020)).

A.5. Ranking with Partial ordering is a well behaved problem

Here, we discuss about building directly 𝜉 𝑆 to initialize our alternative minimization scheme or considering 𝜇 𝑆 given by the definition of well-behaved problem (Definition 5). Since the existence of 𝜇 𝑆 implying 𝜉 𝑆 defined as E 𝑌 ∼𝜇 𝑆 [𝜑(𝑌 )], we will only study when 𝜉 𝑆 can be cast as a 𝜇 𝑆 .

In ranking, we have that 𝜓 = -𝜑, which corresponds to "correlation losses". In this setting, we have that Span(𝜑(Y)) = Span(𝜓(Y)). More generally, looking at a "minimal" representation of ℓ, one can always assume the equality of those spans, as what happens on the orthogonal of the intersection of those spans, does not modify the scalar product 𝜑(𝑦) 𝜓(𝑧). Similarly, 𝜉 𝑆 can be restricted to Span(𝜓(Y)), and therefore Span(𝜑(Y)), which exactly the image by 𝜇 → E 𝑌 ∼𝜇 [𝜑(𝑌 )] of the set of signed measures, showing the existence of a 𝜇 𝑆 matching Definition 5.

B. IQP implementation for Eq. (4)

In this section, we introduce an IQP implementation to solve for Eq. ( 4). We first mention that our alternative minimization scheme is not restricted to well-behaved problem, before motivating the introduction of the IQP algorithm in two different ways, and finally describing its implementation.

B.1. Initialization of alternative minimization for non well-behaved problem

Before describing the IQP implementation to solve Eq. ( 12), we would like to stress that, even for non well-behaved partial labelling problems, it is possible to search for smart ways to initialize variables of the alternative minimization scheme. For example, one could look at 𝑧 (0) 𝑖 ∈ ∩ 𝑗;𝑥 𝑗 ∈N 𝑘 𝑖 𝑆 𝑗 , where N 𝑘 designs the 𝑘 nearest neighbors of 𝑥 𝑖 in (𝑥 𝑗 ) 𝑗 ≤𝑛 , and 𝑘 𝑖 is chosen such that this intersection is a singleton.

The Wasserstein metric is useful to think in term of distributions, which is natural when considering partial supervision that can be cast as a set of admissible fully supervised distributions. This approach has been successfully followed by [START_REF] Perchet | On a unified framework for approachability with full or partial monitoring[END_REF] to deal with partial monitoring in games. Experiments were run on Python, extensively relying on the NumPy library [START_REF] Harris | Array programming with NumPy[END_REF]. The heaviest computation is Figure 2. Its total runtime, cross-validation included, was around 70 seconds. This paper is the results of experimentations, we evaluate the total cost of our experimentations to be three orders of magnitude higher than the cost of reproducing the final computations presented on Figure 1, 2 and 3. The total computational energy cost is very negligible.

D.3. Semi-supervised learning -Figure 3

On Figure 3, we review a semi-supervised classification problem with 4) with 𝑘-nearest neighbors, with 𝑘 = 20, and solve this equation with a variant of alternative minimization, leading to the optimal solution ỹ𝑖 = 𝑦 * 𝑖 . In order to be able to compute the baseline (13), we design weights 𝛼 for the inference task based on Nadaraya-Watson estimators with Gaussian kernel, defined as 𝛼 𝑖 (𝑥) = exp 𝑥 -𝑥 𝑖 2 /ℎ , with ℎ = .08. We solve the inference task on a grid of X composed of 2500 points, and artificially recreate the observation to make them neat and reduce the resulting pdf size. Note that it is possible to design weights 𝛼 that capture the cluster structure of the data, which, in this case, will lead to a nice behavior of the baseline as well as our algorithm. Arguably, this experiment showcase a regularization property of our algorithm (4).

D.4. Ranking with partial ordering

To conclude this experiment section, we look at ranking with partial ordering. We refer to Section 5.4 for a clear description of this instance of partial labelling. We provide to the reader eager to use our method, an implementation of our algorithm, available online at https://github.com/VivienCabannes/partial_labelling. It is based on LP relaxation of the NP-hard minimum feedback arcset problem. This relaxation was proven exact when 𝑚 ≤ 6 by [START_REF] Cabannes | Structured prediction with partial labelling through the infimum loss[END_REF]. The LP implementation relies on CPLEX (IBM, 2017). As complementary experiments, we will not provide much reproducibility details, those details would be really similar to the previous paragraphs, and the curious reader could run our code instead. We present our ranking setup on Figure 5 and our results on Figure 6.