{"id":{"repo_id":"clemson","oai_identifier":"oai:open.clemson.edu:all_theses-4289"},"canonical_url":"https://search.ndltd.org/etd/clemson/oai:open.clemson.edu:all_theses-4289","repository":{"repo_id":"clemson","name":"Clemson University","base_url":"https://open.clemson.edu/do/oai/"},"display":{"title":"Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods","abstract":"In this thesis, we construct worst case binary logistic regression datasets for any deterministic first order methods. We show that our datasets require at least $\\cO(1/\\sqrt{\\varepsilon})$ first-order oracle inquires to obtain a $\\varepsilon-$approximate solution under the assumption that the problem dimension is sufficiently large. Using our result, on worst case datasets we conclude that existing algorithms such as Nesterov's Optimal Gradient Descent are optimal algorithms for solving binary logistic regression under large scale assumptions. Our analysis combines Nemirovski's Krylov subspace technique and Nesterov's construction of worst case convex quadratic programming problem instance. Our result is the first worst case dataset constructed against all first order methods for solving binary logistic regression, and a new worst case instance among smooth convex optimization problems.","abstract_html":"In this thesis, we construct worst case binary logistic regression datasets for any deterministic first order methods. We show that our datasets require at least $\\cO(1/\\sqrt{\\varepsilon})$ first-order oracle inquires to obtain a $\\varepsilon-$approximate solution under the assumption that the problem dimension is sufficiently large. Using our result, on worst case datasets we conclude that existing algorithms such as Nesterov&#x27;s Optimal Gradient Descent are optimal algorithms for solving binary logistic regression under large scale assumptions. Our analysis combines Nemirovski&#x27;s Krylov subspace technique and Nesterov&#x27;s construction of worst case convex quadratic programming problem instance. Our result is the first worst case dataset constructed against all first order methods for solving binary logistic regression, and a new worst case instance among smooth convex optimization problems.","abstract_has_math":true,"creators":["Squires, Trevor"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":["Yuyuan Ouyang","Fei Xue","Chris McMahan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:23:07Z","subjects":["binary logistic regression","lower complexity bound","operations research"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://open.clemson.edu/all_theses/3282","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://open.clemson.edu/all_theses/3282","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-4289","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yuyuan Ouyang","Fei Xue","Chris McMahan"]},{"key":"dc:creator","label":"Author","values":["Squires, Trevor"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2020-05-27T15:42:07Z"]},{"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":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["binary logistic regression","lower complexity bound","operations research"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://open.clemson.edu/all_theses/3282"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis, we construct worst case binary logistic regression datasets for any deterministic first order methods. We show that our datasets require at least $\\cO(1/\\sqrt{\\varepsilon})$ first-order oracle inquires to obtain a $\\varepsilon-$approximate solution under the assumption that the problem dimension is sufficiently large. Using our result, on worst case datasets we conclude that existing algorithms such as Nesterov's Optimal Gradient Descent are optimal algorithms for solving binary logistic regression under large scale assumptions. Our analysis combines Nemirovski's Krylov subspace technique and Nesterov's construction of worst case convex quadratic programming problem instance. Our result is the first worst case dataset constructed against all first order methods for solving binary logistic regression, and a new worst case instance among smooth convex optimization problems."]},{"key":"dc:title","label":"Title","values":["Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods"]}]}],"canonical_facts":{"dc:contributor":["Yuyuan Ouyang","Fei Xue","Chris McMahan"],"dc:creator":["Squires, Trevor"],"dc:date.available":["2020-05-27T15:42:07Z"],"dc:date.created":["2020-05-01T07:00:00Z"],"dc:description.abstract":["In this thesis, we construct worst case binary logistic regression datasets for any deterministic first order methods. We show that our datasets require at least $\\cO(1/\\sqrt{\\varepsilon})$ first-order oracle inquires to obtain a $\\varepsilon-$approximate solution under the assumption that the problem dimension is sufficiently large. Using our result, on worst case datasets we conclude that existing algorithms such as Nesterov's Optimal Gradient Descent are optimal algorithms for solving binary logistic regression under large scale assumptions. Our analysis combines Nemirovski's Krylov subspace technique and Nesterov's construction of worst case convex quadratic programming problem instance. Our result is the first worst case dataset constructed against all first order methods for solving binary logistic regression, and a new worst case instance among smooth convex optimization problems."],"dc:identifier":["https://open.clemson.edu/all_theses/3282"],"dc:subject":["binary logistic regression","lower complexity bound","operations research"],"dc:title":["Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods"],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T07:23:07Z"}