artificialintelbulletin.com

Tag: math.ST

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

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

    [Submitted on 9 Oct 2026]

    View PDF HTML (experimental)

    Abstract: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 $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(sqrt{ln N/N})$ above $boldsymbol{k}/N$. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level $1-delta$, the risk is bounded with probability at least $1-delta$ by $$ frac{boldsymbol{k}}{N} + Oleft(frac{1}{sqrt{N}}right), $$ uniformly over all possible values of $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 $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/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/sqrt{N})$ rate.

    Submission history

    From: Simone Garatti [view email]
    [v1] Fri, 9 Oct 2026 11:44:43 UTC (24 KB)

  • Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure

    Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure

    [Submitted on 8 Oct 2026]

    View PDF HTML (experimental)

    Abstract:Masked diffusion models (MDMs) generate discrete data by iteratively unmasking multiple tokens in parallel using a learned mask predictor. Their output carries two errors: parallelization error due to parallel sampling, and estimation error from the mask predictor learned with finite samples. Existing theory treats these errors separately, and the available statistical bounds typically scale with the number $V^L$ of length-$L$ sequences over a vocabulary of size $V$, suffering from the curse of dimensionality. In this work, we establish end-to-end statistical guarantees showing that transformer-based MDMs learn structured distributions with a sample complexity governed by their latent structure. Specifically, we model this structure through mixtures of hidden Markov trees, which capture latent dependencies within components and heterogeneity across components. When the data distribution is well approximated by such a mixture, a transformer-based MDM with parallel unmasking schedules achieves $varepsilon$-accurate sampling in KL divergence with $widetilde{O}(LK_{mathrm{par}}/varepsilon)$ training samples, where $K_{mathrm{par}}$ is polynomial in $L$, $V$, the number of hidden states, and the number of mixture components. The transformer network and sampling procedure require no knowledge of the tree topologies or component parameters, thereby adapting to the unknown latent structure automatically. Overall, our results provide theoretical justification for the empirical effectiveness of MDMs on real-world data.

    Submission history

    From: Jingda Wu [view email]
    [v1] Thu, 8 Oct 2026 17:54:49 UTC (90 KB)