Back to search

Clemson University

A Projection-Free Algorithm for Solving Support Vector Machine Models

Abstract

dc:description.abstract

In this thesis our goal is to solve the dual problem of the support vector machine (SVM) problem, which is an example of convex smooth optimization problem over a polytope. To this goal, we apply the conditional gradient (CG) method by providing explicit solution to the linear programming (LP) subproblem. We also describe the conditional gradient sliding (CGS) method that can be considered as an improvement of CG in terms of number of gradient evaluations. Even though CGS performs better than CG in terms of optimal complexity bounds, it is not a practical method because it requires the knowledge of the Lipschitz constant and also the number of iterations. As an improvement of CGS, we designed a new method, conditional gradient sliding with line search (CGS-ls) that resolves the issues in CGS method. CGS-ls requires O(1/\sqrt{1/ε}) gradient evaluations and O(1/ε) linear optimization calls that achieves the optimal complexity bounds in CGS method. We also compare the performance of our method with CG and CGS methods as numerical results by experimenting them in dual problem of SVM for binary classification of two subsets of the MNIST hand-written digits dataset.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nazari, Seyed Hamid
Contributors dc:contributor
  • Yuyuan Ouyang
  • Boshi Yang
  • Cristopher McMahan

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/3361

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Nazari, Seyed Hamid. A Projection-Free Algorithm for Solving Support Vector Machine Models. Thesis thesis, https://open.clemson.edu/all_theses/3361