Title: Efficient Stochastic Optimization for Attacking Randomness Involved Inference. Abstract: Recent years witnessed a surging interest in test-time defense against adversarial attacks by introducing randomness during model inference. Notable examples include randomized smoothing equipped with probabilistic certified robustness and adversarial purification that leverages score-based generalization models. Specifically, the adversarial purification achieves state-of-the-art adversarial robustness under the strongest existing attack. Perhaps the most important component to developing and validating adversarial robustness is efficient attacks. Stochastic Projected Gradient Descent (S-PGD), which combines Expectation over Transformation (EOT) and PGD attacks, has become a common strategy to attack inference randomness and validate defense strategies. However, it often has severe efficiency issues that make it prohibitive for complete verification. For example, one step of S-PGD requires multiple runs of score-based purification models for each data point. This work revisits the techniques attacking randomness-involved inference and subsumes them into a unified stochastic optimization framework, which enables us to use acceleration and variance reduction techniques to largely improve the convergence and thus reduce the cost of attack. In other words, the proposed work can significantly improve attack performance, given a fixed budget for attacking. 