Chain rules for one-shot entropic quantities via operational methods

• URL: http://arxiv.org/abs/2305.08521v1
• Date: Mon, 15 May 2023 10:29:42 GMT
• Title: Chain rules for one-shot entropic quantities via operational methods
• Authors: Sayantan Chakraborty, Upendra Kapshikar
• Abstract summary: We introduce a new operational technique for deriving chain rules for general information theoretic quantities. Our framework considers a simple information transmission task and obtains lower and upper bounds for it. As a demonstration of this technique, we derive chain rules for the smooth max mutual information and the smooth-Hypothesis testing mutual information.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a new operational technique for deriving chain rules for general information theoretic quantities. This technique is very different from the popular (and in some cases fairly involved) methods like SDP formulation and operator algebra or norm interpolation. Instead, our framework considers a simple information transmission task and obtains lower and upper bounds for it. The lower bounds are obtained by leveraging a successive cancellation encoding and decoding technique. Pitting the upper and lower bounds against each other gives us the desired chain rule. As a demonstration of this technique, we derive chain rules for the smooth max mutual information and the smooth-Hypothesis testing mutual information.

Related papers

• Mutual information chain rules for security proofs robust against device imperfections [0.0]
  We analyze quantum cryptography with imperfect devices that leak additional information to an adversary. We show that these results can be used to handle some device imperfections in a variety of device-dependent and device-independent protocols.
  arXiv  Detail & Related papers  (2024-07-29T19:47:47Z)
• Bottoms Up for CHCs: Novel Transformation of Linear Constrained Horn Clauses to Software Verification [0.09786690381850355]
  Constrained Horn Clauses (CHCs) have conventionally been used as a low-level representation in formal verification. We propose an alternative bottom-up approach for linear CHCs, and evaluate the two options in the open-source model checking framework THETA.
  arXiv  Detail & Related papers  (2024-04-23T16:46:27Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep unrolling is an emerging learning-to-optimize method that unrolls a truncated iterative algorithm in the layers of a trainable neural network. We show that convergence guarantees and generalizability of the unrolled networks are still open theoretical problems. We numerically assess unrolled architectures trained under the proposed constraints in two different applications.
  arXiv  Detail & Related papers  (2023-12-25T18:51:23Z)
• Perfectly Secure Steganography Using Minimum Entropy Coupling [60.154855689780796]
  We show that a steganography procedure is perfectly secure under Cachin 1998's information-theoretic model of steganography. We also show that, among perfectly secure procedures, a procedure maximizes information throughput if and only if it is induced by a minimum entropy coupling.
  arXiv  Detail & Related papers  (2022-10-24T17:40:07Z)
• Chained Generalisation Bounds [26.043342234937747]
  We derive upper bounds for the expected generalisation error of supervised learning algorithms by means of the chaining technique. We establish a duality between generalisation bounds based on the regularity of the loss function, and their chained counterparts.
  arXiv  Detail & Related papers  (2022-03-02T09:34:36Z)
• Adversarial Skill Chaining for Long-Horizon Robot Manipulation via Terminal State Regularization [65.09725599705493]
  We propose to chain multiple policies without excessively large initial state distributions. We evaluate our approach on two complex long-horizon manipulation tasks of furniture assembly. Our results have shown that our method establishes the first model-free reinforcement learning algorithm to solve these tasks.
  arXiv  Detail & Related papers  (2021-11-15T18:59:03Z)
• Robust Predictable Control [149.71263296079388]
  We show that our method achieves much tighter compression than prior methods, achieving up to 5x higher reward than a standard information bottleneck. We also demonstrate that our method learns policies that are more robust and generalize better to new tasks.
  arXiv  Detail & Related papers  (2021-09-07T17:29:34Z)
• Autoregressive Belief Propagation for Decoding Block Codes [113.38181979662288]
  We revisit recent methods that employ graph neural networks for decoding error correcting codes. Our method violates the symmetry conditions that enable the other methods to train exclusively with the zero-word. Despite not having the luxury of training on a single word, and the inability to train on more than a small fraction of the relevant sample space, we demonstrate effective training.
  arXiv  Detail & Related papers  (2021-01-23T17:14:55Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian [15.813217907813778]
  We first clarify serious limitations of current methods as well as the inappropriateness of the standard iteratively reweighted least squares procedure. In view of these limitations, we suggest a novel and more reliable iterative reweighting strategy that incorporates information from higher-order neighborhoods. We demonstrate the superior performance of our procedure over state-of-the-art methods using both synthetic and real datasets.
  arXiv  Detail & Related papers  (2020-06-11T17:53:01Z)

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.