Author name cluster

Xiuzhen Cheng

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.

5 papers

1 author row

TCS Journal 2025 Journal Article

Robust matroid bandit optimization: Near-optimal rates under adversarial contamination

Youming Tao
Xiuzhen Cheng
Falko Dressler
Zhipeng Cai
Dongxiao Yu

We study the matroid bandit optimization problem, a fundamental and broadly applicable framework for combinatorial multi-armed bandits where the action space is constrained by a matroid. In particular, we address the challenge of designing algorithms that remain effective under adversarial contamination of feedback rewards, which may severely degrade performance or even mislead existing methods. Our main contribution is an efficient and robust algorithm named ROMM, which builds upon the principle of optimistic matroid maximization and leverages robust statistical estimators to assess base arm quality in polynomial time. Under the ϵ-contamination model, we establish lower bounds and prove that ROMM achieves near-optimal regret guarantees up to polylogarithmic factors. Our analysis further reveals a sharp phase transition between the low and high contamination regimes. Notably, ROMM can tolerate up to a universal constant fraction of corrupted feedback, which is optimal under mild conditions. Finally, we validate our theoretical findings with numerical experiments that demonstrate the effectiveness of the proposed method.

Details DOI

NeurIPS Conference 2025 Conference Paper

Second-Order Convergence in Private Stochastic Non-Convex Optimization

Youming Tao
Zuyuan Zhang
Dongxiao Yu
Xiuzhen Cheng
Falko Dressler
Di Wang

We investigate the problem of finding second-order stationary points (SOSP) in differentially private (DP) stochastic non-convex optimization. Existing methods suffer from two key limitations: \textbf{(i)} inaccurate convergence error rate due to overlooking gradient variance in the saddle point escape analysis, and \textbf{(ii)} dependence on auxiliary private model selection procedures for identifying DP-SOSP, which can significantly impair utility, particularly in distributed settings. To address these issues, we propose a generic perturbed stochastic gradient descent (PSGD) framework built upon Gaussian noise injection and general gradient oracles. A core innovation of our framework is using model drift distance to determine whether PSGD escapes saddle points, ensuring convergence to approximate local minima without relying on second-order information or additional DP-SOSP identification. By leveraging the adaptive DP-SPIDER estimator as a specific gradient oracle, we develop a new DP algorithm that rectifies the convergence error rates reported in prior work. We further extend this algorithm to distributed learning with heterogeneous data, providing the first formal guarantees for finding DP-SOSP in such settings. Our analysis also highlights the detrimental impacts of private selection procedures in distributed learning under high-dimensional models, underscoring the practical benefits of our design. Numerical experiments on real-world datasets validate the efficacy of our approach.

PDF Details

AAAI Conference 2022 Conference Paper

ASM2TV: An Adaptive Semi-supervised Multi-Task Multi-View Learning Framework for Human Activity Recognition

Zekai Chen
Xiao Zhang
Xiuzhen Cheng

Many real-world scenarios, such as human activity recognition (HAR) in IoT, can be formalized as a multi-task multiview learning problem. Each specific task consists of multiple shared feature views collected from multiple sources, either homogeneous or heterogeneous. Common among recent approaches is to employ a typical hard/soft sharing strategy at the initial phase separately for each view across tasks to uncover common knowledge, underlying the assumption that all views are conditionally independent. On the one hand, multiple views across tasks possibly relate to each other under practical situations. On the other hand, supervised methods might be insufficient when labeled data is scarce. To tackle these challenges, we introduce a novel framework ASM2TV for semi-supervised multi-task multiview learning. We present a new perspective named gating control policy, a learnable task-view-interacted sharing policy that adaptively selects the most desirable candidate shared block for any view across any task, which uncovers more fine-grained task-view-interacted relatedness and improves inference efficiency. Significantly, our proposed gathering consistency adaption procedure takes full advantage of large amounts of unlabeled fragmented time-series, making it a general framework that accommodates a wide range of applications. Experiments on two diverse real-world HAR benchmark datasets collected from various subjects and sources demonstrate our framework’s superiority over other state-of-the-arts. The detailed codes are available at https: //github. com/zachstarkk/ASM2TV.

PDF Details

IJCAI Conference 2022 Conference Paper

Private Stochastic Convex Optimization and Sparse Learning with Heavy-tailed Data Revisited

Youming Tao
Yulian Wu
Xiuzhen Cheng
Di Wang

In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) with heavy-tailed data, where the gradient of the loss function has bounded moments. Instead of the case where the loss function is Lipschitz or each coordinate of the gradient has bounded second moment studied previously, we consider a relaxed scenario where each coordinate of the gradient only has bounded (1+v)-th moment with some v∈(0, 1]. Firstly, we start from the one dimensional private mean estimation for heavy-tailed distributions. We propose a novel robust and private mean estimator which is optimal. Based on its idea, we then extend to the general d-dimensional space and study DP-SCO with general convex and strongly convex loss functions. We also provide lower bounds for these two classes of loss under our setting and show that our upper bounds are optimal up to a factor of O(Poly(d)). To address the high dimensionality issue, we also study DP-SCO with heavy-tailed gradient under some sparsity constraint (DP sparse learning). We propose a new method and show it is also optimal up to a factor of O(s*), where s* is the underlying sparsity of the constraint.

PDF Details DOI

TCS Journal 2012 Journal Article

Verifiable multi-secret sharing based on LFSR sequences

Chunqiang Hu
Xiaofeng Liao
Xiuzhen Cheng

In verifiable multi-secret sharing schemes (VMSSs), many secrets can be shared but only one share is kept by each user and this share is verifiable by others. In this paper, we propose two secure, efficient, and verifiable ( t, n ) multi-secret sharing schemes, namely Scheme-I and Scheme-II. Scheme-I is based on the Lagrange interpolating polynomial and the LFSR-based public key cryptosystem. The Lagrange interpolating polynomial is used to split and reconstruct the secrets and the LFSR-based public key cryptosystem is employed to verify the validity of the data. Scheme-II is designed according to the LFSR sequence and the LFSR-based public key cryptosystem. We compare our schemes with the state-of-the-art in terms of attack resistance, computation complexity, and so on, and conclude that our schemes have better performance and incur less computation overhead. Our schemes can effectively detect a variety of forgery or cheating actions to ensure that the recovery of the secrets is secure and creditable, and the length of the private key is only one third of that of others for the same security level.

Details DOI