6 papers
Learning Nearest-Neighbor Maps from Adaptive Queries
Hadley Black, Geelon So
We study the problem of learning nearest-neighbor maps from adaptive queries, which is equivalent to the following problem of reconstructing a hidden set via a nearest-neighbor…
Learnable Mixed Nash Equilibria are Collectively Rational
Geelon So, Yi-An Ma
We extend the study of learning in games to dynamics that exhibit non-asymptotic stability. We do so through the notion of uniform stability, which is concerned with equilibria of…
Actively Learning Halfspaces without Synthetic Data
Hadley Black, Kasper Green Larsen, Arya Mazumdar +2
In the classic point location problem, one is given an arbitrary dataset of points with query access to an unknown halfspace $f : \mathbb{R}^d \to \{0,…
Hedging on the Frontier: Learning New Tasks with Few Samples
Tobias Wegel, Federico Di Gennaro, Geelon So +1
When a learner faces a new task with few samples, it must leverage any available side information. In practice, this often comes in the form of model evaluations on related tasks i…
On the sample complexity of semi-supervised multi-objective learning
Tobias Wegel, Geelon So, Junhyung Park +1
In multi-objective learning (MOL), several possibly competing prediction tasks must be solved jointly by a single model. Achieving good trade-offs may require a model class $\mathc…
Online Consistency of the Nearest Neighbor Rule
Sanjoy Dasgupta, Geelon So
In the realizable online setting, a learner is tasked with making predictions for a stream of instances, where the correct answer is revealed after each prediction. A learning rule…