We study an important variant of the stochastic multi-armed bandit (MAB) problem, which takes penalization into consideration. Instead of directly maximizing cumulative expected reward, we need to balance between the total reward and fairness level. In this paper, we present some new insights into MAB and formulate the problem in the penalization framework, where a rigorous penalized regret can be well defined and a more sophisticated regret analysis is possible. Under such a framework, we propose a hard-threshold UCB-like algorithm, which enjoys many merits including the asymptotic fairness, nearly optimal regret, good tradeoff between reward and fairness. Both gap-dependent and gap-independent regret bounds have been established. Multiple insightful comments are given to illustrate the soundness of our theoretical analysis. Numerous experimental results corroborate the theory and show the usefulness of our formulation of the problem and our method to solve it.

Extreme events are ubiquitous in various domains, including finance, meteorology, and network analysis. Nevertheless, modern deep learning techniques exhibit limitations in capturing extreme samples, treating them as outliers. In this paper, we propose Generalized Pareto Generative Adversarial Network (GPGAN), a novel generative model for tackling the generation of extreme values in distributions. Our methodology specifically entails the direct modeling of the multi-dimensional Generalized Pareto Distribution (GPD) using deep generative neural networks. Compared to prior work, GPGAN excels at faithfully representing the dependence structure exhibited by extreme values. To ensure effective generation, we employ an adaptive Generalized Pareto parameter strategy. This strategy dynamically selects appropriate GPD parameters for each generation step, enabling compatibility with user-defined extremeness functions within the multi-dimensional GPD framework. Extensive evaluations on a benchmark precipitation dataset demonstrate the effectiveness of our model.

We propose a spectral clustering algorithm for analyzing the dependence structure of multivariate extremes. More specifically, we focus on the asymptotic dependence of multivariate extremes characterized by the angular or spectral measure in extreme value theory. Our work studies the theoretical performance of spectral clustering based on a random $k$-nearest neighbor graph constructed from an extremal sample, i.e., the angular part of random vectors for which the radius exceeds a large threshold. In particular, we derive the asymptotic distribution of extremes arising from a linear factor model and prove that, under certain conditions, spectral clustering can consistently identify the clusters of extremes arising in this model. Leveraging this result we propose a simple consistent estimation strategy for learning the angular measure. Our theoretical findings are complemented with numerical experiments illustrating the finite sample performance of our methods.

Although there has been work to develop ex-post private mechanisms from Ligett et al. '17 and Whitehouse et al '22 that seeks to provide privacy guarantees subject to a target level of accuracy, there was not a way to use them in conjunction with differentially private mechanisms. Furthermore, there has yet to be work in developing a theory for how these ex-post privacy mechanisms compose, so that we can track the accumulated privacy over several mechanisms. We develop privacy filters that allow an analyst to adaptively switch between differentially private mechanisms and ex-post private mechanisms subject to an overall privacy loss guarantee. We show that using a particular ex-post private mechanism --- noise reduction mechanisms --- can substantially outperform baseline approaches that use existing privacy loss composition bounds. We use the common task of returning as many counts as possible subject to a relative error guarantee and an overall privacy budget as a motivating example.

Motivated by situations where the extreme values – as opposed to expected values in the classical stochastic multi-armed bandit (MAB) setting – are of interest, we propose a distribution-free algorithm for$\textit {extreme bandits}$and characterize its statistical properties. The proposed novel algorithm is index based, where the index is fashioned in a non-parametric way using combinatorics and robust statistics. For distributions having “exponential-like tails” and “polynomial-like tails”, we establish the following results: (i) the proposed algorithm is consistent, i.e., the index corresponding to the best arm will have the largest value asymptotically; (ii) the proposed algorithm achieves vanishing extremal regret under weaker conditions than the existing algorithms. Numerical experiments on the common class of distributions considered in the literature on extreme bandits highlight the superior finite-sample performance of the proposed algorithm compared to the state of the art.

This paper studies the scale-invariant "probability Jaccard'' (ProbJ), noted as ℐ℘, which is another variant of weighted Jaccard similarity. The standard and commonly used Jaccard index is not invariant of data scaling. Thus, the probability Jaccard can be a potentially useful extension to probability distributions. Before our paper, the problem of hashing the ℐ℘ for continuous probability measures is an open problem, where rigorous definitions and analysis are still absent in literature. In our work, we solve this problem systematically and completely. Specifically, we formalize the definition of ℐ℘ in continuous measure space, and propose a general ℘-MinHash sampling algorithm which generates samples following any target distribution, and preserves ℐ℘ between two distributions by the hash collision. In addition, a refined early stopping rule is proposed under a practical boundedness assumption. We validate the theory through simulation and experiments, and demonstrate the application of our method in machine learning problems.

We present a new finite-sample analysis of Catoni’s M-estimator under adversarial contamination, where an adversary is allowed to corrupt a fraction of the samples arbitrarily. We make minimal assumptions on the distribution of the uncontaminated random variables, namely, we only assume the existence of a known upper bound $\upsilon_{\varepsilon} > 0$ on the $(1+\varepsilon)^{th}$ central moment of the random variables, namely, for $\varepsilon \in (0,1]$ \[ \mathbb{E}_{X_1 \sim \mathcal{D}} \Big| X_1 - \mu \Big|^{1+\varepsilon} \leq \upsilon_{\varepsilon}. \]{We} provide a lower bound on the minimax error rate for the mean estimation problem under adversarial corruption under this weak assumption, and establish that the proposed M-estimator achieves this lower bound (up to multiplicative constants). When the variance is infinite, the tolerance to contamination of any estimator reduces as $\varepsilon \downarrow 0$. We establish a tight upper bound that characterizes this bargain. To illustrate the usefulness of the derived robust M-estimator in an online setting, we present a bandit algorithm for the partially identifiable best arm identification problem that improves upon the sample complexity of the state of the art algorithms.

In this paper, we extend the remarkable M-estimator of Catoni \citep{Cat12} to situations where the variance is infinite. In particular, given a sequence of i.i.d random variables $\{X_i\}_{i=1}^n$ from distribution $\mathcal{D}$ over $\mathbb{R}$ with mean $\mu$, we only assume the existence of a known upper bound $\upsilon_{\varepsilon} > 0$ on the $(1+\varepsilon)^{th}$ central moment of the random variables, namely, for $\varepsilon \in (0,1]$ \[ \mathbb{E}_{X_1 \sim \mathcal{D}} \Big| X_1 - \mu \Big|^{1+\varepsilon} \leq \upsilon_{\varepsilon}. \]{The} extension is non-trivial owing to the difficulty in characterizing the roots of certain polynomials of degree smaller than $2$. The proposed estimator has the same order of magnitude and the same asymptotic constant as in \citet{Cat12}, but for the case of bounded moments. We further propose a version of the estimator that does not require even the knowledge of $\upsilon_{\varepsilon}$, but adapts the moment bound in a data-driven manner. Finally, to illustrate the usefulness of the derived non-asymptotic confidence bounds, we consider an application in multi-armed bandits and propose best arm identification algorithms, in the fixed confidence setting, that outperform the state of the art.

Learning in a Markov Decision Process (MDP) framework is a fundamental challenge for sequential decision making under uncertainty. In this paper, we present a new perspective on model-based learning in MDPs using ideas from renewal theory. In particular, we reformulate the problem of controlling a Markov chain to one of controlling a renewal reward process with bandit feedback. For this reformulated problem, we provide a regret decomposition that informs novel algorithm design for MDPs. We further provide a naive algorithm based¨ on this reformulation along with the regret analysis. A simple greedy variant of the proposed algorithm is shown to empirically outperform popular value-based methods for finite MDPs.

The1 Jaccard similarity has been widely used in search and machine learning, especially in industrial practice. For binary (0/1) data, the Jaccard similarity is often called the “resemblance” and the method of minwise hashing has been the standard tool for computing resemblances in massive data. For general weighted data, the commonly used sampling algorithm for computing the (weighted) Jaccard similarity is the Consistent Weighted Sampling (CWS). A convenient (and perhaps also mysterious) implementation of CWS is the so-called “0-bit CWS” published in KDD 2015 [31], which, in this paper, we refer to as the “relaxed CWS” and was purely an empirical observation without theoretical justification. The difficulty in the analysis of the “relaxed CWS” is due to the complicated probability problem, which we could not resolve at this point.

We study information diffusion modeled by epidemic models on a class of growing preferential attachment networks. We show through a thorough simulation study that there is a fundamental difference in the nature of the epidemic process on growing temporal networks in comparison to the same process on static networks. The empirical distribution of the epidemic lifetime on growing networks has a considerably heavier, and possibly infinite, tail. Furthermore, the notion of the epidemic threshold has only minor significance in this context, since network growth reduces the critical value of the corresponding static graph.

The method of Cauchy random projections is popular for computing the $l_1$ distance in high dimension. In this paper, we propose to use only the signs of the projected data and show that the probability of collision (i.e., when the two signs differ) can be accurately approximated as a function of the chi-square ($\chi^2$) similarity, which is a popular measure for nonnegative data (e.g., when features are generated from histograms as common in text and vision applications). Our experiments confirm that this method of sign Cauchy random projections is promising for large-scale learning applications. Furthermore, we extend the idea to sign $\alpha$-stable random projections and derive a bound of the collision probability.