Carnegie Mellon University
file.pdf (432.24 kB)

Saddle Points and Accelerated Perceptron Algorithms

Download (432.24 kB)
journal contribution
posted on 2014-01-01, 00:00 authored by Adams Wei Yu, Fatma Kilinc-KarzanFatma Kilinc-Karzan, Jaime G. Carbonell

In this paper, we consider the problem of finding a linear (binary) classifier or providing a near-infeasibility certificate if there is none. We bring a new perspective to addressing these two problems simultaneously in a single efficient process, by investigating a related Bilinear Saddle Point Problem (BSPP). More specifically, we show that a BSPP-based approach provides either a linear classifier or an ϵ-infeasibility certificate. We show that the accelerated primal-dual algorithm, Mirror Prox, can be used for this purpose and achieves the best known convergence rate of O(√logn/ρ(A)) (O(√logn/ϵ)), which is almost independent of the problem size, n. Our framework also solves kernelized and conic versions of the problem, with the same rate of convergence. We support our theoretical findings with an empirical study on synthetic and real data, highlighting the efficiency and numerical stability of our algorithms, especially on large-scale instances.


Publisher Statement

Copyright 2014 by the author(s).



Usage metrics