Learning, compression, and leakage: Minimising classification error via meta-universal compression principles

• URL: http://arxiv.org/abs/2010.07382v2
• Date: Sun, 31 Jan 2021 20:18:19 GMT
• Title: Learning, compression, and leakage: Minimising classification error via meta-universal compression principles
• Authors: Fernando E. Rosas, Pedro A.M. Mediano, Michael Gastpar
• Abstract summary: A promising group of compression techniques for learning scenarios is normalised maximum likelihood (NML) coding. Here we consider a NML-based decision strategy for supervised classification problems, and show that it attains PAC learning when applied to a wide variety of models. We show that the misclassification rate of our method is upper bounded by the maximal leakage, a recently proposed metric to quantify the potential of data leakage in privacy-sensitive scenarios.
• Score: 87.054014983402
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning and compression are driven by the common aim of identifying and exploiting statistical regularities in data, which opens the door for fertile collaboration between these areas. A promising group of compression techniques for learning scenarios is normalised maximum likelihood (NML) coding, which provides strong guarantees for compression of small datasets - in contrast with more popular estimators whose guarantees hold only in the asymptotic limit. Here we consider a NML-based decision strategy for supervised classification problems, and show that it attains heuristic PAC learning when applied to a wide variety of models. Furthermore, we show that the misclassification rate of our method is upper bounded by the maximal leakage, a recently proposed metric to quantify the potential of data leakage in privacy-sensitive scenarios.

Related papers

• Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filtering [17.446431849022346]
  Distributed learning has become the standard approach for training large-scale machine learning models across private data silos. It faces critical challenges related to robustness and communication preservation. We propose a novel Byzantine-robust and communication-efficient distributed learning method.
  arXiv  Detail & Related papers  (2024-09-13T08:53:10Z)
• Anti-Collapse Loss for Deep Metric Learning Based on Coding Rate Metric [99.19559537966538]
  DML aims to learn a discriminative high-dimensional embedding space for downstream tasks like classification, clustering, and retrieval. To maintain the structure of embedding space and avoid feature collapse, we propose a novel loss function called Anti-Collapse Loss. Comprehensive experiments on benchmark datasets demonstrate that our proposed method outperforms existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-07-03T13:44:20Z)
• Differential error feedback for communication-efficient decentralized learning [48.924131251745266]
  We propose a new decentralized communication-efficient learning approach that blends differential quantization with error feedback. We show that the resulting communication-efficient strategy is stable both in terms of mean-square error and average bit rate. The results establish that, in the small step-size regime and with a finite number of bits, it is possible to attain the performance achievable in the absence of compression.
  arXiv  Detail & Related papers  (2024-06-26T15:11:26Z)
• Bi-Level Offline Policy Optimization with Limited Exploration [1.8130068086063336]
  We study offline reinforcement learning (RL) which seeks to learn a good policy based on a fixed, pre-collected dataset. We propose a bi-level structured policy optimization algorithm that models a hierarchical interaction between the policy (upper-level) and the value function (lower-level) We evaluate our model using a blend of synthetic, benchmark, and real-world datasets for offline RL, showing that it performs competitively with state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-10-10T02:45:50Z)
• Compression, Generalization and Learning [3.045851438458641]
  A compression function is a map that slims down an observational set into a subset of reduced size. In multiple applications, the condition that one new observation makes the compressed set change is interpreted that this observation brings in extra information. In this paper, we lay the foundations of a new theory that allows one to keep control on the probability of change of compression.
  arXiv  Detail & Related papers  (2023-01-30T10:27:45Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)

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.