Shiqian Ma

A Riemannian smoothing steepest descent method for non-Lipschitz optimization on submanifolds

  • Xiaojun Chen
  • Shiqian Ma
  • Chao Zhang
    • Categories Nonlinear Optimization Tags , , , ,

    In this paper, we propose a Riemannian smoothing steepest descent method to minimize a nonconvex and non-Lipschitz function on submanifolds. The generalized subdifferentials on Riemannian manifold and the Riemannian gradient sub-consistency are defined and discussed. We prove that any accumulation point of the sequence generated by the Riemannian smoothing steepest descent method is a stationary … Read more

    Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold

  • Shiqian Ma
  • Bokun Wang
  • Lingzhou Xue
    • Categories Nonlinear Optimization

    Riemannian optimization has drawn a lot of attention due to its wide applications in practice. Riemannian stochastic first-order algorithms have been studied in the literature to solve large-scale machine learning problems over Riemannian manifolds. However, most of the existing Riemannian stochastic algorithms require the objective function to be differentiable, and they do not apply to … Read more

    A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis

  • Shixiang Chen
  • Shiqian Ma
  • Bingyuan Liu
  • Zhongruo Wang
  • Lingzhou Xue
  • Hongyu Zhao
    • Categories Nonlinear Optimization

    Spectral clustering is one of the fundamental unsupervised learning methods widely used in data analysis. Sparse spectral clustering (SSC) imposes sparsity to the spectral clustering and it improves the interpretability of the model. This paper considers a widely adopted model for SSC, which can be formulated as an optimization problem over the Stiefel manifold with … Read more

    Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization

  • Krishnakumar Balasubramanian
  • Shiqian Ma
  • Jiaxiang Li
    • Categories Nonlinear Optimization

    We consider stochastic zeroth-order optimization over Riemannian submanifolds embedded in Euclidean space, where the task is to solve Riemannian optimization problem with only noisy objective function evaluations. Towards this, our main contribution is to propose estimators of the Riemannian gradient and Hessian from noisy objective function evaluations, based on a Riemannian version of the Gaussian … Read more

    Accelerated Dual-Averaging Primal-Dual Method for Composite Convex Minimization

  • Shiqian Ma
  • Yuqiu Qian
  • Conghui Tan
  • Tong Zhang
    • Categories Convex and Nonsmooth Optimization

    Dual averaging-type methods are widely used in industrial machine learning applications due to their ability to promoting solution structure (e.g., sparsity) efficiently. In this paper, we propose a novel accelerated dual-averaging primal-dual algorithm for minimizing a composite convex function. We also derive a stochastic version of the proposed method which solves empirical risk minimization, and … Read more

    Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities

  • Krishnakumar Balasubramanian
  • Shiqian Ma
  • Meisam Razaviyayn
  • Zhongruo Wang
    • Categories Nonlinear Optimization

    In this paper, we study zeroth-order algorithms for minimax optimization problems that are nonconvex in one variable and strongly-concave in the other variable. Such minimax optimization problems have attracted significant attention lately due to their applications in modern machine learning tasks. We first design and analyze the Zeroth-Order Gradient Descent Ascent (ZO-GDA) algorithm, and provide … Read more

    Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning

  • Shixiang Chen
  • Shiqian Ma
  • Anthony Man-Cho So
  • Zengde Deng
    • Categories Nonlinear Optimization

    We consider the problem of maximizing the $\ell_1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well … Read more

    An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA

  • Shixiang Chen
  • Shiqian Ma
  • Lingzhou Xue
  • Hui Zou
    • Categories Constrained Nonlinear Optimization, Statistics

    Sparse principal component analysis (PCA) and sparse canonical correlation analysis (CCA) are two essential techniques from high-dimensional statistics and machine learning for analyzing large-scale data. Both problems can be formulated as an optimization problem with nonsmooth objective and nonconvex constraints. Since non-smoothness and nonconvexity bring numerical difficulties, most algorithms suggested in the literature either solve … Read more

    Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold

  • Shixiang Chen
  • Shiqian Ma
  • Anthony Man-Cho So
  • Tong Zhang
    • Categories Nonlinear Optimization

    We consider optimization problems over the Stiefel manifold whose objective function is the summation of a smooth function and a nonsmooth function. Existing methods for solving this kind of problems can be classified into three classes. Algorithms in the first class rely on information of the subgradients of the objective function and thus tend to … Read more

    Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity

  • Ji Liu
  • Shiqian Ma
  • Conghui Tan
  • Tong Zhang
    • Categories Convex and Nonsmooth Optimization

    Regularized empirical risk minimization problem with linear predictor appears frequently in machine learning. In this paper, we propose a new stochastic primal-dual method to solve this class of problems. Different from existing methods, our proposed methods only require O(1) operations in each iteration. We also develop a variance-reduction variant of the algorithm that converges linearly. … Read more