cs.LGNov 18, 2026

Continuous Noisy-Loop Models

Authors: An T. Le

Organizations: Center for AI Research, VinUniversity Vinhomes Ocean Park, Gia Lam, Hanoi, Vietnam · Intelligent Autonomous Systems, TU Darmstadt Hochschulstrasse 10, 64289 Darmstadt, Germany

Abstract

Efficient learning and inference need not imply a compact probabilistic circuit. We quantify this distinction for continuous noisy readings of agreement between adjacent latent spins on a known square grid with dd edges. With known margins and bounded Lipschitz channels, minimax squared Hellinger risk is Θ(min⁡{1,dN−2/3})Θ(\min\{1,dN^{-2/3}\}) from NN independent vectors, without a reliability lower bound. A spline estimator reaches this rate in polynomial arithmetic time given a fixed positive reliability bound; an exponential-size mixture removes that requirement. At fixed positive reliability, nonnegative decomposable circuits need exp⁡(Θ(d))\exp(Θ(\sqrt d)) nodes for fixed total-variation error below one, even when each leaf uses at most αdαd coordinates, 0<α<10<α<1. Optimal Kullback--Leibler (KL) approximation error is Θ(d/max⁡{log⁡d,ℓ})Θ(d/\max\{\log d,\sqrt\ell\}) in either direction with at most drd^r nodes and leaf scopes ℓ≤αd\ell\leqαd, for fixed r>1r>1 and 0<α<2/30<α<2/3. Node counts exclude leaf computation. For three fixed masks, optimal joint conditional KL has order d/log⁡dd/\log d when ℓ≤(log⁡d)2\ell\leq(\log d)^2. Local cycle identities relate joint divergence to identifiable channel products and separate weak-channel recovery from density estimation. Factorized evidence preserves a planar zero-field Ising model: given local integrals, exact queries cost O(d3/2)O(d^{3/2}) arithmetic operations and one root extraction.

Figures & tables

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Feb 12, 2026

Computationally sufficient statistics for Ising models

Learning Gibbs distributions using only sufficient statistics has long been recognized as a computationally hard problem. On the other hand, computationally efficient algorithms for learning Gibbs distributions rely on access to full sample configurations generated from the model. For many systems of interest that arise in physical contexts, expecting a full sample to be observed is not practical, and hence it is important to look for computationally efficient methods that solve the learning problem with access to only a limited set of statistics. We examine the trade-offs between the power of computation and observation within this scenario, employing the Ising model as a paradigmatic example. We show that the couplings of the model can be learned to a desired accuracy from statistics whose order grows linearly with the ℓ1\ell_1 width of the model and only logarithmically with the inverse of the accuracy. In particular, for a fixed accuracy, the required order is proportional to the width. This allows us to infer the model's structure, using statistics whose order grows logarithmically with the inverse of the weakest coupling, and also to learn its magnetic fields. When the width and the accuracy are fixed, the running time is polynomial in the number of variables. We also discuss a setting where prior information about structure of the model is available and show that the learning problem can be solved efficiently with even more limited observational power.
Oct 9, 2026

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity k\boldsymbol{k}, defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order O(ln⁡N/N)O(\sqrt{\ln N/N}) above k/N\boldsymbol{k}/N. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level 1−δ1-δ, the risk is bounded with probability at least 1−δ1-δ by kN+O(1N),\frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right), uniformly over all possible values of k\boldsymbol{k}. Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term k/N\boldsymbol{k}/N is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the O(1/N)O(1/\sqrt{N}) convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the O(1/N)O(1/\sqrt{N}) rate.
Sep 22, 2026

Statistical Gains from Looped Estimation under Parameter Budgets

Memory constraints in artificial intelligence motivate accurate function approximation with fewer parameters. We study looping, which repeatedly composes one update function with shared parameters; each output becomes the next input. A looped Transformer, for example, reuses one block, whereas its conventional untied counterpart uses separately parameterized blocks. We compare their parameter requirements for a given worst-case approximation accuracy, or equivalently, their approximation accuracy under a common budget limiting distinct trainable coefficients. We then ask whether this representational parsimony improves statistical accuracy. For general likelihood models, we establish an upper squared Hellinger risk bound for looped sieve maximum likelihood and a minimax lower bound for the jointly tuned untied family. Further loop iterations improve the approximation bound without adding parameters, while increasing computation and the fitted-class complexity bound. For targets of known Hölder smoothness, looped residual feedforward networks and post-layer-normalized Transformers attain the minimax polynomial rate up to logarithmic factors with a fixed number of bounded real parameters. At sufficiently large fixed budgets, looped worst-case risk vanishes while optimal worst-case untied risk remains bounded away from zero. The loop-to-untied risk ratio also tends to zero under specified growing-budget conditions. Regression, binary response, and energy-based generative models illustrate the theory.