Article
Computer Science, Artificial Intelligence
Matthias C. Caro
Summary: Currently, there is no general-purpose procedure to evaluate whether a machine learning model can successfully learn from data. Through computational proofs, we show that for certain learning problems, learnability is undecidable, both in terms of independence of axioms and computability. This implies that we cannot automate the process of assessing new learning models.
INTERNATIONAL JOURNAL OF APPROXIMATE REASONING
(2023)
Article
Mathematics
Hunter Chase, James Freitag
Summary: We establish a general context for proving Sauer-Shelah type lemmas and apply it to answer a question and improve an existing result. We also prove a new Sauer-Shelah type lemma in the context of op-rank.
JOURNAL OF SYMBOLIC LOGIC
(2022)
Article
Computer Science, Hardware & Architecture
Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, Shay Moran
Summary: H, a binary-labeled concept class, can be PAC learned by an (approximate) differentially private algorithm if and only if it has a finite Littlestone dimension, showing a qualitative equivalence between online learnability and private PAC learnability.
JOURNAL OF THE ACM
(2022)
Article
Automation & Control Systems
Valeria Fonseca Diaz, Bart De Ketelaere, Ben Aernouts, Wouter Saeys
Summary: This study aims to select the most informative calibration samples in an unsupervised way based on spectral measurements by providing guidelines for addressing challenges in PLSR model building. Recommendations include calculating a sample size exceeding the model complexity by a factor of 12, performing selection in a PCA score space with a sufficient number of principal components, and using methods such as Kennard-Stone.
CHEMOMETRICS AND INTELLIGENT LABORATORY SYSTEMS
(2021)
Article
Automation & Control Systems
Shaun Fallat, David Kirkpatrick, Hans U. Simon, Abolghasem Soltani, Sandra Zilles
Summary: This paper introduces a new teaching model called no-clash teaching and proves its optimality in the strong sense. It also studies the corresponding concept for learning from positive data only and discusses the relationship between these parameters and other complexity parameters in computational learning theory. Furthermore, a stricter notion of collusion-avoidance is introduced, and it is demonstrated that preference-based teaching is the optimal choice among all teaching schemes that strongly avoid collusion.
JOURNAL OF MACHINE LEARNING RESEARCH
(2022)
Article
Computer Science, Artificial Intelligence
Giulia Preti, Gianmarco De Francisci Morales, Matteo Riondato
Summary: We propose a sampling-based randomized algorithm called MANIACS for computing high-quality approximations of frequent subgraph patterns in large vertex-labeled graphs. MANIACS provides strong probabilistic guarantees by using the empirical VC dimension and probabilistic tail bounds. It leverages the MNI frequency properties to aggressively prune the pattern search space, resulting in faster exploration of subspaces without frequent patterns. Experimental evaluation shows that MANIACS returns high-quality collections of frequent patterns in large graphs up to two orders of magnitude faster than the exact algorithm.
ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY
(2023)
Article
Mathematics, Applied
G. Conant, A. Pillay, C. Terry
Summary: The paper investigates the structural characteristics of subsets A in a finite group with VC-dimension less than k, using algebraically well-structured sets to describe the structure of A and considering normal subgroups with bounded index in terms of k, r, and ε for groups with a uniformly fixed finite exponent r. For nonabelian groups, the introduction of Bohr neighborhoods involves model-theoretic methods and structural analysis of compactifications of pseudofinite groups, as well as results related to approximate homomorphisms.
JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY
(2022)
Article
Mathematics, Applied
Pieter Kleer, Hans Simon
Summary: We provide tight bounds on the relation between the primal and dual of various combinatorial dimensions for multi-valued function classes. These dimensions are important in the field of learning theory. We review classical results that bound the dual dimension of a function class based on its primal, and introduce almost matching lower bounds. Furthermore, we generalize Assouad's well-known bound on primal and dual VC-dimensions of binary function classes to multi-valued function classes.
DISCRETE APPLIED MATHEMATICS
(2023)
Proceedings Paper
Computer Science, Theory & Methods
Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran
Summary: This paper extends the classical theory of PAC learning to model practical learning tasks where data has special properties. By considering partial concepts, it allows expressing assumptions on the data and reveals a different algorithmic landscape compared to the traditional PAC theory. The paper also addresses the limitations of the traditional theory and suggests future research directions.
2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021)
(2022)
Article
Computer Science, Artificial Intelligence
Vladimir Vapnik, Rauf Izmailov
Summary: The paper explores reinforcement of SVM algorithms and justification of memorization mechanisms for generalization. It introduces modifications to existing SVM algorithms to improve classification performance. VC theory provides bounds for relative uniform convergence, aiding in more accurate estimate of the expected loss.
PATTERN RECOGNITION
(2021)
Article
Mathematics
Vincent Guingona
Summary: This article establishes an upper bound for the VC-density of formulas with two free variables in a Vapnik-Chervonenkis (VC) minimal theory. By slightly modifying the argument, a new proof is provided to show that in a VC-minimal theory where acl(eq) = dcl(eq), the VC-density of a formula is at most the number of free variables.
NOTRE DAME JOURNAL OF FORMAL LOGIC
(2022)
Article
Mathematics
Jacob Fox, Janos Pach, Andrew Suk
Summary: According to the famous conjecture of Erdos and Rado, for families F with bounded VC-dimension, if |F| >= 2(10k(dr)2 log* k), then F contains an r-sunflower.
Article
Computer Science, Theory & Methods
Joel Ratsaby
Summary: This paper investigates the VC-dimension of the class of half-spaces in an infinite distance space chi, where no assumptions about the distance function are made and the metric axioms need not be satisfied. It is not clear what the VC-dimension of Hof half-spaces in chi may be and if there are generalization error bounds for learning H. The authors define a combinatorial dimension of chi as the independence number of the class of balls in chi and compute it for different types of distance spaces. They then use this dimension to provide a generalization error bound for learning H in any infinite distance space chi.
INFORMATION AND COMPUTATION
(2023)
Article
Mathematics, Applied
Isolde Adler, Bjarki Geir Benediktsson, Dugald Macpherson
Summary: VC-dimension and VC-density are measures of combinatorial complexity of set systems. This paper studies the VC-dimension and VC-density of the edge relation Exy on Johnson graphs and Hamming graphs, and provides corresponding bounds. The results show that the VC-dimension and VC-density of Johnson graphs and Hamming graphs are finite.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Statistics & Probability
Man Fung Leung, Yiqi Lin, Nicolas Wicker
Summary: This paper corrects the learning risk lower bound in the non-realizable case provided by Anthony and Bartlett in 1999. The main contribution is the technical corrections made to their proof, including correcting the lemma used and adapting the lower bound proof itself.
COMMUNICATIONS IN STATISTICS-THEORY AND METHODS
(2023)
Article
Computer Science, Hardware & Architecture
John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
(2015)
Article
Computer Science, Information Systems
Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
(2017)
Article
Computer Science, Information Systems
Matteo Riondato, Eli UPfal
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
(2018)
Article
Computer Science, Artificial Intelligence
Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, Eli Upfal
Article
Computer Science, Artificial Intelligence
Alessandro Epasto, Eli Upfal
Proceedings Paper
Computer Science, Information Systems
Zheguang Zhao, Lorenzo De Stefani, Emanuel Zgraggen, Carsten Binnig, Eli Upfal, Tim Kraska
SIGMOD'17: PROCEEDINGS OF THE 2017 ACM INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA
(2017)
Proceedings Paper
Computer Science, Information Systems
Zheguang Zhao, Emanuel Zgraggen, Lorenzo De Stefani, Carsten Binnig, Eli Upfal, Tim Kraska
SIGMOD'17: PROCEEDINGS OF THE 2017 ACM INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA
(2017)
Proceedings Paper
Telecommunications
Megumi Ando, Eli Upfal
2017 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS (ICC)
(2017)
Article
Computer Science, Information Systems
Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, Eli Upfal
PROCEEDINGS OF THE VLDB ENDOWMENT
(2017)
Proceedings Paper
Computer Science, Information Systems
Cyrus Cousins, Eli Upfal
2017 IEEE INTERNATIONAL CONFERENCE ON DATA SCIENCE AND ADVANCED ANALYTICS (DSAA)
(2017)
Proceedings Paper
Computer Science, Hardware & Architecture
Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, Eli Upfal
2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016)
(2016)
Proceedings Paper
Computer Science, Artificial Intelligence
Ahmad Mahmoody, Matteo Riondato, Eli Upfal
PROCEEDINGS OF THE NINTH ACM INTERNATIONAL CONFERENCE ON WEB SEARCH AND DATA MINING (WSDM'16)
(2016)
Proceedings Paper
Computer Science, Interdisciplinary Applications
Ahmad Mahmoody, Evgenios M. Kornaropoulos, Eli Upfal
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015)
(2015)
Proceedings Paper
Computer Science, Hardware & Architecture
Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, Eli Upfal
SPAA'15: PROCEEDINGS OF THE 27TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES
(2015)