{"ID":6537407,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.11719","arxiv_id":"2607.11719","title":"A uniform relative deviation inequality for VC-subgraph classes","abstract":"We establish a new Bernstein-type deviation inequality for classes of functions whose complexity is characterized through subgraphs. The inequality is non-asymptotic, involves explicit constants, and features a relative normalization by the probability level. Applied to kernel density estimation, it produces a location and bandwidth-adaptive error bound between the estimator and the smoothed density, holding simultaneously over all points on the real line and all positive bandwidths. The proof is elementary, combining a new symmetrization principle, which incorporates the relative normalization, with the maximal sub-Gaussian inequality, and requires neither concentration nor entropy-integral arguments. When specialized to classes of sets, our technique improves the constants in the classical Vapnik-Chervonenkis inequality with relative deviation of Anthony and Shawe-Taylor (1993), reducing the factor 4 S A (2n) to S A (2n) in the right-tail inequality and to 3 S A (2n) in the left-tail inequality.","short_abstract":"We establish a new Bernstein-type deviation inequality for classes of functions whose complexity is characterized through subgraphs. The inequality is non-asymptotic, involves explicit constants, and features a relative normalization by the probability level. Applied to kernel density estimation, it produces a location...","url_abs":"https://arxiv.org/abs/2607.11719","url_pdf":"https://arxiv.org/pdf/2607.11719v1","authors":"[\"François Portier\"]","published":"2026-07-13T15:45:48Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"math.PR\"]","methods":"[]","has_code":false}