Keywords: [ OPT: Convex ] [ MISC: Supervised Learning ] [ T: Optimization ] [ OPT: Learning for Optimization ] [ T: Learning Theory ]

[
Abstract
]
Oral presentation:
T: Online Learning and Bandits/Learning Theory

Wed 20 Jul 10:15 a.m. PDT — 11:45 a.m. PDT

Wed 20 Jul 3:30 p.m. PDT — 5:30 p.m. PDT

Wed 20 Jul 10:15 a.m. PDT — 11:45 a.m. PDT

Abstract:

We investigate approximation guarantees provided by logistic regression for the fundamental problem of agnostic learning of homogeneous halfspaces. Previously, for a certain broad class of “well-behaved” distributions on the examples, Diakonikolas et al. (2020) proved an tilde{Omega}(OPT) lower bound, while Frei et al. (2021) proved an tilde{O}(sqrt{OPT}) upper bound, where OPT denotes the best zero-one/misclassification risk of a homogeneous halfspace. In this paper, we close this gap by constructing a well-behaved distribution such that the global minimizer of the logistic risk over this distribution only achieves Omega(sqrt{OPT}) misclassification risk, matching the upper bound in (Frei et al., 2021). On the other hand, we also show that if we impose a radial-Lipschitzness condition in addition to well-behaved-ness on the distribution, logistic regression on a ball of bounded radius reaches tilde{O}(OPT) misclassification risk. Our techniques also show for any well-behaved distribution, regardless of radial Lipschitzness, we can overcome the Omega(sqrt{OPT}) lower bound for logistic loss simply at the cost of one additional convex optimization step involving the hinge loss and attain tilde{O}(OPT) misclassification risk. This two-step convex optimization algorithm is simpler than previous methods obtaining this guarantee, all of which require solving O(log(1/OPT)) minimization problems.

Chat is not available.