Title: Simple Optimization Methods for Extremely Large-Scale Convex Problems
Abstract
Presentation Slides
Paper


When solving extremely large-scale problems (with design dimension n like tens/hundreds of thousands), one is enforced to use methods with linear in n arithmetic cost of a step --- otherwise the very first iteration will never be finished. This requirement rules out all advanced polynomial time methods (for these methods, the arithmetic cost of a step is in-between O(n^2) and O(n^3)) and, as far as nonsmooth/constrained problems are concerned, leaves us with the only choice - simple black-box-oriented subgradient-type techniques.

A bad news about black-box-oriented techniques is that they are unable to solve large-scale problems to high accuracy (for small ε, the arithmetic cost of /ε -solution cannot be less than O(n^2\ln(1/ε)), and for all known methods it is at least O(n^4\ln(1/ε))). A good news is that there are cases when low accuracy solutions can be obtained in nearly dimension-independent number of steps, like O(1/ε), and that the corresponding methods are ``cheap'' (the arithmetic cost of a step, modulo the effort to evaluate the objective at a current iterate, is just O(n)).

In the talk, we

1. Overview theoretical limits of performance of black-box-oriented methods,
2. Present a new ``cheap'' Bundle-Mirror method for minimizing Lipschitz continuous convex functions over ``simple solids'' X and demonstrate that with this method, an ε -solution can be obtained in a (nearly) dimension-independent number of steps, provided that X possesses ``favourable geometry'' (e.g., is an Euclidean ball, or a simplex, or the spectahedron {X belong to R^(m x m): X=X^T >= 0, Tr(X)=1}, and discuss the issue of theoretical optimality of the Bundle-Mirror algorithm,
3. Illustrate the practical potential of simple optimization methods by a numerical example (Image Reconstruction in Positron Emission Tomography).