GRAD-MATCH: A Gradient Matching Based Data Subset Selection for Efficient Learning

• URL: http://arxiv.org/abs/2103.00123v1
• Date: Sat, 27 Feb 2021 04:09:32 GMT
• Title: GRAD-MATCH: A Gradient Matching Based Data Subset Selection for Efficient Learning
• Authors: Krishnateja Killamsetty, Durga Sivasubramanian, Baharan Mirzasoleiman, Ganesh Ramakrishnan, Abir De, Rishabh Iyer
• Abstract summary: We propose a general framework, GRAD-MATCH, which finds subsets that closely match the gradient of the training or validation set. We show that GRAD-MATCH significantly and consistently outperforms several recent data-selection algorithms.
• Score: 23.75284126177203
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The great success of modern machine learning models on large datasets is contingent on extensive computational resources with high financial and environmental costs. One way to address this is by extracting subsets that generalize on par with the full data. In this work, we propose a general framework, GRAD-MATCH, which finds subsets that closely match the gradient of the training or validation set. We find such subsets effectively using an orthogonal matching pursuit algorithm. We show rigorous theoretical and convergence guarantees of the proposed algorithm and, through our extensive experiments on real-world datasets, show the effectiveness of our proposed framework. We show that GRAD-MATCH significantly and consistently outperforms several recent data-selection algorithms and is Pareto-optimal with respect to the accuracy-efficiency trade-off. The code of GRADMATCH is available as a part of the CORDS toolkit: https://github.com/decile-team/cords.

Related papers

• OOD-Chameleon: Is Algorithm Selection for OOD Generalization Learnable? [18.801143204410913]
  We formalize the task of algorithm selection for OOD generalization and investigate whether it could be approached by learning. We propose a solution, dubbed OOD-Chameleon that treats the task as a supervised classification over candidate algorithms. We train the model to predict the relative performance of algorithms given a dataset's characteristics.
  arXiv  Detail & Related papers  (2024-10-03T17:52:42Z)
• Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning [55.96599486604344]
  We introduce an approach aimed at enhancing the reasoning capabilities of Large Language Models (LLMs) through an iterative preference learning process. We use Monte Carlo Tree Search (MCTS) to iteratively collect preference data, utilizing its look-ahead ability to break down instance-level rewards into more granular step-level signals. The proposed algorithm employs Direct Preference Optimization (DPO) to update the LLM policy using this newly generated step-level preference data.
  arXiv  Detail & Related papers  (2024-05-01T11:10:24Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  Subset selection is a fundamental problem that can play a key role in identifying smaller portions of the training data. We develop a novel factor 3-approximation algorithm to compute subsets based on the weighted sum of both k-center and uncertainty sampling objective functions.
  arXiv  Detail & Related papers  (2023-12-17T04:41:07Z)
• Relation-aware Ensemble Learning for Knowledge Graph Embedding [68.94900786314666]
  We propose to learn an ensemble by leveraging existing methods in a relation-aware manner. exploring these semantics using relation-aware ensemble leads to a much larger search space than general ensemble methods. We propose a divide-search-combine algorithm RelEns-DSC that searches the relation-wise ensemble weights independently.
  arXiv  Detail & Related papers  (2023-10-13T07:40:12Z)
• Composable Core-sets for Diversity Approximation on Multi-Dataset Streams [4.765131728094872]
  Composable core-sets are core-sets with the property that subsets of the core set can be unioned together to obtain an approximation for the original data. We introduce a core-set construction algorithm for constructing composable core-sets to summarize streamed data for use in active learning environments.
  arXiv  Detail & Related papers  (2023-08-10T23:24:51Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
  Active learning frameworks aim to reduce the cost of data annotation by actively requesting the labeling for the most informative data points. Some proposed approaches include uncertainty-based techniques, geometric methods, implicit combination of uncertainty-based and geometric approaches. We present an innovative integration of recent progress in both uncertainty-based and geometric frameworks to enable an efficient exploration/exploitation trade-off in sample selection strategy. Our framework provides two advantages: (1) accurate posterior estimation, and (2) tune-able trade-off between computational overhead and higher accuracy.
  arXiv  Detail & Related papers  (2022-10-11T20:20:20Z)
• How Fine-Tuning Allows for Effective Meta-Learning [50.17896588738377]
  We present a theoretical framework for analyzing representations derived from a MAML-like algorithm. We provide risk bounds on the best predictor found by fine-tuning via gradient descent, demonstrating that the algorithm can provably leverage the shared structure. This separation result underscores the benefit of fine-tuning-based methods, such as MAML, over methods with "frozen representation" objectives in few-shot learning.
  arXiv  Detail & Related papers  (2021-05-05T17:56:00Z)
• GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning [11.220278271829699]
  We introduce Glister, a GeneraLIzation based data Subset selecTion for Efficient and Robust learning framework. We propose an iterative online algorithm Glister-Online, which performs data selection iteratively along with the parameter updates. We show that our framework improves upon state of the art both in efficiency and accuracy (in cases (a) and (c)) and is more efficient compared to other state-of-the-art robust learning algorithms.
  arXiv  Detail & Related papers  (2020-12-19T08:41:34Z)
• Deep Reinforcement Learning of Graph Matching [63.469961545293756]
  Graph matching (GM) under node and pairwise constraints has been a building block in areas from optimization to computer vision. We present a reinforcement learning solver for GM i.e. RGM that seeks the node correspondence between pairwise graphs. Our method differs from the previous deep graph matching model in the sense that they are focused on the front-end feature extraction and affinity function learning.
  arXiv  Detail & Related papers  (2020-12-16T13:48:48Z)
• Optimally Combining Classifiers for Semi-Supervised Learning [43.77365242185884]
  We propose a new semi-supervised learning method that is able to adaptively combine the strengths of Xgboost and transductive support vector machine. The experimental results on the UCI data sets and real commercial data set demonstrate the superior classification performance of our method over the five state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-06-07T09:28:34Z)

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.