Foundations of Distributed and Large Scale Computing Optimization

Objective

In a wide range of application fields (inverse problems, machine learning, computer vision, data analysis, networking,...), large scale optimization problems need to be solved.

The objective of this course is to introduce the theoretical background which makes it possible to develop efficient algorithms to successfully address these problems by taking advantage of modern multicore or distributed computing architectures. This course will be mainly focused on nonlinear optimization tools for dealing with convex problems. Proximal tools, splitting techniques and Majorization-Minimization strategies which are now very popular for processing massive datasets will be presented. Illustrations of these methods on various applicative examples will be provided.

Course outline

• 1. Background on convex analysis
• 2. Parallel and distributed proximal splitting methods
• 3. Parallelization through Majorization-Minimization approaches

1. Background on convex analysis

• 1.1. Convex sets and functions
• 1.2. Differentiability and subdifferentiability
• 1.3. Proximity operator
• 1.4. Conjugate function
• 1.5. Duality results

2. Parallel and distributed proximal splitting methods

• 2.1. Fixed point algorithm and Fejér sequences
• 2.2. Minimization of a sum of convex functions
• 2.3. Primal-dual proximal parallel algorithms
• 2.4. Distributed techniques based on consensus approaches

3. Parallelization through Majorization-Minimization approaches

• 3.1. Majorization-Minimization principle
• 3.2. Majorization techniques
• 3.3. Half-Quadratic methods
• 3.4. Variable metric Forward-Backward algorithm
• 3.5. Subspace algorithms (memory gradient, BFGS, ...)
• 3.6. Parallel approaches using block-coordinate strategies