Back to Search
Start Over
Sample Compression Schemes for Balls in Graphs
- Source :
- [Research Report] CISPA Helmholtz Center for Information Security, Saarbrücken, Germany; Aix-Marseile Université, France. 2022, MFCS 2022--47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022--47th International Symposium on Mathematical Foundations of Computer Science, 2022, Vienna, Austria. pp.31:1--31:14, ⟨10.4230/LIPIcs.MFCS.2022.31⟩
- Publication Year :
- 2022
- Publisher :
- HAL CCSD, 2022.
-
Abstract
- One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size~$O(d)$. In this paper, we study this problem for balls in graphs. For balls of arbitrary radius $r$, we design proper sample compression schemes of size $2$ for trees, of size $3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of cycles, and of size $22$ for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size $2$ for trees and of size $4$ for interval graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.<br />Comment: 26 pages, 9 figures
- Subjects :
- FOS: Computer and information sciences
Computer Science - Machine Learning
Discrete Mathematics (cs.DM)
Theory of computation → Machine learning theory
Mathematics of computing → Graph algorithms
Sample Compression Schemes
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Machine Learning (cs.LG)
VC-dimension
Proper Sample Compression Schemes
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Balls
Graph algorithms
Machine learning theory phrases
Graphs
Theory of computation
Computer Science - Discrete Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- [Research Report] CISPA Helmholtz Center for Information Security, Saarbrücken, Germany; Aix-Marseile Université, France. 2022, MFCS 2022--47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022--47th International Symposium on Mathematical Foundations of Computer Science, 2022, Vienna, Austria. pp.31:1--31:14, ⟨10.4230/LIPIcs.MFCS.2022.31⟩
- Accession number :
- edsair.doi.dedup.....039bd19761d383e2e26559cb2b4dc038