Online Importance Weight Aware Updates

By Nikos Karampatziakis, J. Langford. 2010

81 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “An alternative is to use stochastic proximal-point-type updates [10, 46, 44, 15, 24], which update Transmission of privatized updates After completing the local update to θ i , we deﬁne the local diﬀerence ∆ i = θ i − θ and transmit this to the aggregator using a separated mechanism (Deﬁnition 2.2).”
Conscientious Classification: A Data Scientist's Guide to Discrimination-Aware Classification (2017, neutral): “22 More generally, data scientists should always be sensitive to misclassiﬁcation costs, since the act of discrimination is usually enforced when a protected class receives an unwarranted negative action.”
A reliable effective terascale linear learning system (2011, methodology): “We start with each node making one online pass over its local data according to adaptive gradient updates (Duchi et al., 2010b; McMahan and Streeter, 2010) modiﬁed for loss non-linearity (Karampatziakis and Langford, 2011).”
Crowdsourced Data Management: Industry and Academic Perspectives (2015, background): “Papers focusing on the theory of active learning [56, 64, 111, 31, 92, 38, 37, 28, 63, 198, 136] show that the adaptive selection strategies proposed (i.”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, unknown): “S k) + hg k;x x ki and choosing x k+1 to minimize the regularized model f x k (x;S k)+ 1 2 2 k kx x kk2. More sophisticated models are plausible. Most familiar is the stochastic proximal point method [50,30,7, 28,8] (the least-mean-squares algorithm [63] for quadratic f), which makes no approximatio”
A Contextual Bandit Bake-off (2018, unknown): “A similar quantity has been used, e.g. , by Huang et al. (2015); Karampatziakis and Langford (2011); Krishnamurthy et al. (2019).”
Practical Evaluation and Optimization of Contextual Bandit Algorithms (2018, methodology): “…itself reduces to multiple online regression problems in VW, and online regression updates are performed using adaptive (Duchi et al., 2011), normalized (Ross et al., 2013) and importance-weight-aware (Karampatziakis and Langford, 2011) gradient updates, with a single tunable step-size parameter.”
Efficient and Parsimonious Agnostic Active Learning (2015, methodology): “See Appendix F of [Karampatziakis and Langford, 2011] for details. multiplier for the constraint (5) for classifier h.”
Distributed coordinate descent for generalized linear models with regularization (2016, background): “Also this problem can be effectively solved by various online learning algorithms [2, 12].”