TBA
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.
Let $W=W^*$ be a large random matrix. For a broad range of ensembles it is known that the resolvent $G(z):=(W-z)^{-1}$ concentrates around a deterministic quantity as long as $|\Im z|$ is larger than the local eigenvalue spacing of $W$. This is the so-called single-resolvent local law. Multi-resolvent local laws extend this framework by showing that products of several resolvents also concentrate. In this talk, I will discuss two phenomena that provide additional information beyond the standard local laws: decorrelation in energy space and gains from taking expectations. I will also present several recent applications of these results, which would not be accessible via standard local laws. These applications include non-Gaussian corrections to fluctuations in local laws, law of fractional logarithm for Wigner minor process and hyperuniformity of eigenvalues of non-Hermitian random matrices. The talk is based on several recent joint works with Z. Bao, G. Cipolloni, L. Erd{\H o}s and J. Henheik.