Cody Melcher Dissertation Defense

Abstract:

This dissertation develops first-order methods and finite-time convergence guarantees for saddle-point (i.e., min--max) optimization problems in several settings. First, we study convex--concave saddle point problems and introduce quadratic growth conditions on either the function values or their gradients, under which our proposed generalized accelerated primal--dual method achieves linear convergence to an optimal solution. We then consider nonconvex semi-infinite constrained min--max problems under either strong concavity or a PL condition on the two inner maximization problems. For this setting, we develop an inexact dynamic barrier primal--dual method and establish finite-time convergence to approximate KKT points. We further consider the problem under mere concavity of the inner maximization problems, resulting in a max-structured nonsmooth, nonconvex optimization problem with semi-infinite constraints. We introduce a quadratically regularized reformulation that allows our inexact dynamic barrier primal--dual method to be applied, and then connect solutions of the regularized problem back to the original nonsmooth problem. This yields finite-time convergence and complexity guarantees for the original max-structured nonsmooth, nonconvex problem. Finally, we demonstrate an end-to-end edge learning implementation in which a neural network is trained using the inexact dynamic barrier primal--dual method, quantized, and deployed on a microcontroller for on-device inference.

 

Join Zoom Meeting

Password: 769441