The Implications of the No-Free-Lunch Theorems for Meta-induction

• URL: http://arxiv.org/abs/2103.11956v1
• Date: Mon, 22 Mar 2021 15:53:00 GMT
• Title: The Implications of the No-Free-Lunch Theorems for Meta-induction
• Authors: David H. Wolpert
• Abstract summary: The no-free-lunch theorems (NFL) have major implications for the problem of (meta) induction. There is a rich set of free lunches which instead concern the statistical correlations among the generalization errors of induction algorithms. The prior that Schurz advocates, which is uniform over bit frequencies rather than bit patterns, is contradicted by thousands of experiments in statistical physics.
• Score: 1.4431534196506413
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The important recent book by G. Schurz appreciates that the no-free-lunch theorems (NFL) have major implications for the problem of (meta) induction. Here I review the NFL theorems, emphasizing that they do not only concern the case where there is a uniform prior -- they prove that there are ``as many priors'' (loosely speaking) for which any induction algorithm $A$ out-generalizes some induction algorithm $B$ as vice-versa. Importantly though, in addition to the NFL theorems, there are many \textit{free lunch} theorems. In particular, the NFL theorems can only be used to compare the \textit{marginal} expected performance of an induction algorithm $A$ with the marginal expected performance of an induction algorithm $B$. There is a rich set of free lunches which instead concern the statistical correlations among the generalization errors of induction algorithms. As I describe, the meta-induction algorithms that Schurz advocate as a ``solution to Hume's problem'' are just an example of such a free lunch based on correlations among the generalization errors of induction algorithms. I end by pointing out that the prior that Schurz advocates, which is uniform over bit frequencies rather than bit patterns, is contradicted by thousands of experiments in statistical physics and by the great success of the maximum entropy procedure in inductive inference.

Related papers

• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  We construct an algorithm that returns a point $hat xin barmathcal X$ such that $f(hat x)$ is as small as possible. We prove that this method is such that the $f(hat x) - min_xin barmathcal X f(x)$ is of smaller order than $d2/sqrtn$ up to poly-logarithmic terms.
  arXiv  Detail & Related papers  (2024-06-26T18:19:10Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  We propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. We introduce two novel algorithms: Restarted Weighted$textOFUL+$ and Restarted $textSAVE+$. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary linear bandits under different settings.
  arXiv  Detail & Related papers  (2024-03-15T23:36:55Z)
• FRRI: a novel algorithm for fuzzy-rough rule induction [0.8575004906002217]
  We introduce a novel rule induction algorithm called Fuzzy Rough Rule Induction (FRRI) We provide background and explain the workings of our algorithm. We find that our algorithm is more accurate while creating small rulesets.
  arXiv  Detail & Related papers  (2024-03-07T12:34:03Z)
• A Unifying Framework for Differentially Private Sums under Continual Observation [20.432568247732206]
  We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for emphany sufficiently smoothangular function.
  arXiv  Detail & Related papers  (2023-07-18T05:04:11Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control [0.0]
  This note complements the paper "One-Way Ticket to Las Vegas and the Quantum Adversary" I develop the ideas behind the adversary bound - universal algorithm duality therein in a different form, using the same perspective as Barnum-Saks-Szegedy.
  arXiv  Detail & Related papers  (2022-11-29T15:25:45Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• What is important about the No Free Lunch theorems? [0.5874142059884521]
  The No Free Lunch theorems prove that under a uniform distribution over induction problems, all induction algorithms perform equally. The importance of the theorems arises by using them to analyze scenarios involving non-uniform' distributions. They also motivate a dictionary'' between supervised learning and improve blackbox optimization.
  arXiv  Detail & Related papers  (2020-07-21T16:42:36Z)
• A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
  We introduce a new type of minimax theorem which can provide a hard distribution $mu$ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, approximate degreelemma, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore.
  arXiv  Detail & Related papers  (2020-02-25T11:46:08Z)

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.