RMITOpt Seminar: Patrick Johnston, Rutgers Business School

Speaker: Dr. Patrick Johnstone, MSIS Department of the Rutgers Business School.

Title: Projective Splitting: A New Breed of First-Order Proximal Algorithms

Date and Time: Friday, February 28th, 3.30– 4.30pm, 2020 (Talk & Q/A)

Location: AGR Building 15, level 03, room 10 (Request for remote connect andy.eberhard (at) rmit.edu.au)

Abstract: Projective splitting is a proximal operator splitting framework for solving convex optimization problems and monotone inclusions. Unlike many operator splitting methods, projective splitting is not based on a fixed-point iteration. Instead, at each iteration a separating hyperplane is constructed between the current point and the primal-dual solution set. This gives more freedom in terms of stepsize selection, incremental updates, and asynchronous parallel computation. Despite these advantages, projective splitting had two important drawbacks which we have rectified in this work. First, the method uses calculations entirely based on the proximal operator of the functions in the objective. However, for many functions this is intractable. We develop new calculations based on forward steps – explicit evaluations of the gradient – whenever the gradient is Lipschitz continuous. This extends the scope of the method to a much wider class of problems. Second, no convergence rates were previously known for the method. We derive an O(1/k) rate for convex optimization problems, which is unimprovable for this algorithm and problem class. Furthermore, we derive a linear convergence rate under certain strong convexity and smoothness conditions.