MSI Weekly Bulletin - Week starting Monday 29 May, 2006

Machine learning typically involves minimizing a differentiable loss function defined over a data set. The size of these data sets is currently exploding as the sensors generating them are becoming cheap, networked, and ubiquitous. Conventional optimization algorithms involving an innermost loop over the entire data set are very inefficient in this scenario. Optimization methods that can handle stochastic approximation of the loss (and its gradient) from small subsamples of data address this issue. Unfortunately many standard tools of optimization, such as Krylov subspaces and line searches, do not tolerate the noise inherent in stochastic approximation. Consequently, the algorithms employed in stochastic optimization tend to be primitive and inefficient; simple first-order gradient descent and evolutionary algorithms are the rule. Even these methods, however, beat sophisticated deterministic optimization by wide margins on large, redundant data sets. I am working on ways to accelerate first-order stochastic gradient descent by using second-order gradient information obtained cheaply and locally through implicit curvature matrix-vector products. In my stochastic meta-descent (SMD) algorithm, this cheap curvature information is built up iteratively into a stochastic approximation of Levenberg-Marquardt steps which are then used to adapt individual gradient step sizes. SMD handles noisy, correlated, and non-stationary data well, and can approach the rapid convergence of second-order methods at only linear cost per iteration, thus scaling up to extremely large systems. To date SMD has been applied to machine learning in multi-layer perceptrons, 3-D projection pipelines, support vector machines, and conditional random fields, enabling adaptive applications in computational fluid dynamics, computer vision, reinforcement learning, and text data mining.

The problem of optimal transportation is the following: given two probabililty measures, find a map that transports one onto the other, minimizing the integral of a cost function which depends only on the departure and arrival points. Although this is an old problem that goes back to Monge, it has come back to light since the discovery of Brenier in the mid eighties who found that when the cost is quadratic, optimal maps are just gradient of convex functions. A general theory is now available concerning the existence of the minimizers for general cost functions, with a generalization of the concept of convexity to c-convexity. All optimal maps derive from a c-convex potential, in turn solution to an elliptic Monge-Ampere equation. We will develop on the notion of c-convexity, and explain how a natural geometric condition on the cost function can been shown to be also a necessary and sufficient condition for smoothness of solutions of the associated Monge-Ampere equation when the measures are smooth. This "necessary" part thus completes the "sufficient" part recently obtained by Ma Trudinger and Wang. Finally we will discuss how this condition can be related to the curvature of the underlying manifold.