Timezone: »
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.
Author Information
Ziwei Ji (Google Research)
Kwangjun Ahn (MIT EECS)
Pranjal Awasthi (Google)
Satyen Kale (Google Research)
Stefani Karp (Google/CMU)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Oral: Agnostic Learnability of Halfspaces via Logistic Loss »
Wed. Jul 20th 06:00 -- 06:20 PM Room Room 327 - 329
More from the Same Authors
-
2022 Poster: Do More Negative Samples Necessarily Hurt In Contrastive Learning? »
Pranjal Awasthi · Nishanth Dikkala · Pritish Kamath -
2022 Oral: Do More Negative Samples Necessarily Hurt In Contrastive Learning? »
Pranjal Awasthi · Nishanth Dikkala · Pritish Kamath -
2022 Poster: Congested Bandits: Optimal Routing via Short-term Resets »
Pranjal Awasthi · Kush Bhatia · Sreenivas Gollapudi · Kostas Kollias -
2022 Spotlight: Congested Bandits: Optimal Routing via Short-term Resets »
Pranjal Awasthi · Kush Bhatia · Sreenivas Gollapudi · Kostas Kollias -
2022 Poster: Understanding the unstable convergence of gradient descent »
Kwangjun Ahn · Jingzhao Zhang · Suvrit Sra -
2022 Poster: H-Consistency Bounds for Surrogate Loss Minimizers »
Pranjal Awasthi · Anqi Mao · Mehryar Mohri · Yutao Zhong -
2022 Poster: Individual Preference Stability for Clustering »
Saba Ahmadi · Pranjal Awasthi · Samir Khuller · Matthäus Kleindessner · Jamie Morgenstern · Pattara Sukprasert · Ali Vakilian -
2022 Poster: Active Sampling for Min-Max Fairness »
Jacob Abernethy · Pranjal Awasthi · Matthäus Kleindessner · Jamie Morgenstern · Chris Russell · Jie Zhang -
2022 Spotlight: Understanding the unstable convergence of gradient descent »
Kwangjun Ahn · Jingzhao Zhang · Suvrit Sra -
2022 Oral: H-Consistency Bounds for Surrogate Loss Minimizers »
Pranjal Awasthi · Anqi Mao · Mehryar Mohri · Yutao Zhong -
2022 Oral: Individual Preference Stability for Clustering »
Saba Ahmadi · Pranjal Awasthi · Samir Khuller · Matthäus Kleindessner · Jamie Morgenstern · Pattara Sukprasert · Ali Vakilian -
2022 Spotlight: Active Sampling for Min-Max Fairness »
Jacob Abernethy · Pranjal Awasthi · Matthäus Kleindessner · Jamie Morgenstern · Chris Russell · Jie Zhang -
2020 Poster: SCAFFOLD: Stochastic Controlled Averaging for Federated Learning »
Sai Praneeth Reddy Karimireddy · Satyen Kale · Mehryar Mohri · Sashank Jakkam Reddi · Sebastian Stich · Ananda Theertha Suresh -
2019 Poster: Escaping Saddle Points with Adaptive Gradient Methods »
Matthew Staib · Sashank Jakkam Reddi · Satyen Kale · Sanjiv Kumar · Suvrit Sra -
2019 Oral: Escaping Saddle Points with Adaptive Gradient Methods »
Matthew Staib · Sashank Jakkam Reddi · Satyen Kale · Sanjiv Kumar · Suvrit Sra