Back to search

Clemson University

Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods

Abstract

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.

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
  • Squires, Trevor
Contributors dc:contributor
  • Yuyuan Ouyang
  • Fei Xue
  • Chris McMahan

Subjects

dc:subject × 3

Identifiers

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

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
citation

Squires, Trevor. Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods. Thesis thesis, https://open.clemson.edu/all_theses/3282