On Properties of the Minimum Entropy Sub-tree to Compute Lower Bounds on the Partition Function

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Given two jointly distributed random variables (X,Y), a functional representation of X is a random variable Z independent of Y, and a deterministic function g(⋅,⋅) such that X=g(Y,Z). The problem of finding a minimum entropy functional representation is kn ...

This paper proposes an algorithm to upper-bound maximal quantile statistics of a state function over the course of a Stochastic Differential Equation (SDE) system execution. This chance-peak problem is posed as a nonconvex program aiming to maximize the Va ...

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

The conditional mean is a fundamental and important quantity whose applications include the theories of estimation and rate-distortion. It is also notoriously difficult to work with. This paper establishes novel bounds on the differential entropy of the co ...

This paper considers an additive Gaussian noise channel with arbitrarily distributed finite variance input signals. It studies the differential entropy of the minimum mean-square error (MMSE) estimator and provides a new lower bound which connects the diff ...

Mechanism design theory examines the design of allocation mechanisms or incentive systems involving multiple rational but self-interested agents and plays a central role in many societally important problems in economics. In mechanism design problems, agen ...

A well-known first-order method for sampling from log-concave probability distributions is the Unadjusted Langevin Algorithm (ULA). This work proposes a new annealing step-size schedule for ULA, which allows to prove new convergence guarantees for sampling ...

We study a mechanism design problem where an indivisible good is auctioned to multiple bidders, for each of whom it has a private value that is unknown to the seller and the other bidders. The agents perceive the ensemble of all bidder values as a random v ...

Many decision problems in science, engineering, and economics are affected by uncertainty, which is typically modeled by a random variable governed by an unknown probability distribution. For many practical applications, the probability distribution is onl ...

The maximal achievable advantage of a (computationally unbounded) distinguisher to determine whether a source

Z

is distributed according to distribution

P_0

P_1

, when given access to one sample of

Z

, is characterized by the statistical distance ...

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

We derive generalization and excess risk bounds for neural networks using a family of complexity measures based on a multilevel relative entropy. The bounds are obtained by introducing the notion of generated hierarchical coverings of neural networks and b ...

Given two probability measures P and Q and an event E, we provide bounds on P(E) in terms of Q(E) and f-divergences. In particular, the bounds are instantiated when the measures considered are a joint distribution and the corresponding product of marginals ...

The distributed remote source coding (the so-called CEO) problem is studied in the case where the underlying source, not necessarily Gaussian, has finite differential entropy and the observation noise is Gaussian. The main result is a new lower bound for t ...

Byzantine reliable broadcast is a powerful primitive that allows a set of processes to agree on a message from a designated sender, even if some processes (including the sender) are Byzantine. Existing broadcast protocols for this setting scale poorly, as ...

xtreme value analysis is concerned with the modelling of extreme events such as floods and heatwaves, which can have large impacts. Statistical modelling can be useful to better assess risks even if, due to scarcity of measurements, there is inherently ver ...

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit ...

We study stochastic bilevel programs where the leader chooses a binary here-and-now decision and the follower responds with a continuous wait-and-see-decision. Using modern decision rule approximations, we construct lower bounds on an optimistic version an ...

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time ...

Information concentration of probability measures have important implications in learning theory. Recently, it is discovered that the information content of a log-concave distribution concentrates around their differential entropy, albeit with an unpleasan ...

On Properties of the Minimum Entropy Sub-tree to Compute Lower Bounds on the Partition Function

Chat with Graph Search

Information Spectrum Converse for Minimum Entropy Couplings and Functional Representations

Peak Value-at-Risk Estimation for Stochastic Differential Equations using Occupation Measures

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Differential Entropy of the Conditional Expectation Under Additive Gaussian Noise

Differential Entropy of the Conditional Expectation under Gaussian Noise

Distributional Robustness in Mechanism Design

Double-Loop Unadjusted Langevin Algorithm

Distributionally Robust Mechanism Design

Wasserstein Distributionally Robust Learning

Sublinear Bounds on the Distinguishing Advantage for Multiple Samples

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Networks

Robust Generalization via f−Mutual Information

Remote Source Coding Under Gaussian Noise: Dueling Roles of Power and Entropy Power

Scalable Byzantine Reliable Broadcast

Contributions to Likelihood-Based Modelling of Extreme Values

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures

Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Dimension-free Information Concentration via Exp-Concavity