Differential geometry and the complexity of robust optimization of smooth functions

Ramarathnam Venkatesan (C+AI, Microsoft)

Joint work with Bhargav Narayanan, SteveMiller (Mathematics Department, RutgersUniversity) and Kartik Gupta (CMU)

As reliance on Al for business purposes goes up, coping with loss functions with no closed form descriptions (e.g., DNNs) and robustness to adversarial corruption are emerging as essential requirements. Hence a general method for using existing solutions to derive robust constructions that are stable under small adversarial perturbations is of importance.

We present a universal construction that uses a random walk (called Property T walk (PTW)) algorithm that is applicable to all smooth loss functions and at each step uses existing optimizers in lower dimensions as a black box.

We describe many fundamental hurdles in formulations for the full generality of smooth functions in this context. Circumventing the hurdles leads us to differential geometric concepts such as Morse approximations and stability, but we need to connect soft topological concepts to concrete run time bounds. Our algorithm uses quantities well defined (=co-ordinate independent) on manifolds and uses its own random co-ordinates. We show that PTW makes progress at a step using property T, and we use a simulation argument that PTW cannot distinguish between a smooth function and its mildly perturbed version, and a new notion of co-convergence we obtain (near) polynomial run time bounds for convergence. The function values attained during the walk constitute a semi-martingale which allows us to correlate the laws at infinity and when the algorithm stops.