Optimization Online


A termination criterion for stochastic gradient descent for binary classification

Sina Baghal(srezazadehbaghal***at***uwaterloo.ca)
Courtney Paquette(yumiko88***at***uw.edu)
Stephen A. Vavasis(vavasis***at***uwaterloo.ca)

Abstract: We propose a new, simple, and computationally inexpensive termination test for constant step-size stochastic gradient descent (SGD) applied to binary classification on the logistic and hinge loss with homogeneous linear predictors. Our theoretical results support the effectiveness of our stopping criterion when the data is Gaussian distributed. This presence of noise allows for the possibility of non-separable data. We show that our test terminates in a finite number of iterations and when the noise in the data is not too large, the expected classifier at termination nearly minimizes the probability of misclassification. Finally, numerical experiments indicate for both real and synthetic data sets that our termination test exhibits a good degree of predictability on accuracy and running time.

Keywords: binary classification; stochastic gradient descent; termination criterion; mixture of Gaussians

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 04/02/2020
Entry Accepted: 04/02/2020
Entry Last Modified: 04/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society