Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers

Xu, Kaidi; Zhang, Huan; Wang, Shiqi; Wang, Yihan; Jana, Suman; Lin, Xue; Hsieh, Cho-Jui.

Abstract We prove that for a GNS-symmetric quantum Markov semigroup, the complete modified logarithmic Sobolev constant is bounded by the inverse of its complete positivity mixing time. For classical Markov semigroups, this gives a short proof that every sub-Laplacian of a Hörmander system on a compact manifold satisfies a modified log-Sobolev inequality uniformly for scalar and matrix-valued functions. For quantum Markov semigroups, we show that the complete modified logarithmic Sobolev constant is comparable to the spectral gap up to the logarithm of the dimension. Such estimates are asymptotically tight for a quantum birth-death process. Our results, along with the consequence of concentration inequalities, are applicable to GNS-symmetric semigroups on general von Neumann algebras.

More Like this