Optimal Approximations Made Easy

• URL: http://arxiv.org/abs/2008.08970v3
• Date: Thu, 1 Sep 2022 13:24:04 GMT
• Title: Optimal Approximations Made Easy
• Abstract summary: The goal of this paper is to give a modular, self-contained, intuitive proof of this result for finite set systems. This makes the proof accessible to a wider audience, readers not familiar with techniques from statistical learning theory, and makes it possible to be covered in a single self-contained lecture.
• Score: 1.2183405753834562
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The fundamental result of Li, Long, and Srinivasan on approximations of set systems has become a key tool across several communities such as learning theory, algorithms, computational geometry, combinatorics and data analysis. The goal of this paper is to give a modular, self-contained, intuitive proof of this result for finite set systems. The only ingredient we assume is the standard Chernoff's concentration bound. This makes the proof accessible to a wider audience, readers not familiar with techniques from statistical learning theory, and makes it possible to be covered in a single self-contained lecture in a geometry, algorithms or combinatorics course.

Related papers

• Efficient Learning and Symmetry Discovery under Exact Invariances [62.27019402162741]
  Learning with group invariances is central to many scientific and geometric learning problems.<n>It has been unclear whether one can efficiently compute a regression function that is exactly in subgroup to a given group action.<n>We present the first-time algorithm for learning with exact group invariants that applies uniformly to finite and infinite groups.
  arXiv  Detail & Related papers  (2026-09-07T04:35:19Z)
• Mapping Uncharted Symmetries: Machine Discovery in Combinatorics [38.59031747973091]
  We show that modern machine learning can meaningfully contribute to verifiable mathematical discoveries.<n>In particular, we focus on the construction of simple mathematical functions under exact distributional constraints.<n>We find a new interpretation of $q,t$-Narayanas arising from representation theory.
  arXiv  Detail & Related papers  (2026-05-18T19:36:08Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  Learning intersections of halfspaces is a central problem in Computational Learning Theory.<n>Even for just two halfspaces, it remains a major open question whether learning is possible in time.<n>We introduce a novel algorithm that provably circumvents the CSQ hardness barrier.
  arXiv  Detail & Related papers  (2025-11-13T00:28:24Z)
• Algebraic Machine Learning: Learning as computing an algebraic decomposition of a task [41.94295877935867]
  We propose an alternative foundation based on Abstract Algebra, with mathematics that facilitates the analysis of learning. In this approach, the goal of the task and the data are encoded as axioms of an algebra, and a model is obtained where only these axioms and their logical consequences hold. We validate this new learning principle on standard datasets such as MNIST, FashionMNIST, CIFAR-10, and medical images, achieving performance comparable to optimized multilayer perceptrons.
  arXiv  Detail & Related papers  (2025-02-27T10:13:42Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  A key challenge in machine learning is the prevalence of one-sided feedback.<n>We introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels.<n>We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• A Margin-Maximizing Fine-Grained Ensemble Method [42.44032031918387]
  This paper introduces an innovative "Margin-Maximizing Fine-Grained Ensemble Method" It achieves performance surpassing large-scale ensembles by meticulously optimizing a small number of learners and enhancing generalization capability. Our method outperforms traditional random forests using only one-tenth of the base learners and other state-of-the-art ensemble methods.
  arXiv  Detail & Related papers  (2024-09-19T15:48:12Z)
• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learning is a novel unified framework for learning with neural networks "over time" It is based on differential equations that: (i) can be integrated without the need of external software solvers; (ii) generalize the well-established notion of gradient-based learning in feed-forward and recurrent networks; (iii) open to novel perspectives.
  arXiv  Detail & Related papers  (2024-09-18T14:57:13Z)
• Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
  Ensemble learning is a method that leverages weak learners to produce a strong learner. We design a smooth and convex objective function that leverages the concept of margin, making the strong learner more discriminative. We then compare our algorithm with random forests of ten times the size and other classical methods across numerous datasets.
  arXiv  Detail & Related papers  (2024-08-06T03:42:38Z)
• Relation-aware Ensemble Learning for Knowledge Graph Embedding [68.94900786314666]
  We propose to learn an ensemble by leveraging existing methods in a relation-aware manner. exploring these semantics using relation-aware ensemble leads to a much larger search space than general ensemble methods. We propose a divide-search-combine algorithm RelEns-DSC that searches the relation-wise ensemble weights independently.
  arXiv  Detail & Related papers  (2023-10-13T07:40:12Z)
• Context-Aware Ensemble Learning for Time Series [11.716677452529114]
  We introduce a new approach using a meta learner that effectively combines the base model predictions via using a superset of the features that is the union of the base models' feature vectors instead of the predictions themselves. Our model does not use the predictions of the base models as inputs to a machine learning algorithm, but choose the best possible combination at each time step based on the state of the problem.
  arXiv  Detail & Related papers  (2022-11-30T10:36:13Z)
• A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity [15.746613321517282]
  We give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric agnostic in probability. Surprisingly, we show that the information-theoretic complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class.
  arXiv  Detail & Related papers  (2022-11-23T21:29:51Z)
• Equivariance with Learned Canonicalization Functions [77.32483958400282]
  We show that learning a small neural network to perform canonicalization is better than using predefineds. Our experiments show that learning the canonicalization function is competitive with existing techniques for learning equivariant functions across many tasks.
  arXiv  Detail & Related papers  (2022-11-11T21:58:15Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  We develop a flexible approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite) The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, exponential/multiplicative weights for learning in finite games, optimistic and bandit variants of the above, etc.
  arXiv  Detail & Related papers  (2022-06-08T14:30:38Z)
• Free Probability, Newton lilypads and Jacobians of neural networks [0.0]
  We present a reliable and very fast method for computing the associated spectral densities. Our technique is based on an adaptative Newton-Raphson scheme, by finding and chaining basins of attraction.
  arXiv  Detail & Related papers  (2021-11-01T11:22:42Z)
• A Dataset-Level Geometric Framework for Ensemble Classifiers [0.76146285961466]
  Majority voting and weighted majority voting are two commonly used combination schemes in ensemble learning. We present a group of properties of these two combination schemes formally under a dataset-level geometric framework.
  arXiv  Detail & Related papers  (2021-06-16T09:48:12Z)
• Fast Few-Shot Classification by Few-Iteration Meta-Learning [173.32497326674775]
  We introduce a fast optimization-based meta-learning method for few-shot classification. Our strategy enables important aspects of the base learner objective to be learned during meta-training. We perform a comprehensive experimental analysis, demonstrating the speed and effectiveness of our approach.
  arXiv  Detail & Related papers  (2020-10-01T15:59:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.