Unlike traditional machine learning problems that only involve independent instance-wise losses, AUC's pair-wise formulation makes the generalization analysis difficult to be carried out. Specifically, the terms in MAUC formulation exert certain degrees of interdependency. This way, the standard symmetrization scheme [1]}, [2]} is not available for our problem. For instance, the terms \(\ell (f^{(i)}(\mathbf {x}_1) - f^{(i)}(\mathbf {x}_2))\)  and \(\ell (f^{(i)}(\mathbf {x}^{\prime }_1)-f^{(i)}(\mathbf {x}^{\prime }_2))\)  are interdependent as long as \(\mathbf {x}_1 = \mathbf {x}^{\prime }_1\)  or \(\mathbf {x}_2 = \mathbf {x}^{\prime }_2\) . To address this issue, we provide an extended form of Rademacher complexity for \({\mathsf {MAUC}^\downarrow }\)  losses, which is defined as follows.
