Online Importance Weight Aware Updates

Abstract

An importance weight quantifies the relative importance of one example over another, coming up in applications of boosting, asymmetric classification costs, reductions, and active learning. The standard approach for dealing with importance weights in gradient descent is via multiplication of the gradient. We first demonstrate the problems of this approach when importance weights are large, and argue in favor of more sophisticated ways for dealing with them. We then develop an approach which enjoys an invariance property: that updating twice with importance weight $h$ is equivalent to updating once with importance weight $2h$. For many important losses this has a closed form update which satisfies standard regret guarantees when all examples have $h=1$. We also briefly discuss two other reasonable approaches for handling large importance weights. Empirically, these approaches yield substantially superior prediction with similar computational performance while reducing the sensitivity of the algorithm to the exact setting of the learning rate. We apply these to online active learning yielding an extraordinarily fast active learning algorithm that works even in the presence of adversarial noise.

References in corpus (1)

• Agnostic Active Learning Without Constraints

Cited by in corpus (19)

• A Reliable Effective Terascale Linear Learning System
• Protection Against Reconstruction and Its Applications in Private Federated Learning
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• A Contextual Bandit Bake-off
• Deep Ensemble Analysis for Imaging X-ray Polarimetry
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Efficient and Parsimonious Agnostic Active Learning
• Learning to Search for Dependencies
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• A Credit Assignment Compiler for Joint Prediction
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Temporal Variability in Implicit Online Learning
• Efficient Online Bootstrapping for Large Scale Learning
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• Scalable Nonlinear Learning with Adaptive Polynomial Expansions
• Para-active learning
• Learning Reductions that Really Work
• The Stochastic Gradient Descent for the Primal L1-SVM Optimization Revisited
• Statistically adaptive learning for a general class of cost functions (SA L-BFGS)