Session: First-order methods for nonsmooth optimization
Chair: Digvijay Boob
Cluster: Nonlinear Optimization
Talk 1: Efficient Subgradient Method for Minimizing Nonsmooth Maximal Value Functions
Speaker: Hanyang Li
Abstract: We consider the minimization of a class of nonsmooth maximal value functions that are piecewise-smooth. Recent implementable Goldstein-style subgradient methods for general Lipschitz functions involve computationally intensive inner loops to approximate the descent direction. In this paper, we introduce a novel subgradient method that eliminates the sophisticated inner loops by employing a regularization technique, significantly improving computational efficiency for minimizing nonsmooth maximal value functions.
Talk 2: Dimension dependence in nonconvex optimization
Speaker: Guy Kornowski
Abstract: Optimization problems that arise in modern machine learning are often neither smooth nor convex, and typically high-dimensional. In this talk we will discuss the intricate role of the dimension in such problems, and compare it to smooth optimization. We will see that some approaches lead to significant gaps in dimension dependencies, yet sometimes these can be eliminated altogether. In particular, we will examine fundamental concepts such as stationarity, smoothing, and zero-order optimization, and show they exhibit exponential, polynomial, and no such gaps, respectively.
Talk 3: On the Sample Complexity of Imitation Learning for Smoothed Model Predictive Control
Speaker: Swati Padmanabhan
Abstract: Recent work in imitation learning has shown that having an expert controller that is both suitably smooth and stable enables stronger guarantees on the performance of the learned controller. However, constructing such smoothed expert controllers for arbitrary systems remains challenging, especially in the presence of input and state constraints. As our primary contribution, we show how such a smoothed expert can be designed for a general class of systems using a log-barrier-based relaxation of a standard Model Predictive Control (MPC) optimization problem. At the crux of this theoretical guarantee on smoothness is a new lower bound we prove on the optimality gap of the analytic center associated with a convex Lipschitz function, which we hope could be of independent interest. We validate our theoretical findings via experiments, demonstrating the merits of our smoothing approach over randomized smoothing.
