Author(s): Alexandre W. d'Aspremont
Journal: Stochastic Systems
ISSN 1946-5238
Volume: 1;
Issue: 2;
Start page: 274;
Date: 2011;
Original page
Keywords: Semidefinite programming | stochastic optimization | subsampling
ABSTRACT
We derive a stochastic gradient algorithm for semidefinite optimization using randomization techniques. The algorithm uses subsampling to reduce the computational cost of each iteration and the subsampling ratio explicitly controls granularity, i.e. the tradeoff between cost per iteration and total number of iterations. Furthermore, the total computational cost is directly proportional to the complexity (i.e. rank) of the solution. We study numerical performance on some large-scale problems arising in statistical learning.
Journal: Stochastic Systems
ISSN 1946-5238
Volume: 1;
Issue: 2;
Start page: 274;
Date: 2011;
Original page
Keywords: Semidefinite programming | stochastic optimization | subsampling
ABSTRACT
We derive a stochastic gradient algorithm for semidefinite optimization using randomization techniques. The algorithm uses subsampling to reduce the computational cost of each iteration and the subsampling ratio explicitly controls granularity, i.e. the tradeoff between cost per iteration and total number of iterations. Furthermore, the total computational cost is directly proportional to the complexity (i.e. rank) of the solution. We study numerical performance on some large-scale problems arising in statistical learning.
