2025/06/17 by Zihan Zhang, Lei Shi, Zhang, Zihan +3
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2506.14899
openalex publication_date 2025/06/17 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28
In this paper, we study the binary classification problem on [0,1]d under the Tsybakov noise condition (with exponent s ∈ [0,∞]) and the compositional assumption. This assumption requires the conditional class probability function of the data distribution to be the composition of q+1 vector-valued multivariate functions, where each component function is either a maximum value function or a Hölder-β smooth function that depends only on d_* of its input variables. Notably, d_* can be significantly smaller than the input dimension d. We prove that, under these conditions, the optimal convergence rate for the excess 0-1 risk of classifiers is ( (1)/(n) )^\fracβ⋅(1\wedgeβ)q(d_*)/(s+1)+(1+(1)/(s+1))⋅β⋅(1\wedgeβ)q, which is independent of the input dimension d. Additionally, we demonstrate that ReLU deep neural networks (DNNs) trained with hinge loss can achieve this optimal convergence rate up to a logarithmic factor. This result provides theoretical justification for the excellent performance of ReLU DNNs in practical classification tasks, particularly in high-dimensional settings. The generalized approach is of independent interest.