{"id":{"repo_id":"clemson","oai_identifier":"oai:open.clemson.edu:all_theses-4368"},"canonical_url":"https://search.ndltd.org/etd/clemson/oai:open.clemson.edu:all_theses-4368","repository":{"repo_id":"clemson","name":"Clemson University","base_url":"https://open.clemson.edu/do/oai/"},"display":{"title":"A Projection-Free Algorithm for Solving Support Vector Machine Models","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/\\epsilon})$ gradient evaluations and $O(1/\\epsilon)$ 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.","abstract_html":"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 <span class=\"etd-inline-math\">O(1/\\sqrt{1/&epsilon;})</span> gradient evaluations and <span class=\"etd-inline-math\">O(1/&epsilon;)</span> 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.","abstract_has_math":true,"creators":["Nazari, Seyed Hamid"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":["Yuyuan Ouyang","Boshi Yang","Cristopher McMahan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:23:14Z","subjects":[],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://open.clemson.edu/all_theses/3361","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://open.clemson.edu/all_theses/3361","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.clemson.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Aopen.clemson.edu%3Aall_theses-4368","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yuyuan Ouyang","Boshi Yang","Cristopher McMahan"]},{"key":"dc:creator","label":"Author","values":["Nazari, Seyed Hamid"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2020-05-27T15:42:10Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2020-05-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematical Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://open.clemson.edu/all_theses/3361"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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/\\epsilon})$ gradient evaluations and $O(1/\\epsilon)$ 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."]},{"key":"dc:title","label":"Title","values":["A Projection-Free Algorithm for Solving Support Vector Machine Models"]}]}],"canonical_facts":{"dc:contributor":["Yuyuan Ouyang","Boshi Yang","Cristopher McMahan"],"dc:creator":["Nazari, Seyed Hamid"],"dc:date.available":["2020-05-27T15:42:10Z"],"dc:date.created":["2020-05-01T07:00:00Z"],"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/\\epsilon})$ gradient evaluations and $O(1/\\epsilon)$ 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."],"dc:identifier":["https://open.clemson.edu/all_theses/3361"],"dc:title":["A Projection-Free Algorithm for Solving Support Vector Machine Models"],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T07:23:14Z"}