Optimistic bounds for multi-output prediction

Multi-output prediction represents an important class of problems that includes multi-class classification Crammer and Singer(2001), multi-label classification Tsoumakas and Katakis(2007); Zhang and Zhou(2013), multi-target regression Borchani et al. (2015), label distribution learning Geng (2016), structured regression Cortes et al. (2016) and others, with a wide range of practical applications Xu et al. (2019). Our objective is to provide a general framework for establishing guarantees for multiple-output prediction problems. A fundamental challenge in the statistical learning theory of multi-output prediction problems is to obtain bounds which allow for (i) favourable convergence rate with the sample size, and (ii) favourable dependence of the risk on the dimensionality of the output space. Whilst modern applications of multioutput prediction deal with increasingly large data sets, they also incorporate problems where the target dimensionality is increasingly large. For example, the number of categories in multi-label is often of the order of tens of thousands, an emergent problem referred to as extreme classification Agrawal et al. (2013); Babbar and Schölkopf (2017); Bhatia et al. (2015); Jain et al. (2019).