Classical Analysis and ODEs
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Monday 13 April
A singular perturbation problem called WKB equation (Eq) $h^2u(x,h)-Q(x)u(x,h)=0$ is studied. $h>0$ is a small parameter. Investigation of (Eq) has long history. Recently it has developed by a new method named "Exact WKB Analysis" based on Borel resummation method and new analytic results. Here we study (Eq) by another elementary method. We only apply advanced calculus and the theory of differential equations to (Eq). We neither assume turning points are simple nor there is no Stokes curve that connects two turning points.
Combinatorics
Matching and intersection problems for non-trivial $r$-partite $r$-uniform hypergraphs
A central theme in extremal combinatorics is the study of the maximum number of edges in an $r$-uniform hypergraph ($r$-graph) with matching number at most $s$ (the Erdős Matching Conjecture) or with pairwise intersection at least $t$ (the $t$-intersection problem). The maximum sizes for these problems are typically achieved by trivial constructions: for the matching problem, the extremal construction consists of all edges intersecting a fixed set of $s$ vertices, while for the intersection problem, it consists of all edges containing a fixed set of $t$ vertices. In this paper, we investigate the non-trivial $r$-partite $r$-graphs where each part is of size $n$. We determine the exact bounds for both the matching problem and the intersection problem when $n$ is sufficiently large. Furthermore, for the intersection problem, we resolve the cases $t=1$ and $t=r-2$ for all $n \ge 2$. Our results partially confirm a conjecture of Lu and Ma (“Matching Stability for 3-Partite 3-Uniform Hypergraphs.” Journal of Graph Theory (2026)).
Read the full abstract
Analysis of PDEs
The $L_p$ dual Christoffel-Minkowski type problem for a class of Hessian quotient equations
In this paper, we investigate an $L_p$ dual Christoffel-Minkowski type problem for the Hessian quotient operator $\frac{\sigma_{k}(\Lambda)}{\sigma_{l}(\Lambda)}$, where the operator $\Lambda$ has been widely studied in the literature. Exploiting the recently discovered “inverse convexity” property of this class of operators, we establish a full rank theorem under suitable structural assumptions. Together with a priori estimates, this result enables us to prove the existence and uniqueness of strictly spherically convex solutions to the above $L_p$ dual Christoffel-Minkowski type problem.
Read the full abstract
Information Theory
$\alpha$-Mutual Information for the Gaussian Noise Channel
In this paper, we study Sibson's $\alpha$-mutual information in the context of the additive Gaussian noise channel. While the classical case $\alpha = 1$ is well understood and admits deep connections to estimation-theoretic quantities, such as the minimum mean-square error (MMSE) and Fisher information, many of the corresponding structural properties for general $\alpha$ remain less explored. Our goal is to develop a systematic understanding of $\alpha$-mutual information in the Gaussian noise setting and to identify which properties extend beyond the Shannon case. To this end, we establish several regularity properties, including finiteness conditions, continuity with respect to the signal-to-noise ratio (SNR) and the input distribution, and strict concavity/convexity properties that ensure uniqueness in associated optimization problems. A central contribution is the development of an $\alpha$-I-MMSE relationship, generalizing the classical identity by relating the derivative of $\alpha$-mutual information with respect to SNR to the MMSE evaluated under appropriately tilted distributions. This connection further leads to a generalized de Bruijn identity and new estimation-theoretic representations of Rényi entropy and differential Rényi entropy. We also characterize the low- and high-SNR behavior. In the low-SNR regime, the first-order behavior depends only on the input variance. In the high-SNR regime, for discrete inputs, $\alpha$-mutual information converges to the Rényi entropy of order $1/\alpha$, while for general inputs we connect it to $\alpha$-information dimension. Overall, our results show that many fundamental relationships between information and estimation extend beyond the Shannon setting, in a form involving $\alpha$-tilted distributions.
Read the full abstract
Functional Analysis
Compactness for pseudo-differential and Toeplitz operators on modulation spaces
We deduce various norm equivalences, and convolution estimates for the modulation space $M^{\sharp ,q}_{(\omega )}$ consisting of all $f\in M^{\infty ,q}_{(\omega )}$ such that $|V_\phi f \cdot \omega |$ satisfies a mild vanishing condition at infinity. We prove that $M^{\sharp ,q}_{(\omega )}$ is the completion of the Gelfand-Shilov space $\Sigma _1$ under the $M^{\infty ,q}_{(\omega )}$ norm. We use these results to deduce compactness for $\Psi$DO $\op (\mathfrak a )$, with $\mathfrak a \in M^{\sharp ,q}_{(\omega )}$, $0<q\le 1$, when acting on a broad family of modulation spaces.
Read the full abstract
Combinatorics
Cusp Form Dimensions, Lattice Uniqueness, and LP Sharpness for Sphere Packing in Dimensions 8 and 24
The Cohn-Elkies linear programming (LP) bound for sphere packing is known to be sharp in dimensions 8 and 24 but in no other dimension above 2. We investigate why by examining three independent necessary conditions for LP sharpness, drawn from number theory, lattice theory, and conformal field theory. The first condition, dim S_{d/2}(SL_2(Z)) <= 1, bounds the freedom in theta series and rules out all d >= 48. The second, derived from Cohn and Triantafillou's dual LP obstruction via cusp forms for the congruence subgroup Gamma_0(2), explains why LP sharpness fails in dimensions 16 and 32 despite the first condition being satisfied. The third, via the Hartman-Mazac-Rastelli correspondence between LP bounds and the modular bootstrap for Narain conformal field theories, reinterprets LP sharpness as the existence of an extremal CFT. We formulate a conjecture that these three conditions are equivalent for d congruent to 0 mod 8, and observe that the Bost-Connes quantum statistical system provides a natural algebraic framework in which all three perspectives are connected through the Hecke algebra.
Read the full abstract
Dynamical Systems
Non-existence of Lyapunov exponents in the Newhouse domain
We show that within the Newhouse domain of $C^r$ surface diffeomorphisms ($r \in [2,\infty )$), there exists a dense subset $\mathcal D$ such that for any $f \in \mathcal D$, Lyapunov exponents fail to exist for all points in some open set $U$ and all nonzero tangent vectors in some open cone $V \subset \mathbb{R}^2$. This demonstrates that the non-existence of Lyapunov exponents is a persistent phenomenon in the setting of robust homoclinic tangencies. The proof relies on constructing diffeomorphisms exhibiting specific oscillatory return times near a homoclinic tangency, incorporating techniques from Newhouse theory and recent results on Lyapunov irregularity, alongside several refinements and new arguments.
Read the full abstract
Analysis of PDEs
Long-range phase coexistence models with degenerate potentials
This survey offers an overview of recent advances in nonlocal phase transition problems, modeled by Ginzburg–Landau type energies of the form \[ \frac{1}{4}\iint_{\R^{2n}\setminus (\R^n \setminus \Omega)^2} \frac{|u(x)-u(y)|^2}{|x-y|^{n+2s}}\,dx\,dy \;+\; \int_\Omega W(u(x))\,dx. \] Here,~$W$ is a smooth and possibly degenerate double well potential, with a polynomial control on its second derivatives near the wells. The emphasis is on qualitative properties of minimizers and critical points of the energy functional.
Read the full abstract
Group Theory
On the Sum of Squares of Irreducible Brauer Character Degrees in Blocks
We study a weakened version of the Holm–Willems Local Conjecture. The problem is reduced to quasi-simple groups under the assumption that the defect group is abelian. Complete proofs are provided in the case \(p = 2\).
Information Theory
Entropic independence via sparse localization
Entropic independence is a structural property of measures that underlies modern proofs of functional inequalities, notably (modified) log-Sobolev inequalities, via “annealing” or local-to-global schemes. Existing sufficient criteria for entropic independence typically require spectral independence and/or uniform bounds on marginals under all pinnings, which can fail in natural canonical-ensemble models even when strong mixing properties are expected. We introduce sparse localization: a restricted localization framework, in the spirit of Chen–Eldan, in which one assumes $\ell_2$-independence only for a sparse family of pinnings (those fixing at most $cn$ coordinates for any $c > 0$), yet still deduces quadratic entropic stability and entropic independence with an explicit multiplicative loss of order $c^{-1}$. As an application, we give a rigorous proof of approximate conservation of entropy for the uniform distribution on independent sets of a given size in bounded degree graphs.
Read the full abstract
Number Theory
Regular ternary sums of generalized polygonal numbers
In this article, we provide an explicit constant $C$ such that there is no regular ternary sum of generalized $m$-gonal numbers for any integer $m$ greater than $C$.
Statistics Theory
Characterisations of Kullback–Leibler approximation by finite Gaussian mixtures
We study the Kullback–Leibler (KL) divergence approximation theory of Gaussian mixture models (GMMs) by isolating an abstract mechanism behind several necessary-and-sufficient statements. The necessity direction is universal: if a density is approximable in KL divergence by finite GMMs, then it must have finite second moment. The sufficient direction is reduced to the construction of approximating GMMs whose likelihood ratios converge pointwise and whose finite log-ratios form a uniformly integrable family. We verify this mechanism on a finite log-moment class of continuous strictly positive target densities, from which bounded, $\mathcal L^p$ $(p>1)$, and Orlicz-dominated subfamilies follow immediately. We also show that a countable-scale support-aware target density class, which allows zero density regions, satisfies the same equivalence. Finally, we give counterexamples showing that the countable-scale class strictly extends the fixed-scale class, that the finite log-moment and countable-scale support-aware classes do not contain one another, and that their union is not exhaustive.
Read the full abstract
Probability
The Gated-Service M/GI/1 Queue with Single Vacations and Its Application to Batch-Service Queues
In this paper, we consider the M/GI/1 queue with single vacations under the gated service discipline. We obtain the probability generating function of the stationary queue length, the Laplace-Stieltjes transform of the system delay distribution in steady state, and the joint transform of the busy cycle length and the number of customers served in the busy cycle. Furthermore, as an application, we consider a batch-service M/G/1 queue, where service times depend on the number of customers in batch.
Read the full abstract
Representation Theory
Character values and conductors of low-rank groups of Lie type
Let $\chi$ be a complex irreducible character of a finite group $G$. The conductor of $\chi$, denoted $c(\chi)$, is the smallest positive integer $n$ such that $\chi(x)\in \mathbb{Q}(\exp({2\pi i/n}))$ for all $x\in G$. We show that for certain rank $1$ finite groups of Lie type, the conductor $c(\chi)$ is realized at a single group element; that is, there exists $g\in G$ such that $c(\chi)=c(\chi(g))$. In some quasisimple cases, we further prove that the field of values \(\mathbb{Q}(\chi)\) is generated by a single value. This phenomenon, which is related to a well-known conjecture of W.~Feit, was recently observed by Boltje et al. in their reduction of the conjecture to finite simple groups. Our approach uses techniques from algebraic number theory together with the known character tables of these groups.
Read the full abstract
Logic
A computably enumerable many-one degree with no least finite-one degree
Richter, Stephan, and Zhang asked whether every nonrecursive many-one degree contains a least finite-one degree. We solve this question in the negative, already within the class of computably enumerable many-one degrees. Positive answers are known in two disjoint natural settings: for a measure-one and comeager class of $m$-rigid sets, and, in a companion paper, for computably enumerable many-one degrees containing a $D$-maximal set. We construct a nonrecursive \ce\ set $A$ such that for every set $X \eqm A$ there exists a c.e.\ set $B \eqm A$ with $X \not\lfo B$. Hence the many-one degree of $A$ contains no least finite-one degree. The proof is a finite-injury priority construction based on virtual target sets and a dynamic trap mechanism forcing any putative finite-one reduction either to violate finite-oneness or to compute an incorrect reduction.
Read the full abstract
Differential Geometry · Cross-listed from gr-qc
Holographic is Hamiltonian, relatively
We show that a relative holographic energy coincides with the relative Hamiltonian energy.
Numerical Analysis
Asymptotic and pre-asymptotic convergence of sparse grids for anisotropic kernel interpolation
Sparse grids are popular tools for high-dimensional function approximation. In this work, we study the use of sparse grids for interpolation using separable Matérn kernels $\Phi_{\boldsymbol{\nu},\boldsymbol{\lambda}}(\mathbf{x},\mathbf{x}')=\prod_{j=1}^d\phi_{\nu_j,\lambda_j}(x_j,x_j')$, with a particular focus on the anisotropic setting where the regularity $\nu_j$ and the lengthscale $\lambda_j$ vary with dimension $j$. We combine the construction of anisotropic sparse grids, which exploit anisotropic $\nu_j$ to improve convergence rates in smooth dimensions, with the construction of lengthscale-informed sparse grids, which diminish the error contribution of less varying dimensions using anisotropic $\lambda_j$. We provide theory and numerical experiments to showcase the benefits on asymptotic and pre-asymptotic error behaviour of sparse grid kernel interpolation.
Read the full abstract
Quantum Algebra
Putting the Brauer back in Brauer-Picard
We establish a 6-term left exact sequence, involving Galois cohomology of the base field $\mathbb K$, and the Brauer-Picard groupoid of a fusion category. This generalizes a result of Etingof, Nikshych, and Ostrik to the setting where $\mathbb K$ is not algebraically closed. Following their example, we use this exact sequence to compute examples of graded extensions of fusion categories over $\mathbb R$. Along the way, we establish several structural theorems regarding the duality morphisms for a fusion category as an object in the 4-category of braided tensor categories. The paper ends with a speculative look at a potential higher categorical explanation of the main result.
Read the full abstract
Information Theory
A Non-Probabilistic Game-Theoretic Information Theory Which Subsumes Probabilistic Channel Coding
Probabilistic settings (e.g., vanishing-error channel coding) and non-probabilistic settings (e.g., zero-error channel coding and adversarial channels) were considered two related but different branches of information theory which do not subsume each other. We propose a unifying non-probabilistic information theory based on game theory and dynamic hedging which subsumes the conventional probabilistic channel coding theorem (vanishing error, with or without feedback) and lossless source coding theorem, as well as zero-error and adversarial settings. Coding is modelled as a deterministic game between an encoder and an adversary, where the encoder may purchase insurance with a payoff that depends on the channel outputs. Our framework is based on a generalization of the works by Ville, Dawid, Shafer and Vovk on the game-theoretic formulation of probabilistic concepts, by relaxing the convex pricing cone to a nonconvex downward closed cone, which is precisely the relaxation needed to model information transmission. Pricing downward closed cone is a versatile tool for non-probabilistic coding results that can subsume their probabilistic counterparts, and provides a canonical form for probabilistic channels, adversarial channels and arbitrarily varying channels.
Read the full abstract
Algebraic Topology
On periodic homotopy and homology equivalences of spaces
There are at least two ways to approach the homotopy theory of spaces `at chromatic height $n$': one may localize with respect to $T(n)$-homology or with respect to $v_n$-periodic homotopy groups. It was already observed by Bousfield that these two options yield rather different results. We build on his work to prove precise comparison results between the two notions. A crucial concept is a more robust notion of $T(n)$-equivalence that we call `parametric $T(n)$-equivalence': this is a map of spaces that induces an equivalence on $\infty$-categories of local systems valued in $T(n)$-local spectra. Our results are sharpest in the case of infinite loop spaces, where amongst other things we prove a $T(n)$-local version of a result of Kuhn on the Morava $K$-theory of the Whitehead tower. As a corollary of our results we also produce a formula for the $L_n^f$-localization of an infinite loop space $\Omega^\infty E$ of a spectrum satisfying $L_{n-1}^f E \simeq 0$.
Read the full abstract
Combinatorics
A linear upper bound on zero-sum Ramsey numbers of $d$-degenerate graphs in $\mathbb{Z}_p$
Let $p$ be a prime number and let $G$ be a graph on $n$ vertices and $m$ edges. The zero-sum Ramsey number of $G$ over $\mathbb{Z}_p$, denoted by $R(G, \mathbb{Z}_p)$, is the minimum $\ell\in \mathbb{N}$ such that for any edge-coloring $c:E(K_\ell)\to\mathbb{Z}_p$, there is a subgraph $G'\subset K_\ell$ isomorphic to $G$ and satisfying $\sum_{e\in E(G')}c(e)=0$. We prove that if $G$ is a $d$-degenerate graph, then $R(G, \mathbb{Z}_p)\leq n + (3+3d)p$ so long as $m\geq 2pd(d+1)^2$, $p$ divides $m$, and $2d<p$. This generalizes a result by Colucci and D'Emidio on $1$-degenerate graphs.
Read the full abstract
Sunday 12 April
Rings and Algebras
A characterization of monoid graded semihereditary rings
Let $\Gamma$ be a cancellation monoid and $R=\bigoplus_{\alpha \in \Gamma}R_{\alpha}$ be a $\Gamma$-graded ring. It is shown that $R$ is graded left semihereditary if and only if $R$ is graded left coherent and every graded submodule of a flat left $R$-module is flat. Hence it gives a new characterization of graded-Prüfer domains.
Read the full abstract
Information Theory · Cross-listed from cs.LG
LAWS: Learning from Actual Workloads Symbolically – A Self-Certifying Parametrized Cache Architecture for Neural Inference, Robotics, and Edge Deployment
We introduce LAWS (Learning from Actual Workloads Symbolically), a self-certifying inference caching architecture that builds a growing library of certified expert functions from deployment observations. Each expert covers a region of input space defined by a node in the Probabilistic Language Trie (PLT) of the base model and carries a formal error bound holding uniformly over all inputs. The central result is a self-certification theorem: for any input x, the LAWS approximation error is bounded by epsilon_fit + 2*Lambda(W)*C_E, where Lambda(W) is the model Lipschitz constant, C_E is the maximum embedding diameter, and epsilon_fit is the expert training error – all checkable at deployment time without ground truth. We prove that LAWS generalizes both Mixture-of-Experts and KV prefix caching as special cases and is strictly more expressive than any fixed-K MoE or finite cache. Further results include a monotone hit rate theorem (any-match routing ensures coverage only increases), an expert library growth rate of O(2^H log N) where H is workload entropy, a fleet learning convergence theorem with Omega(K) speedup for K-unit fleets, and an over-the-air update bandwidth bound. We conjecture that LAWS is acquisition-optimal among stationary online caching algorithms and that the effective Lipschitz constant on the training distribution grows polynomially rather than exponentially in depth. Applications are developed for LLM inference, robotic control, and multi-agent edge deployment.
Read the full abstract
Complex Variables
Bohr Radius and Landau-type Theorems for Harmonic Mappings with Boundary Functions in Lebesgue Spaces
This paper investigates the geometric and analytical properties of harmonic mappings $f$ in the unit disk $\mathbb{D}$ induced by boundary functions $F$ belonging to the Lebesgue spaces $L^{p}(\mathbb{T})$ for $1 \le p \le \infty$. We first establish a sharp Bohr-type inequality for the class of bounded harmonic mappings. Specifically, we prove that for a fixed analytic part $|a_{0}|= aM$, the majorant series $M_{f}(r)$ satisfies $M_{f}(r) \le M$ for $r \le (1-a)/(1-a+4/\pi)$, and demonstrate that this radius is best possible. This result is subsequently extended to harmonic mappings with $L^p$ boundary functions, where we determine the sharp Bohr radius $r_{p} = 1/(2C_{q}+1)$, with $C_{q}$ being a constant depending on the conjugate exponent $q$. Furthermore, the paper provides improved Landau-type theorems for these mappings. Under standard normalization, we derive explicit expressions for the radius of univalence $r_{0}$ and the radius of the inscribed schlicht disk $R_{0}$. The sharpness of these constants is discussed through the construction of extremal functions related to the Poisson kernel.
Read the full abstract
General Mathematics
Degree Variance and the Fuzzy Sigma Index in Fuzzy Graphs
The sigma index of a graph, defined as the population variance of its degree sequence, is a fundamental measure of structural irregularity. In this paper, we introduce and systematically investigate its natural extension to fuzzy graphs, termed the fuzzy sigma index $$ \sigma^*(\Gamma) = \frac{1}{n} \sum_{v \in V(\Gamma)} \left( d_\Gamma(v) - \frac{2\,\mathrm{ew}}{n}\right)^2, $$ where $d_\Gamma(v)$ denotes the fuzzy degree of a vertex $v$, and $\mathrm{ew}$ represents the fuzzy size of the fuzzy graph $\Gamma=(V,\nu, \mu)$. We establish several fundamental properties of this topological index. In particular, we derive sharp lower and upper bounds. Analyze the behavior of $\sigma^*(\Gamma)$ under standard fuzzy graph operations. This work provides a foundation for further study of variance-based topological indices in fuzzy graph theory.
Read the full abstract
Dynamical Systems
Linear Response for Contracting on Average Iterated Function Systems
Consider the following probabilistic contracting on average iterated function system $$\Phi = \left\{f_i (x) = \lambda_i x + d_i,\;i=1,2 ;\;\; p = \left(\frac{1}{2} , \frac{1}{2}\right) \right\},$$ where the contraction ratios $\lambda_1 , \lambda_2$ are such that $0<\lambda_1<1<\lambda_2$ and $\lambda_1\lambda_2<1$. Denote by $\mu_{\lambda_1,\lambda_2}$ its stationary measure. We study the differentiability of $$(\heartsuit)\quad\quad\quad\quad\quad \lambda_1 \mapsto \int_{\mathbb{R}} \phi(x) \,d\mu_{\lambda_1,\lambda_2}(x),$$ where $\phi$ is a suitable test function. We establish three cases where $(\heartsuit)$ is differentiable and show the derivative coincides with the one obtained by taking formal derivative, which can be generalized to the case of multiple maps with different probabilities. We also present sufficient conditions under which there exists a smooth, bounded test function $\phi$ so that $(\heartsuit)$ is not differentiable.
Read the full abstract
Combinatorics
Support and Support Jumps in the Partition Graph
Let $G_n$ be the partition graph whose vertices are the partitions of $n$, with adjacency given by elementary transfers of one cell between parts, followed by reordering. We study the support of a partition – the set of distinct part sizes – as a global vertex invariant of $G_n$. We show that support size $r$ occurs in $G_n$ if and only if $T_r=r(r+1)/2\le n$, so the maximal support size is $\rho(n)=\max\{r:T_r\le n\}$. We determine exactly how support changes along an edge: the support jump always lies in $\{-2,-1,0,1,2\}$, and we give an explicit birth-death formula in terms of the source and target part sizes. We also prove the degree bound $\deg(\lambda)\ge \sigma(\lambda)(\sigma(\lambda)-1)$ for every partition $\lambda$, with equality exactly for staircase partitions. In addition, support size is invariant under conjugation, the support-$1$ stratum consists exactly of rectangular partitions, and the coarse support-level graph always contains the chain $1-2-\cdots-\rho(n)$. We conclude with computational data for small $n$, including support-stratum counts, support-jump counts, and connectivity data for fixed-support subgraphs.
Read the full abstract
Optimization and Control
Stochastic Modified Equations for Stochastic Gradient Descent in Infinite-Dimensional Hilbert Spaces
Inverse problems in scientific computing often require optimization over infinite-dimensional Hilbert spaces. A commonly used solver in such settings is stochastic gradient descent (SGD), where gradients are approximated using randomly sampled sub-objective functions. In this work we study the continuous-time limit of SGD in the small step-size regime. We show that the discrete dynamics can be approximated by a stochastic differential equation (SDE) driven by cylindrical Brownian motion. The analysis extends diffusion-approximation results previously established in Euclidean spaces to the infinite-dimensional setting. Two analytical difficulties arise in this extension. First, the cylindrical nature of the noise requires establishing well-posedness of the resulting stochastic evolution equation through appropriate structural conditions on the covariance operator. Second, since the randomness in SGD originates from discrete sampling while the limiting equation is driven by Gaussian noise, the comparison between the two dynamics must be carried out in a weak sense. We therefore introduce a suitable class of smooth functionals on the Hilbert space and prove that the discrepancy between SGD and the limiting SDE, when evaluated through these functionals, is of second order in the step size. Numerical experiments confirm the predicted convergence behavior.
Read the full abstract
Statistics Theory · Cross-listed from cs.LG
Query Lower Bounds for Diffusion Sampling
Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for $d$-dimensional distributions, given access to score estimates with polynomial accuracy $\varepsilon=d^{-O(1)}$ (in any $L^p$ sense), any sampling algorithm requires $\widetilde{\Omega}(\sqrt{d})$ adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over $\widetilde{\Omega}(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.
Read the full abstract
Optimization and Control
Sample Average Approximation for Distributionally Robust Optimization with $\phi$-divergences
It is well known that estimating the expectation of any given bounded random variable with values in $[-B, B]$ has two basic properties: (1) the number of samples needed scales at the order of $O(B^2/\epsilon^2)$, where $\epsilon$ is the prescribed target precision, and (2) such a sample complexity is independent of the underlying probability measure. We show that neither of these properties can no longer hold when evaluating the worst-case expectation of the random variable, where the probability measures defining the expectation belong to a $\phi$-divergence ball centered at some nominal measure $P$. Specifically, the sample complexity and its dependence on the nominal measure can be completely characterized by the growth of the divergence function. When the divergence function $\phi$ exhibits superlinear growth, a $P$-independent sample complexity can be obtained for sample average approximation, which depends only on the growth of $\phi$, the radius of the divergence ball, and the target precision. We also provide sample complexity lower bounds and demonstrate the optimality of the obtained bounds for commonly used $\phi$-divergences. On the other hand, when superlinear growth does not hold for $\phi$, we show that for any estimation method, evaluating the worst-case expectation has a $P$-dependent sample complexity lower bound that can be made arbitrarily large by changing $P$. In this case, we discuss the approach of adopting the generalized definition of $\phi$-divergence, through which $P$-independent sample complexity can be recovered, and hence demonstrate the essential role of absolute continuity in affecting statistical tractability.