PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameter Estimation for Unnormalized Discrete Models via Empirically Localized Deformed Bregman Divergence

Takashi Takenouchi

arXiv:2609.30713v1stat.MLcs.LG

TL;DR

Estimating discrete probabilistic models is difficult when normalization requires summing over a large state space. The paper combines empirical localization with deformed Bregman divergence to avoid that calculation, and reports Fisher consistency plus deformation choices for efficiency or robustness.

  • Problem

    For high-dimensional discrete models, exact evaluation of the partition function requires an exhaustive sum over 2^d states, making parameter estimation computationally difficult.

    Source: §1 · p. 1, §2.1 · p. 4

  • Method

    The estimator combines empirical localization with a deformed Bregman divergence to avoid calculating the normalization constant and expensive MCMC sampling.

    Source: §1 · pp. 2–3

  • Results

    The estimator is Fisher consistent across divergence and deformation choices, with suitable deformations yielding MLE-equivalent asymptotic efficiency or B-robustness against outlier noise.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The framework also provides a computationally feasible MAP-like estimator that incorporates prior domain knowledge.

    Source: §1 · p. 3

    The Bayesian-like localized-mixture estimator generally lacks Fisher consistency, and its efficiency or robustness depends on U and f.

    Source: §5 · p. 14

Abstract

from arXiv · show

Estimation of parameter of probabilistic models is an important task in the field of machine learning.For models of discrete variables, calculation of the normalization constant of model is sometimes difficult and a lot of researches have been done to avoid the calculation of the normalization constant. In this paper, we tackle with the difficulty by combining a technique of empirical localization and a deformed Bregman divergence.The technique of empirical localization makes it possible to drastically reduce computational cost of the calculation of the normalization constant, and in addition, appropriate choice of the deformation for the Bregman divergence can invest the proposed estimator with various kinds of favorable statistical properties, such as efficiency or robustness against outlier noise.

1 Introduction

Estimating discrete probabilistic models is computationally difficult when evaluating the partition function requires summing over a large state space. The paper combines empirical localization with a deformed Bregman divergence and extends the framework to a Bayesian-like MAP estimator.

1 Introduction

  • Prior alternatives include CD, NCE, discrete score matching [9], and MPF; CD lacks strong consistency guarantees unless its chain fully converges.Source: §1 · p. 2
  • The framework combines empirical localization with a deformed Bregman divergence, relaxing the prior localized estimator’s restriction to homogeneous γ-divergences.The authors also extend the framework to a Bayesian-like MAP estimator that incorporates prior domain knowledge.Source: §1 · p. 2
  • The estimator avoids calculating the normalization constant and performing expensive MCMC sampling.For high-dimensional binary state spaces, exact normalization requires summing over 2^d states.Source: §1 · pp. 1–3
  • The proposed estimator is Fisher consistent for any divergence and deformation, while deformation choices can yield MLE-equivalent asymptotic efficiency or B-robustness against outlier noise.B-robustness is described as bounded gross-error sensitivity.Source: §1 · p. 3
  • The Bayesian-like MAP extension incorporates prior domain knowledge in a computationally feasible estimator.Source: §1 · p. 3

2 Deformed Bregman divergence and Empirical localization

This section sets up unnormalized discrete models and introduces deformed Bregman divergence and empirical localization as tools for estimation without direct normalization.

2.1 Setup

  • For normalized models, MLE maximizes log likelihood, but evaluating it can be computationally demanding because it requires the normalization constant.The paper formulates the unnormalized model through a parameterized function ψθ and a partition function Zθ.Source: §2.1 · pp. 3–4

2.2 Deformed Bregman divergence

  • The deformed Bregman divergence is defined for positive measures using a strictly convex generating function U and increasing function f.The conventional Bregman divergence is recovered with f(z) = z, while the statistical version permits direct empirical-distribution plug-in; minimizing these divergences alone does not remove partition-function-scale computation.Source: §2.2 · p. 5

2.3 Empirical Localization

  • The empirically localized model is a probability distribution constructed only with the unnormalized model (2), because the normalization constant Zθ of q̄θ(x) cancels out.The term ˜rα,θ can be calculated only on the domain Z of observed examples, requiring O(n) summations; computation is drastically reduced compared with q̄θ or Zθ, which can be O(2d) for X = {±1}d.Source: §2.3 · p. 6

3 Proposed Estimator and statistical properties

The estimator minimizes a deformed Bregman divergence between empirically localized models, avoiding calculation of the normalization constant. Its statistical behavior can be tuned through the deformation and generating functions, with results on Fisher consistency, efficiency, and robustness.

3 Proposed Estimator and statistical properties

  • Empirical localization cancels the normalization constant and reduces the estimator’s computational cost to O(n) by ignoring unobserved examples.Source: §3 · p. 6

3.1 Information geometry of the proposed estimator

  • The estimator minimizes deformed Bregman divergence between two localized models lying between the empirical distribution and the model on an e-geodesic.Source: §3.1 · p. 7, Figure 1 · p. 7

3.2 Statistical Properties of Proposed estimator

  • The estimator is Fisher consistent regardless of the choices of U and f.Source: §3.2 · pp. 7–8
  • When f satisfies condition (11), the estimator is asymptotically efficient; its efficiency does not depend on α or α′.Source: §3.2 · pp. 8–9

3.3 Robust estimation with the deformed Bregman divergence

  • Under condition (18), the estimator has bounded gross-error sensitivity even when ψ diverges, yielding B-robustness against outlier noise.For Poisson and multivariate lattice Gaussian models, ψ′ may be unbounded and the influence function can diverge.Source: §3.3 · p. 11

4 Related works

The paper contrasts its estimator with empirical localization using γ-divergence, contrastive divergence, and minimum probability flow. Its stated distinctions are deformation-based flexibility, avoiding MCMC sampling, and asymptotic efficiency.

4.1 Relation with [28]

  • Unlike the γ-divergence estimator, which is restricted to homogeneous divergences, the proposed estimator uses deformation to offer flexibility between efficiency and robustness.Source: §4.1 · p. 12

4.2 Relation with contrastive divergence

  • Unlike contrastive divergence, which uses short MCMC trajectories, the proposed estimator uses empirical localization and does not require MCMC sampling.Source: §4.2 · p. 12

4.3 Relation with minimum probability flow

  • Although minimum probability flow avoids normalization-constant computation and MCMC sampling, its asymptotic efficiency is generally lower than that of the proposed estimator or MLE.Source: §4.3 · p. 13

5 Extension for Bayesian-like MAP Estimation

This extension adds prior knowledge to the empirically localized estimator through a regularized model and a deformed Bregman divergence. The prior function shapes the estimate, but the resulting mixture generally lacks Fisher consistency.

  • The MAP-like estimator minimizes a deformed Bregman divergence over a regularized localized model incorporating prior function η(x).The condition η(x) < qθ(x) restricts the feasible parameter space.Source: §5 · p. 13
  • With constant η(x), the localized model mixes the empirical distribution with the uniform distribution, corresponding potentially to a non-informative prior.Source: §5 · p. 14
  • The influence of η is controlled by ⟨η⟩Zθ0 and shifts the estimate from empirical ˜p toward normalized ¯η; this mixture generally lacks Fisher consistency.Source: §5 · pp. 14–15
  • An alternative regularized formulation requires summation over all points in X, losing computational tractability.Source: §5 · p. 15
  • In Figure 2, stronger c increases the prior’s influence, while the feasible parameter set is restricted.The example uses a Bernoulli distribution and varies c across 0.2, 0.5, 1, and 1.5.Source: §5 · p. 15

6 Experiments

The experiments assess efficiency and robustness using synthetic data. Efficient deformation versions match MLE estimation error with much lower computational time, while the robust version is less affected by added outlier noise.

6 Experiments

  • Two small synthetic experiments assessed statistical efficiency and robustness against outlier noise.Source: §6 · p. 16

6.1 Efficiency

  • With U(z) = exp(z) and f(z) = log z, MSE decreased as sample size increased, while computational time increased with observed-domain size.The tested sample sizes ranged from 50 to 12,800.Source: §6.1 · p. 16
  • Efficient versions of f attained estimation error comparable to MLE and drastically reduced computational time versus MLE.Across choices of U, efficient versions improved MSE over statistical versions of f.Source: §6.1 · pp. 16–17

6.2 Robustness

  • Without contamination, MLE outperformed the non-efficient robust estimator; with added outlier noise, the robust version was less affected while MLE worsened.Source: §6.2 · p. 17

7 Conclusions

The conclusion is that combining empirical localization with deformed Bregman divergence yields a computationally feasible estimator that avoids calculating the normalization constant and can be configured for efficiency or robustness.

  • Empirical localization combined with deformed Bregman divergence avoids normalization-constant calculation, while specific deformations provide asymptotic efficiency or robustness to outlier noise.Source: §7 · p. 17

Appendix A: Proof of Lemma 1

The proof analyzes the estimator under a small perturbation of the empirical distribution around the model distribution. It derives an asymptotic normal distribution for the estimator.

  • The proof starts from an empirical distribution written as the model distribution plus a small, zero-mean perturbation.Source: Appendix A · p. 22
  • The derivation uses a central-limit result for one term and convergence of the empirical distribution to the model as n increases.Source: Appendix A · pp. 24–26
  • The estimator asymptotically follows a normal distribution after scaling its error by √n.Source: Appendix A · p. 26
Loading 2609.30713v1…