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.
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.
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.
Sharp inequalities for star bodies in 2D space.
problem Understanding star bodies in 2D space.
method Sharp inequalities for star bodies in R2. result New inequalities and proofs for star bodies.
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.
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…
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.
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.
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.
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 "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.
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…
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.
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 d 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…
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…
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 work tackles community detection in networks with node attributes, achieving exact recovery.
problem Community detection in networks with correlated node attributes.
method Information-theoretic criterion and iterative clustering algorithm maximizing joint likelihood.
result Exact recovery of community labels under a general model for network and node attributes.
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 ildeO(d) for isotropic log-concave distributions. 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…
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…
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 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…
Mixture distributions arise in many parametric and non-parametric settings -- for example, in Gaussian mixture models and in non-parametric estimation. It is often necessary to compute the entropy of a mixture, but, in most cases, this quantity has no closed-form expression, making some form of approximation necessary.…
Sharp threshold for exact recovery in non-uniform hypergraph stochastic block model.
problem Community detection in random hypergraphs with non-uniform hyperedge probabilities.
method Sharp threshold established; two efficient algorithms for exact recovery.
result Sharp threshold for exact recovery; information-theoretic lower bound on misclassification.
A trade-off between accuracy and fairness is almost taken as a given in the existing literature on fairness in machine learning. Yet, it is not preordained that accuracy should decrease with increased fairness. Novel to this work, we examine fair classification through the lens of mismatched hypothesis testing: trying …
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.
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.
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.
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.
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.
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.
The paper develops a method to sparsify magnetic Laplacians using multi-type spanning forests.
problem Sparsifying magnetic Laplacians for large and dense graphs.
method Sampling multi-type spanning forests using a determinantal point process.
result The method provides statistical guarantees for estimating the connection Laplacian.
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,…
New bounds for Neyman-Pearson region using f-divergences.
problem Bounding the Neyman-Pearson region for hypothesis testing.
method Establishing novel lower and upper bounds using f-divergences. result Best possible lower bound for the Neyman-Pearson boundary using hockey-stick f-divergences. 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.
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.
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.
Machine learning classification limits estimated using Kullback-Leibler divergence and Cohen's Kappa.
problem Estimating the best possible performance of machine learning classification algorithms.
method Relating Kullback-Leibler divergence to Cohen's Kappa and using the Chernoff-Stein Lemma to estimate error rates.
result Classification algorithms could not have performed any better due to underlying probability density functions for the two classes.
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.
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.
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.