Accelerated Coordinate Descent Methods for Big Data Problems

Much of modern society and economy, in the United Kingdom and elsewhere, is moving in the direction of digitization and computation. Humankind is now able to collect and store enormous quantities of digital data coming from sources such as health records (e.g., IBM ``Watson'' project, MRI/CT scans), government databases (e.g., e-Government, GORS: government operational research service), social networks (e.g., Facebook, Linked-IN, delicious), online news (e.g., New York Times article database), corporate databases (e.g., bank records, Amazon.com) and the internet. Global society is, as a consequence, facing many unprecedented challenges and opportunities. One of the biggest of these has to do with the ability (or rather, lack thereof) to distill, understand and utilize in an optimal way the information contained within these gigantic data sources. The main technology for this is to "form an optimization problem'' and then solve it using a well-chosen optimization algorithm in a suitable computing environment (e.g., a multicore workstation, GPU-enabled machine, cloud).

In this project we aim to contribute to a breakthrough in our ability to solve optimization problems arising from big data domains via developing, analyzing and implementing new accelerated parallel coordinate descent (CD) methods. Since in big data problems the data is typically highly structured, well-designed CD methods can have very low memory requirements and arithmetic cost per iteration---often much smaller than the dimension of the problem. This is in sharp contrast with standard methods whose arithmetic complexity of a single iteration depends on the dimension at least quadratically.

Our research objectives are:

1. Acceleration Theory. We will analyze the iteration complexity (i.e., give bounds on the number of iterations/steps needed to achieve a prescribed level of accuracy) of new parallel coordinate descent methods accelerated using the following 4 strategies: a) nonuniformity (of the frequency with which individual coordinates are updated), b) asynchronicity (of updates and computation), c) distribution (of data and computation to nodes of a cluster) and d) inexactness (of certain operations and computations the algorithm depends on).

2. Stochastic Gradient Descent. We will analyze theoretically and test numerically the relationship between parallel coordinate descent (CD) methods and parallel stochastic gradient descent (SGD) methods.

3. ACDC Code. We will implement the accelerated algorithms in a code which we will make publicly available.

The pathways to impact document details the ways in which we plan to achieve non-academic impact. The Case for Support details the academic impact.

Here we offer a brief summary:

Academic Impact:
- close research communities: optimization, operational research, numerical analysis, computer science, machine learning, compressed sensing, high performance computing, ITC
- more distant research communities: biology, astronomy, civil engineering, topology design, signal processing
- individuals: Prof Nesterov (Louvain), Prof Srebro (Chicago), Martin Takac (Edinburgh), PDRA, Prof Gondzio (Edinburgh), Prof Recht (Madison), Prof Wright (Madison), Dr Forgan (Astronomy)

Non-academic Impact:
- ACDC code (publicly available efficient code based on the algorithms developed in Module 1)
- SAS Institute (Dr Polik, Dr Chari, Dr Griffin)
- Western General Hospital (Dr Green)
- Arup (Mr Simpson)

Pathways:
- writing papers in top journals
- presenting at top conferences and workshops
- website with code at code.google.com + links to it from various places
- meetings with and feedback from SAS Institute at conferences (at least 1-2 x per year) and via teleconferencing facilities
- visit to SAS Headquarters in Cary, North Carolina
- impact workshop (to be held in May 2015)
- supervision of 2 MSc dissertations (Summer 2013 and Summer 2014)

Since structured convex optimization, randomized algorithms and data mining are important and fast growing fields, this proposal is timely for establishing and growing an internationally competitive research group in this area based in the UK.

Quote from EPSRC website: "For UK research to have maximum impact, our researchers need to work with the very best on the global stage." We strongly believe that, given the quality of the network of researchers involved and, in particular, of the visiting researchers, this proposal falls into this category.