Optimal e-variables under constraints

1. Problem Statement

The paper addresses the construction of growth-rate optimal (GROW) e-variables for composite hypothesis testing under various structural constraints.

• Context: E-variables are non-negative random variables $E$ such that $\sup_{P_0 \in H_0} \mathbb{E}_{P_0}[E] \le 1$. They provide "safe" and "anytime-valid" inference. In unconstrained settings, the log-optimal e-variable (maximizing expected log-growth under the alternative) is the likelihood ratio between the Least Favorable Distributions (LFDs) $(P^*_0, P^*_1)$ of the null and alternative classes.
• The Challenge: In practical applications, e-variables often face structural constraints such as:
  1. Local Differential Privacy (LDP): The e-variable must depend only on a privatized output $Y$ generated via an $\epsilon$-LDP channel.
  2. Quantization: The e-variable must take values in a finite set (e.g., binary outputs).
  3. Boundedness: The e-variable must be bounded within an interval $[c_1, c_2]$ to ensure numerical stability or robustness.
  4. Bounded Convex Integral Constraints: Constraints on moments (e.g., variance) or general convex penalties $\mathbb{E}_{P_0}[\phi(E)] \le C$.
• The Core Question: Does the optimal constrained e-variable require solving a completely new, complex optimization problem from scratch, or can it be derived from the unconstrained optimal solution?

2. Methodology

The authors propose and validate a "Optimize-then-Constrain" principle. The methodology involves:

1. Unconstrained Baseline: First, identify the unconstrained log-optimal e-variable, which is the likelihood ratio $L(X) = \frac{dP^*_1}{dP^*_0}$ between the LFD pair.
2. Constraint Application: Apply a specific transformation (deterministic or randomized) to this unconstrained solution to satisfy the structural constraint.
3. Theoretical Framework:
   • Simple vs. Simple: Derive exact closed-form solutions for the constrained optimization problem in the simple hypothesis setting.
   • Composite Extension: Leverage the existence of an LFD pair to lift the simple-hypothesis results to composite testing. The key insight is that if the constrained optimizer for simple hypotheses is a non-decreasing transformation of the likelihood ratio, it remains optimal for the composite problem defined by the LFD pair.
   • Utility Generalization: While the primary focus is logarithmic utility (Kelly betting), the proofs are extended to general strictly increasing and strictly concave utility functions.

3. Key Contributions and Results

A. Local Differential Privacy (LDP)

• Problem: Maximize the KL-divergence between induced marginals under an $\epsilon$-LDP constraint where the output is binary ($Y \in \{0, 1\}$).
• Result: The optimal mechanism is a stochastic thresholding of the likelihood ratio.
  • The mechanism $Q^*(y|x)$ outputs 1 with probability $\frac{e^\epsilon}{1+e^\epsilon}$ if $L(X) > t$ and $\frac{1}{1+e^\epsilon}$ if $L(X) \le t$.
  • The threshold $t$ is determined by a fixed-point equation involving the marginal probabilities.
  • Significance: This generalizes the "binary mechanism" of Kairouz et al. (2016), proving its optimality for all $\epsilon$ (not just high privacy) and for arbitrary distributions, not just finite support. The optimal e-variable is a randomized post-processing of the unconstrained likelihood ratio.

B. Quantization (Binary Outputs)

• Problem: Find the optimal e-variable taking only two distinct values $\{u_0, u_1\}$.
• Result: The optimal solution is a deterministic step function based on a threshold of the likelihood ratio.
  • $E^* = u_1$ if $L(X) > t^*$, and $u_0$ otherwise.
  • The values $u_0, u_1$ and threshold $t^*$ are explicitly derived to satisfy the e-variable constraint ($\mathbb{E}_{P_0}[E^*] \le 1$) and maximize growth.
  • Significance: Confirms that quantization simply discretizes the likelihood ratio without altering the fundamental ordering of evidence.

C. Boundedness

• Problem: Maximize growth subject to $c_1 \le E \le c_2$ almost surely.
• Result: The optimal solution is a clipped (truncated) likelihood ratio.
  • $E^* = \min(c_2, \max(c_1, \frac{L(X)}{\lambda^*}))$, where $\lambda^*$ is a normalization constant ensuring $\mathbb{E}_{P_0}[E^*] = 1$.
  • Significance: This provides a systematic way to construct robust, bounded e-variables by simply truncating the unconstrained optimal solution.

D. Bounded Convex Integral Constraints

• Problem: Maximize growth subject to $\mathbb{E}_{P_0}[\phi(E)] \le C$ for a strictly convex, superlinear function $\phi$ (e.g., $\phi(x)=x^2$ for variance control).
• Result: The optimal solution is a strictly monotone transformation of the likelihood ratio.
  • $E^* = \psi(L(X))$, where $\psi$ is derived via Lagrange multipliers.
  • For the specific case of bounded second moment ($\phi(x)=x^2$), the solution takes a specific square-root form.
  • Significance: Demonstrates that moment constraints do not break the monotonic relationship with the likelihood ratio.

E. Generalization to Composite Testing (The "LFD Bridge")

• Theorem 6.1: If an LFD pair $(P^*_0, P^*_1)$ exists for the composite classes, and the constrained optimizer for the simple pair $(P^*_0, P^*_1)$ is a non-decreasing function of the likelihood ratio, then this same function is the GROW e-variable for the entire composite problem.
• Counter-example: The paper provides a counter-example where no LFD pair exists (composite null with bounded mean). In this case, the "optimize-then-constrain" principle fails, and the constrained optimal solution is not a simple transformation of the unconstrained one. This highlights the critical necessity of the LFD assumption.

4. Significance and Impact

1. Unifying Principle: The paper establishes that for a wide range of realistic constraints (privacy, quantization, boundedness), the complex problem of finding constrained optimal e-variables reduces to a simple post-processing of the unconstrained solution. This avoids the need to re-solve difficult minimax problems for every new constraint.
2. Practical Implementation: It provides explicit, closed-form algorithms (e.g., Algorithm 1 for LDP Kelly betting) that practitioners can implement immediately.
3. Robustness and Privacy: The results bridge the gap between theoretical optimality (GROW) and practical requirements like differential privacy and numerical stability, showing that safety and privacy can be achieved without sacrificing the fundamental growth-rate optimality of e-variables.
4. Theoretical Boundary: By identifying the necessity of the LFD pair for this principle to hold, the paper clarifies the limits of the "optimize-then-constrain" approach, guiding future research on composite problems where LFDs do not exist.

In summary, the paper demonstrates that structural constraints act as monotonic transformations on the likelihood ratio. As long as the underlying hypothesis testing problem admits a Least Favorable Distribution pair, the optimal constrained e-variable is simply the unconstrained optimal e-variable passed through a specific filter (clipping, thresholding, or stochastic mapping) dictated by the constraint.