TITLE: Smooth Optimization with Approximate Gradient.
AUTHOR: Alexandre d'Aspremont
ABSTRACT: We show that the optimal complexity of Nesterov's smooth first-order optimization algorithm is preserved when the gradient is only computed up to a small, uniformly bounded error. In applications of this method to semidefinite programs, this often means computing only a few dominant eigenvalues of the current iterate instead of a full matrix exponential, which significantly reduces the method's computational cost. This also allows sparse problems to be solved efficiently using maximum eigenvalue packages such as ARPACK.
STATUS: Submitted. Title changed from "Smooth Optimization for Sparse Semidefinite Programs".