Shiqian Ma

Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation

  • Bo Jiang
  • Shiqian Ma
  • Anthony Man-Cho So
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , ,

    In this paper, we propose a vector transport-free stochastic variance reduced gradient (SVRG) method with general retraction for empirical risk minimization over Riemannian manifold. Existing SVRG methods on manifold usually consider a specific retraction operation, and involve additional computational costs such as parallel transport or vector transport. The vector transport-free SVRG with general retraction we … Read more

    Geometric descent method for convex composite minimization

  • Shixiang Chen
  • Wei Liu
  • Shiqian Ma
    • Categories Convex and Nonsmooth Optimization

    In this paper, we extend the geometric descent method recently proposed by Bubeck, Lee and Singh to tackle nonsmooth and strongly convex composite problems. We prove that our proposed algorithm, dubbed geometric proximal gradient method (GeoPG), converges with a linear rate $(1-1/\sqrt{\kappa})$ and thus achieves the optimal rate among first-order methods, where $\kappa$ is the … Read more

    Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

  • Donald Goldfarb
  • Wei Liu
  • Shiqian Ma
  • Xiao Wang
    • Categories Nonlinear Optimization Tags , , , , ,

    In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle ($\SFO$). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case … Read more

    Barzilai-Borwein Step Size for Stochastic Gradient Descent

  • Yu-Hong Dai
  • Shiqian Ma
  • Yuqiu Qian
  • Conghui Tan
    • Categories Convex Optimization, Stochastic Approaches Tags , ,

    One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step … Read more

    Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

  • Bo Jiang
  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Nonlinear Optimization Tags , , , , ,

    Nonconvex optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its … Read more

    Inertial Proximal ADMM for Linearly Constrained Separable Convex Optimization

  • Raymond Chan
  • Caihua Chen
  • Shiqian Ma
  • Junfeng Yang
    • Categories Convex Optimization Tags , , , ,

    The \emph{alternating direction method of multipliers} (ADMM) is a popular and efficient first-order method that has recently found numerous applications, and the proximal ADMM is an important variant of it. The main contributions of this paper are the proposition and the analysis of a class of inertial proximal ADMMs, which unify the basic ideas of … Read more

    A general inertial proximal point algorithm for mixed variational inequality problem

  • Caihua Chen
  • Shiqian Ma
  • Junfeng Yang
    • Categories Convex Optimization Tags , , ,

    In this paper, we first propose a general inertial \emph{proximal point algorithm} (PPA) for the mixed \emph{variational inequality} (VI) problem. Based on our knowledge, without stronger assumptions, convergence rate result is not known in the literature for inertial type PPAs. Under certain conditions, we are able to establish the global convergence and nonasymptotic $O(1/k)$ convergence … Read more

    On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming

  • Xin Liu
  • Ya-Feng Liu
  • Shiqian Ma
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags ,

    In this paper, we consider the linearly constrained composite convex optimization problem, whose objective is a sum of a smooth function and a possibly nonsmooth function. We propose an inexact augmented Lagrangian (IAL) framework for solving the problem. The stopping criterion used in solving the augmented Lagrangian (AL) subproblem in the proposed IAL framework is … Read more

    Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems

  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-block ADMM globally converges for any penalty parameter $\gamma>0$. In this … Read more

    Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity

  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization Tags , ,

    The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in [7] indicating that the multi-block ADMM for minimizing the sum of $N$ $(N\geq 3)$ convex functions with $N$ block variables linked by linear … Read more