Bottleneck Problems: Information and Estimation-Theoretic View

• URL: http://arxiv.org/abs/2011.06208v1
• Date: Thu, 12 Nov 2020 05:16:44 GMT
• Title: Bottleneck Problems: Information and Estimation-Theoretic View
• Authors: Shahab Asoodeh and Flavio Calmon
• Abstract summary: Information bottleneck (IB) and privacy funnel (PF) are two closely related optimization problems. We show how to evaluate bottleneck problems in closed form by equivalently expressing them in terms of lower envelope or upper envelope of certain functions.
• Score: 2.7793394375935088
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Information bottleneck (IB) and privacy funnel (PF) are two closely related optimization problems which have found applications in machine learning, design of privacy algorithms, capacity problems (e.g., Mrs. Gerber's Lemma), strong data processing inequalities, among others. In this work, we first investigate the functional properties of IB and PF through a unified theoretical framework. We then connect them to three information-theoretic coding problems, namely hypothesis testing against independence, noisy source coding and dependence dilution. Leveraging these connections, we prove a new cardinality bound for the auxiliary variable in IB, making its computation more tractable for discrete random variables. In the second part, we introduce a general family of optimization problems, termed as \textit{bottleneck problems}, by replacing mutual information in IB and PF with other notions of mutual information, namely $f$-information and Arimoto's mutual information. We then argue that, unlike IB and PF, these problems lead to easily interpretable guarantee in a variety of inference tasks with statistical constraints on accuracy and privacy. Although the underlying optimization problems are non-convex, we develop a technique to evaluate bottleneck problems in closed form by equivalently expressing them in terms of lower convex or upper concave envelope of certain functions. By applying this technique to binary case, we derive closed form expressions for several bottleneck problems.

Related papers

• Investigating the Relation Between Problem Hardness and QUBO Properties [0.0]
  This work aims to shed some light on the relationship between the problems' properties. We analyze two well-known problems from Machine Learning, namely Clustering and Support Vector Machine (SVM) training. An empirical evaluation provides interesting insights, showing that the spectral gap of Clustering QUBO instances positively correlates with data separability, while for SVM QUBO the opposite is true.
  arXiv  Detail & Related papers  (2024-04-03T13:53:03Z)
• Privacy-preserving Federated Primal-dual Learning for Non-convex and Non-smooth Problems with Model Sparsification [51.04894019092156]
  Federated learning (FL) has been recognized as a rapidly growing area, where the model is trained over clients under the FL orchestration (PS) In this paper, we propose a novel primal sparification algorithm for and guarantee non-smooth FL problems. Its unique insightful properties and its analyses are also presented.
  arXiv  Detail & Related papers  (2023-10-30T14:15:47Z)
• Manually Selecting The Data Function for Supervised Learning of small datasets [0.0]
  Supervised learning problems may become ill-posed when there is a lack of information. Initializing an informative ill-posed operator is akin to posing better questions to achieve more accurate answers. The Fredholm integral equation of the first kind (FIFK) is a reliable ill-posed operator that can integrate distributions and prior knowledge as input information.
  arXiv  Detail & Related papers  (2023-03-07T13:38:04Z)
• QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
  We learn QUBO forms from data through gradient backpropagation instead of deriving them. We demonstrate the advantages of learnt QUBOs on the diverse problem types of graph matching, 2D point cloud alignment and 3D rotation estimation.
  arXiv  Detail & Related papers  (2022-10-13T17:59:46Z)
• Variational Distillation for Multi-View Learning [104.17551354374821]
  We design several variational information bottlenecks to exploit two key characteristics for multi-view representation learning. Under rigorously theoretical guarantee, our approach enables IB to grasp the intrinsic correlation between observations and semantic labels.
  arXiv  Detail & Related papers  (2022-06-20T03:09:46Z)
• Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
  Federated learning (FL) is a promising privacy-preserving machine learning paradigm over distributed located data. We propose a learning-based reweighting approach to mitigate the effect of noisy labels in FL. Our approach has shown superior performance on several real-world datasets compared to various baselines.
  arXiv  Detail & Related papers  (2022-06-11T16:21:17Z)
• BayesIMP: Uncertainty Quantification for Causal Data Fusion [52.184885680729224]
  We study the causal data fusion problem, where datasets pertaining to multiple causal graphs are combined to estimate the average treatment effect of a target variable. We introduce a framework which combines ideas from probabilistic integration and kernel mean embeddings to represent interventional distributions in the reproducing kernel Hilbert space.
  arXiv  Detail & Related papers  (2021-06-07T10:14:18Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Batch Value-function Approximation with Only Realizability [17.692408242465763]
  We make progress in a long-standing problem of batch reinforcement learning (RL): learning $Qstar$ from an exploratory dataset. Our algorithm, BVFT, breaks the hardness conjecture (albeit under a stronger notion of exploratory data) via a tournament procedure. We also discuss how BVFT can be applied to model selection among other extensions and open problems.
  arXiv  Detail & Related papers  (2020-08-11T20:09:37Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  The distributionally robust optimization framework is considered for training a parametric model. The objective is to endow the trained model with robustness against adversarially manipulated input data. Proposed algorithms offer robustness with little overhead.
  arXiv  Detail & Related papers  (2020-07-07T18:25:25Z)
• On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views [39.49498500593645]
  This tutorial paper focuses on the variants of the bottleneck problem taking an information theoretic perspective. It discusses practical methods to solve it, as well as its connection to coding and learning aspects.
  arXiv  Detail & Related papers  (2020-01-31T15:23:19Z)

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.