Random coloured digraphs defined by a Markov logic network

• URL: http://arxiv.org/abs/2606.23715v1
• Date: Tue, 16 Jun 2026 11:49:14 GMT
• Title: Random coloured digraphs defined by a Markov logic network
• Abstract summary: An MLN consists of soft constraints with associated weights which are nonnegative real numbers.<n>We consider a language speaking about a property $P(x)$ and a relation $(x, y)R.<n>For every choice of weights, if the weights are scaled by $1/n$ then for every first-order $varphi$ the probability that $varphi$ holds tends to either 0 or 1 as $n to in relational; that is, a 0-1 law for first-order logic holds.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A Markov Logic Network (MLN) is a probabilistic relational model used in Statistical Relational Artificial Intelligence for defining a probability distribution on the set of possible worlds with domain $D$ for an arbitrary finite domain $D$. An MLN consists of soft constraints with associated weights which are nonnegative real numbers. In this study we consider a language speaking about a property $P(x)$ and a relation $R(x, y)$. We consider an MLN for which every Boolean combination of $P(x)$ and $R(x, y)$ is a soft constraint (with associated weight). Let $n$ denote the size (cardinality) of the domain. We show that, for every choice of weights, if the weights are scaled by $1/n$ then, for every first-order sentence $\varphi$, the probability that $\varphi$ holds tends to either 0 or 1 as $n \to \infty$; that is, a 0-1 law for first-order logic holds. Morover, the limit probability does {\em not} depend on the weights. If we instead use the standard semantics of MLNs, in the case of which the weights are {\em not} scaled, then the limit behaviour is more complicated and {\em depends} on the weights. With unscaled weights we get 7 qualitatively different cases which depend on the weights. In some cases we have a 0-1 law for first-order logic, in some cases not, but we may still have a convergence law. The influence of the weights on the asymptotic probability of a first-order sentence may be in the form of a sudden ``phase transition'' from one of the 7 cases to another. The presence of a convergence law has positive implications for inference on large domains.

Related papers

• Bias-Induced Crossover in Absolute Capacity of Dense Associative Memory [0.0]
  Asymptotic matching predicts a bias-induced crossover in the region $1-2q=O( N/Nl n/2rfloor-1)$.<n>Activity-dependent control potential that cancels the conditional crosstalk mean restores the $Nn-1/ln N$ capacity for fixed $0q1/2$.
  arXiv  Detail & Related papers  (2026-09-15T17:16:38Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck, Li and Nagaraj conjectured that, for generic data, any two-layer neural network with $m$ neurons that fits noisy labels must have Lipschitz constant.<n>We prove the conjectured law, up to one logarithmic factor, for every continuous piecewise-linear activation in particular for ReLU networks.
  arXiv  Detail & Related papers  (2026-07-08T17:44:15Z)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability.<n>Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning.<n>We also highlight several open questions on quantitative sample complexity and evaluability.
  arXiv  Detail & Related papers  (2026-05-13T15:41:30Z)
• Domain size asymptotics for Markov logic networks [0.0]
  A Markov logic network (MLN) determines a probability distribution on the set of structures.<n>We study the properties of such distributions as the domain size tends to infinity.
  arXiv  Detail & Related papers  (2025-09-04T13:15:02Z)
• Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
  We study a federated linear bandits model, where $M$ clients communicate with a central server to solve a linear contextual bandits problem. To address the unique challenges of adversarial finite action sets, we propose the FedSupLinUCB algorithm. We prove that FedSupLinUCB achieves a total regret of $tildeO(sqrtd T)$, where $T$ is the total number of arm pulls from all clients, and $d$ is the ambient dimension of the linear model.
  arXiv  Detail & Related papers  (2023-11-02T03:41:58Z)
• A Neural Scaling Law from Lottery Ticket Ensembling [19.937894875216507]
  Sharma & Kaplan predicted that MSE losses decay as $N-alpha$, $alpha=4/d$, where $N$ is the number of model parameters, and $d$ is the intrinsic input dimension. We find that a simple 1D problem manifests a different scaling law ($alpha=1$) from their predictions.
  arXiv  Detail & Related papers  (2023-10-03T17:58:33Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)
• Multicalibrated Partitions for Importance Weights [17.1726078570842]
  importance weights play a fundamental role in many different fields, most notably, statistics and machine learning. We show that the MaxEntropy approach may fail to assign high average scores to sets $C in mathcalC$, even when the average of ground truth weights for the set is evidently large. We present an efficient algorithm that under standard learnability assumptions computes weights which satisfy these bounds.
  arXiv  Detail & Related papers  (2021-03-10T03:32:36Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  We analyze the linear bandits with heavy-tailed payoffs, where the payoffs admit finite $1+epsilon$ moments. We propose two novel algorithms which enjoy a sublinear regret bound of $widetildeO(dfrac12Tfrac11+epsilon)$.
  arXiv  Detail & Related papers  (2020-04-28T13:01:38Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.