CaltechAUTHORS
  A Caltech Library Service

The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data

Salehi, Fariborz and Abbasi, Ehsan and Hassibi, Babak (2020) The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20201109-155538204

[img] PDF - Submitted Version
See Usage Policy.

527Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20201109-155538204

Abstract

Logistic models are commonly used for binary classification tasks. The success of such models has often been attributed to their connection to maximum-likelihood estimators. It has been shown that gradient descent algorithm, when applied on the logistic loss, converges to the max-margin classifier (a.k.a. hard-margin SVM). The performance of the max-margin classifier has been recently analyzed. Inspired by these results, in this paper, we present and study a more general setting, where the underlying parameters of the logistic model possess certain structures (sparse, block-sparse, low-rank, etc.) and introduce a more general framework (which is referred to as "Generalized Margin Maximizer", GMM). While classical max-margin classifiers minimize the 2-norm of the parameter vector subject to linearly separating the data, GMM minimizes any arbitrary convex function of the parameter vector. We provide a precise analysis of the performance of GMM via the solution of a system of nonlinear equations. We also provide a detailed study for three special cases: (1) ℓ₂-GMM that is the max-margin classifier, (2) ℓ₁-GMM which encourages sparsity, and (3) ℓ_∞-GMM which is often used when the parameter vector has binary entries. Our theoretical results are validated by extensive simulation results across a range of parameter values, problem instances, and model structures.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2010.15379arXivDiscussion Paper
Additional Information:Copyright 2020 by the author(s).
Record Number:CaltechAUTHORS:20201109-155538204
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20201109-155538204
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106573
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:10 Nov 2020 15:29
Last Modified:10 Nov 2020 15:29

Repository Staff Only: item control page