Four papers have been selected as finalists of the best paper competition by the best paper committee
The finalists will be featured in a dedicated session at ICCOPT 2019, and the prize winner will be determined after the finalist session.
joint work with Michael Hintermüller, Carlos Rautenberg
In this talk, which is based on recent work with Prof. Michael Hintermüller and Dr. Carlos N. Rautenberg, I will discuss the directional differentiability of solution maps associated to elliptic quasi-variational inequalities (QVIs) of obstacle type. QVIs are generalisations of variational inequalities (VIs) where the constraint set associated to the inequality also depends on the solution, adding an extra source of potential nonlinearity and nonsmoothness to the problem. I will show that the map taking the source term into the set of solutions is directionally differentiable in a certain sense and give an outline of the proof, and we will see that the directional derivative can be characterised as the monotone limit of directional derivatives associated to certain VIs. If time allows, the theory will be illustrated with an application of QVIs in thermoforming.
joint work with Emmanuel J. Candes
We consider the fundamental problem of solving quadratic systems of equations in n variables. We propose a novel method, which starting with an initial guess computed by means of a spectral method, proceeds by minimizing a nonconvex functional. There are several key distinguishing features, most notably, a distinct objective functional and novel update rules, which operate in an adaptive fashion and drop terms bearing too much influence on the search direction. These careful selection rules provide a tighter initial guess, better descent directions, and thus enhanced practical performance. On the theoretical side, we prove that for certain unstructured models of quadratic systems, our algorithms return the correct solution in linear time, i.e. in time proportional to reading the data as soon as the ratio between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems and prove that our algorithms achieve a statistical accuracy, which is nearly un-improvable. We complement our theoretical study with numerical examples showing that solving random quadratic systems is both computationally and statistically not much harder than solving linear systems of the same size. For instance, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a least-squares problem of the same size.
joint work with Dmitriy Drusvyatskiy, Sham Kakade, Jason D. Lee
The stochastic subgradient method forms the algorithmic core of modern statistical and machine learning. We understand much about how it behaves for problems that are smooth or convex, but what guarantees does it have in the absence of smoothness and convexity? We prove that the stochastic subgradient method, on any semialgebraic locally Lipschitz function, produces limit points that are all first-order stationary. More generally, our result applies to any function with a Whitney stratifiable graph. In particular, this work endows the stochastic subgradient method, and its proximal extension, with rigorous convergence guarantees for a wide class of problems arising in data science—including all popular deep learning architectures.
In this talk, we shall demonstrate how second order sparsity (SOS) in important optimization problems can be exploited to design highly efficient algorithms. The SOS property appears naturally when one applies a semismooth Newton (SSN) method to solve the subproblems in an augmented Lagrangian method (ALM) designed for certain classes of structured convex optimization problems. With in-depth analysis of the underlying generalized Jacobians and sophisticated numerical implementation, one can solve the subproblems at surprisingly low costs. For lasso problems with sparse solutions, the cost of solving a single ALM subproblem by our second order method is comparable or even lower than that in a single iteration of many first order methods. Consequently, with the fast convergence of the SSN based ALM, we are able to solve many challenging large scale convex optimization problems in big data applications efficiently and robustly. For the purpose of illustration, we present a highly efficient software called SuiteLasso for solving various well-known Lasso-type problems.