Generalization Analysis for Multi-Dimensional Classification

Recent studies have experimentally demonstrated that multi-dimensional classification (MDC), where each example is represented by a single instance while associated with multiple class variables, can achieve empirical success in many application scenarios, however, the problem of theoretically understanding MDC remains under-explored. In an attempt to make up for the gap in the generalization theory of MDC, we establish an effective unified theoretical framework, which makes it possible to analyze the generalization of MDC using existing theoretical results. However, the generalization bounds induced by existing theoretical results are vacuous for MDC. To this end, we introduce two decomposition operators and exploit the Lipschitz continuity of loss functions to develop novel vector-contraction inequalities, and derive tight generalization bounds with a logarithmic dependency on the maximum number of classes and with square-root and logarithmic dependency on the number of dimensions, respectively. In addition, we derive generalization bounds for prediction models of different architectures, which reveal the impact of various architectures on generalization bounds. Our tight generalization bounds without strong assumptions explain the good generalization ability of MDC.