Many machine learning tasks (e.g. metric and manifold learning problems)
can be formulated as convex semidefinite programs. To enable the applica-
tion of these tasks on a large-scale, scalability and computational efficiency
are considered desirable properties for a practical semidefinite programming
algorithm. In this paper, we theoretically analyse a new bilateral greedy opti-
mization(denoted BILGO) strategy in solving general semidefinite programs
on large-scale datasets. As compared to existing methods, BILGO employs
a bilateral search strategy during each optimization iteration. In such an
iteration, the current semidefinite matrix solution is updated as a bilater-
al linear combination of the previous solution and a suitable rank-1 matrix,
which can be efficiently computed from the leading eigenvector of the descent
direction at this iteration. By optimizing for the coefficients of the bilateral
combination, BILGO reduces the cost function in every iteration until the
KKT conditions are fully satisfied, thus, it tends to converge to a global opti-
mum. For an ǫ-accurate solution, we prove the number of BILGO iterations
needed for convergence is O(ǫ−1). The algorithm thus successfully combines
the efficiency of conventional rank-1 update algorithms and the effectiveness
of gradient descent. Moreover, BILGO can be easily extended to handle
low rank constraints. To validate the effectiveness and efficiency of BILGO,
we apply it to two important machine learning tasks, namely Mahalanobis
metric learning and maximum variance unfolding. Extensive experimental
results clearly demonstrate that BILGO can solve large-scale semidefinite programs efficiently.