Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions

arXiv:2202.00992v3 Announce Type: replace-cross
Abstract: Performance of optimization on quadratic problems sensitively depends on the low-lying part of the spectrum. For large (effectively infinite-dimensional) problems, this part of the spectrum can often be naturally represented or approximated by power law distributions, resulting in power law convergence rates for iterative solutions of these problems by gradient-based algorithms. In this paper, we propose a new spectral condition providing tighter upper bounds for problems with power law optimization trajectories. We use this condition …

abstract arxiv convergence cs.lg cs.ne iterative law low math.oc optimization part performance power rate spectrum type