Lagrangian Sketching Methods for Large-Scale Optimization

Abstract

We developed the Lagrangian Sketching framework for solving large-scale optimization problems. The proposed framework extends the scope of Skecth & Project (SP) methods. The generic SP method for solving $\min_{Ax = b} |x|^2_B$ goes as follows. Starting from a random point $x_k$, the SP method updates $x_{k+1}$ as the solution of the following problem$:$ $$x_{k+1} = \text{argmin}_{S^{\top}Ax\ = \ S^{\top} b} ||x-x_k||^2_B = x_k - B^{-1} A^{\top}S (S^{\top}AB^{-1}A^{\top}S)^{\dagger}S^{\top}(Ax_k-b)$$