Entropy Regularization in the Mean-Field Free-Energy Machine for Combinatorial Optimization

The free-energy machine (FEM) relaxes discrete combinatorial optimization by minimizing expected energy plus a temperature-dependent negative-entropy penalty over product distributions. This contribution investigates the computational and mathematical role of that entropy term. At high temperature, entropy drives the optimizer toward the uniform product law; explicit relative-entropy and total-variation bounds quantify this effect, while an influence condition and a restricted Hessian characterize uniqueness, contraction, and the first possible loss of stability. As temperature decreases, the entropy coefficient vanishes. Uniform and variational convergence then connect free energy to the original discrete objective, obtaining an inverse-temperature excess-energy bound, ground-state concentration, and entropy selection among degenerate optima. Extraction bounds, path tracking, perturbation stability, and factorwise complexity further distinguish the effects of entropy, annealing, and replica selection. A batched annealed FEM algorithm is evaluated on exactly enumerable Ising, MaxCut, and Max-3SAT instances; the results reveal the predicted entropy-to-energy transition and show problem-dependent benefits of annealing and replication. For empirical-loss energies, a PAC-Bayes inequality additionally calibrates inverse temperature to sample size. The analysis characterizes entropy-dominated, instability, and energy-dominated regimes without attributing global guarantees to the nonconvex optimizer.