On the Convergence of Loss and Uncertainty-based Active Learning Algorithms

• URL: http://arxiv.org/abs/2312.13927v4
• Date: Fri, 22 Nov 2024 21:59:25 GMT
• Title: On the Convergence of Loss and Uncertainty-based Active Learning Algorithms
• Authors: Daniel Haimovich, Dima Karamshuk, Fridolin Linder, Niek Tax, Milan Vojnovic,
• Abstract summary: We investigate the convergence rates and data sample sizes required for training a machine learning model using a gradient descent (SGD) algorithm. We present convergence results for linear classifiers and linearly separable datasets using squared hinge loss and similar training loss functions.
• Score: 3.506897386829711
• License:
• Abstract: We investigate the convergence rates and data sample sizes required for training a machine learning model using a stochastic gradient descent (SGD) algorithm, where data points are sampled based on either their loss value or uncertainty value. These training methods are particularly relevant for active learning and data subset selection problems. For SGD with a constant step size update, we present convergence results for linear classifiers and linearly separable datasets using squared hinge loss and similar training loss functions. Additionally, we extend our analysis to more general classifiers and datasets, considering a wide range of loss-based sampling strategies and smooth convex training loss functions. We propose a novel algorithm called Adaptive-Weight Sampling (AWS) that utilizes SGD with an adaptive step size that achieves stochastic Polyak's step size in expectation. We establish convergence rate results for AWS for smooth convex training loss functions. Our numerical experiments demonstrate the efficiency of AWS on various datasets by using either exact or estimated loss values.

Related papers

• Dynamic Loss-Based Sample Reweighting for Improved Large Language Model Pretraining [55.262510814326035]
  Existing reweighting strategies primarily focus on group-level data importance. We introduce novel algorithms for dynamic, instance-level data reweighting. Our framework allows us to devise reweighting strategies deprioritizing redundant or uninformative data.
  arXiv  Detail & Related papers  (2025-02-10T17:57:15Z)
• Capturing the Temporal Dependence of Training Data Influence [100.91355498124527]
  We formalize the concept of trajectory-specific leave-one-out influence, which quantifies the impact of removing a data point during training. We propose data value embedding, a novel technique enabling efficient approximation of trajectory-specific LOO. As data value embedding captures training data ordering, it offers valuable insights into model training dynamics.
  arXiv  Detail & Related papers  (2024-12-12T18:28:55Z)
• SUDS: A Strategy for Unsupervised Drift Sampling [0.5437605013181142]
  Supervised machine learning encounters concept drift, where the data distribution changes over time, degrading performance. We present the Strategy for Drift Sampling (SUDS), a novel method that selects homogeneous samples for retraining using existing drift detection algorithms. Our results demonstrate the efficacy of SUDS in optimizing labeled data use in dynamic environments.
  arXiv  Detail & Related papers  (2024-11-05T10:55:29Z)
• Online Importance Sampling for Stochastic Gradient Optimization [33.42221341526944]
  We propose a practical algorithm that efficiently computes data importance on-the-fly during training. We also introduce a novel metric based on the derivative of the loss w.r.t. the network output, designed for mini-batch importance sampling.
  arXiv  Detail & Related papers  (2023-11-24T13:21:35Z)
• Adaptive Sampling for Deep Learning via Efficient Nonparametric Proxies [35.29595714883275]
  We develop an efficient sketch-based approximation to the Nadaraya-Watson estimator. Our sampling algorithm outperforms the baseline in terms of wall-clock time and accuracy on four datasets.
  arXiv  Detail & Related papers  (2023-11-22T18:40:18Z)
• TRIAGE: Characterizing and auditing training data for improved regression [80.11415390605215]
  We introduce TRIAGE, a novel data characterization framework tailored to regression tasks and compatible with a broad class of regressors. TRIAGE utilizes conformal predictive distributions to provide a model-agnostic scoring method, the TRIAGE score. We show that TRIAGE's characterization is consistent and highlight its utility to improve performance via data sculpting/filtering, in multiple regression settings.
  arXiv  Detail & Related papers  (2023-10-29T10:31:59Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Variation-Incentive Loss Re-weighting for Regression Analysis on Biased Data [8.115323786541078]
  We aim to improve the accuracy of the regression analysis by addressing the data skewness/bias during model training. We propose a Variation-Incentive Loss re-weighting method (VILoss) to optimize the gradient descent-based model training for regression analysis.
  arXiv  Detail & Related papers  (2021-09-14T10:22:21Z)
• Learning Curves for SGD on Structured Features [23.40229188549055]
  We show that the geometry of the data in the induced feature space is crucial to accurately predict the test error throughout learning. We show that modeling the geometry of the data in the induced feature space is indeed crucial to accurately predict the test error throughout learning.
  arXiv  Detail & Related papers  (2021-06-04T20:48:20Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  We present a provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. ABSGD is flexible enough to combine with other robust losses without any additional cost.
  arXiv  Detail & Related papers  (2020-12-13T03:41:52Z)
• Evaluating representations by the complexity of learning low-loss predictors [55.94170724668857]
  We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning a predictor on top of the representation that achieves low loss on a task of interest.
  arXiv  Detail & Related papers  (2020-09-15T22:06:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.