Dual Representation of Minimum Divergence Under Integral Constraints

1. Problem Statement

The paper addresses the problem of finding the minimum divergence between a reference probability distribution $P$ and a class of distributions $Q$ that satisfy specific integral constraints.

• Setting: The distributions are supported on a compact domain $\mathcal{X} = [0, 1]^K$ (where $K \ge 1$).
• Objective: Minimize a divergence measure $D(P, Q)$ subject to the constraint that the expected value of a continuous function $g(X)$ under $Q$ lies within a closed, convex set $C \subset \mathbb{R}^J$.
  $$I(P, g, C) = \inf_{Q \in \mathcal{Q}(g, C)} D(P, Q), \quad \text{where } \mathcal{Q}(g, C) = \{Q \in \mathcal{P}(\mathcal{X}) : \mathbb{E}_Q[g(X)] \in C\}$$
• Significance: This quantity characterizes the fundamental limits (information-theoretic lower bounds) for various sequential decision-making problems, including multi-armed bandits, sequential hypothesis testing, estimation, and change detection.
• Challenge: The primal problem involves optimization over an infinite-dimensional space of probability measures, making it computationally intractable. While dual representations exist for specific cases (e.g., mean-constrained relative entropy, or $KL_{inf}$), they are often implicit or limited to specific divergence types and constraints.

2. Methodology: A Two-Stage Discretization Recipe

The authors propose a general, constructive, two-stage methodology to derive explicit dual representations for constrained minimum divergence problems. This approach generalizes the argument used by Honda and Takemura (2010) for $KL_{inf}$.

Stage 1: Finite-Support Dual Derivation

• Discretization: The authors first consider the case where the reference distribution $P$ has finite support on a subset of $\mathcal{X}$.
• Finite-Dimensional Reduction: Using Carathéodory's theorem, they show that the optimal $Q$ can be restricted to a finite-dimensional subspace (specifically, a subset of the support of $P$ plus the vertices of the domain).
• Convex Duality: Standard finite-dimensional convex duality (Lagrangian duality) is applied to derive an explicit, concave dual objective function over a compact dual domain.

Stage 2: Limiting Argument to General Distributions

The second stage lifts the dual from finitely supported distributions to arbitrary distributions on $\mathcal{X}$ using a sequence of discretizations.

• Discretization Channels: A sequence of Markov kernels (channels) $\{K_k\}$ is constructed to map the continuous domain to a discrete grid of vertices $V_k$.
  • For mean constraints, they utilize mean-preserving channels (based on stochastic rounding) that exactly preserve the constraint $\mathbb{E}[X] = \mu$ during discretization.
  • For general integral constraints, they use arbitrary discretization channels that approximately preserve constraints, relying on the continuity of $g$.
• Interchange of Limits: The core technical contribution is proving that:
  $$\lim_{k \to \infty} \sup_{\theta} H_k(\theta, P_k) = \sup_{\theta} H(\theta, P)$$
  where $H_k$ is the dual objective for the discretized problem and $H$ is the dual for the original problem.
• Key Tools: The proof relies on:
  1. Data Processing Inequality (DPI): To show the primal value of the discretized problem is an upper bound on the original.
  2. Lower Semicontinuity (LSC): Of the divergence measure under weak convergence to establish the lower bound.
  3. Concavity and Uniform Continuity: To justify the interchange of the limit ($\lim$) and the supremum ($\sup$) in the dual objective.

3. Key Contributions

1. Generalization of $KL_{inf}$: The paper extends the dual representation of mean-constrained relative entropy ($KL_{inf}$) from the 1D case to arbitrary dimensions $K \ge 1$.
2. Extension to General $f$-Divergences: The methodology is not limited to relative entropy. It is successfully applied to a broad class of $f$-divergences (including Hellinger and Chi-squared divergences), providing explicit dual forms for these measures under mean constraints.
3. General Integral Constraints: The authors develop an abstract limiting argument (Theorem 3.6) that handles general continuous constraint functions $g(X)$ (beyond just the mean). This involves relaxing the constraints in the discretized steps and proving convergence, leading to a dual representation for $I(P, g, C)$.
4. Constructive and Explicit Formulations: Unlike previous works that often provide implicit duals or require strong constraint qualifications (like non-empty relative interiors which may not exist in measure spaces), this approach yields explicit, computable dual objectives over compact domains.
5. Statistical Applications: The paper demonstrates the utility of these duals by constructing optimal procedures for:
   • Sequential Testing: Designing level-$\alpha$, power-one tests that achieve the fundamental lower bound on sample complexity.
   • Confidence Sequences: Constructing anytime-valid confidence sets for unknown means.
   • Change Detection: Developing optimal change detection schemes (Lorden-style) with minimized detection delay.

4. Key Results

• Dual for Mean-Constrained $KL_{inf}$ (Theorem 2.5):
  $$KL_{inf}(P, \mu) = \sup_{\lambda \in \mathcal{L}_\mu} \mathbb{E}_P \left[ \log(1 - \lambda^T (X - \mu)) \right]$$
  where $\mathcal{L}_\mu = \{ \lambda : 1 - \lambda^T(x-\mu) \ge 0, \forall x \in \mathcal{X} \}$.
• Dual for General $f$-Divergences (Theorem 2.7):
  Provides a unified dual form involving the perspective function $\tilde{f}$ and its conjugate, applicable to any $f$-divergence under mean constraints.
• Dual for General Constraints (Theorem 3.7):
  For a Lipschitz constraint $g$ and set $C$:
  $$KL_{inf}(P, g, C) = \sup_{(\lambda, \gamma)} \left( \mathbb{E}_P[\log(\gamma - \langle \lambda, g(X) \rangle)] + 1 - \gamma + \inf_{c \in C} \langle \lambda, c \rangle \right)$$
  subject to $\gamma - \langle \lambda, g(x) \rangle \ge 0$.
• Optimality in Sequential Inference: The paper proves that tests constructed using these duals (e.g., stopping when the empirical dual exceeds a threshold) achieve the asymptotic lower bound:
  $$\lim_{\alpha \to 0} \frac{\mathbb{E}[\tau_\alpha]}{\log(1/\alpha)} = \frac{1}{I(P, g, C)}$$

5. Significance and Impact

• Computational Tractability: By converting infinite-dimensional optimization problems into finite-dimensional convex programs (via the dual), the paper enables the practical implementation of optimal sequential inference algorithms. These can be solved efficiently using off-the-shelf convex solvers.
• Theoretical Unification: It unifies the treatment of various divergence measures and constraint types under a single, rigorous framework, bridging the gap between information-theoretic lower bounds and algorithmic achievability.
• Robustness: The results apply to distributionally robust optimization and settings with bounded support, offering a pathway to handle uncertainty in sequential decision-making.
• Future Directions: The authors note that while the current work relies on the compactness of $[0, 1]^K$, the methodology could potentially be extended to unbounded domains ($\mathbb{R}^K$) and applied to non-asymptotic empirical likelihood constructions.

In summary, this paper provides a powerful, modular toolkit for deriving tractable duals of constrained minimum divergence problems, directly enabling the design of statistically optimal and computationally feasible sequential algorithms.