Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysis

• URL: http://arxiv.org/abs/2601.01311v1
• Date: Sun, 04 Jan 2026 00:24:43 GMT
• Title: Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysis
• Authors: Hong T. M. Chu,
• Abstract summary: Distributionally Robust (DR) optimization aims to certify worst-case risk within a Wasserstein uncertainty set.<n>This paper introduces a novel geometric framework based on the least concave majorants of the growth rate function.<n>We extend this framework to complexity analysis, introducing a deterministic bound that complements standard statistical bound.
• Score: 0.7106986689736828
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Lipschitz-Based Robustness Certification for Recurrent Neural Networks via Convex Relaxation [0.0]
  We present RNN-SDP, a relaxation based method that models the RNN's layer interactions as a convex problem.<n>We also explore an extension that incorporates known input constraints to further tighten the resulting Lipschitz bounds.
  arXiv  Detail & Related papers  (2025-09-22T15:26:46Z)
• Distributionally Robust Safety Verification of Neural Networks via Worst-Case CVaR [3.0458514384586404]
  This paper builds on Fazlyab's quadratic-constraint (QC) and semidefinite-programming (SDP) framework for neural network verification.<n>The integration broadens input-uncertainty geometry-covering ellipsoids, polytopes, and hyperplanes-and extends applicability to safety-critical domains.
  arXiv  Detail & Related papers  (2025-09-22T07:04:53Z)
• Risk-Averse Certification of Bayesian Neural Networks [70.44969603471903]
  We propose a Risk-Averse Certification framework for Bayesian neural networks called RAC-BNN.<n>Our method leverages sampling and optimisation to compute a sound approximation of the output set of a BNN.<n>We validate RAC-BNN on a range of regression and classification benchmarks and compare its performance with a state-of-the-art method.
  arXiv  Detail & Related papers  (2024-11-29T14:22:51Z)
• Error Bounds of Supervised Classification from Information-Theoretic Perspective [0.0]
  We explore bounds on the expected risk when using deep neural networks for supervised classification from an information theoretic perspective. We introduce model risk and fitting error, which are derived from further decomposing the empirical risk.
  arXiv  Detail & Related papers  (2024-06-07T01:07:35Z)
• VALID: a Validated Algorithm for Learning in Decentralized Networks with Possible Adversarial Presence [13.612214163974459]
  We introduce the paradigm of validated decentralized learning for undirected networks with heterogeneous data. VALID protocol is the first to achieve a validated learning guarantee. Remarkably, VALID retains optimal performance metrics in adversary-free environments.
  arXiv  Detail & Related papers  (2024-05-12T15:55:43Z)
• Distributionally Robust Skeleton Learning of Discrete Bayesian Networks [9.46389554092506]
  We consider the problem of learning the exact skeleton of general discrete Bayesian networks from potentially corrupted data. We propose to optimize the most adverse risk over a family of distributions within bounded Wasserstein distance or KL divergence to the empirical distribution. We present efficient algorithms and show the proposed methods are closely related to the standard regularized regression approach.
  arXiv  Detail & Related papers  (2023-11-10T15:33:19Z)
• Capsa: A Unified Framework for Quantifying Risk in Deep Neural Networks [142.67349734180445]
  Existing algorithms that provide risk-awareness to deep neural networks are complex and ad-hoc. Here we present capsa, a framework for extending models with risk-awareness.
  arXiv  Detail & Related papers  (2023-08-01T02:07:47Z)
• Fine-grained analysis of non-parametric estimation for pairwise learning [9.676007573960383]
  We are concerned with the generalization performance of non-parametric estimation for pairwise learning. Our results can be used to handle a wide range of pairwise learning problems including ranking, AUC, pairwise regression and metric and similarity learning.
  arXiv  Detail & Related papers  (2023-05-31T08:13:14Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Self-Certifying Classification by Linearized Deep Assignment [65.0100925582087]
  We propose a novel class of deep predictors for classifying metric data on graphs within PAC-Bayes risk certification paradigm. Building on the recent PAC-Bayes literature and data-dependent priors, this approach enables learning posterior distributions on the hypothesis space.
  arXiv  Detail & Related papers  (2022-01-26T19:59:14Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• CC-Cert: A Probabilistic Approach to Certify General Robustness of Neural Networks [58.29502185344086]
  In safety-critical machine learning applications, it is crucial to defend models against adversarial attacks. It is important to provide provable guarantees for deep learning models against semantically meaningful input transformations. We propose a new universal probabilistic certification approach based on Chernoff-Cramer bounds.
  arXiv  Detail & Related papers  (2021-09-22T12:46:04Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.