Our derived certified intersection size is the optimal solution to an optimization problem, which involves the label probabilities. However, it is very challenging to compute the exact label probabilities due to the continuity of the isotropic Gaussian noise and the complexity of the base multi-label classifiers (e.g., complex deep neural networks). In response, we design a Monte Carlo algorithm to estimate the lower or upper bounds of label probabilities with probabilistic guarantees. More specifically, we can view the estimation of lower or upper bounds of label probabilities as a binomial proportion confidence interval estimation problem in statistics. Therefore, we use the Clopper-Pearson [1]} method from the statistics community to obtain the label probability bounds. Given the estimated lower or upper bounds of label probabilities, we design an efficient algorithm to solve the optimization problem to obtain the certified intersection size.
