## All Theses

May 2020

Thesis

#### Degree Name

Master of Science (MS)

#### Department

Mathematical Sciences

Yuyuan Ouyang

Fei Xue

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.

COinS