Sharp inequalities for star bodies in 2D space.
problem Understanding star bodies in 2D space.
method Sharp inequalities for star bodies in .
result New inequalities and proofs for star bodies.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Chernoff inequalities”
New PAC-Bayes bounds for unbounded losses using Cramér-Chernoff techniques.
problem Developing bounds for unbounded losses in PAC-Bayesian settings.
method Introducing a new PAC-Bayes oracle bound using Cramér-Chernoff bounds and controlling random variable tails.
result Our bounds generalize and improve upon previous results, providing more informative and potentially tighter bounds.
We derive exponential tail inequalities for sums of random matrices with no dependence on the explicit matrix dimensions. These are similar to the matrix versions of the Chernoff bound and Bernstein inequality except with the explicit matrix dimensions replaced by a trace quantity that can be small even when the dimens…
Paper analyzes trade-offs between fairness, privacy, and accuracy using Chernoff Information.
problem The relationship between fairness and privacy in machine learning.
method Utilizes Chernoff Information to characterize trade-offs, proposes Chernoff Difference and Noisy Chernoff Difference, develops CINE for neural estimation.
result Shows three distinct behaviors of Noisy Chernoff Difference based on data distribution.
Unified approach to discrete and smooth isoperimetric inequalities of arbitrary order.
problem Finding higher order isoperimetric inequalities for both discrete and smooth curves.
method Unified approach via Fourier analysis of linear operators.
result Unified upper and lower bounds for isoperimetric deficit in smooth curves.
Paper extends Chernoff sampling for active testing and parameter estimation, improving neural network and regression models.
problem Reducing sample complexity in hypothesis testing and model parameter estimation.
method Developed an extension of Chernoff sampling for active learning and parameter estimation.
result Non-asymptotic bounds for sample complexity and estimation error in active learning.
New inequalities for matrix supermartingales converge under various conditions.
problem Convergence and maximal inequalities of supermartingales in positive semidefinite matrices.
method Developed new concentration inequalities for matrix supermartingales.
result New inequalities for matrix supermartingales under different tail conditions.
Improved sample complexity for learning halfspaces with malicious noise.
problem Efficiently learning halfspaces in the presence of malicious noise.
method New analysis of Awasthi et al. algorithm with matrix Chernoff inequality and localization schemes.
result Achieved near-optimal sample complexity of for isotropic log-concave distributions.
Matrix Chernoff bound for Markov chains applied to co-occurrence matrices.
problem Analyzing the behavior of co-occurrence statistics in sequential data.
method Proved a matrix Chernoff-type bound for sums of matrix-valued random variables sampled via a regular Markov chain.
result Achieved exponentially fast convergence rate and sample complexity analysis for co-occurrence matrices.
A note on extending Chernoff bound for unit interval random variables.
problem Extending the Chernoff bound to random variables in the unit interval.
method Proof of extension of the Chernoff bound.
result A proof provided for the extension of the Chernoff bound.
Optimizes network sampling for efficient community detection.
problem Prohibitive cost of observing entire network for community detection.
method Chernoff-optimal dynamic sampling scheme for stochastic blockmodel.
result Significant resource savings while maintaining block structure recovery.
Method bounds tail probabilities of continuous RVs.
problem Bounding tail probabilities of continuous random variables.
method Setting continuous, positive, and strictly decreasing/increasing functions to derive upper and lower bounds.
result Provides tighter bounds than existing methods, including a novel asymptotic capacity bound for AWGN channel.
New bounds for Neyman-Pearson region using -divergences.
problem Bounding the Neyman-Pearson region for hypothesis testing.
method Establishing novel lower and upper bounds using -divergences.
result Best possible lower bound for the Neyman-Pearson boundary using hockey-stick -divergences.
Near-optimal confidence intervals for bounded data.
problem Online inference for sequential decision problems like A/B testing.
method Utilizing Bentkus' concentration results to improve on existing methods.
result Near-optimal confidence intervals confirmed favorable in synthetic and practical applications.
This paper introduces a new bound to explain generalization in over-parameterized models.
problem Understanding why some over-parameterized models generalize well while others do not.
method PAC-Chernoff bounds and smoothness measures based on large deviation theory.
result Interpolators with smoother structures generalize better, according to the new theoretical framework.
We study nonzero-sum hypothesis testing games that arise in the context of adversarial classification, in both the Bayesian as well as the Neyman-Pearson frameworks. We first show that these games admit mixed strategy Nash equilibria, and then we examine some interesting concentration phenomena of these equilibria. Our…
We study "active" decision making over sensor networks where the sensors' sequential probing actions are actively chosen by continuously learning from past observations. We consider two network settings: with and without central coordination. In the first case, the network nodes interact with each other through a centr…
We improve the over-parametrization size over two beautiful results [Li and Liang' 2018] and [Du, Zhai, Poczos and Singh' 2019] in deep learning theory.
Simplified proof for approximations of set systems.
problem Approximations of set systems in various fields.
method Modular, self-contained proof using Chernoff's bound.
result Accessible proof for a wider audience.
Improved regret bounds for DP-KLUCB and DP-IMED in Bernoulli bandits.
problem Minimizing regret in stochastic bandits under ε-global Differential Privacy.
method Developed DP versions of KLUCB and IMED, proving tighter lower bounds and matching upper bounds.
result DP-KLUCB and DP-IMED achieve asymptotically optimal regret under ε-global DP.
Chernoff Bounds for Tensor Expanders on Riemannian Manifolds Using Graph Laplacian Approximationmath.PR
Paper extends tail bounds to high-dimensional random objects on Riemannian manifolds.
problem Need for tail bounds in high-dimensional data.
method Random walks on graph approximating the manifold, ensuring spectral similarity.
result Derived tensor Chernoff bound for Riemannian manifolds.
Recent research has made significant progress on the problem of bounding log partition functions for exponential family graphical models. Such bounds have associated dual parameters that are often used as heuristic estimates of the marginal probabilities required in inference and learning. However these variational est…
Two spectral algorithms for community detection in graphs with covariates are compared.
problem Detecting community structure in graphs with covariates.
method Two model-based spectral algorithms are presented and compared.
result The second algorithm often better estimates block assignments by accounting for vertex covariates.
Paper improves CI and CS for bounded means using betting and mixtures.
problem Estimating means of bounded random variables.
method Composite nonnegative martingales, testing by betting, method of mixtures.
result Empirically outperforms existing CI and CS methods.
We recall the Chernoff-Marsden definition of weak symplectic structure and give a rigorous treatment of the functional analysis and geometry of weak symplectic Banach spaces. We define the Maslov index of a continuous path of Fredholm pairs of Lagrangian subspaces in continuously varying Banach spaces. We derive basic …
This paper improves coreset size via smoothed analysis.
problem Efficiently computing small subsets that approximate query errors.
method Smoothed analysis for approximate average error over queries.
result Deterministic and randomized algorithms for smaller coresets.
New model for community detection with side information improves recovery accuracy.
problem Community detection in networks with additional node data.
method Data Block Model (DBM) with Chernoff--TV divergence for threshold characterization and efficient algorithm.
result Sharp exact recovery threshold and efficient algorithm for DBM.
We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optim…
In this paper, we develop a general theory of truncated inverse binomial sampling. In this theory, the fixed-size sampling and inverse binomial sampling are accommodated as special cases. In particular, the classical Chernoff-Hoeffding bound is an immediate consequence of the theory. Moreover, we propose a rigorous and…
Develops new methods for risk-aware decision-making in medical bandits.
problem Risk-averse decision-making in medical contexts with limited data.
method Safe, anytime-valid concentration bounds, risk-aware contextual bandits, nonparametric algorithms.
result Improved decision-making algorithms for postoperative patient follow-up.
Open problem: fixed-budget best arm identification complexity.
problem Understanding the complexity of identifying the best arm in a fixed budget setting.
method Analyzing existing results and conjectures in the fixed-confidence setting.
result Open questions remain about the fixed-budget setting.
Investigates tight PAC-Bayes bounds for small datasets.
problem Tightening PAC-Bayes bounds for small data.
method Generic PAC-Bayes theorem, meta-learning, synthetic tasks.
result PAC-Bayes bounds are competitive with Chernoff bounds but not as tight.
A single algebraic identity unifies information-theoretic variational results.
problem Deriving and generalizing classical information-theoretic variational results
method Proving a single algebraic mixed coincidence identity
result Unified derivation of classical cornerstones of information theory
In many machine learning applications, crowdsourcing has become the primary means for label collection. In this paper, we study the optimal error rate for aggregating labels provided by a set of non-expert workers. Under the classic Dawid-Skene model, we establish matching upper and lower bounds with an exact exponent …
We prove a central limit theorem for the components of the eigenvectors corresponding to the largest eigenvalues of the normalized Laplacian matrix of a finite dimensional random dot product graph. As a corollary, we show that for stochastic blockmodel graphs, the rows of the spectral embedding of the normalized La…
This paper develops a new mathematical-statistical approach to analyze a class of Flajolet-Martin algorithms (FMa), and provides analytical confidence intervals for the number F0 of distinct elements in a stream, based on Chernoff bounds. The class of FMa has reached a significant popularity in bigdata stream learning,…
In this dissertation, I derive a new method to estimate the Vapnik-Chervonenkis Dimension (VCD) for the class of linear functions. This method is inspired by the technique developed by Vapnik et al. Vapnik et al. (1994). My contribution rests on the approximation of the expected maximum difference between two empirical…
Paper tackles best arm identification with cost consideration.
problem Best arm identification with cost consideration in product development.
method Derives a theoretical lower bound and proposes algorithms CTAS and CO.
result Simple algorithms can deliver near-optimal performance.
The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatori…
Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.
problem Achieving optimal error rates in clustering sub-exponential mixture models.
method Establishes universal lower bounds and demonstrates iterative algorithms' optimality in sub-exponential mixture models.
result Iterative algorithms achieve the universal lower bound in sub-exponential mixture models.
The isoperimetric inequalitymath.DG
The isoperimetric inequality and related inequalities are explored.
problem Proving the isoperimetric inequality and related inequalities.
method Discussing classical and recent proofs.
result Various proofs of the isoperimetric inequality and Sobolev inequality.
Optimizes ranking from click feedback in a bandit setting.
problem Learning to rank from Bernoulli click feedback in a bandit setting.
method Variance-aware confidence sets derived from Bernstein and Chernoff bounds for optimal algorithms.
result Optimal algorithms for the case of small mean rewards, improving on previous suboptimal results.
New proof of Willmore inequality using geometric divergence inequality.
problem Proving the Willmore inequality for bounded domains.
method Using a parametric geometric inequality derived from a divergence form geometric differential inequality.
result New proofs of quantitative Willmore-type and weighted Minkowski inequalities.
Surprisal-Rényi Free Energystat.ML
SRFE clarifies KL divergences without unifying learning frameworks.
problem Inductive biases of KL divergences and their limitations.
method Introducing SRFE, a log-moment-based functional of the likelihood ratio.
result SRFE recovers KL divergences as limits and reveals a mean-variance tradeoff.
Lorentz-Finsler geometry reveals new and old inequalities.
problem Finding new inequalities using Lorentz-Finsler geometry.
method Applying reverse Cauchy-Schwarz and reverse triangle inequalities in Lorentz-Finsler geometry.
result Proved new and refined inequalities, including refinements of Aczél's inequality.
The paper derives new inequalities on manifolds and applies them to convex hypersurfaces.
problem Deriving new inequalities on manifolds and convex hypersurfaces.
method Using Fourier theory and geometric implications of Poincare-type inequalities.
result Sharp Minkowski-type inequalities, including stability and Alexandrov-Fenchel inequalities.
The paper proves inequalities on Finsler manifolds under Ricci curvature bounds.
problem Proving -Sobolev and Nash inequalities on Finsler metric measure manifolds.
method Global -Poincaré inequality, -Sobolev inequality, Nash inequality derivation.
result Established global optimal -Sobolev inequality with a sharp constant.
Paper improves PAC-Bayes bounds for various loss types.
problem Improving PAC-Bayes bounds for different types of losses.
method Introducing new high-probability PAC-Bayes bounds for bounded and general tail behaviors losses, and extending to anytime-valid bounds.
result New fast-rate and mixed-rate bounds for losses with bounded ranges, and parameter-free bounds for losses with general tail behaviors.