Author name cluster

Youming Tao

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

Adaptive pruning-based Newton's method for distributed learning

Shuzhen Chen
Yuan Yuan
Youming Tao
Tianzhu Wang
Zhipeng Cai
Dongxiao Yu

Newton's method leverages curvature information to boost performance, and thus outperforms first-order methods for distributed learning problems. However, Newton's method is not practical in large-scale and heterogeneous learning environments, due to obstacles such as high computation and communication costs of the Hessian matrix, sub-model diversity, staleness of training, and data heterogeneity. To overcome these obstacles, this paper presents a novel and efficient algorithm named Distributed Adaptive Newton Learning (DANL), which solves the drawbacks of Newton's method by using a simple Hessian initialization and adaptive allocation of training regions. The algorithm exhibits remarkable convergence properties, which are rigorously examined under standard assumptions in stochastic optimization. The theoretical analysis proves that DANL attains a linear convergence rate while efficiently adapting to available resources and keeping high efficiency. Furthermore, DANL shows notable independence from the condition number of the problem and removes the necessity for complex parameter tuning. Experiments demonstrate that DANL achieves linear convergence with efficient communication and strong performance across different datasets.

Details DOI

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

NeurIPS Conference 2023 Conference Paper

On Private and Robust Bandits

Yulian Wu
Xingyu Zhou
Youming Tao
Di Wang

We study private and robust multi-armed bandits (MABs), where the agent receives Huber's contaminated heavy-tailed rewards and meanwhile needs to ensure differential privacy. We consider both the finite $k$-th raw moment and the finite $k$-th central moment settings for heavy-tailed rewards distributions with $k\ge 2$. We first present its minimax lower bound, characterizing the information-theoretic limit of regret with respect to privacy budget, contamination level, and heavy-tailedness. Then, we propose a meta-algorithm that builds on a private and robust mean estimation sub-routine \texttt{PRM} that essentially relies on reward truncation and the Laplace mechanism. For the above two different heavy-tailed settings, we give corresponding schemes of \texttt{PRM}, which enable us to achieve nearly-optimal regrets. Moreover, our two proposed truncation-based or histogram-based \texttt{PRM} schemes achieve the optimal trade-off between estimation accuracy, privacy and robustness. Finally, we support our theoretical results and show the effectiveness of our algorithms with experimental studies.

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