Concept

Chernoff bound

Related publications (168)

Chebyshev Inequalities for Products of Random Variables

Daniel Kuhn, Napat Rujeerapaiboon, Wolfram Wiesemann

We derive sharp probability bounds on the tails of a product of symmetric non-negative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed nu ...

2018

Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo

Nisheeth Vishnoi, Oren Rami Mangoubi

Hamiltonian Monte Carlo (HMC) is a widely deployed method to sample from high-dimensional distributions in Statistics and Machine learning. HMC is known to run very efficiently in practice and its popular second-order "leapfrog" implementation has long bee ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018

Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs

Daniel Kuhn

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 ...

2018

Localizing the Source of an Epidemic Using Few Observations

Brunella Marta Spinelli

Localizing the source of an epidemic is a crucial task in many contexts, including the detection of malicious users in social networks and the identification of patient zeros of disease outbreaks. The difficulty of this task lies in the strict limitation ...

EPFL2018

Two-term, asymptotically sharp estimates for eigenvalue means of the Laplacian

Joachim Stubbe

We present asymptotically sharp inequalities for the eigenvalues mu(k) of the Laplacian on a domain with Neumann boundary conditions, using the averaged variational principle introduced in [14]. For the Riesz mean R-1(z) of the eigenvalues we improve the k ...

EUROPEAN MATHEMATICAL SOC2018

On multivariate trace inequalities of Sutter, Berta, and Tomamichel

Marius Christopher Lemm

We consider a family of multivariate trace inequalities recently derived by Sutter, Berta, and Tomamichel. These inequalities generalize the Golden-Thompson inequality and Lieb’s triple matrix inequality to an arbitrary number of matrices in a way that fea ...

2018

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

Robust Bounds In Multivariate Extremes

Sebastian Engelke

Extreme value theory provides an asymptotically justified framework for estimation of exceedance probabilities in regions where few or no observations are available. For multivariate tail estimation, the strength of extremal dependence is crucial and it is ...

Institute of Mathematical Statistics2017

Lower Bounds on Active Learning for Graphical Model Selection

Volkan Cevher, Jonathan Mark Scarlett

We consider the problem of estimating the underlying graph associated with a Markov random field, with the added twist that the decoding algorithm can iteratively choose which subsets of nodes to sample based on the previous samples, resulting in an active ...

2017

Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression

Nicolas Henri Bernard Flammarion, Aymeric Daphnis Kévin Dieuleveut

We consider the optimization of a quadratic objective function whose gradients are only accessible through a stochastic oracle that returns the gradient at any given point plus a zero-mean finite variance random error. We present the first algorithm that a ...

2017

Graph Chatbot

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.