SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning

• URL: http://arxiv.org/abs/2309.12253v2
• Date: Mon, 20 Nov 2023 12:38:42 GMT
• Title: SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning
• Authors: Julian Minder, Florian Gr\"otschla, Jo\"el Mathys, Roger Wattenhofer
• Abstract summary: We introduce an extension to the CLRS algorithmic learning benchmark, prioritizing scalability and the utilization of sparse representations. Our approach includes adapted algorithms from the original CLRS benchmark and introduces new problems from distributed and randomized algorithms.
• Score: 20.706469085872516
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We introduce an extension to the CLRS algorithmic learning benchmark, prioritizing scalability and the utilization of sparse representations. Many algorithms in CLRS require global memory or information exchange, mirrored in its execution model, which constructs fully connected (not sparse) graphs based on the underlying problem. Despite CLRS's aim of assessing how effectively learned algorithms can generalize to larger instances, the existing execution model becomes a significant constraint due to its demanding memory requirements and runtime (hard to scale). However, many important algorithms do not demand a fully connected graph; these algorithms, primarily distributed in nature, align closely with the message-passing paradigm employed by Graph Neural Networks. Hence, we propose SALSA-CLRS, an extension of the current CLRS benchmark specifically with scalability and sparseness in mind. Our approach includes adapted algorithms from the original CLRS benchmark and introduces new problems from distributed and randomized algorithms. Moreover, we perform a thorough empirical evaluation of our benchmark. Code is publicly available at https://github.com/jkminder/SALSA-CLRS.

Related papers

• A General Online Algorithm for Optimizing Complex Performance Metrics [5.726378955570775]
  We introduce and analyze a general online algorithm that can be used in a straightforward way with a variety of complex performance metrics in binary, multi-class, and multi-label classification problems. The algorithm's update and prediction rules are appealingly simple and computationally efficient without the need to store any past data.
  arXiv  Detail & Related papers  (2024-06-20T21:24:47Z)
• The CLRS-Text Algorithmic Reasoning Language Benchmark [48.45201665463275]
  CLRS-Text is a textual version of the CLRS benchmark. CLRS-Text is capable of procedurally generating trace data for thirty diverse, challenging algorithmic tasks. We fine-tune and evaluate various LMs as generalist executors on this benchmark.
  arXiv  Detail & Related papers  (2024-06-06T16:29:25Z)
• LoRA-Ensemble: Efficient Uncertainty Modelling for Self-attention Networks [52.46420522934253]
  We introduce LoRA-Ensemble, a parameter-efficient deep ensemble method for self-attention networks. By employing a single pre-trained self-attention network with weights shared across all members, we train member-specific low-rank matrices for the attention projections. Our method exhibits superior calibration compared to explicit ensembles and achieves similar or better accuracy across various prediction tasks and datasets.
  arXiv  Detail & Related papers  (2024-05-23T11:10:32Z)
• Sketch and shift: a robust decoder for compressive clustering [17.627195350266796]
  Compressive learning is an emerging approach to drastically reduce the memory footprint of large-scale learning. We propose an alternative decoder offering substantial improvements over CL-OMPR. The proposed algorithm can extract clustering information from a sketch of the MNIST dataset that is 10 times smaller than previously.
  arXiv  Detail & Related papers  (2023-12-15T16:53:55Z)
• Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling [6.599344783327054]
  Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximation algorithms for an NP-hard parameterized clustering framework called LambdaCC.
  arXiv  Detail & Related papers  (2023-06-08T02:29:37Z)
• Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! [100.19080749267316]
  "Sparsity May Cry" Benchmark (SMC-Bench) is a collection of carefully-curated 4 diverse tasks with 10 datasets. SMC-Bench is designed to favor and encourage the development of more scalable and generalizable sparse algorithms.
  arXiv  Detail & Related papers  (2023-03-03T18:47:21Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  This paper is concerned with the computational complexity of learning the Hidden Markov Model (HMM) In this paper, we consider an interactive access model, in which the algorithm can query for samples from the conditional distributions of the HMMs. Specifically, we obtain efficient algorithms for learning HMMs in settings where we have query access to the exact conditional probabilities.
  arXiv  Detail & Related papers  (2023-02-28T16:53:41Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm [3.7491936479803054]
  We propose a new hierarchical clustering linkage criterion called Genie. Our algorithm links two clusters in such a way that a chosen economic inequity measure does not drastically increase above a given threshold. A reference implementation of the algorithm has been included in the open source 'genie' package for R.
  arXiv  Detail & Related papers  (2022-09-13T06:42:53Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• Optimal Continual Learning has Perfect Memory and is NP-hard [19.629732320437856]
  Continual Learning (CL) algorithms incrementally learn a predictor or representation across multiple sequentially observed tasks. The current paper develops a theoretical approach that explains why. We derive the computational properties which CL algorithms would have to possess in order to avoid catastrophic forgetting.
  arXiv  Detail & Related papers  (2020-06-09T11:20:38Z)

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.