Publications (45)
Weakly Private Information Retrieval from Heterogeneously Trusted Servers
Wenyuan Zhao, Yu-Shin Huang, Ruida Zhou +1
We study the problem of weakly private information retrieval (PIR) when there is heterogeneity in servers' trustworthiness under the maximal leakage (Max-L) metric and mutual infor…
ADEPT: Hierarchical Bayes Approach to Personalized Federated Unsupervised Learning
Kaan Ozkara, Bruce Huang, Ruida Zhou +1
Statistical heterogeneity of clients' local data is an important characteristic in federated learning, motivating personalized algorithms tailored to the local data statistics. Tho…
Approximate Top- Arm Identification with Heterogeneous Reward Variances
Ruida Zhou, Chao Tian
We study the effect of reward variance heterogeneity in the approximate top- arm identification setting. In this setting, the reward for the -th arm follows a -sub-Ga…
REVES: REvision and VErification--Augmented Training for Test-Time Scaling
Yuanxin Liu, Ruida Zhou, Xinyan Zhao +6
Test-time scaling via sequential revision has emerged as a powerful paradigm for enhancing Large Language Model (LLM) reasoning. However, standard post-training methods primarily o…
On the optimal regret of collaborative personalized linear bandits
Bruce Huang, Ruida Zhou, Lin F. Yang +1
Stochastic linear bandits are a fundamental model for sequential decision making, where an agent selects a vector-valued action and receives a noisy reward with expected value give…
On the Information Leakage in Private Information Retrieval Systems
Tao Guo, Ruida Zhou, Chao Tian
We consider information leakage to the user in private information retrieval (PIR) systems. Information leakage can be measured in terms of individual message leakage or total leak…
On the Training Convergence of Transformers for In-Context Classification of Gaussian Mixtures
Wei Shen, Ruida Zhou, Jing Yang +1
Although transformers have demonstrated impressive capabilities for in-context learning (ICL) in practice, theoretical understanding of the underlying mechanism that allows transfo…
Regional Multi-Armed Bandits
Zhiyang Wang, Ruida Zhou, Cong Shen
We consider a variant of the classic multi-armed bandit problem where the expected reward of each arm is a function of an unknown parameter. The arms are divided into different gro…
Stochastic Chaining and Strengthened Information-Theoretic Generalization Bounds
Ruida Zhou, Chao Tian, Tie Liu
We propose a new approach to apply the chaining technique in conjunction with information-theoretic measures to bound the generalization error of machine learning algorithms. Diffe…
HiPER: Hierarchical Reinforcement Learning with Explicit Credit Assignment for Large Language Model Agents
Jiangweizhi Peng, Yuanxin Liu, Ruida Zhou +4
Training LLMs as interactive agents for multi-turn decision-making remains challenging, particularly in long-horizon tasks with sparse and delayed rewards, where agents must execut…
Online Learning with Diverse User Preferences
Chao Gan, Jing Yang, Ruida Zhou +1
In this paper, we investigate the impact of diverse user preference on learning under the stochastic multi-armed bandit (MAB) framework. We aim to show that when the user preferenc…
Policy Optimization for Constrained MDPs with Provable Fast Global Convergence
Tao Liu, Ruida Zhou, Dileep Kalathil +2
We address the problem of finding the optimal policy of a constrained Markov decision process (CMDP) using a gradient descent-based algorithm. Previous results have shown that a pr…
Two-Level Private Information Retrieval
Ruida Zhou, Chao Tian, Hua Sun +1
In the conventional robust -colluding private information retrieval (PIR) system, the user needs to retrieve one of the possible messages while keeping the identity of the reque…
Cost-Aware Learning and Optimization for Opportunistic Spectrum Access
Chao Gan, Ruida Zhou, Jing Yang +1
In this paper, we investigate cost-aware joint learning and optimization for multi-channel opportunistic spectrum access in a cognitive radio system. We investigate a discrete time…
Federated Linear Bandits with Finite Adversarial Actions
Li Fan, Ruida Zhou, Chao Tian +1
We study a federated linear bandits model, where clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets that…
On Top- Selection from -wise Partial Rankings via Borda Counting
Wenjing Chen, Ruida Zhou, Chao Tian +1
We analyze the performance of the Borda counting algorithm in a non-parametric model. The algorithm needs to utilize probabilistic rankings of the items within -sized subsets to…
Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation
Ruida Zhou, Tao Liu, Min Cheng +3
We study robust reinforcement learning (RL) with the goal of determining a well-performing policy that is robust against model mismatch between the training simulator and the testi…
DISPO: Enhancing Training Efficiency and Stability in Reinforcement Learning for Large Language Model Mathematical Reasoning
Batuhan K. Karaman, Aditya Rawal, Suhaila Shakiah +4
Reinforcement learning with verifiable rewards has emerged as a promising paradigm for enhancing the reasoning capabilities of large language models particularly in mathematics. Cu…
New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems
Tao Guo, Ruida Zhou, Chao Tian
In a private information retrieval (PIR) system, the user needs to retrieve one of the possible messages from a set of storage servers, but wishes to keep the identity of requested…
Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning
Ruida Zhou, Tao Liu, Dileep Kalathil +2
We study policy optimization for Markov decision processes (MDPs) with multiple reward value functions, which are to be jointly optimized according to given criteria such as propor…
An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains
Ruida Zhou, Chao Tian, Suhas Diggavi
We study transformers' in-context learning of variable-length Markov chains (VOMCs), focusing on the finite-sample accuracy as the number of in-context examples increases. Compared…
Individually Conditional Individual Mutual Information Bound on Generalization Error
Ruida Zhou, Chao Tian, Tie Liu
We propose a new information-theoretic bound on generalization error based on a combination of the error decomposition technique of Bu et al. and the conditional mutual information…
From Function to Distribution Modeling: A PAC-Generative Approach to Offline Optimization
Qiang Zhang, Ruida Zhou, Yang Shen +1
This paper considers the problem of offline optimization, where the objective function is unknown except for a collection of ``offline" data examples. While recent years have seen…
Harnessing the Power of Federated Learning in Federated Contextual Bandits
Chengshuai Shi, Ruida Zhou, Kun Yang +1
Federated learning (FL) has demonstrated great potential in revolutionizing distributed machine learning, and tremendous efforts have been made to extend it beyond the original foc…
Direct Preference Optimization with Rating Information: Practical Algorithms and Provable Gains
Luca Viano, Ruida Zhou, Yifan Sun +4
The class of direct preference optimization (DPO) algorithms has emerged as a promising approach for solving the alignment problem in foundation models. These algorithms work with…
Improved Weakly Private Information Retrieval Codes
Chengyuan Qian, Ruida Zhou, Chao Tian +1
We study the problem of weakly private information retrieval (W-PIR), where a user wishes to retrieve a desired message from non-colluding servers in a way that the privacy lea…
SPIRE: Conditional Personalization for Federated Diffusion Generative Models
Kaan Ozkara, Ruida Zhou, Suhas Diggavi
Recent advances in diffusion models have revolutionized generative AI, but their sheer size makes on device personalization, and thus effective federated learning (FL), infeasible.…
Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games
Youbang Sun, Tao Liu, Ruida Zhou +2
This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. It is shown that, under mild…
Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size
Ruida Zhou, Chao Tian, Hua Sun +1
We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from non-colluding databases, where each message is c…
Cost-aware Cascading Bandits
Ruida Zhou, Chao Gan, Jing Yan +1
In this paper, we propose a cost-aware cascading bandits model, a new variant of multi-armed ban- dits with cascading feedback, by considering the random cost of pulling arms. In e…
On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery
Renpu Liu, Ruida Zhou, Cong Shen +1
An intriguing property of the Transformer is its ability to perform in-context learning (ICL), where the Transformer can solve different inference tasks without parameter updating…
Beyond Binary Preferences: A Principled Framework for Reward Modeling with Ordinal Feedback
Amirhossein Afsharrad, Ruida Zhou, Luca Viano +2
Reward modeling is crucial for aligning large language models with human preferences, yet current approaches lack a principled mathematical framework for leveraging ordinal prefere…
Learning from Few Samples: Transformation-Invariant SVMs with Composition and Locality at Multiple Scales
Tao Liu, P. R. Kumar, Ruida Zhou +1
Motivated by the problem of learning with small sample sizes, this paper shows how to incorporate into support-vector machines (SVMs) those properties that have made convolutional…
Path-Guided Particle-based Sampling
Mingzhou Fan, Ruida Zhou, Chao Tian +1
Particle-based Bayesian inference methods by sampling from a partition-free target (posterior) distribution, e.g., Stein variational gradient descent (SVGD), have attracted signifi…
Directional-Clamp PPO
Gilad Karpel, Ruida Zhou, Shoham Sabach +1
Proximal Policy Optimization (PPO) is widely regarded as one of the most successful deep reinforcement learning algorithms, known for its robustness and effectiveness across a rang…
Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs
Tao Liu, Ruida Zhou, Dileep Kalathil +2
We address the issue of safety in reinforcement learning. We pose the problem in an episodic framework of a constrained Markov decision process. Existing results have shown that it…
Correlational Lagrangian Schrödinger Bridge: Learning Dynamics with Population-Level Regularization
Yuning You, Ruida Zhou, Yang Shen
Accurate modeling of system dynamics holds intriguing potential in broad scientific fields including cytodynamics and fluid mechanics. This task often presents significant challeng…
User Manual CAI version-1.0: An Open-Source Toolbox for Computer-Aided Investigation on the Fundamental Limits of Information Systems
Chao Tian, James S. Plank, Brent Hurst +1
We provide an open source toolbox on https://github.com/ct2641/CAI/releases/tag/1.0 to conduct computer-aided investigation on the fundamental limits of information systems. The to…
Staggered Quantizers for Perfect Perceptual Quality: A Connection between Quantizers with Common Randomness and Without
Ruida Zhou, Chao Tian
The rate-distortion-perception (RDP) framework has attracted significant recent attention due to its application in neural compression. It is important to understand the underlying…
Provable Policy Gradient Methods for Average-Reward Markov Potential Games
Min Cheng, Ruida Zhou, P. R. Kumar +1
We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on…
Cost-Aware Optimal Pairwise Pure Exploration
Di Wu, Chengshuai Shi, Ruida Zhou +1
Pure exploration is one of the fundamental problems in multi-armed bandits (MAB). However, existing works mostly focus on specific pure exploration tasks, without a holistic view o…
Data-adaptive Differentially Private Prompt Synthesis for In-Context Learning
Fengyu Gao, Ruida Zhou, Tianhao Wang +2
Large Language Models (LLMs) rely on the contextual information embedded in examples/demonstrations to perform in-context learning (ICL). To mitigate the risk of LLMs potentially l…
Understanding Uncertainty-based Active Learning Under Model Mismatch
Amir Hossein Rahmati, Mingzhou Fan, Ruida Zhou +3
Instead of randomly acquiring training data points, Uncertainty-based Active Learning (UAL) operates by querying the label(s) of pivotal samples from an unlabeled pool selected bas…
Reframing Data Value for Large Language Models Through the Lens of Plausibility
Mohamad Rida Rammal, Ruida Zhou, Suhas Diggavi
Data valuation seeks to answer the important question, "How much is this data worth?" Existing data valuation methods have largely focused on discriminative models, primarily exami…
Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem
Ruida Zhou, Chao Tian, Tie Liu
We provide a new information-theoretic generalization error bound that is exactly tight (i.e., matching even the constant) for the canonical quadratic Gaussian (location) problem.…