Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions
Authors: Adam Block, Max Simchowitz
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we give a computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/σ) regret for realizable K-wise linear classification. We extend our results to settings where the true classifier is linear in an over-parameterized polynomial featurization of the contexts, as well as to a realizable piecewise-regression setting assuming access to an appropriate ERM oracle. Somewhat surprisingly, standard disagreement-based analyses are insufficient to achieve regret logarithmic in 1/σ. Instead, we develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers. Along the way, we develop numerous technical tools of independent interest, including a general anti-concentration bound for the determinant of certain matrix averages. If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] |
| Researcher Affiliation | Academia | Adam Block Department of Mathematics MIT Cambridge, MA 02139 ablock@mit.edu Max Simchowitz MIT Cambridge, MA 02139 msimchow@csail.mit.edu |
| Pseudocode | Yes | Algorithm 1 Binary Classification with Linear Thresholds |
| Open Source Code | No | Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] |
| Open Datasets | No | The paper is theoretical and does not describe experiments that use datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that use datasets, thus no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments, thus no software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper is theoretical and does not describe experiments, thus no experimental setup details like hyperparameters or training configurations are provided. |