The support vector machine (SVM) has been used in a wide variety of classification problems. The original SVM uses the hinge loss function, which is non-differentiable and makes the problem difficult to solve in particular for regularized SVMs, such as with 1 -regularization. This paper considers the Huberized SVM (HSVM), which uses a differentiable approximation of the hinge loss function. We first explore the use of the proximal gradient (PG) method to solving binary-class HSVM (B-HSVM) and then generalize it to multi-class HSVM (M-HSVM). Under strong convexity assumptions, we show that our algorithm converges linearly. In addition, we give a finite convergence result about the support of the solution, based on which we further accelerate the algorithm by a two-stage method. We present extensive numerical experiments on both synthetic and real datasets which demonstrate the superiority of our

Stochastic gradient (SG) method has been popularly applied to solve optimization problems with objective that is stochastic or an average of many functions. Most existing works on SG assume that the underlying problem is unconstrained or has an easy-to-project constraint set. In this paper, we consider problems that have a stochastic objective and also many functional constraints. For such problems, it could be extremely expensive to project a point to the feasible set, or even compute subgradient and/or function value of all constraint functions. To find solutions of these problems, we propose a novel SG method based on the augmented Lagrangian function. Within every iteration, it inquires a stochastic subgradient of the objective, a subgradient and function value of one randomly sampled constraint function, and function value of another sampled constraint function. Hence, the per-iteration complexity is low. We establish its convergence rate for convex and also strongly convex problems. It can achieve the optimal O (1/\sqrt {k}) convergence rate for convex case and nearly optimal O (1/\sqrt {k}) rate for strongly convex case. Numerical experiments on quadratically constrained quadratic programming are conducted to demonstrate its efficiency.

Recent several years have witnessed the surge of asynchronous (async-) parallel computing methods due to the extremely big data involved in many modern applications and also the advancement of multi-core machines and computer clusters. In optimization, most works about async-parallel methods are on unconstrained problems or those with block separable constraints. In this paper, we propose an async-parallel method based on block coordinate update (BCU) for solving convex problems with <i>nonseparable</i> linear constraint. Running on a single node, the method becomes a novel randomized primaldual BCU for multi-block affinely constrained problems. For these problems, GaussSeidel cyclic primaldual BCU is not guaranteed to converge to an optimal solution if no additional assumptions, such as strong convexity, are made. On the contrary, assuming convexity and existence of a primaldual