Randomized Algorithms for Extreme Convex Optimization

The field of mathematical optimization experienced a paradigm shift in the last decade: while the 20 years prior to about year 2005 were dominated by the development of interior-point methods, research activity since has almost entirely been focused on first-order methods. This was caused by several factors. Most notably, there has been a surge in the demand from practitioners, in fields such as machine learning, signal processing and data science, for new methods able to cope with new large scale problems. Moreover, an important role in the transition was played by the fact that accuracy requirements in many modern applications (such as classification and image denoising) were only moderate or low, which was in sharp contrast with the preceding focus on applications in classical domains such as engineering and physics where accuracy requirements were typically high. The paradigm shift would not have been possible, however, were it not for the development and success of modern gradient methods, the complexity of which improved upon classical results by an order of magnitude, using sophisticated tools such as the estimate sequence method and smoothing.

At the moment, mathematical optimization is experiencing yet another revolution, related to the introduction of randomization as an algorithmic design and analysis tool, much in the same way that probabilistic reasoning has recently begun to transform several other "continuous" fields, including numerical linear algebra and control theory. The import of randomization is at least twofold: it makes it possible to design new algorithms which scale to extreme dimensions, and at the same time it often leads to improved theoretical complexity bounds.

This project focuses on the design, complexity analysis and high-performing implementations of efficient randomized algorithms suitable for extreme convex optimization.

The project is designed to span the spectrum with i) foundational theoretical research at one end, ii) algorithm design and efficient HPC implementations in the middle, and iii) uptake of the methods by a high-tech company at the other extreme. Hence, the project is set up to achieve impact both in academia and in industry. The optimization algorithms that will be developed in this project will have countless applications in nearly all data-laden domains of human endeavour, including optimization, scientific computing, engineering, digital economy, machine learning, operational research, finance and healthcare.

Amazon. Amazon is the largest commercial cloud computing vendor - through Amazon Web Services (AWS) in general, and the Elastic Compute Cloud (EC2) in particular. Amazon supports my project in several ways. First, they offer $20,000 worth of compute and storage at AWS. I plan to implement the algorithms that will be developed in the proposal on EC2, which will facilitate direct take-up by industry. Implementation will be done by the PDRA or my existing collaborators already familiar with distributed computing, depending on the skills of the PDRA that will be employed. In my past research, my team has produced efficient multi-core, GPU and cluster (open MP / MPI) implementations of several algorithms we developed - and all members of my team were trained in parallel computing in Edinburgh. Further, Amazon is prepared to host the members of my team (PDRA, PhD students and myself) as Summer interns and/or research visitors for 1 to 6 months. In the past they have offered a Summer internship to my PhD student M. Takac.

Baidu. Baidu is the largest search engine in China. Their Big Data Lab, led by Prof Tong Zhang, has collaborated with me in the past on a different project [p22], and in Summer 2014 hosted my current PDRA Zheng Qu as a research visitor (covering all associated costs) for nearly 2 months. Baidu, as a project partner, will provide us with data orders of magnitude larger than what is normally available to researchers in academia, so that the algorithms developed in the project can be tested on genuinely massive data sets. Further, Baidu is prepared to fund research visits for the members of my team (myself, PDRA, PhD students) to their Beijing office, which demonstrates direct relevance of the project to the interests of Baidu. Finally, through this industrial partner I hope for the research results obtained during the Fellowship to get substantial visibility in Asia, further strengthening its impact.

Google. In September 2013, I have given an invited research talk on parallel coordinate descent methods [p32] in the Google Machine Learning seminar in Mountain View, California. Between then and December 2013, I have had several fruitful meetings with Google scientists Dr Yoram Singer and Dr Maya Gupta; some related to specific workpackages in this proposal. A version of an algorithm I developed is in operation at Google in their YouTube video recommendation system. I will continue utilizing my existing contacts at Google in the pursuit of collaboration on specific work packages in this proposal. In particular, I will seek Google's input in identifying the most relevant applications of the developed algorithms, so as to ensure wider impact. Should any of the methods be particularly successful, there is a chance it might be implemented at Google. My current PhD student Jakub Konecny will be working on all work packages of the project. As of his 2nd year of PhD, he is being fully funded by Google, through the Google European Doctoral Fellowship. As a part of this, he will visit Google for Summer internships and will benefit from having a Google mentor (Dr McMahan). This formal connection with Google provides another channel for knowledge exchange, impact and collaboration.

MSc Projects. Throughout the duration of the Fellowship I will supervise 3 MSc summer dissertation projects.