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

2019/08/12 by Yuyuan Ouyang, Ouyang, Yuyuan, Trevor Squires +1
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1908.04091

arxiv created 2019/08/12 · openalex publication_date 2019/08/12 · arxiv updated 2019/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present in this paper some worst-case datasets of deterministic first-order methods for solving large-scale binary logistic regression problems. Under the assumption that the number of algorithm iterations is much smaller than the problem dimension, with our worst-case datasets it requires at least O(1/√(ε)) first-order oracle inquiries to compute an ε-approximate solution. From traditional iteration complexity analysis point of view, the binary logistic regression loss functions with our worst-case datasets are new worst-case function instances among the class of smooth convex optimization problems.

Citations

• Lower bounds for finding stationary points I
• Lower Bounds for Parallel and Randomized Convex Optimization

Related

• Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods
• Logistic Regression: Tight Bounds for Stochastic and Online Optimization
• Gradient Descent Converges Linearly for Logistic Regression on Separable Data
• Binary Kernel Logistic Regression: a sparsity-inducing formulation and a convergent decomposition training algorithm
• Efficient and robust high-dimensional sparse logistic regression via nonlinear primal-dual hybrid gradient algorithms