A combinatorial conjecture from PAC-Bayesian machine learning

• URL: http://arxiv.org/abs/2006.01387v2
• Date: Thu, 4 Jun 2020 21:02:29 GMT
• Title: A combinatorial conjecture from PAC-Bayesian machine learning
• Authors: M. Younsi, A. Lacasse
• Abstract summary: We present a proof of a conjecture from the second author's Ph.D. thesis. The proof relies on binomial and multinomial sums identities. We discuss the relevance of the conjecture in the context of PAC-Bayesian machine learning.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a proof of a combinatorial conjecture from the second author's Ph.D. thesis. The proof relies on binomial and multinomial sums identities. We also discuss the relevance of the conjecture in the context of PAC-Bayesian machine learning.

Related papers

• Learning Formal Mathematics From Intrinsic Motivation [34.986025832497255]
  Minimo is an agent that learns to pose problems for itself (conjecturing) and solve them (theorem proving) We combine methods for constrained decoding and type-directed synthesis to sample valid conjectures from a language model. Our agent targets generating hard but provable conjectures - a moving target, since its own theorem proving ability also improves as it trains.
  arXiv  Detail & Related papers  (2024-06-30T13:34:54Z)
• Machine Learning of the Prime Distribution [49.84018914962972]
  We provide a theoretical argument explaining the experimental observations of Yang-Hui He about the learnability of primes. We also posit that the ErdHos-Kac law would very unlikely be discovered by current machine learning techniques.
  arXiv  Detail & Related papers  (2024-03-19T09:47:54Z)
• Mathematical conjecture generation using machine intelligence [0.0]
  We focus on strict inequalities of type f g and associate them with a vector space. We develop a structural understanding of this conjecture space by studying linear automorphisms of this manifold. We propose an algorithmic pipeline to generate novel conjectures using geometric gradient descent.
  arXiv  Detail & Related papers  (2023-06-12T17:58:38Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  This paper contributes to the study of CPAC learnability by solving three open questions from recent papers. Firstly, we prove that every CPAC learnable class is contained in a class which is properly CPAC learnable with a sample complexity. Secondly, we show that there exists a decidable class of hypothesis which is properly learnable, but only with uncomputably fast growing sample complexity.
  arXiv  Detail & Related papers  (2023-02-06T02:52:36Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron [21.356438315715888]
  We consider the symmetric binary perceptron model, a simple model of neural networks. We establish several conjectures for this model. Our proof technique relies on a dense counter-part of the small graph conditioning method.
  arXiv  Detail & Related papers  (2021-02-25T18:39:08Z)
• Prove-It: A Proof Assistant for Organizing and Verifying General Mathematical Knowledge [0.0]
  We introduce Prove-It, a Python-based general-purpose interactive theorem-proving assistant. Prove-It uses a highly-flexible Jupyter notebook-based user interface that documents interactions and proof steps. Current development and future work includes promising applications to quantum circuit manipulation and quantum algorithm verification.
  arXiv  Detail & Related papers  (2020-12-20T18:15:12Z)
• Investigation of the PPT Squared Conjecture for High Dimensions [0.0]
  We present the positive-partial-transpose squared conjecture introduced by M. Christandl. We offer two novel approaches (decomposition and composition of quantum channels) and several schemes for finding counterexamples to this conjecture.
  arXiv  Detail & Related papers  (2020-10-27T16:26:57Z)
• Counterexamples to the Low-Degree Conjecture [80.3668228845075]
  A conjecture of Hopkins posits that for certain high-dimensional hypothesis testing problems, no-time algorithm can outperform so-called "simple statistics" This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs.
  arXiv  Detail & Related papers  (2020-04-17T21:08:11Z)
• On the complex behaviour of the density in composite quantum systems [62.997667081978825]
  We study how the probability of presence of a particle is distributed between the two parts of a composite fermionic system. We prove that it is a non-perturbative property and we find out a large/small coupling constant duality. Inspired by the proof of KAM theorem, we are able to deal with this problem by introducing a cut-off in energies that eliminates these small denominators.
  arXiv  Detail & Related papers  (2020-04-14T21:41:15Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.