Professor Liza Rebrova will talk about: 'On designing efficient randomized solvers for structured linear systems and optimization problems'
Randomized iterative solvers approach large linear systems through a sequence of small random subproblems, usually with the aim of reducing overall computational cost. While inexpensive iterations alone do not guarantee an efficient solver, I will discuss how these methods can be very effective in multiple contexts, and why their effectiveness depends on local updates exploiting the global structure of the problem well.
Specifically, based on recent work on sketch-and-project methods, I plan to discuss both the design of randomized linear solvers and their role within optimization methods. I will first discuss subspace-constrained randomized coordinate descent, which uses a fixed Nyström core together with fresh block updates to provide implicit preconditioning. This allows a low-rank approximation to accelerate the solution of the full system, with convergence gains quantified by a tail condition number that can be much smaller than the standard condition number. I will then discuss accelerated sketch-and-project as an inner solver for online Newton methods and its effect on the statistical efficiency of averaged iterates.