Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysis
This work addresses the challenge of conservative or approximate risk certifications in machine learning, offering a more precise and broadly applicable method for distributionally robust optimization.
The paper tackles the problem of certifying worst-case risk in distributionally robust optimization by introducing a geometric framework based on least concave majorants, which provides tight bounds for non-Lipschitz and non-differentiable losses and eliminates dependencies on network parameters in complexity analysis. It validates these results with numerical experiments on real-world classification and regression tasks.
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.