Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

The model selection problem in the pure exploration linear bandit setting is introduced and studied in both the fixed confidence and fixed budget settings. The model selection problem considers a nested sequence of hypothesis classes of increasing complexities. Our goal is to automatically adapt to the instancedependent complexity measure of the smallest hypothesis class containing the true model, rather than suffering from the complexity measure related to the largest hypothesis class. We provide evidence showing that a standard doubling trick over dimension fails to achieve the optimal instancedependent sample complexity. Our algorithms define a new optimization problem based on experimental design that leverages the geometry of the action set to efficiently identify a nearoptimal hypothesis class. Our fixed budget algorithm uses a novel application of a selectionvalidation trick in bandits. This provides a new method for the understudied fixed budget setting in linear bandits (even without the added challenge of model selection). We further generalize the model selection problem to the misspecified regime, adapting our algorithms in both fixed confidence and fixed budget settings.more » « less

Active learning is a labelefficient approach to train highly effective models while interactively selecting only small subsets of unlabelled data for labelling and training. In "open world" settings, the classes of interest can make up a small fraction of the overall dataset  most of the data may be viewed as an outofdistribution or irrelevant class. This leads to extreme classimbalance, and our theory and methods focus on this core issue. We propose a new strategy for active learning called GALAXY (Graphbased Active Learning At the eXtrEme), which blends ideas from graphbased active learning and deep learning. GALAXY automatically and adaptively selects more classbalanced examples for labeling than most other methods for active learning. Our theory shows that GALAXY performs a refined form of uncertainty sampling that gathers a much more classbalanced dataset than vanilla uncertainty sampling. Experimentally, we demonstrate GALAXY's superiority over existing stateofart deep active learning algorithms in unbalanced vision classification settings generated from popular datasets.more » « less

Outofdistribution (OOD) detection is important for machine learning models deployed in the wild. Recent methods use auxiliary outlier data to regularize the model for improved OOD detection. However, these approaches make a strong distributional assumption that the auxiliary outlier data is completely separable from the indistribution (ID) data. In this paper, we propose a novel framework that leverages wild mixture data  that naturally consists of both ID and OOD samples. Such wild data is abundant and arises freely upon deploying a machine learning classifier in their \emph{natural habitats}. Our key idea is to formulate a constrained optimization problem and to show how to tractably solve it. Our learning objective maximizes the OOD detection rate, subject to constraints on the classification error of ID data and on the OOD error rate of ID examples. We extensively evaluate our approach on common OOD detection tasks and demonstrate superior performance.more » « less

Many active learning and search approaches are intractable for largescale industrial settings with billions of unlabeled examples. Existing approaches search globally for the optimal examples to label, scaling linearly or even quadratically with the unlabeled data. In this paper, we improve the computational efficiency of active learning and search methods by restricting the candidate pool for labeling to the nearest neighbors of the currently labeled set instead of scanning over all of the unlabeled data. We evaluate several selection strategies in this setting on three largescale computer vision datasets: ImageNet, OpenImages, and a deidentified and aggregated dataset of 10 billion publicly shared images provided by a large internet company. Our approach achieved similar mean average precision and recall as the traditional global approach while reducing the computational cost of selection by up to three orders of magnitude, enabling webscale active learning.more » « less

We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification. We begin our investigation with the observation that agnostic algorithms \emph{cannot} be minimaxoptimal in the realizable setting. Hence, we design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors and are generalpurpose, accommodating a wide variety of function classes including kernel methods, H{ö}lder smooth functions, and convex functions. The sample complexities of our algorithms can be quantified in terms of wellknown quantities like the extended teaching dimension and haystack dimension. However, unlike algorithms based directly on those combinatorial quantities, our algorithms are computationally efficient. To achieve computational efficiency, our algorithms sample from the version space using Monte Carlo "hitandrun" algorithms instead of maintaining the version space explicitly. Our approach has two key strengths. First, it is simple, consisting of two unifying, greedy algorithms. Second, our algorithms have the capability to seamlessly leverage prior knowledge that is often available and useful in practice. In addition to our new theoretical results, we demonstrate empirically that our algorithms are competitive with Gaussian process UCB methods.more » « less

We propose a new variant of the top arm identification problem, top feasible arm identification, where there are K arms associated with Ddimensional distributions and the goal is to find m arms that maximize some known linear function of their means subject to the constraint that their means belong to a given set P € R D. This problem has many applications since in many settings, feedback is multidimensional and it is of interest to perform constrained maximization. We present problemdependent lower bounds for top feasible arm identification and upper bounds for several algorithms. Our most broadly applicable algorithm, TFLUCBB, has an upper bound that is loose by a factor of OpDlogpKqq. Many problems of practical interest are two dimensional and, for these, it is loose by a factor of OplogpKqq. Finally, we conduct experiments on synthetic and realworld datasets that demonstrate the effectiveness of our algorithms. Our algorithms are superior both in theory and in practice to a naive twostage algorithm that first identifies the feasible arms and then applies a best arm identification algorithm to the feasible arms.more » « less