An improved uniform convergence bound with fat-shattering dimension

Roberto Colomboni; Emmanuel Esposito; Andrea Paudice

doi:10.1016/j.ipl.2024.106539

An improved uniform convergence bound with fat-shattering dimension

Roberto Colomboni, Emmanuel Esposito, Andrea Paudice^*

^*Corresponding author for this work

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

1 Citation (Scopus)

Abstract

The fat-shattering dimension characterizes the uniform convergence property of real-valued function classes. The state-of-the-art upper bounds in [6] feature a multiplicative squared logarithmic factor on the sample complexity, leaving an open gap with the existing lower bound. By relying on a refined packing number bound given in [20], we provide an improved uniform convergence bound that closes this gap.

Original language	English
Article number	106539
Number of pages	6
Journal	Information Processing Letters
Volume	188
Early online date	31 Oct 2024
DOIs	https://doi.org/10.1016/j.ipl.2024.106539
Publication status	Published - 1 Feb 2025

Bibliographical note

Publisher Copyright:
© 2024 Elsevier B.V.

Keywords

Chaining
Fat-shattering dimension
Uniform convergence

Access to Document

10.1016/j.ipl.2024.106539

Handle.net

Persistent link

Cite this

@article{ad8cde48a0a342d99776537206c97508,

title = "An improved uniform convergence bound with fat-shattering dimension",

abstract = "The fat-shattering dimension characterizes the uniform convergence property of real-valued function classes. The state-of-the-art upper bounds in [6] feature a multiplicative squared logarithmic factor on the sample complexity, leaving an open gap with the existing lower bound. By relying on a refined packing number bound given in [20], we provide an improved uniform convergence bound that closes this gap.",

keywords = "Chaining, Fat-shattering dimension, Uniform convergence",

author = "Roberto Colomboni and Emmanuel Esposito and Andrea Paudice",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V. ",

year = "2025",

month = feb,

day = "1",

doi = "10.1016/j.ipl.2024.106539",

language = "English",

volume = "188",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - An improved uniform convergence bound with fat-shattering dimension

AU - Colomboni, Roberto

AU - Esposito, Emmanuel

AU - Paudice, Andrea

PY - 2025/2/1

Y1 - 2025/2/1

N2 - The fat-shattering dimension characterizes the uniform convergence property of real-valued function classes. The state-of-the-art upper bounds in [6] feature a multiplicative squared logarithmic factor on the sample complexity, leaving an open gap with the existing lower bound. By relying on a refined packing number bound given in [20], we provide an improved uniform convergence bound that closes this gap.

AB - The fat-shattering dimension characterizes the uniform convergence property of real-valued function classes. The state-of-the-art upper bounds in [6] feature a multiplicative squared logarithmic factor on the sample complexity, leaving an open gap with the existing lower bound. By relying on a refined packing number bound given in [20], we provide an improved uniform convergence bound that closes this gap.

KW - Chaining

KW - Fat-shattering dimension

KW - Uniform convergence

U2 - 10.1016/j.ipl.2024.106539

DO - 10.1016/j.ipl.2024.106539

M3 - Article (Academic Journal)

AN - SCOPUS:85208216203

SN - 0020-0190

VL - 188

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106539

ER -

An improved uniform convergence bound with fat-shattering dimension

Abstract

Bibliographical note

Keywords

Access to Document

Handle.net

Fingerprint

Cite this