
## 5.2.2  Optimizing Z In Our Setting

As previously argued in Theorem 4, minimizing Z in the setting of Schapire & Singer (1998)
can be done optimally, but at the expense of complex optimization procedures, with large complexities. One can wonder whether such procedures, to optimize only the computation of v (a small part of WIDC), are really well worth the adaptation to our setting, in which more values are authorized. We are now going to show that a much simpler combinatorial procedure, with comparatively very low complexity, can bring optimal results in fairly general situations. The most simple way to describe most of these situations is to make the following assumption on the examples:

## (A) Each Example Used To Compute V Has Only One "1" In Its Class Vector.

A careful reading of assumption ( A ) reveals that it implies that each example belongs to exactly one class, but it does not prevent an observation to be element of more than one class, as long as different examples sharing the same observation have different classes (the
"1" of the class vectors is in different positions among these examples). Therefore, even if it does not integrate the most general features of the ranking loss setting, our assumption still authorizes to consider problems with non zero Bayes optimum. This is really interesting, as many commonly used datasets fall into the category of our assumption, as for example many datasets of the UCI repository of Machine Learning database (Blake et al., 1998). Finally, en if the assumption does not hold, we show that in many of the remaining (interesting)
cases, our approximation algorithm is asymptotically optimal, that is, finds solutions closer to the minimal value of Z as c increases.

Suppose for now that (A) holds.  Our objective is to calculate the vector v of some monomial t .  We use the shorthands W n +, W n +, …, W c +, to denote the sum of weights of the examples satisfying t and belonging respectively to classes 0,1, ...,c - 1. We want to minimize Z as proposed in eq. (3). Suppose without loss of generality that

$$W_{0}^{+}\,\leq W_{1}^{+}\quad\leq\quad\dots\,\leq\,W_{c-1}^{+}$$

otherwise, reorder the classes so that they verify this assertion. Given only three possible values for each component of -, the testing of all 3c possibilities for - is exponential and time-consuming. But we can propose a very fast approach. We have indeed

## Lemma 1  Vl ≤ J < K ≤ C, V[J] ≤ V[K] .

Proof:  See the Appendix.

D
Thus, the optimal i does not belong to a set of cardinality 3 c , but to a set of cardinality O (c 2 ). Our algorithm is then straightforward: simply explore this set of O (c 2 ) elements, and keep the vector having the lowest value of Z . Note that this combinatorial algorithm has the advantage to be adaptable to more general settings in which l particular values are authorized for the components of v , for any fixed l not necessarily equal to 3. In that case, the complexity is larger, but limited to O (c'-').

There are slightly more general settings in which our algorithm remains optimal, in particular when we can certify ∀ j, k, (( W j > W j +) ↔ ( Vi ̸ = j, k : W j, i > W j )) V (( W j <
W t ) $ ( Vi + j, k : W j, i > W k,i )). Here, W + denotes the sum of weights of the examples belonging at least to class x, and Wx,y denotes the sum of weights of the examples belonging