BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Ruida Zhou

Ruida Zhou contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITMachine LearningArtificial IntelligenceData Structures and Algorithmseess.SPInformation Retrievalmath.OC

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2024arXiv

From Function to Distribution Modeling: A PAC-Generative Approach to Offline Optimization

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 a flurry of work on applying various machine learning techniques to the offline optimization problem, the majority of these work focused on learning a surrogate of the unknown objective function and then applying existing optimization algorithms. While the idea of modeling the unknown objective function is intuitive and appealing, from the learning point of view it also makes it very difficult to tune the objective of the learner according to the objective of optimization. Instead of learning and then optimizing the unknown objective function, in this paper we take on a less intuitive but more direct view that optimization can be thought of as a process of sampling from a generative model. To learn an effective generative model from the offline data examples, we consider the standard technique of ``re-weighting", and our main technical contribution is a probably approximately correct (PAC) lower bound on the natural optimization objective, which allows us to jointly learn a weight function and a score-based generative model. The robustly competitive performance of the proposed approach is demonstrated via empirical studies using the standard offline optimization benchmarks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Approximate Top-$m$ Arm Identification with Heterogeneous Reward Variances

We study the effect of reward variance heterogeneity in the approximate top-$m$ arm identification setting. In this setting, the reward for the $i$-th arm follows a $σ^2_i$-sub-Gaussian distribution, and the agent needs to incorporate this knowledge to minimize the expected number of arm pulls to identify $m$ arms with the largest means within error $ε$ out of the $n$ arms, with probability at least $1-δ$. We show that the worst-case sample complexity of this problem is $$Θ\left( \sum_{i =1}^n \frac{σ_i^2}{ε^2} \ln\frac{1}δ + \sum_{i \in G^{m}} \frac{σ_i^2}{ε^2} \ln(m) + \sum_{j \in G^{l}} \frac{σ_j^2}{ε^2} \text{Ent}(σ^2_{G^{r}}) \right),$$ where $G^{m}, G^{l}, G^{r}$ are certain specific subsets of the overall arm set $\{1, 2, \ldots, n\}$, and $\text{Ent}(\cdot)$ is an entropy-like function which measures the heterogeneity of the variance proxies. The upper bound of the complexity is obtained using a divide-and-conquer style algorithm, while the matching lower bound relies on the study of a dual formulation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improved Weakly Private Information Retrieval Codes

We study the problem of weakly private information retrieval (W-PIR), where a user wishes to retrieve a desired message from $N$ non-colluding servers in a way that the privacy leakage regarding the desired message's identity is less than or equal to a threshold. We propose a new code construction which significantly improves upon the best known result in the literature, based on the following critical observation. In previous constructions, for the extreme case of minimum download, the retrieval pattern is to download the message directly from $N-1$ servers; however this causes leakage to all these $N-1$ servers, and a better retrieval pattern for this extreme case is to download the message directly from a single server. The proposed code construction allows a natural transition to such a pattern, and for both the maximal leakage metric and the mutual information leakage metric, significant improvements can be obtained. We provide explicit solutions, in contrast to a previous work by Lin et al., where only numerical solutions were obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Top-$k$ Selection from $m$-wise Partial Rankings via Borda Counting

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 $m$-sized subsets to accurately determine which items are the overall top-$k$ items in a total of $n$ items. The Borda counting algorithm simply counts the cumulative scores for each item from these partial ranking observations. This generalizes a previous work of a similar nature by Shah et al. using probabilistic pairwise comparison data. The performance of the Borda counting algorithm critically depends on the associated score separation $Δ_k$ between the $k$-th item and the $(k+1)$-th item. Specifically, we show that if $Δ_k$ is greater than certain value, then the top-$k$ items selected by the algorithm is asymptotically accurate almost surely; if $Δ_k$ is below certain value, then the result will be inaccurate with a constant probability. In the special case of $m=2$, i.e., pairwise comparison, the resultant bound is tighter than that given by Shah et al., leading to a reduced gap between the error probability upper and lower bounds. These results are further extended to the approximate top-$k$ selection setting. Numerical experiments demonstrate the effectiveness and accuracy of the Borda counting algorithm, compared with the spectral MLE-based algorithm, particularly when the data does not necessarily follow an assumed parametric model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Policy Optimization for Constrained MDPs with Provable Fast Global Convergence

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 primal-dual approach can achieve an $\mathcal{O}(1/\sqrt{T})$ global convergence rate for both the optimality gap and the constraint violation. We propose a new algorithm called policy mirror descent-primal dual (PMD-PD) algorithm that can provably achieve a faster $\mathcal{O}(\log(T)/T)$ convergence rate for both the optimality gap and the constraint violation. For the primal (policy) update, the PMD-PD algorithm utilizes a modified value function and performs natural policy gradient steps, which is equivalent to a mirror descent step with appropriate regularization. For the dual update, the PMD-PD algorithm uses modified Lagrange multipliers to ensure a faster convergence rate. We also present two extensions of this approach to the settings with zero constraint violation and sample-based estimation. Experimental results demonstrate the faster convergence rate and the better performance of the PMD-PD algorithm compared with existing policy gradient-based algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Stochastic Chaining and Strengthened Information-Theoretic Generalization Bounds

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. Different from the deterministic chaining approach based on hierarchical partitions of a metric space, previously proposed by Asadi et al., we propose a stochastic chaining approach, which replaces the hierarchical partitions with an abstracted Markovian model borrowed from successive refinement source coding. This approach has three benefits over deterministic chaining: 1) the metric space is not necessarily bounded, 2) facilitation of subsequent analysis to yield more explicit bound, and 3) further opportunity to optimize the bound by removing the geometric rigidity of the partitions. The proposed approach includes the traditional chaining as a special case, and can therefore also utilize any deterministic chaining construction. We illustrate these benefits using the problem of estimating Gaussian mean and that of phase retrieval. For the former, we derive a bound that provides an order-wise improvement over previous results, and for the latter we provide a stochastic chain that allows optimization over the chaining parameter.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size

We consider constructing capacity-achieving linear codes with minimum message size for private information retrieval (PIR) from $N$ non-colluding databases, where each message is coded using maximum distance separable (MDS) codes, such that it can be recovered from accessing the contents of any $T$ databases. It is shown that the minimum message size (sometimes also referred to as the sub-packetization factor) is significantly, in fact exponentially, lower than previously believed. More precisely, when $K>T/\textbf{gcd}(N,T)$ where $K$ is the total number of messages in the system and $\textbf{gcd}(\cdot,\cdot)$ means the greatest common divisor, we establish, by providing both novel code constructions and a matching converse, the minimum message size as $\textbf{lcm}(N-T,T)$, where $\textbf{lcm}(\cdot,\cdot)$ means the least common multiple. On the other hand, when $K$ is small, we show that it is in fact possible to design codes with a message size even smaller than $\textbf{lcm}(N-T,T)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Individually Conditional Individual Mutual Information Bound on Generalization Error

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 (CMI) construction of Steinke and Zakynthinou. In a previous work, Haghifam et al. proposed a different bound combining the two aforementioned techniques, which we refer to as the conditional individual mutual information (CIMI) bound. However, in a simple Gaussian setting, both the CMI and the CIMI bounds are order-wise worse than that by Bu et al.. This observation motivated us to propose the new bound, which overcomes this issue by reducing the conditioning terms in the conditional mutual information. In the process of establishing this bound, a conditional decoupling lemma is established, which also leads to a meaningful dichotomy and comparison among these information-theoretic bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems

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 message private from any given server. Existing efforts in this area have made it clear that the efficiency of the retrieval will be impacted significantly by the amount of the storage space allowed at the servers. In this work, we consider the tradeoff between the storage cost and the retrieval cost. We first present three fundamental results: 1) a regime-wise 2-approximate characterization of the optimal tradeoff, 2) a cyclic permutation lemma that can produce more sophisticated codes from simpler ones, and 3) a relaxed entropic linear program (LP) lower bound that has a polynomial complexity. Equipped with the cyclic permutation lemma, we then propose two novel code constructions, and by applying the lemma, obtain new storage-retrieval points. Furthermore, we derive more explicit lower bounds by utilizing only a subset of the constraints in the relaxed entropic LP in a systematic manner. Though the new upper bound and lower bound do not lead to a more precise approximate characterization in general, they are significantly tighter than the existing art.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Information Leakage in Private Information Retrieval Systems

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 leakage. Individual message leakage, or simply individual leakage, is defined as the amount of information that the user can obtain on any individual message that is not being requested, and the total leakage is defined as the amount of information that the user can obtain about all the other messages except the one being requested. In this work, we characterize the tradeoff between the minimum download cost and the individual leakage, and that for the total leakage, respectively. New codes are proposed to achieve these optimal tradeoffs, which are also shown to be optimal in terms of the message size. We further characterize the optimal tradeoff between the minimum amount of common randomness and the total leakage. Moreover, we show that under individual leakage, common randomness is in fact unnecessary when there are more than two messages.

0 citations0 reviewsNo code linkedOpen access