Author name cluster

Xiaoyun Li

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers

2 author rows

YNIMG Journal 2025 Journal Article

Pain in focus: How persistent pain disrupts the attentional bias towards pain-related information

Jia Li
Xiaohan Lyu
Xiaoyun Li
Xilin Yang
Lingling Weng
Yi Wang
Weiwei Peng

Pain modulates attentional biases, contributing to chronic pain development and maintenance through enhanced focus on pain-related stimuli. This study employed drift-diffusion modeling (DDM) and multivariate EEG to investigate how sustained pain affects attention allocation. Using a crossover design, 58 healthy volunteers underwent two sessions (capsaicin-induced pain vs. control cream) while performing word- and picture-based dot-probe tasks. Probes appeared in locations either congruent or incongruent with pain-related stimuli, or after neutral stimulus pairs. Behavioral and neural responses to congruency and incongruency effects were compared between pain states. DDM revealed increased incongruency effects during pain, characterized by slower drift rates and narrower decision thresholds, suggesting impaired evidence accumulation. EEG analyses revealed two distinct pain-state modulations: (1) amplified P3 amplitudes (300-600 ms) during incongruent trials, and (2) multivariate decoding of δ/θ oscillations (1-7 Hz, 116-364 ms post-stimulus) that uniquely differentiated incongruent from neutral conditions specifically under pain. These behavioral and neural signatures of attentional disruption manifested selectively during verbal tasks, with no parallel effects observed in pictorial processing. Our findings demonstrate how pain disrupts cognitive control: impaired expectancy processing (early δ/θ oscillations), compromised decision formation (altered DDM parameters), and deficient response inhibition (P3 modulation). These results highlight verbal information processing as a key vulnerability in pain-related attentional bias, suggesting targeted interventions for cognitive control components could mitigate chronic pain consequences.

Details DOI

ICLR Conference 2024 Conference Paper

Stochastic Controlled Averaging for Federated Learning with Communication Compression

Xinmeng Huang
Ping Li 0001
Xiaoyun Li

Communication compression has been an important topic in Federated Learning (FL) for alleviating the communication overhead. However, communication compression brings forth new challenges in FL due to the interplay of compression-incurred information distortion and inherent characteristics of FL such as partial participation and data heterogeneity. Despite the recent development, the existing approaches either cannot accommodate arbitrary data heterogeneity or partial participation, or require stringent conditions on compression. In this paper, we revisit the seminal stochastic controlled averaging method by proposing an equivalent but more efficient/simplified formulation with halved uplink communication costs, building upon which we propose two compressed FL algorithms, SCALLION and SCAFCOM, to support unbiased and biased compression, respectively. Both the proposed methods outperform the existing compressed FL methods in terms of communication and computation complexities. Moreover,SCALLION and SCAFCOM attain fast convergence rates under arbitrary data heterogeneity without any additional assumptions on compression errors. Experiments show that \scallion and \scafcom outperform recent compressed FL methods under the same communication budget.

Details

ICML Conference 2023 Conference Paper

Analysis of Error Feedback in Federated Non-Convex Optimization with Biased Compression: Fast Convergence and Partial Participation

Xiaoyun Li
Ping Li 0001

In practical federated learning (FL) systems, the communication cost between the clients and the central server can often be a bottleneck. In this paper, we focus on biased gradient compression in non-convex FL problems. In the classical distributed learning, the method of error feedback (EF) is a common technique to remedy the downsides of biased gradient compression, but the performance of EF in FL still lacks systematic investigation. In this work, we study a compressed FL scheme with error feedback, named Fed-EF, with two variants depending on the global model optimizer. While directly applying biased compression in FL leads to poor convergence, we show that Fed-EF is able to match the convergence rate of the full-precision FL counterpart with a linear speedup w. r. t. the number of clients. Experiments verify that Fed-EF achieves the same performance as the full-precision FL approach, at the substantially reduced communication cost. Moreover, we develop a new analysis of the EF under partial participation (PP), an important scenario in FL. Under PP, the convergence rate of Fed-EF exhibits an extra slow-down factor due to a so-called “stale error compensation” effect, which is also justified in our experiments. Our results provide insights on a theoretical limitation of EF, and possible directions for improvements.

Details

UAI Conference 2023 Conference Paper

Fed-LAMB: Layer-wise and Dimension-wise Locally Adaptive Federated Learning

Belhal Karimi
Ping Li 0001
Xiaoyun Li

In the emerging paradigm of Federated Learning (FL), large amount of clients such as mobile devices are used to train possibly high-dimensional models on their respective data. Combining (dimension-wise) adaptive gradient methods (e. g. , Adam, AMSGrad) with FL has been an active direction, which is shown to outperform traditional SGD based FL in many cases. In this paper, we focus on the problem of training federated deep neural networks, and propose a novel FL framework which further introduces layer-wise adaptivity to the local model updates to accelerate the convergence of adaptive FL methods. Our framework includes two variants based on two recent locally adaptive federated learning algorithms. Theoretically, we provide a convergence analysis of our layer-wise FL methods, coined Fed-LAMB and Mime-LAMB, which match the convergence rate of state-of-the-art results in adaptive FL and exhibits linear speedup in terms of the number of workers. Experimental results on various datasets and models, under both IID and non-IID local data settings, show that both Fed-LAMB and Mime-LAMB achieve faster convergence speed and better generalization performance, compared to various recent adaptive FL methods.

Details

ICLR Conference 2023 Conference Paper

Improved Convergence of Differential Private SGD with Gradient Clipping

Huang Fang
Xiaoyun Li
Chenglin Fan
Ping Li 0001

Differential private stochastic gradient descent (DP-SGD) with gradient clipping (DP-SGD-GC) is an effective optimization algorithm that can train machine learning models with a privacy guarantee. Despite the popularity of DP-SGD-GC, its convergence in unbounded domain without the Lipschitz continuous assumption is less-understood; existing analysis of DP-SGD-GC either impose additional assumptions or end up with an utility bound that involves an non-vanishing bias term. In this work, for smooth and unconstrained problems, we improve the current analysis and show that DP-SGD-GC can achieve a vanishing utility bound without any bias term. Furthermore, when the noise generated from subsampled gradients is light-tailed, we prove that DP-SGD-GC can achieve nearly the same utility bound as DP-SGD applies to the Lipschitz continuous objectives. As a by-product, we propose a new clipping technique, called value clipping, to mitigate the computational overhead caused by the classic gradient clipping. Experiments on standard benchmark datasets are conducted to support our analysis.

Details

NeurIPS Conference 2023 Conference Paper

k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy

Chenglin Fan
Ping Li
Xiaoyun Li

In clustering algorithms, the choice of initial centers is crucial for the quality of the learned clusters. We propose a new initialization scheme for the $k$-median problem in the general metric space (e. g. , discrete space induced by graphs), based on the construction of metric embedding tree structure of the data. We propose a novel and efficient search algorithm, for good initial centers that can be used subsequently for the local search algorithm. The so-called HST initialization method can produce initial centers achieving lower error than those from another popular method $k$-median++, also with higher efficiency when $k$ is not too small. Our HST initialization can also be easily extended to the setting of differential privacy (DP) to generate private initial centers. We show that the error of applying DP local search followed by our private HST initialization improves previous results on the approximation error, and approaches the lower bound within a small factor. Experiments demonstrate the effectiveness of our proposed methods.

PDF Details

ICML Conference 2023 Conference Paper

LSDS++: Dual Sampling for Accelerated k-means++

Chenglin Fan
Ping Li 0001
Xiaoyun Li

k-means clustering is an important problem in machine learning and statistics. The k-means++ initialization algorithm has driven new acceleration strategies and theoretical analysis for solving the k-means clustering problem. The state-of-the-art variant, called LocalSearch++, adds extra local search steps upon k-means++ to achieve constant approximation error in expectation. In this paper, we propose a new variant named LSDS++, which improves the sampling efficiency of LocalSearch++ via a strategy called dual sampling. By defining a new capture graph based on the concept of coreset, we show that the proposed LSDS++ is able to achieve the same expected constant error with reduced complexity. Experiments are conducted to justify the benefit of LSDS++ in practice.

Details

NeurIPS Conference 2023 Conference Paper

Smooth Flipping Probability for Differential Private Sign Random Projection Methods

Ping Li
Xiaoyun Li

We develop a series of differential privacy (DP) algorithms from a family of random projection (RP) and sign random projection (SignRP) methods. We first show how to improve the previous DP-RP approach using the ``optimal Gaussian mechanism''. Then, we propose a series of DP-SignRP algorithms that leverage the robustness of the ``sign flipping probability'' of random projections. That is, given $x = \sum_{i=1}^p u_i w_{i}$ where $u$ is a $p$-dimensional data vector and $w$ is a symmetric random vector, $sign(x)$ only has a fairly small probability to be flipped if there is a small modification on data $u$, depending on the specific distribution of $w$. This robustness leads to our novel design of ``smooth flipping probability'' for SignRP-type algorithms with better utility than using the standard randomized response mechanism. Retrieval and classification experiments demonstrate that, among the presented DP-RP algorithms, \textbf{DP-SignOPORP} (where OPORP is an improvement over the celebrated count-sketch algorithms), performs the best in general. In the industrial practice, DP methods were not very popular for machine learning or search, largely because the performance typically would drop substantially if DP is applied. Since our proposed new DP algorithms have significantly improved the performance, it is anticipated that our work will motivate a wide adoption of DP in practice. Finally, we stress that, since our methods are applied to the original data (i. e. , feature vectors), the privacy of downstream tasks is naturally protected.

PDF Details

ICML Conference 2022 Conference Paper

C-MinHash: Improving Minwise Hashing with Circulant Permutation

Xiaoyun Li
Ping Li 0001

Minwise hashing (MinHash) is an important and practical algorithm for generating random hashes to approximate the Jaccard (resemblance) similarity in massive binary (0/1) data. The basic theory of MinHash requires applying hundreds or even thousands of independent random permutations to each data vector in the dataset, in order to obtain reliable results for (e. g. ,) building large-scale learning models or approximate near neighbor search. In this paper, we propose Circulant MinHash (C-MinHash) and provide the surprising theoretical results that using only two independent random permutations in a circulant manner leads to uniformly smaller Jaccard estimation variance than that of the classical MinHash with K independent permutations. Experiments are conducted to show the effectiveness of the proposed method. We also propose a more convenient C-MinHash variant which reduces two permutations to just one, with extensive numerical results to validate that it achieves essentially the same estimation accuracy as using two permutations.

Details

IJCAI Conference 2022 Conference Paper

Learning Cluster Causal Diagrams: An Information-Theoretic Approach

Xueyan Niu
Xiaoyun Li
Ping Li

Many real-world phenomena arise from causal relationships among a set of variables. As a powerful tool, Bayesian Network (BN) has been successful in describing high-dimensional distributions. However, the faithfulness condition, enforced in most BN learning algorithms, is violated in the settings where multiple variables synergistically affect the outcome (i. e. , with polyadic dependencies). Building upon recent development in cluster causal diagrams (C-DAGs), we initiate the formal study of learning C-DAGs from observational data to relax the faithfulness condition. We propose a new scoring function, the Clustering Information Criterion (CIC), based on information-theoretic measures that represent various complex interactions among variables. The CIC score also contains a penalization of the model complexity under the minimum description length principle. We further provide a searching strategy to learn structures of high scores. Experiments on both synthetic and real data support the effectiveness of the proposed method.

PDF Details DOI

ICLR Conference 2022 Conference Paper

On Distributed Adaptive Optimization with Gradient Compression

Xiaoyun Li
Belhal Karimi
Ping Li 0001

We study COMP-AMS, a distributed optimization framework based on gradient averaging and adaptive AMSGrad algorithm. Gradient compression with error feedback is applied to reduce the communication cost in the gradient transmission process. Our convergence analysis of COMP-AMS shows that such compressed gradient averaging strategy yields same convergence rate as standard AMSGrad, and also exhibits the linear speedup effect w.r.t. the number of local workers. Compared with recently proposed protocols on distributed adaptive methods, COMP-AMS is simple and convenient. Numerical experiments are conducted to justify the theoretical findings, and demonstrate that the proposed method can achieve same test accuracy as the full-gradient AMSGrad with substantial communication savings. With its simplicity and efficiency, COMP-AMS can serve as a useful distributed training framework for adaptive methods.

Details

YNIMG Journal 2022 Journal Article

Ongoing first-hand pain facilitates somatosensory resonance but inhibits affective sharing in empathy for pain

Xiaoyun Li
Wutao Lou
Wenyun Zhang
Raymond Kai-yu Tong
Li Hu
Weiwei Peng

Alterations of empathy for others' pain among patients with chronic pain remained inconsistent. Here, applying a capsaicin-based ongoing pain model on healthy participants, this study investigated how ongoing first-hand pain influences empathic reactions to vicarious pain stimuli. Healthy participants were randomly treated with topical capsaicin cream (capsaicin group) or hand cream (control group) on the left forearm. Video clips showing limbs in painful and non-painful situations were used to induce empathic responses. The capsaicin group showed greater empathic neural responses in the right primary somatosensory cortex (S1) than the control group but smaller responses in the left anterior insula (AI) accompanied with smaller empathic pain-intensity ratings. Notably, the intensity of ongoing pain negatively correlated with empathy-related neural responses in the left AI. Inter-subject phase synchronization analysis was used to assess stimulus-dependent dynamic functional connectivity within or between brain regions engaged in pain empathy. The capsaicin group showed greater empathy-related neural synchronization within S1 and between S1 and AI, but less synchronization within AI and between AI and MCC. Behaviorally, the differential inter-subject pain-intensity rating alignment between painful and non-painful videos was more positive for the capsaicin group than for the control group, and this effect was partially mediated by the inter-subject neural synchronization between S1 and AI. These results suggest that ongoing first-hand pain facilitates neural activation and synchronization within brain regions associated with empathy-related somatosensory resonance at the cost of inhibiting activation and synchronization within brain regions engaged in empathy-related affective sharing.

Details DOI

NeurIPS Conference 2022 Conference Paper

Private Graph All-Pairwise-Shortest-Path Distance Release with Improved Error Rate

Chenglin Fan
Ping Li
Xiaoyun Li

Releasing all pairwise shortest path (APSP) distances between vertices on general graphs under weight Differential Privacy (DP) is known as a challenging task. In previous work, to achieve DP with some fixed budget, with high probability the maximal absolute error among all published pairwise distances is roughly O(n) where n is the number of nodes. It was shown that this error could be reduced for some special graphs, which, however, is hard for general graphs. Therefore, whether the approximation error can be reduced to sublinear is posted as an interesting open problem. In this paper, we break the linear barrier on the distance approximation error of previous result, by proposing an algorithm that releases a constructed synthetic graph privately. Computing all pairwise distances on the constructed graph only introduces O(n^{1/2}) error in answering all pairwise shortest path distances for fixed privacy parameter. Our method is based on a novel graph diameter (link length) augmentation via constructing ``shortcuts'' for the paths. By adding a set of shortcut edges to the original graph, we show that any node pair has a shortest path with link length O(n^{1/2}). Then by adding noises with some positive mean to the edge weights, the new graph is differentially private and can be published to answer all pairwise shortest path distances with O(n^{1/2}) approximation error using standard APSP computation. Numerical examples are also provided. Additionally, we also consider the graph with small feedback vertex set number. A feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles, and the feedback vertex set number of a graph, k, is the size of a smallest feedback vertex set. We propose a DP algorithm with error rate O(k), which improves the error of general graphs provided k=o(n^{1/2}).

PDF Details

NeurIPS Conference 2022 Conference Paper

SignRFF: Sign Random Fourier Features

Xiaoyun Li
Ping Li

The industry practice has been moving to embedding based retrieval (EBR). For example, in many applications, the embedding vectors are trained by some form of two-tower models. During serving phase, candidates (embedding vectors) are retrieved according to the rankings of cosine similarities either exhaustively or by approximate near neighbor (ANN) search algorithms. For those applications, it is natural to apply ``sign random projections'' (SignRP) or variants, on the trained embedding vectors to facilitate efficient data storage and cosine distance computations. SignRP is also one of the standard indexing schemes for conducting approximate near neighbor search. In the literature, SignRP has been popular and, to an extent, becomes the default method for ``locality sensitive hashing'' (LSH). In this paper, we propose ``sign random Fourier features'' (SignRFF) as an alternative to SignRP. The original method of random Fourier features (RFF) is a standard technique for approximating the Gaussian kernel (as opposed to the linear cosine kernel), in the literature of large-scale machine learning. Basically, RFF applies a simple nonlinear transformation on the samples generated by random projections (RP). Thus, in the pipeline of EBR, it is straightforward to replace SignRP by SignRFF. This paper explains, in a principled manner, why it makes sense to do so. In this paper, a new analytical measure called \textbf{Ranking Efficiency (RE)} is developed, which in retrospect is closely related to the ``two-sample mean'' $t$-test statistic for binomial variables. RE provides a systematic and unified framework for comparing different LSH methods. We compare our proposed SignRP with SignRP, KLSH (kernel LSH), as well SQ-RFF (which is another 1-bit coding scheme for RFF). According to the RE expression, SignRFF consistently outperforms KLSH (for Gaussian kernel) and SQ-RFF. SignRFF also outperforms SignRP in the relatively high similarity region. The theoretical comparison results are consistent with our empirical findings. In addition, experiments are conducted to compare SignRFF with a wide range of data-dependent and deep learning based hashing methods and show the advantage of SignRFF with a sufficient number of hash bits.

PDF Details

AAAI Conference 2021 Conference Paper

Fast and Compact Bilinear Pooling by Shifted Random Maclaurin

Tan Yu
Xiaoyun Li
Ping Li

Bilinear pooling has achieved an excellent performance in many computer vision tasks. However, the high-dimension features from bilinear pooling can sometimes be inefficient and prone to over-fitting. Random Maclaurin (RM) is a widely used GPU-friendly approximation method to reduce the dimensionality of bilinear features. However, to achieve good performance, huge projection matrices are usually required in practice, making it extremely costly in computation and memory. In this paper, we propose a Shifted Random Maclaurin (SRM) strategy for fast and compact bilinear pooling. With merely negligible extra computational cost, the proposed SRM provides an estimator with a provably smaller variance than RM, which benefits accurate kernel approximation and thus the learning performance. Using a small projection matrix, the proposed SRM achieves a comparable estimation performance as RM based on a large projection matrix, and thus considerably boosts the efficiency. Furthermore, we upgrade the proposed SRM to SRM+ to further improve the efficiency and make the compact bilinear pooling compatible with fast matrix normalization. Fast and Compact Bilinear Network (FCBN) built upon the proposed SRM+ is devised, achieving an end-to-end training. Systematic experiments conducted on four public datasets demonstrate the effectiveness and efficiency of the proposed FCBN.

PDF Details

ICML Conference 2021 Conference Paper

Quantization Algorithms for Random Fourier Features

Xiaoyun Li
Ping Li 0001

The method of random projection (RP) is the standard technique for dimensionality reduction, approximate near neighbor search, compressed sensing, etc. , which provides a simple and effective scheme for approximating pairwise inner products and Euclidean distances in massive data. Closely related to RP, the method of random Fourier features (RFF) has also become popular for approximating the (nonlinear) Gaussian kernel. RFF applies a specific nonlinear transformation on the projected data from RP. In practice, using the Gaussian kernel often leads to better performance than the linear kernel (inner product). After random projections, quantization is an important step for efficient data storage, computation and transmission. Quantization for RP has been extensively studied in the literature. In this paper, we focus on developing quantization algorithms for RFF. The task is in a sense challenging due to the tuning parameter $\gamma$ in the Gaussian kernel. For example, the quantizer and the quantized data might be tied to each specific Gaussian kernel parameter $\gamma$. Our contribution begins with the analysis on the probability distributions of RFF, and an interesting discovery that the marginal distribution of RFF is free of the parameter $\gamma$. This significantly simplifies the design of the Lloyd-Max (LM) quantization scheme for RFF in that there would be only one LM quantizer (regardless of $\gamma$). Detailed theoretical analysis is provided on the kernel estimators and approximation error, and experiments confirm the effectiveness and efficiency of the proposed method.

Details

AAAI Conference 2021 Conference Paper

Rejection Sampling for Weighted Jaccard Similarity Revisited

Xiaoyun Li
Ping Li

Efficiently1 computing the weighted Jaccard similarity has become an active research topic in machine learning and theory. For sparse data, the standard technique is based on the consistent weighed sampling (CWS). For dense data, however, methods based on rejection sampling (RS) can be much more efficient. Nevertheless, existing RS methods are still slow for practical purposes. In this paper, we propose to improve RS by a strategy, which we call efficient rejection sampling (ERS), based on “early stopping + densification”. We analyze the statistical property of ERS and provide experimental results to compare ERS with RS and other algorithms for hashing weighted Jaccard. The results demonstrate that ERS significantly improves the existing methods for estimating the weighted Jaccard similarity in relatively dense data.

PDF Details

YNIMG Journal 2020 Journal Article

Deficits in ascending and descending pain modulation pathways in patients with postherpetic neuralgia

Hong Li
Xiaoyun Li
Yi Feng
Fei Gao
Yazhuo Kong
Li Hu

Postherpetic Neuralgia (PHN), develops after the resolution of the herpes zoster mucocutaneous eruption, is a debilitating chronic pain. However, there is a lack of knowledge regarding the underlying mechanisms associated with ascending and descending pain modulations in PHN patients. Here, we combined psychophysics with structural and functional magnetic resonance imaging (MRI) techniques to investigate the brain alternations in PHN patients. Psychophysical tests showed that compared with healthy controls, PHN patients had increased state and trait anxiety and depression. Structural MRI data indicated that PHN patients had significantly smaller gray matter volumes of the thalamus and amygdala than healthy controls, and the thalamus volume was negatively correlated with pain intensity (assessed using the Short-form of the McGill pain questionnaire) in PHN patients. When the thalamus and periaqueductal gray matter (PAG) were used as the seeds, resting-state functional MRI data revealed abnormal patterns of functional connectivity within ascending and descending pain pathways in PHN patients, e. g. , increased functional connectivity between the thalamus and somatosensory cortices and decreased functional connectivity between the PAG and frontal cortices. In addition, subjective ratings of both Present Pain Index (PPI) and Beck-Depression Inventory (BDI) were negatively correlated with the strength of functional connectivity between the PAG and primary somatosensory cortex (SI), and importantly, the effect of BDI on PPI was mediated by the PAG-SI functional connectivity. Overall, our results provided evidence suggesting deficits in ascending and descending pain modulation pathways, which were highly associated with the intensity of chronic pain and its emotional comorbidities in PHN patients. Therefore, our study deepened our understanding of the pathogenesis of PHN, which would be helpful in determining the optimized treatment for the patients.

Details DOI

AAAI Conference 2020 Conference Paper

IVFS: Simple and Efficient Feature Selection for High Dimensional Topology Preservation

Xiaoyun Li
Chenxi Wu
Ping Li

Feature selection is an important tool to deal with high dimensional data. In unsupervised case, many popular algorithms aim at maintaining the structure of the original data. In this paper, we propose a simple and effective feature selection algorithm to enhance sample similarity preservation through a new perspective, topology preservation, which is represented by persistent diagrams from the context of computational topology. This method is designed upon a uniﬁed feature selection framework called IVFS, which is inspired by random subset method. The scheme is ﬂexible and can handle cases where the problem is analytically intractable. The proposed algorithm is able to well preserve the pairwise distances, as well as topological patterns, of the full data. We demonstrate that our algorithm can provide satisfactory performance under a sharp sub-sampling rate, which supports ef- ﬁcient implementation of our proposed method to large scale datasets. Extensive experiments validate the effectiveness of the proposed feature selection scheme.

PDF Details

ECAI Conference 2020 Conference Paper

Randomized Kernel Multi-View Discriminant Analysis

Xiaoyun Li
Jie Gui
Ping Li 0001

In many artificial intelligence and computer vision systems, the same object can be observed at distinct viewpoints or by diverse sensors, which raises the challenges for recognizing objects from different, even heterogeneous views. Multi-view discriminant analysis (MvDA) is an effective multi-view subspace learning method, which finds a discriminant common subspace by jointly learning multiple view-specific linear projections for object recognition from multiple views, in a non-pairwise way. In this paper, we propose the kernel version of multi-view discriminant analysis, called kernel multi-view discriminant analysis (KMvDA). To overcome the well-known computational bottleneck of kernel methods, we also study the performance of using random Fourier features (RFF) to approximate Gaussian kernels in KMvDA, for large scale learning. Theoretical analysis on stability of this approximation is developed. We also conduct experiments on several popular multi-view datasets to illustrate the effectiveness of our proposed strategy.

Details

NeurIPS Conference 2019 Conference Paper

Generalization Error Analysis of Quantized Compressive Learning

Xiaoyun Li
Ping Li

Compressive learning is an effective method to deal with very high dimensional datasets by applying learning algorithms in a randomly projected lower dimensional space. In this paper, we consider the learning problem where the projected data is further compressed by scalar quantization, which is called quantized compressive learning. Generalization error bounds are derived for three models: nearest neighbor (NN) classifier, linear classifier and least squares regression. Besides studying finite sample setting, our asymptotic analysis shows that the inner product estimators have deep connection with NN and linear classification problem through the variance of their debiased counterparts. By analyzing the extra error term brought by quantization, our results provide useful implications to the choice of quantizers in applications involving different learning tasks. Empirical study is also conducted to validate our theoretical findings.

PDF Details

NeurIPS Conference 2019 Conference Paper

Random Projections with Asymmetric Quantization

Xiaoyun Li
Ping Li

The method of random projection has been a popular tool for data compression, similarity search, and machine learning. In many practical scenarios, applying quantization on randomly projected data could be very helpful to further reduce storage cost and facilitate more efficient retrievals, while only suffering from little loss in accuracy. In real-world applications, however, data collected from different sources may be quantized under different schemes, which calls for a need to study the asymmetric quantization problem. In this paper, we investigate the cosine similarity estimators derived in such setting under the Lloyd-Max (LM) quantization scheme. We thoroughly analyze the biases and variances of a series of estimators including the basic simple estimators, their normalized versions, and their debiased versions. Furthermore, by studying the monotonicity, we show that the expectation of proposed estimators increases with the true cosine similarity, on a broader family of stair-shaped quantizers. Experiments on nearest neighbor search justify the theory and illustrate the effectiveness of our proposed estimators.

PDF Details

NeurIPS Conference 2019 Conference Paper

Re-randomized Densification for One Permutation Hashing and Bin-wise Consistent Weighted Sampling

Ping Li
Xiaoyun Li
Cun-Hui Zhang

Jaccard similarity is widely used as a distance measure in many machine learning and search applications. Typically, hashing methods are essential for the use of Jaccard similarity to be practical in large-scale settings. For hashing binary (0/1) data, the idea of one permutation hashing (OPH) with densification significantly accelerates traditional minwise hashing algorithms while providing unbiased and accurate estimates. In this paper, we propose a strategy named “re-randomization” in the process of densification that could achieve the smallest variance among all densification schemes. The success of this idea naturally inspires us to generalize one permutation hashing to weighted (non-binary) data, which results in the socalled “bin-wise consistent weighted sampling (BCWS)” algorithm. We analyze the behavior of BCWS and compare it with a recent alternative. Extensive experiments on various datasets illustrates the effectiveness of our proposed methods.

PDF Details