Adversarial attacks pose a major challenge to distributed learning systems, prompting the development of numerous robust learning methods. However, most existing approaches suffer from the curse of dimensionality, i.e. the error increases with the number of model parameters. In this paper, we make a progress towards high dimensional problems, under arbitrary number of Byzantine attackers. The cornerstone of our design is a direct high dimensional semi-verified mean estimation method. The idea is to identify a subspace with large variance. The components of the mean value perpendicular to this subspace are estimated using corrupted gradient vectors uploaded from worker machines, while the components within this subspace are estimated using auxiliary dataset. As a result, a combination of large corrupted dataset and small clean dataset yields significantly better performance than using them separately. We then apply this method as the aggregator for distributed learning problems. The theoretical analysis shows that compared with existing solutions, our method gets rid of sqrt{d} dependence on the dimensionality, and achieves minimax optimal statistical rates. Numerical results validate our theory as well as the effectiveness of the proposed method.

Evolutionary algorithms (EAs) are optimization algorithms that simulate natural selection and genetic mechanisms. Despite advancements, existing EAs have two main issues: (1) they rarely update next-generation individuals based on global correlations, thus limiting comprehensive learning; (2) it is challenging to balance exploration and exploitation, excessive exploitation leads to premature convergence to local optima, while excessive exploration results in an excessively slow search. Existing EAs heavily rely on manual parameter settings, inappropriate parameters might disrupt the exploration-exploitation balance, further impairing model performance. To address these challenges, we propose a novel evolutionary algorithm framework called Graph Neural Evolution (GNE). Unlike traditional EAs, GNE represents the population as a graph, where nodes correspond to individuals, and edges capture their relationships, thus effectively leveraging global information. Meanwhile, GNE utilizes spectral graph neural networks (GNNs) to decompose evolutionary signals into their frequency components and designs a filtering function to fuse these components. High-frequency components capture diverse global information, while low-frequency components capture more consistent information. This explicit frequency filtering strategy directly controls global-scale features through frequency components, overcoming the limitations of manual parameter settings and making the exploration-exploitation control more interpretable and effective. Extensive evaluations on nine benchmark functions (e.g., Sphere, Rastrigin, and Rosenbrock) demonstrate that GNE consistently outperforms both classical algorithms (GA, DE, CMA-ES) and advanced algorithms (SDAES, RL-SHADE) under various conditions, including original, noise-corrupted, and optimal solution deviation scenarios. GNE achieves solution quality several orders of magnitude better than other algorithms (e.g., 3.07e-20 mean on Sphere vs. 1.51e-07).

Large Language Models (LLMs) have exhibited remarkable capabilities but remain vulnerable to jailbreaking attacks, which can elicit harmful content from the models by manipulating the input prompts. Existing black-box jailbreaking techniques primarily rely on static prompts crafted with a single, non-adaptive strategy, or employ rigid combinations of several underperforming attack methods, which limits their adaptability and generalization. To address these limitations, we propose MAJIC, a Markovian adaptive jailbreaking framework that attacks black-box LLMs by iteratively combining diverse innovative disguise strategies. MAJIC first establishes a ''Disguise Strategy Pool'' by refining existing strategies and introducing several innovative approaches. To further improve the attack performance and efficiency, MAJIC formulate the sequential selection and fusion of strategies in the pool as a Markov chain. Under this formulation, MAJIC initializes and employs a Markov matrix to guide the strategy composition, where transition probabilities between strategies are dynamically adapted based on attack outcomes, thereby enabling MAJIC to learn and discover effective attack pathways tailored to the target model. Our empirical results demonstrate that MAJIC significantly outperforms existing jailbreak methods on prominent models such as GPT-4o and Gemini-2.0-flash, achieving over 90\% attack success rate with fewer than 15 queries per attempt on average.

Most models for Weakly Supervised Video Anomaly Detection (WS-VAD) rely on multiple instance learning, aiming to distinguish normal and abnormal snippets without specifying the type of anomaly. However, the ambiguous nature of anomaly definitions across contexts may introduce inaccuracy in discriminating abnormal and normal events. To show the model what is anomalous, a novel framework is proposed to guide the learning of suspected anomalies from event prompts. Given a textual prompt dictionary of potential anomaly events and the captions generated from anomaly videos, the semantic anomaly similarity between them could be calculated to identify the suspected events for each video snippet. It enables a new multi-prompt learning process to constrain the visual-semantic features across all videos, as well as provides a new way to label pseudo anomalies for self-training. To demonstrate its effectiveness, comprehensive experiments and detailed ablation studies are conducted on four datasets, namely XD-Violence, UCF-Crime, TAD, and ShanghaiTech. Our proposed model outperforms most state-of-the-art methods in terms of AP or AUC (86.5%, 90.4%, 94.4%, and 97.4%). Furthermore, it shows promising performance in open-set and cross-dataset cases. The data, code, and models can be found at: https://github.com/shiwoaz/lap .

We study convex optimization problems under differential privacy (DP). With heavy-tailed gradients, existing works achieve suboptimal rates. The main obstacle is that existing gradient estimators have suboptimal tail property, resulting in a superfluous factor of d in the union bound. In this paper, we explore algorithms achieving optimal rates of DP optimization with heavy-tailed gradients. Our first method is a simple clipping approach. Under bounded p-th order moments of gradients, with n samples, it achieves minimax optimal population risk with epsilon less than 1/d. We then propose an iterative updating method, which is more complex but achieves this rate for all epsilon smaller than 1. The results significantly improve over existing methods. Such improvement relies on a careful treatment of the tail behavior of gradient estimators. Our results match the minimax lower bound, indicating that the theoretical limit of stochastic convex optimization under DP is achievable.

Label differential privacy (DP) is a framework that protects the privacy of labels in training datasets, while the feature vectors are public. Existing approaches protect the privacy of labels by flipping them randomly, and then train a model to make the output approximate the privatized label. However, as the number of classes K increases, stronger randomization is needed, thus the performances of these methods become significantly worse. In this paper, we propose a vector approximation approach for learning with label local differential privacy, which is easy to implement and introduces little additional computational overhead. Instead of flipping each label into a single scalar, our method converts each label into a random vector with K components, whose expectations reflect class conditional probabilities. Intuitively, vector approximation retains more information than scalar labels. A brief theoretical analysis shows that the performance of our method only decays slightly with K. Finally, we conduct experiments on both synthesized and real datasets, which validate our theoretical analysis as well as the practical performance of our method.

Identifying the most representative subset for a close-to-submodular objective while satisfying the predefined partition constraint is a fundamental task with numerous applications in machine learning. However, the existing distorted local-search methods are often hindered by their prohibitive query complexities and the rigid requirement for prior knowledge of difficult-to-obtain structural parameters. To overcome these limitations, we introduce a novel algorithm titled **Multinoulli-SCG**, which not only is parameter-free, but also can achieve the same approximation guarantees as the distorted local-search methods with significantly fewer function evaluations. The core of our **Multinoulli-SCG** algorithm is an innovative continuous-relaxation framework named Multinoulli Extension(***ME***), which can effectively convert the discrete subset selection problem subject to partition constraints into a solvable continuous maximization focused on learning the optimal multinoulli priors across the considered partition. In sharp contrast with the well-established multi-linear extension for submodular subset selection, a notable advantage of our proposed ***ME*** is its intrinsic capacity to provide a lossless rounding scheme for any set function. Finally, we validate the practical efficacy of our proposed algorithms by applying them to video summarization, bayesian A-optimal design and coverage maximization.

Nonparametric contextual bandit is an important model of sequential decision making problems. Under $\alpha$-Tsybakov margin condition, existing research has established a regret bound of $\tilde{O}\left(T^{1-\frac{\alpha+1}{d+2}}\right)$ for bounded supports. However, the optimal regret with unbounded contexts has not been analyzed. The challenge of solving contextual bandit problems with unbounded support is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. In this paper, we solve the nonparametric contextual bandit problem with unbounded contexts. We propose two nearest neighbor methods combined with UCB exploration. The first method uses a fixed $k$. Our analysis shows that this method achieves minimax optimal regret under a weak margin condition and relatively light-tailed context distributions. The second method uses adaptive $k$. By a proper data-driven selection of $k$, this method achieves an expected regret of $\tilde{O}\left(T^{1-\frac{(\alpha+1)\beta}{\alpha+(d+2)\beta}}+T^{1-\beta}\right)$, in which $\beta$ is a parameter describing the tail strength. This bound matches the minimax lower bound up to logarithm factors, indicating that the second method is approximately optimal.

In this paper, we present two effective policy learning algorithms for multi-agent online coordination(MA-OC) problem. The first one, **MA-SPL**, not only can achieve the optimal $(1-\frac{c}{e})$-approximation guarantee for the MA-OC problem with submodular objectives but also can handle the unexplored $\alpha$-weakly DR-submodular and $(\gamma,\beta)$-weakly submodular scenarios, where $c$ is the curvature of the investigated submodular functions, $\alpha$ denotes the diminishing-return(DR) ratio and the tuple$(\gamma,\beta)$ represents the submodularity ratios. Subsequently, in order to reduce the reliance on the unknown parameters $\alpha,\gamma,\beta$ inherent in the **MA-SPL** algorithm, we then introduce the second online algorithm named **MA-MPL**. This **MA-MPL** algorithm is entirely *parameter-free* and simultaneously can maintain the same approximation ratio as the first **MA-SPL** algorithm. The core of our **MA-SPL** and **MA-MPL** algorithms is a novel continuous-relaxation technique term as policy-based continuous extension. Compared with the well-established multi-linear extension, a notable advantage of this new policy-based continuous extension is its ability to provide a lossless rounding scheme for any set function, thereby enabling us to tackle the challenging weakly submodular objective functions. Finally, extensive simulations are conducted to demonstrate the effectiveness of our proposed algorithms.

Federated Learning (FL) enables multiple clients to collaboratively train models without sharing raw data, but is vulnerable to Byzantine attacks and data heterogeneity, which can severely degrade performance. Existing Byzantine-robust approaches tackle data heterogeneity, but incur high computational overhead during gradient aggregation, thereby slowing down the training process. To address this issue, we propose a simple yet effective Federated Normalized Gradients Algorithm (Fed-NGA), which performs aggregation by merely computing the weighted mean of the normalized gradients from each client. This approach yields a favorable time complexity of $\mathcal{O}(pM)$, where $p$ is the model dimension and $M$ is the number of clients. We rigorously prove that Fed-NGA is robust to both Byzantine faults and data heterogeneity. For non-convex loss functions, Fed-NGA achieves convergence to a neighborhood of stationary points under general assumptions, and further attains zero optimality gap under some mild conditions, which is an outcome rarely achieved in existing literature. In both cases, the convergence rate is $\mathcal{O}(1/T^{\frac{1}{2} - \delta})$, where $T$ denotes the number of iterations and $\delta \in (0, 1/2)$. Experimental results on benchmark datasets confirm the superior time efficiency and convergence performance of Fed-NGA over existing methods.

Protection of local differential privacy (LDP) proto-cols against manipulation attacks is an important and challenging problem. We hope to design an attack-agnostic framework, which does not rely on any knowledge of attackers. An early work [1] restricts the attacker's capability by converting each sample into a binary signal. However, the compression of signal leads to severe loss of information, and thus results in unnecessary sacrifice of utility, especially when$\epsilon > 1$. In this paper, we propose a general estimation framework RobustLDP for robust estimation under LDP. The general idea is to send carefully crafted pre-defined information to all users, and then aggregate the feedback at the server. We strike a better tradeoff between preserving information and restricting the attacker's capability. We instantiate RobustLDP for frequency estimation and mean estimation in$\ell_{1}$and$\ell_{2}$support, which serve as building blocks for more advanced tasks. We also establish theoretical guarantees for all possible attacks. The result shows that our method significantly outperforms the existing one for$\epsilon > 1$. Extensive experiments on multiple real-world datasets validate the effectiveness of our method.

Robustness is one of the critical concerns in federated learning. Existing research focuses primarily on the worst case, typically modeled as the Byzantine attack, which alters the gradients in an optimal way. However, in practice, the corruption usually happens randomly, and is much weaker than the Byzantine attack. Therefore, existing methods overestimate the power of corruption, resulting in unnecessary sacrifice of performance. In this article, we build practical algorithms that can withstand realistic corruption, which is weaker than the Byzantine attack, in a better way. Toward this goal, we propose a new iterative filtering approach. In each iteration, it calculates the geometric median of all gradient vectors uploaded from clients and remove the gradients that are far away from the geometric median. A theoretical analysis is then provided, showing that under suitable parameter regimes, gradient vectors from corrupted clients are filtered if the noise is large, while those from benign clients are never filtered throughout the training process. For realistic gradient noise, our approach significantly outperforms existing methods, while the performance under the worst-case attack (i.e., the Byzantine attack) remains nearly the same. Experiments on both synthesized and real data validate our theoretical results, as well as the practical performance of our approach. In particular, we have achieved 3%–10% increase in MNIST and CIFAR10 datasets.

Target speaker extraction (TSE) aims to isolate a specific speaker’s voice from multi-talker environments using enrollment data. While current approaches primarily utilize speaker embeddings from enrollment, they often neglect contextual information and the dynamic interactions between the mixture and enrollment. To address this limitation, we propose a novel DualStream Contextual Fusion Network (DCF-Net) that operates in the time-frequency (T-F) domain. Our framework introduces a DualStream Fusion Block (DSFB) that: 1) captures contextual information, 2) models interactions between contextualized enrollment and mixture representations across spatial and channel dimensions, and 3) employs these enriched representations to guide the extraction process. Comprehensive experiments show that DCF-Net achieves state-of-the-art (SOTA) performance with a 21.6 dB improvement in scale-invariant signal-to-distortion ratio (SI-SDR) on benchmark datasets while demonstrating robustness in noisy and reverberant conditions. Notably, our model significantly reduces the wrong extraction rate to just 0.4% when testing on target confusion problem (TCP), underscoring its practical applicability.

Markov decision process (MDP) is an important model of sequential decision making problems. Existing theoretical analysis focus primarily on finite state spaces. For continuous state spaces, a recent interesting work (Shah and Xie, 2018) proposes a nearest neighbor Q learning approach. Under the streaming setting, in shich samples are received in a sequential manner, the sample complexity of this method is$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+3}(1-\gamma)^{d+7}}}}\right)$for$\epsilon $-accurate Q function estimation of infinite horizon discounted MDP with discount factor$\gamma $, in which$|\mathcal {A}|$is the size of the action space. However, the sample complexity is not optimal, and the method is suitable only for bounded state spaces. In this paper, we propose two new nearest neighbor Q learning methods, one for the offline setting and the other for the streaming setting. We show that the sample complexities of these two methods are$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+2}(1-\gamma)^{d+2}}}}\right)$and$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+2}(1-\gamma)^{d+3}}}}\right)$for offline and streaming settings respectively, which significantly improve over existing results and have minimax optimal dependence over$\epsilon $. We achieve such improvement by utilizing samples more efficiently. In particular, the method by Shah and Xie, 2018, clears up all samples after each iteration, thus these samples are somewhat wasted. On the other hand, our offline method does not remove any samples, and our streaming method only removes samples with time earlier than$\beta t$at time t, thus our methods significantly reduce the loss of information. Apart from the sample complexity, our methods also have additional advantages of better computational complexity, as well as suitability to unbounded state spaces. Finally, we extend our work to the case where both state and action spaces are continuous.

In a real federated learning (FL) system, communication overhead for passing model parameters between the clients and the parameter server (PS) is often a bottleneck. Hierarchical federated learning (HFL) that poses multiple edge servers (ESs) between clients and the PS can partially alleviate communication pressure but still needs the aggregation of model parameters from multiple ESs at the PS. To further reduce communication overhead, we remove the central PS, so that each iteration only completes model training by transmitting the global model between two adjacent ES. We call this serial learning method Sequential FL (SFL). For the first time, we introduced SFL into HFL and proposed a novel algorithm adapted to this combined framework, called Fed-CHS. Convergence results are derived for strongly convex and non-convex loss functions under various data heterogeneity setups, which show comparable convergence performance with the algorithms for HFL or SFL solely. Experimental results provide evidence of the superiority of our proposed Fed-CHS on both communication overhead saving and test accuracy over baseline methods.

This paper addresses federated learning (FL) in the context of malicious Byzantine attacks and data heterogeneity. We introduce a novel Robust Average Gradient Algorithm (RAGA), which uses the geometric median for aggregation and allows flexible round number for local updates. Unlike most existing resilient approaches, which base their convergence analysis on strongly-convex loss functions or homogeneously distributed datasets, this work conducts convergence analysis for both strongly-convex and non-convex loss functions over heterogeneous datasets. The theoretical analysis indicates that as long as the fraction of the data from malicious users is less than half, RAGA can achieve convergence at a rate of$\mathcal {O}({1}/{T^{2/3- \delta }})$for non-convex loss functions, where$T$is the iteration number and$\delta \in (0, 2/3)$. For strongly-convex loss functions, the convergence rate is linear. Furthermore, the stationary point or global optimal solution is shown to be attainable as data heterogeneity diminishes. Experimental results validate the robustness of RAGA against Byzantine attacks and demonstrate its superior convergence performance compared to baselines under varying intensities of Byzantine attacks on heterogeneous datasets.

This paper studies robust nonparametric regression, in which an adversarial attacker can modify the values of up to q samples from a training dataset of size N. Our initial solution is an M-estimator based on Huber loss minimization. Compared with simple kernel regression, i.e. the Nadaraya-Watson estimator, this method can significantly weaken the impact of malicious samples on the regression performance. We provide the convergence rate as well as the corresponding minimax lower bound. The result shows that, with proper bandwidth selection, supremum error is minimax optimal. The L2 error is optimal with relatively small q, but is suboptimal with larger q. The reason is that this estimator is vulnerable if there are many attacked samples concentrating in a small region. To address this issue, we propose a correction method by projecting the initial estimate to the space of Lipschitz functions. The final estimate is nearly minimax optimal for arbitrary q, up to a logarithmic factor.

Federated learning systems are susceptible to adversarial attacks. To combat this, we introduce a novel aggregator based on Huber loss minimization, and provide a comprehensive theoretical analysis. Under independent and identically distributed (i.i.d) assumption, our approach has several advantages compared to existing methods. Firstly, it has optimal dependence on epsilon, which stands for the ratio of attacked clients. Secondly, our approach does not need precise knowledge of epsilon. Thirdly, it allows different clients to have unequal data sizes. We then broaden our analysis to include non-i.i.d data, such that clients have slightly different distributions.

Privacy protection of users' entire contribution of samples is important in distributed systems. The most effective approach is the two-stage scheme, which finds a small interval first and then gets a refined estimate by clipping samples into the interval. However, the clipping operation induces bias, which is serious if the sample distribution is heavy-tailed. Besides, users with large local sample sizes can make the sensitivity much larger, thus the method is not suitable for imbalanced users. Motivated by these challenges, we propose a Huber loss minimization approach to mean estimation under user-level differential privacy. The connecting points of Huber loss can be adaptively adjusted to deal with imbalanced users. Moreover, it avoids the clipping operation, thus significantly reducing the bias compared with the two-stage approach. We provide a theoretical analysis of our approach, which gives the noise strength needed for privacy protection, as well as the bound of mean squared error. The result shows that the new method is much less sensitive to the imbalance of user-wise sample sizes and the tail of sample distributions. Finally, we perform numerical experiments to validate our theoretical analysis.

In order to improve performance and avoid overheating on mobile devices, precise thermal control with low overhead is crucial. To achieve this, we propose incorporating a performance monitoring counter (PMC)-based power model into thermal control, which enables a more accurate evaluation of the CPU’s power consumption. We demonstrate the plausibility of this approach using polynomial regression based on Moore’s Law. Additionally, we introduce a lightweight PMC sampling method that can collect multiple PMCs at once in the kernel space, reducing sampling overhead. By replacing the utilization-based model in the original the intelligent power allocation (IPA) with a PMC-based power model, we realize the PMC-based IPA governor can be ported to real mobile devices. After updating the thermal control governor in the Linux kernel, we perform tests on our PMC-based IPA using a mobile phone device. We compare it with Stepwise and IPA, which are commonly used in current mobile phone systems. We choose the CPU-intensive workbench, I/O-intensive workbench, and CPU and I/O-intensive hybrid workbench as workloads. The results show that PMC-based IPA effectively reduces energy consumption while improving performance. In particular, during the CPU and I/O-intensive hybrid experiment, where CPU-intensive and I/O-intensive tasks are executed alternately, PMC-based IPA reduces the running time by 10.0% and energy consumption by 16.6% compared to the original IPA. In order to verify the benefits of PMC-based IPA, mobile phone testing software AI Bench and Antutu are utilized. The results show that our scheme is able to control temperature more precisely than IPA and achieves a better score while consuming less energy, particularly during AI computing. These experiment results suggest that PMC-based IPA is valuable for practical use.

Entropy rate estimation has a broad range of applications such as bioinformatics, feature clustering etc. Although there are many existing work on the estimation of entropy rate for Markov chains with discrete distributions, the understanding for the entropy rate estimation of Markov chains with continuous distributions is limited. In this paper, efficient methods for estimating the entropy rate for Markov chains with continuous distributions are proposed. Moreover, we derive bounds on the convergence rate of the proposed entropy rate estimators.

We analyze the convergence rates of$k$nearest neighbor density estimation method, under$\ell _{\alpha} $norm with$\alpha \in [1,\infty]$. Our analysis includes two different cases depending on whether the support set is bounded or not. In the first case, the probability density function has a bounded support. We show that if the support set is known, then the kNN density estimator is minimax optimal under$\ell _{\alpha} $with both$\alpha \in \big[1,\infty\big)$and$\alpha =\infty $. If the support is unknown, the kNN density estimator is still minimax optimal under$\ell _{1}$, but is suboptimal under$\ell _{\alpha} $for$\alpha >1$, and not consistent under$\ell _\infty $. In the second case, the support is unbounded and the probability density function is smooth everywhere. Moreover, the Hessian is assumed to decay with the density values. For this case, our result shows that the$\ell _\infty $error of kNN density estimation is nearly minimax optimal. The$\ell _{\alpha} $error for the original kNN density estimator is not consistent. To address this issue, we design a new adaptive kNN estimator, which can select different$k$for different samples. Using this adaptive estimator, the$\ell _{\alpha} $bound is minimax optimal. For comparison, we show that the popular kernel density estimator is not minimax optimal for this case.

In this paper, we propose an adaptive kNN method for classification, in which different k are selected for different test samples. Our selection rule is easy to implement since it is completely adaptive and does not require any knowledge of the underlying distribution. The convergence rate of the risk of this classifier to the Bayes risk is shown to be minimax optimal for various settings. Moreover, under some special assumptions, the convergence rate is especially fast and does not decay with the increase of dimensionality.

We analyze the$\ell_{1}$and$\ell_{\infty}$convergence rates of$k$nearest neighbor density estimation method. Our analysis includes two different cases depending on whether the support set is bounded or not. In the first case, the probability density function has a bounded support and is bounded away from zero. We show that kNN density estimation is minimax optimal under both$\ell_{1}$and$\ell_{\infty}$criteria, if the support set is known. If the support set is unknown, then the convergence rate of$\ell_{1}$error is not affected, while$\ell_{\infty}$error does not converge. In the second case, the probability density function can approach zero and is smooth everywhere. Moreover, the Hessian is assumed to decay with the density values. For this case, our result shows that the$\ell_{\infty}$error of kNN density estimation is nearly minimax optimal.

k Nearest Neighbor (kNN) method is a simple and popular statistical method for classification and regression. For both classification and regression problems, existing works have shown that, if the distribution of the feature vector has bounded support and the probability density function is bounded away from zero in its support, the convergence rate of the standard kNN method, in which k is the same for all test samples, is minimax optimal. On the contrary, if the distribution has unbounded support, we show that there is a gap between the convergence rate achieved by the standard kNN method and the minimax bound. To close this gap, we propose an adaptive kNN method, in which different k is selected for different samples. Our selection rule does not require precise knowledge of the underlying distribution of features. The proposed adaptive method significantly outperforms the standard one. We characterize the convergence rate of the proposed adaptive method, and show that it matches the minimax lower bound.

Estimating Kullback-Leibler divergence from identically and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the k nearest neighbor distances between these samples. In this paper, we analyze the convergence rates of the bias and variance of this estimator.

KSG mutual information estimator, which is based on the distances of each sample to its k-th nearest neighbor, is widely used to estimate mutual information between two continuous random variables. Existing work has analyzed the convergence rate of this estimator for random variables whose densities are bounded away from zero in its support. In practice, however, KSG estimator also performs well for a much broader class of distributions, including not only those with bounded support and densities bounded away from zero, but also those with bounded support but densities approaching zero, and those with unbounded support. In this paper, we analyze the convergence rate of the error of KSG estimator for smooth distributions, whose support of density can be both bounded and unbounded. As KSG mutual information estimator can be viewed as an adaptive recombination of KL entropy estimators, in our analysis, we also provide convergence analysis of KL entropy estimator for a broad class of distributions.

Estimating Kullback-Leibler divergence from identical and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the k nearest neighbor distances between these samples. In this paper, we analyze the convergence rates of the bias and variance of this estimator. Furthermore, we derive a lower bound of the minimax mean square error and show that kNN method is asymptotically rate optimal.

In this paper, we investigate the convergence rate of k Nearest Neighbor (kNN) regression methods. We first derive the minimax bound for nonparametric regression under some general tail and smoothness assumptions. This bound shows that, when the distribution of features has heavy tails, there is a gap between this minimax bound and that can be achieved by the standard kNN methods where the same k is used for all query points. To close this gap, we propose an adaptive kNN method that selects smaller k when the query sample falls in the region with lower density, and vice versa. As the density function is unknown, we design a simple method to determine the value of k from training samples. Using this selection rule, we obtain a desirable tradeoff between bias and variance. Furthermore, we show that the convergence rate of our new regression method attains the minimax lower bound and hence is rate optimal when the underlying regression function is bounded. We further extend the analysis to the case with unbounded underlying regression functions and show that the proposed method significantly outperforms the standard kNN regression method in this case as well.

We propose a nonparametric method to directly estimate the difference of Shannon entropy between two continuous random variables using finite number of samples. This method is based on a k-nearest-neighbor approach. We provide a finite sample analysis of the bias and variance of our proposed estimator. Numerical experiments show that our method performs better than estimating the entropy of two random variables separately. As an application of our estimator, we show that it can be used to significantly improve the performance of mutual information estimation using k-nearest-neighbor method for strongly dependent variables.