UC Berkeley

Standard machine learning (ML) algorithms exhibit catastrophic failures when subject to uncertainties in their input data, such as attacks generated by an adversary. Robustness against such uncertainties must be guaranteed in order to reliably deploy ML in safety-critical settings, such as autonomous driving, healthcare, and the operation of power systems. This dissertation presents theoretical and computational advancements in provably robust machine learning. We both introduce efficient optimization methods to certify the robustness of prior ML models, as well as design novel ML models endowed with mathematical proof of robustness. By exploiting key structures in the underlying certification problems, the proposed methods achieve state-of-the-art robustness and efficiency.

In the first part of this dissertation, we consider certifying the robustness of given, pretrained machine learning models. This robustness certification problem amounts to solving a difficult nonconvex optimization problem, and therefore a more tractable approach for generating safety guarantees is to lower-bound the optimization. We begin by considering a branch-and-bound approach to computing such lower bounds. In doing so, we leverage the piecewise linear structure of ReLU neural networks to develop branching schemes that minimize the looseness of the desired lower bounds in a worst-case sense. Next, we show that ReLU neural networks may be rewritten in a min-max affine form. We prove that this min-max affine structure allows us to efficiently solve the nonconvex robustness certification problem to global optimality by solving an equivalent convex reformulation. We also consider certifying the robustness of models in the case where the inputs are subject to random noise. A data-driven, convex optimization-based method is developed that simultaneously localizes neural network outputs and verifies their safety, all with high-probability guarantees. We show that our data-driven method's sample complexity can be dramatically reduced by leveraging the compositional structure of neural networks.

In the second part of this dissertation, we consider the design of robust machine learning models that are capable of withstanding uncertainties and attacks in their inputs, and are amenable to robustness certification. First, we propose feature-convex neural networks, which consist of the composition of a Lipschitz continuous feature map followed by a convex neural network. We utilize this composite convex structure of our model to derive deterministic, closed-form robustness certificates that match or outperform those of prior provably robust ML methods. Finally, we introduce locally biased randomized smoothing as a means to robustify an otherwise general, non-robust pretrained classifier. Our model inherits a nonlinear interpolation structure from which we prove certified robustness guarantees, and empirically show an enhancement in robustness against adversarial attacks.