Date of Award
May 2020
Document Type
Thesis
Degree Name
Master of Science (MS)
Department
Mathematical Sciences
Committee Member
Yuyuan Ouyang
Committee Member
Fei Xue
Committee Member
Chris McMahan
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.
Recommended Citation
Squires, Trevor, "Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods" (2020). All Theses. 3282.
https://tigerprints.clemson.edu/all_theses/3282