Optimization Online


A Coordinate Gradient Descent Method for Linearly Constrained Smooth Optimization and Support Vector Machines Training

Paul Tseng(tseng***at***math.washington.edu)
Sangwoon Yun(sangwoon***at***math.washington.edu)

Abstract: Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. We establish global convergence and, under a local error bound assumption (which is satisfied by the SVM QP), linear rate of convergence for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We show that, for SVM QP with n variables, this rule can be implemented in O(n) operations using Rockafellar's notion of conformal realization. Thus, for SVM training, our method requires only O(n) operations per iteration and, in contrast to existing decomposition methods, achieves linear convergence without additional assumptions. We report our numerical experience with the method on some large SVM QP arising from two-class data classification. Our experience suggests that the method can be efficient for SVM training with nonlinear kernel.

Keywords: Support vector machine, quadratic program, continuous quadratic knapsack problem, linear constraints, conformal realization, coordinate gradient descent, global convergence, linear convergence rate, error bound

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Applications -- Science and Engineering (Data-Mining )

Citation: Report, Department of Mathematics University of Washington, Seattle, WA, March 18, 2007

Download: [PDF]

Entry Submitted: 05/20/2007
Entry Accepted: 05/20/2007
Entry Last Modified: 05/20/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society