Speaker: Yixuan Qiu

Abstract: This work is motivated by the computation of the Fantope projection and selection model (FPS, Vu et al., 2013), a convex formulation of the sparse principal component analysis (SPCA). Most existing SPCA algorithms are based on nonconvex objective functions, which are computationally fast but have little global optimum guarantee. FPS, on the other hand, is convex, but requires solving a highly constrained optimization problem. The existing ADMM-based algorithm for FPS includes a projection step in each iteration, which requires a full eigen decomposition of a large matrix. Inspired by Kundu et al. (2018) and Mahdavi et al. (2012), we first develop a general projection-free algorithm for solving constrained convex optimization problems, where the constraint set is the intersection of several simple sets. Each of the simple sets can either be trivially projected onto, or has a simple boundary function. Under certain conditions, we prove that the original constrained problem is equivalent to a new unconstrained one, where fast iteration methods such as subgradient descent can be applied. In the final part, we go back to the FPS problem, and prove that it satisfies the sufficient conditions imposed in the algorithm above. New computational methods are then developed for solving FPS.

References:

Fantope projection and selection: https://papers.nips.cc/paper/5136-fantope-projection-and-selection-a-near-optimal-convex-relaxation-of-sparse-pca.pdf

Convex optimization over intersection of simple sets: https://arxiv.org/pdf/1710.06465.pdf

SGD with only one projection: https://papers.nips.cc/paper/4797-stochastic-gradient-descent-with-only-one-projection.pdf