Sketch and shift: a robust decoder for compressive clustering

• URL: http://arxiv.org/abs/2312.09940v2
• Date: Mon, 17 Jun 2024 03:44:46 GMT
• Title: Sketch and shift: a robust decoder for compressive clustering
• Authors: Ayoub Belhadji, Rémi Gribonval,
• Abstract summary: 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.
• Score: 17.627195350266796
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Compressive learning is an emerging approach to drastically reduce the memory footprint of large-scale learning, by first summarizing a large dataset into a low-dimensional sketch vector, and then decoding from this sketch the latent information needed for learning. In light of recent progress on information preservation guarantees for sketches based on random features, a major objective is to design easy-to-tune algorithms (called decoders) to robustly and efficiently extract this information. To address the underlying non-convex optimization problems, various heuristics have been proposed. In the case of compressive clustering, the standard heuristic is CL-OMPR, a variant of sliding Frank-Wolfe. Yet, CL-OMPR is hard to tune, and the examination of its robustness was overlooked. In this work, we undertake a scrutinized examination of CL-OMPR to circumvent its limitations. In particular, we show how this algorithm can fail to recover the clusters even in advantageous scenarios. To gain insight, we show how the deficiencies of this algorithm can be attributed to optimization difficulties related to the structure of a correlation function appearing at core steps of the algorithm. To address these limitations, we propose an alternative decoder offering substantial improvements over CL-OMPR. Its design is notably inspired from the mean shift algorithm, a classic approach to detect the local maxima of kernel density estimators. The proposed algorithm can extract clustering information from a sketch of the MNIST dataset that is 10 times smaller than previously.

Related papers

• Anchor Attention, Small Cache: Code Generation with Large Language Models [15.94784908771546]
  Current practices in NLP often use sparse attention which may, unfortunately, lead to substantial inaccuracies, or hallucinations, in code generation tasks. We propose a novel approach, AnchorCoder, which features token-wise anchor attention designed to extract and compress contextual information. It can consistently achieve a significant (at least 70%) reduction in KV cache requirements, while preserving the majority of model's performance.
  arXiv  Detail & Related papers  (2024-11-11T02:47:05Z)
• Robust Clustering on High-Dimensional Data with Stochastic Quantization [0.0]
  This paper addresses the limitations of conventional vector quantization algorithms. It investigates the Quantization (SQ) as an alternative for high-dimensionality computation.
  arXiv  Detail & Related papers  (2024-09-03T17:13:55Z)
• Sparse Attention-Based Neural Networks for Code Classification [15.296053323327312]
  We introduce an approach named the Sparse Attention-based neural network for Code Classification (SACC) In the first step, source code undergoes syntax parsing and preprocessing. The encoded sequences of subtrees are fed into a Transformer model that incorporates sparse attention mechanisms for the purpose of classification.
  arXiv  Detail & Related papers  (2023-11-11T14:07:12Z)
• SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning [20.706469085872516]
  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.
  arXiv  Detail & Related papers  (2023-09-21T16:57:09Z)
• Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
  We propose two strategies to learn from large-scale unlabeled data. The first strategy performs a local neighborhood sampling to reduce the dataset size in each without violating neighborhood relationships. A second strategy leverages a novel Re-Ranking technique, which has a lower time upper bound complexity and reduces the memory complexity from O(n2) to O(kn) with k n.
  arXiv  Detail & Related papers  (2023-07-26T16:19:19Z)
• 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)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  We present a new branch-and-bound algorithm for semi-supervised MSSC. Background knowledge is incorporated as pairwise must-link and cannot-link constraints. For the first time, the proposed global optimization algorithm efficiently manages to solve real-world instances up to 800 data points.
  arXiv  Detail & Related papers  (2021-11-30T17:08:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Learnable Subspace Clustering [76.2352740039615]
  We develop a learnable subspace clustering paradigm to efficiently solve the large-scale subspace clustering problem. The key idea is to learn a parametric function to partition the high-dimensional subspaces into their underlying low-dimensional subspaces. To the best of our knowledge, this paper is the first work to efficiently cluster millions of data points among the subspace clustering methods.
  arXiv  Detail & Related papers  (2020-04-09T12:53:28Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)

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.