strongly convex sets

Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets

  • Benjamin Grimmer
  • nliu15
    • Categories Convex Optimization Tags , , ,

    We consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the $L$-smooth, strongly convex objective. This model includes Frank-Wolfe methods and their many variants. Over the problem class of strongly convex constraint sets $S$, our main result proves that … Read more

    Generalized power method for sparse principal component analysis

  • Michel Journee
  • Yurii Nesterov
  • Peter Richtarik
  • Rodolphe Sepulchre
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, … Read more