Smooth Optimization with Approximate Gradient

  • TITLE: Smooth Optimization with Approximate Gradient.

  • AUTHORS: 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: SIAM Journal on Optimization, 19(3), pp. 1171-1183, December 2008.

  • ArXiv PREPRINT: math.OC/0512344

  • PAPER: Local [PDF/SmoothSparseSDP.pdf pdf file