7 Minimax-Entropy Learning
7.1 Which features should a model include?
Maximum entropy (Chapter 5) answers a precise question: given a set of measured features, which model is least biased? It is silent on a prior question — which features should we measure at all?
Every model is a lossy compression that trades complexity against uncertainty. Include too few features and the model stays vague; include too many and it ceases to be a compression. For a fixed budget of features, we want the description that leaves the least uncertainty.
7.2 The minimax entropy principle
Starting from the minimum description length (MDL) principle (Grünwald 2007), two results follow in sequence. First, among all models consistent with a feature set \(F\), the shortest description is the maximum-entropy model (Feder 1986). Second, for such models the description length equals the model’s own entropy, \(L(P_F) = S(P_F)\). Choosing features to minimize description length therefore means choosing them to minimize that entropy.
The optimal features are the ones producing the maximum-entropy model with minimum entropy (Carcamo et al. 2025):
\[ F^{*} = \arg\min_{F}\; S(P_F), \qquad P_F = \arg\max_{P}\;\big\{\, S(P) \;:\; \mathbb{E}_P[f_\mu] = \langle f_\mu \rangle_{\exp},\; f_\mu \in F \,\big\}. \]
The nesting gives the principle its name: maximize entropy on the inside, minimize it on the outside. The best features are those that maximally constrain our expectations while leaving the model maximally random about everything unobserved. The principle was first proposed for texture modeling in computer vision (Zhu et al. 1997).
7.3 Three equivalent views
Minimizing \(S(P_F)\) optimizes three quantities at once. In what follows, \(P_{\text{true}}\) denotes the distribution that actually generated the data, and \(P_{\text{ind}}\) the featureless baseline model in which the variables are treated as independent.
- Shortest description. Since \(L(P_F) = S(P_F)\), the optimum is the most compressed account of the data.
- Closest to the truth. The entropy gap to the true distribution is exactly a divergence, \(S(P_F) - S(P_{\text{true}}) = D_{\mathrm{KL}}(P_{\text{true}} \Vert P_F)\), so the optimum is also the most accurate model.
- Most informative features. The information carried by the selected features, \(I_F = S(P_{\text{ind}}) - S(P_F)\), is maximized at the same point.
Compression, accuracy, and informativeness coincide — a reassuring sign that the criterion is the right one.
7.4 Solving it
The difficulty is combinatorial. Each candidate feature set requires solving a maximum-entropy problem for its parameters, and the number of candidate sets grows super-exponentially, so brute-force search is infeasible beyond small systems (Carcamo et al. 2025). The practical workhorse is a greedy algorithm that repeatedly adds whichever remaining feature reduces the entropy most.
Structure sometimes restores exactness. For trees of pairwise correlations the entropy reduction decomposes into a sum of mutual informations, the problem becomes a maximum-spanning-tree problem, and greedy is optimal. More generally, if entropy reduction is submodular — diminishing returns as features accumulate — greedy comes within \(1 - 1/e\) of the optimum (Nemhauser et al. 1978). Whether the minimax entropy objective is submodular in general remains open; where it is not, guarantees can still be recovered in terms of how far the objective departs from submodularity (Bian et al. 2017).
7.5 Takeaway
Minimax entropy couples the two preceding principles into a single criterion: maximize entropy to model the world, minimize entropy to commit to what matters. Maximum entropy supplies possibility, minimum entropy supplies certainty, and the minimax formulation decides which details deserve to be modelled at all.
The principle has recently yielded exactly solvable models of large neuronal populations (Lynn et al. 2025), yet its reach in machine learning is largely untapped. Open directions include scalability and sample complexity in high dimensions, realizations for LLMs, agents, and multimodal models, and the relationship to the free-energy principle (Friston 2010).