Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysis
Hong T.M. Chu · 2026
Read Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysis by Hong T.M. Chu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-01311.txt.
Introduction
Hong Chu builds a geometric tool for certifying risk when the true data pattern is uncertain. Distributionally robust methods promise a worst-case risk inside a ball of plausible patterns. Common certificates are either loose, because they assume the worst slope everywhere, or shallow, because they use only local slope information.
Chu's concave certificates instead cap the loss's growth curve with the tightest concave curve above it. That yields a tight risk bound that still works when the loss is not smooth. She extends the idea to generalization, bounding how much worse a model can do on fresh data, and to the gap between attacked and clean complexity measures. Some dependencies on network size drop out entirely. A practical version, the adversarial score, allows layer-by-layer checks of neural networks. Numerical tests on classification and regression back the theory.
Catalog record
| CREATOR | Hong T.M. Chu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-01311
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysis Hong T.M. Chu Abstract Distributionally Robust (DR) optimization aims to certify worst-case risk within a Wasserstein uncertainty set. Current certifications typically rely either on global Lipschitz bounds, which are often conservative, or on local gradient information, which provides only a first-order approximation. This paper introduces a novel geometric framework based on the least concave majorants of the growth rate function. Our proposed concave certificate establishes a tight bound of DR risk that remains applicable to non-Lipschitz and non-differentiable losses. We extend this framework to complexity analysis, introducing a deterministic bound that complements standard statistical generalization bound. Furthermore, we utilize this certificate to bound the gap between adversarial and empirical Rademacher complexity, demonstrating that dependencies on input diameter, network width, and depth can be eliminated. For practical application in deep learning, we introduce the adversarial score as a tractable relaxation of the concave certificate that enables efficient and layer-wise analysis of neural networks. We validate our theoretical results in various numerical experiments on classification and regression tasks on real-world data. Keywords: Distributionally Robust Optimization, Generalization Bound, Rademacher Complexity 1 Introduction Given feature data X and label Y , we seek a parameterized network f_{\theta} to model their relationship Y\approx f_{\theta}(X) . This is typically formulated as minimizing the expected loss \inf_{\theta\in\Theta}\mathbb{E}_{Z\sim\mathbb{P}_{\rm true}}[\bm{l}(Z;\theta)], (1) where Z=(X,Y) , \Theta is the set of feasible parameters and \bm{l} is the loss function. The true data distribution \mathbb{P}_{\rm true} in ( 1 ) is often unknown and approximated by the empirical distribution \mathbb{P}_{N}=\frac{1}{N}\sum_{i=1}^{N}\bm{\chi}_{\{Z^{(i)}\}} , which can lead to over-fitting. To mitigate this issue, the robust counterpart of ( 1 ) aims to minimize the worst-case loss within a neighborhood of \mathbb{P}_{N} by solving \inf_{\theta\in\Theta}\sup_{\mathbb{P}:\mathcal{D}(\mathbb{P},\mathbb{P}_{N})\leq\epsilon}\ \mathbb{E}_{\mathbb{P}}[\bm{l}(Z;\theta)], (2) where \mathcal{D} is a discrepancy on the probability space \mathcal{P}(\mathcal{Z}) . In this work, we focus on the Wasserstein discrepancy (Definition 3 ), which intuitively represents the minimum cost to transport the mass of \mathbb{P} to that of \mathbb{P}_{N} . The inner supremum problem is referred to as the distributionally robust (DR) risk: \text{(DR risk)}\quad\mathcal{R}_{p}(\epsilon)=\sup_{\mathbb{P}:\mathcal{W}_{p}(\mathbb{P},\mathbb{P}_{N})\leq\epsilon}\mathbb{E}_{\mathbb{P}}[\bm{l}(Z;\theta)]. (3) Distributionally Robust Risk. Essentially, the DR risk ( 3 ) quantifies the sensitivity of the loss value under distributional shifts bounded by a budget \delta . In general, computing \mathcal{R}_{p}(\epsilon) is intractable. To bypass this, two primary approaches are used: the Lipschitz certificate and the gradient certificate . The Lipschitz certificate estimates an upper bound of \mathcal{R}_{p}(\epsilon) . For instance, if \bm{l} is L_{\theta} -Lipschitz then \mathcal{R}_{p}(\epsilon)\leq\mathbb{E}_{\mathbb{P}_{N}}[\bm{l}(Z;\theta)]+L_{\theta}\epsilon , and this bound is known to be tight for linear hypothesis ( 16 , 11 , 10 , 1 , 13 , 14 ) . We refer reader to a recent survey by 41 on how Lipschitz calculus can be used to study robustness. Estimating the global Lipschitz constant L_{\theta} for deep networks often reduces to a layer-wise estimation of Lipschitz constants ( 35 , 32 , 24 ) . This raises fundamental questions: why do functions like the entropy loss or the square-root loss ( 8 ) exhibit robustness despite being non-Lipschitz? Furthermore, even though the 4\times Sigmoid, Tanh and ReLU activations share a Lipschitz modulus of 1, why do they not possess identical robustness properties? Alternatively, the other approach of gradient certificate ( 5 , 15 , 3 ) approximates \mathcal{R}_{p}(\epsilon) using first-order information as \mathcal{R}_{p}(\epsilon)\approx\mathbb{E}_{\mathbb{P}_{N}}[\bm{l}(Z;\theta)]+\epsilon\left(\mathbb{E}_{\mathbb{P}_{N}}[\left\|\nabla_{x}\bm{l}(Z;\theta)\right\|^{q}]\right)^{1/q} where 1/p+1/q=1 . However, this first-order estimation is asymptotic and holds only as the budget \epsilon\rightarrow 0 . Moreover, it requires \bm{l} to be differentiable and does not provide a true upper bound of \mathcal{R}_{p}(\epsilon) . Generalization Capability. To understand the model’s generalization capability in this robust setting, we utilize the notion of Rademacher complexity ( 6 , 23 ) . For a class of loss functions \mathcal{L}:=\{z\mapsto\bm{l}(z;\theta)\mid\theta\in\Theta\} , the empirical Rademacher Complexity (RC) measures the richness of \mathcal{L} by its ability to correlate with random noise on the sample \mathcal{Z}_{N} : \text{(RC)}\quad\hat{\mathfrak{R}}_{\mathcal{Z}_{N}}(\mathcal{L})=\mathbb{E}_{\sigma}\left[\sup_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}\sigma_{i}\bm{l}(Z^{(i)};\theta)\right], (4) where \sigma=(\sigma_{1},\dots,\sigma_{N}) are independent Rademacher variables taking values in \{-1,+1\} with equal probability. Intuitively, if RC is large, then \mathcal{L} has the capacity to fit arbitrary noise \sigma , leading to overfitting. Conversely, a small RC indicates that \mathcal{L} learns meaningful patterns. Standard results by 7 , 23 show that \hat{\mathfrak{R}}_{\mathcal{Z}_{N}}(\mathcal{L}) directly bounds the generalization gap: \mathbb{E}_{\mathbb{P}_{\rm true}}[\bm{l}(Z;\theta)]\lesssim\mathbb{E}_{\mathbb{P}_{N}}[\bm{l}(Z;\theta)]+c\hat{\mathfrak{R}}_{\mathcal{Z}_{N}}(\mathcal{L})+C\!(\delta)\!, (5) where C(\delta) is a confidence term. Therefore, a small RC also implies a tight generalization bound. In the context of DRO, we focus on the class of worst-case loss functions \tilde{\mathcal{L}}_{\epsilon}:=\{z\mapsto\tilde{\bm{l}}_{\epsilon}(z;\theta)=\sup_{z^{\prime}:d(z^{\prime},z)\leq\epsilon}\bm{l}(z^{\prime};\theta)\mid\theta\in\Theta\} , which leads to the definition of Adversarial Rademacher Complexity (ARC) ( 22 , 38 , 2 , 36 ) : \text{(ARC)}\,\hat{\mathfrak{R}}_{\mathcal{Z}_{N}}(\tilde{\mathcal{L}}_{\epsilon})=\mathbb{E}_{\sigma}\left[\sup_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}\sigma_{i}\tilde{\bm{l}}_{\epsilon}(Z^{(i)};\theta)\right]. (6) Deriving tight bounds for ARC is significantly more challenging than for RC because the inner supremum operator destroys structural properties that are typically exploited in traditional complexity analysis. For linear hypotheses, 22 , 38 establish that the gap between ARC and RC scales linearly with the weight norm \left\|\theta\right\| , which serves as the Lipschitz constant. For deep neural networks, however, 2 and 36 show these bounds grow not just with weights, but also with the network’s depth, width, and data diameter \mathcal{Z}_{N} . This predicted surge is counter-intuitive when compared to the DR risk \mathcal{R}_{p} mentioned earlier: the adversarial risk of a feedforward network is fundamentally controlled by its Lipschitz constant, suggesting that the actual complexity should not blow up simply because a network becomes wider or deeper. Main Contributions. We summarize our main contributions and organize our paper as follows. • We introduce a novel framework to estimate the distributionally robust risk \mathcal{R}_{p}(\epsilon) . This geometric framework establishes an elegant bound showing that the robust-empirical risk gap \mathcal{R}_{p}(\epsilon)-\hat{\mathcal{R}} stays between the average of the least star-shaped majorants \operatorname{lb}_{p}(\epsilon) and the least concave majorant \operatorname{cc}_{p}(\epsilon) of loss’s growth functions (Theorem 1 ). Notably, we do not require the loss \bm{l} to be convex/differentiable/Lipschitz, or the cost d to be a metric, or the domain \mathcal{Z} to be bounded. Our analysis reveals how the DR risk \mathcal{R}_{p}(\epsilon) evolves as the exponent p changes (Corollary 1 ) and provides exact conditions for determining whether \mathcal{R}_{p}(\epsilon) is finite (Corollary 2 , Example 1 ). • We extend this framework to analyze robust generalization by introducing concave complexity \hat{\mathfrak{C}}_{\mathcal{Z}_{N}}(\mathcal{L},\epsilon) , defined as the supremum of the least concave majorant of the maximal rates across the loss class \mathcal{L} . This metric allows us to derive a deterministic generalization bound (Proposition 1 ) that complements the standard statistical bound ( 5 ). Analogous to standard Rademacher complexity, we prove that our proposed concave complexity exhibits several calculus properties, including monotonicity, subadditivity, invariance under convex hull, and a contraction lemma. • By leveraging these properties, we prove that the adversarial-empirical Rademacher complexity gap is controlled by \frac{1}{\sqrt{N}}\hat{\mathfrak{C}}_{\mathcal{Z}_{N}}(\mathcal{L},\epsilon) (Theorem 2 ) and establish a corresponding result for the adversarial-empirical concave complexity gap (Theorem 3 ). Specifically, our framework recovers existing complexity bounds for linear classifiers (Example 3 ) while providing significantly tighter bounds for MLPs (Example 5 ) compared to previous works. We demonstrate that many components in existing bounds (such as input diameter, network width, and depth) can be removed entirely, and the loss class can be tailored to obtain dimension-free bound. • To facilitate practical implementation in deep learning when d is the