Author name cluster

Ke Yi

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.

7 papers

1 author row

NeurIPS Conference 2025 Conference Paper

Differential Privacy on Fully Dynamic Streams

Yuan Qiu
Ke Yi

A fundamental problem in differential privacy is to release privatized answers to a class of linear queries with small error. This problem has been well studied in the static case. In this paper, we consider the fully dynamic setting where items may be inserted into or deleted from the dataset over time, and we need to continually release query answers at every time instance. We present efficient black-box constructions of such dynamic differentially private mechanisms from static ones with only a polylogarithmic degradation in the utility.

PDF Details

NeurIPS Conference 2025 Conference Paper

Sum Estimation under Personalized Local Differential Privacy

Dajun Sun
Wei Dong
Yuan Qiu
Ke Yi
Graham Cormode

People have diverse privacy requirements. This is best modeled using a personalized local differential privacy model where each user privatizes their data using a possibly different privacy parameter. While the model of personalized local differential privacy is a natural and important one, prior work has failed to give meaningful error bounds. In this paper, we study the foundational sum/mean estimation problem under this model. We present two novel protocols that achieve strong error guarantees. The first gives a guarantee based on the radius of the data, suiting inputs that are centered around zero. The second extends the guarantee to the diameter of the data, capturing the case when the points are situated arbitrarily. Experimental results on both synthetic and real data show that our protocols significantly outperform existing methods in terms of accuracy while providing a strong level of privacy.

PDF Details

NeurIPS Conference 2023 Conference Paper

Learning Topology-Agnostic EEG Representations with Geometry-Aware Modeling

Ke Yi
Yansen Wang
Kan Ren
Dongsheng Li

Large-scale pre-training has shown great potential to enhance models on downstream tasks in vision and language. Developing similar techniques for scalp electroencephalogram (EEG) is suitable since unlabelled data is plentiful. Meanwhile, various sampling channel selections and inherent structural and spatial information bring challenges and avenues to improve existing pre-training strategies further. In order to break boundaries between different EEG resources and facilitate cross-dataset EEG pre-training, we propose to map all kinds of channel selections to a unified topology. We further introduce MMM, a pre-training framework with Multi-dimensional position encoding, Multi-level channel hierarchy, and Multi-stage pre-training strategy built on the unified topology to obtain topology-agnostic representations. Experiments demonstrate that our approach yields impressive improvements over previous state-of-the-art techniques on emotional recognition benchmark datasets.

PDF Details

NeurIPS Conference 2022 Conference Paper

Differentially Private Covariance Revisited

Wei Dong
Yuting Liang
Ke Yi

In this paper, we present two new algorithms for covariance estimation under concentrated differential privacy (zCDP). The first algorithm achieves a Frobenius error of $\tilde{O}(d^{1/4}\sqrt{\mathrm{tr}}/\sqrt{n} + \sqrt{d}/n)$, where $\mathrm{tr}$ is the trace of the covariance matrix. By taking $\mathrm{tr}=1$, this also implies a worst-case error bound of $\tilde{O}(d^{1/4}/\sqrt{n})$, which improves the standard Gaussian mechanism's $\tilde{O}(d/n)$ for the regime $d>\widetilde{\Omega}(n^{2/3})$. Our second algorithm offers a tail-sensitive bound that could be much better on skewed data. The corresponding algorithms are also simple and efficient. Experimental results show that they offer significant improvements over prior work.

PDF Details

NeurIPS Conference 2021 Conference Paper

Instance-optimal Mean Estimation Under Differential Privacy

Ziyue Huang
Yuting Liang
Ke Yi

Mean estimation under differential privacy is a fundamental problem, but worst-case optimal mechanisms do not offer meaningful utility guarantees in practice when the global sensitivity is very large. Instead, various heuristics have been proposed to reduce the error on real-world data that do not resemble the worst-case instance. This paper takes a principled approach, yielding a mechanism that is instance-optimal in a strong sense. In addition to its theoretical optimality, the mechanism is also simple and practical, and adapts to a variety of data characteristics without the need of parameter tuning. It easily extends to the local and shuffle model as well.

PDF Details

NeurIPS Conference 2019 Conference Paper

Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation

zengfeng Huang
Ziyue Huang
Yilei Wang
Ke Yi

We consider the problem of estimating the mean of a set of vectors, which are stored in a distributed system. This is a fundamental task with applications in distributed SGD and many other distributed problems, where communication is a main bottleneck for scaling up computations. We propose a new sparsity-aware algorithm, which improves previous results both theoretically and empirically. The communication cost of our algorithm is characterized by Hoyer's measure of sparseness. Moreover, we prove that the communication cost of our algorithm is information-theoretic optimal up to a constant factor in all sparseness regime. We have also conducted experimental studies, which demonstrate the advantages of our method and confirm our theoretical findings.

PDF Details

TCS Journal 2008 Journal Article

A dynamic data structure for top-k queries on uncertain data

Jiang Chen
Ke Yi

In an uncertain data set S = ( S, p, f ) where S is the ground set consisting of n elements, p: S → [ 0, 1 ] a probability function, and f: S → R a score function, each element i ∈ S with score f ( i ) appears independently with probability p ( i ). The top- k query on S asks for the set of k elements that has the maximum probability of appearing to be the k elements with the highest scores in a random instance of S. Computing the top- k answer on a fixed S is known to be easy. In this paper, we consider the dynamic problem, that is, how to maintain the top- k query answer when S changes, including element insertions and deletions in the ground set S, changes in the probability function p and in the score function f. We present a fully dynamic data structure that handles an update in O ( k log n ) time, and answers a top- j query in O ( log n + j ) time for any j ≤ k. The structure has O ( n ) size and can be constructed in O ( n log k ) time. As a building block of our dynamic structure, we present an algorithm for the all-top- k problem, that is, computing the top- j answers for all j = 1, …, k, which may be of independent interest.

Details DOI