Undecidability of Underfitting in Learning Algorithms

• URL: http://arxiv.org/abs/2102.02850v2
• Date: Mon, 8 Feb 2021 17:48:49 GMT
• Title: Undecidability of Underfitting in Learning Algorithms
• Authors: Sonia Sehra, David Flores, George D. Montanez
• Abstract summary: We prove that deciding whether an encodable learning algorithm will always underfit a dataset, even if given unlimited training time, is undecidable. We discuss the importance of this result and potential topics for further research, including information-theoretic and probabilistic strategies for bounding learning algorithm fit.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Using recent machine learning results that present an information-theoretic perspective on underfitting and overfitting, we prove that deciding whether an encodable learning algorithm will always underfit a dataset, even if given unlimited training time, is undecidable. We discuss the importance of this result and potential topics for further research, including information-theoretic and probabilistic strategies for bounding learning algorithm fit.

Related papers

• 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)
• Structured Prediction in Online Learning [66.36004256710824]
  We study a theoretical and algorithmic framework for structured prediction in the online learning setting. We show that our algorithm is a generalisation of optimal algorithms from the supervised learning setting. We consider a second algorithm designed especially for non-stationary data distributions, including adversarial data.
  arXiv  Detail & Related papers  (2024-06-18T07:45:02Z)
• Gauge-optimal approximate learning for small data classification problems [0.0]
  Small data learning problems are characterized by a discrepancy between the limited amount of response variable observations and the large feature space dimension. We propose the Gauge- Optimal Approximate Learning (GOAL) algorithm, which provides an analytically tractable joint solution to the reduction dimension, feature segmentation and classification problems. GOAL has been compared to other state-of-the-art machine learning (ML) tools on both synthetic data and challenging real-world applications from climate science and bioinformatics.
  arXiv  Detail & Related papers  (2023-10-29T16:46:05Z)
• Advancing continual lifelong learning in neural information retrieval: definition, dataset, framework, and empirical evaluation [3.2340528215722553]
  A systematic task formulation of continual neural information retrieval is presented. A comprehensive continual neural information retrieval framework is proposed. Empirical evaluations illustrate that the proposed framework can successfully prevent catastrophic forgetting in neural information retrieval.
  arXiv  Detail & Related papers  (2023-08-16T14:01:25Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• Latent Properties of Lifelong Learning Systems [59.50307752165016]
  We introduce an algorithm-agnostic explainable surrogate-modeling approach to estimate latent properties of lifelong learning algorithms. We validate the approach for estimating these properties via experiments on synthetic data.
  arXiv  Detail & Related papers  (2022-07-28T20:58:13Z)
• Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information [77.19830787312743]
  In real-world reinforcement learning applications the learner's observation space is ubiquitously high-dimensional with both relevant and irrelevant information about the task at hand. We introduce a new problem setting for reinforcement learning, the Exogenous Decision Process (ExoMDP), in which the state space admits an (unknown) factorization into a small controllable component and a large irrelevant component. We provide a new algorithm, ExoRL, which learns a near-optimal policy with sample complexity in the size of the endogenous component.
  arXiv  Detail & Related papers  (2022-06-09T05:19:32Z)
• Information-theoretic generalization bounds for black-box learning algorithms [46.44597430985965]
  We derive information-theoretic generalization bounds for supervised learning algorithms based on the information contained in predictions rather than in the output of the training algorithm. We show experimentally that the proposed bounds closely follow the generalization gap in practical scenarios for deep learning.
  arXiv  Detail & Related papers  (2021-10-04T17:28:41Z)
• Low-Regret Active learning [64.36270166907788]
  We develop an online learning algorithm for identifying unlabeled data points that are most informative for training. At the core of our work is an efficient algorithm for sleeping experts that is tailored to achieve low regret on predictable (easy) instances.
  arXiv  Detail & Related papers  (2021-04-06T22:53:45Z)
• An Information-Theoretic Perspective on Overfitting and Underfitting [0.0]
  We present an information-theoretic framework for understanding overfitting and underfitting in machine learning. We prove the formal undecidability of determining whether an arbitrary classification algorithm will overfit a dataset.
  arXiv  Detail & Related papers  (2020-10-12T23:24:47Z)

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.