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

Wenshuo Guo

Wenshuo Guo contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Machine LearningInformation Theorymath.ITComputer Science and Game TheoryData Structures and AlgorithmsArtificial IntelligenceCryptography and Securitycs.CYDistributed, Parallel, and Cluster Computingecon.THMethodologyMultiagent SystemsRobotics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
13topics
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)

preprint2022arXiv

Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits

We introduce the "inverse bandit" problem of estimating the rewards of a multi-armed bandit instance from observing the learning process of a low-regret demonstrator. Existing approaches to the related problem of inverse reinforcement learning assume the execution of an optimal policy, and thereby suffer from an identifiability issue. In contrast, we propose to leverage the demonstrator's behavior en route to optimality, and in particular, the exploration phase, for reward estimation. We begin by establishing a general information-theoretic lower bound under this paradigm that applies to any demonstrator algorithm, which characterizes a fundamental tradeoff between reward estimation and the amount of exploration of the demonstrator. Then, we develop simple and efficient reward estimators for upper-confidence-based demonstrator algorithms that attain the optimal tradeoff, showing in particular that consistent reward estimation -- free of identifiability issues -- is possible under our paradigm. Extensive simulations on both synthetic and semi-synthetic data corroborate our theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Mechanisms that Incentivize Data Sharing in Federated Learning

Federated learning is typically considered a beneficial technology which allows multiple agents to collaborate with each other, improve the accuracy of their models, and solve problems which are otherwise too data-intensive / expensive to be solved individually. However, under the expectation that other agents will share their data, rational agents may be tempted to engage in detrimental behavior such as free-riding where they contribute no data but still enjoy an improved model. In this work, we propose a framework to analyze the behavior of such rational data generators. We first show how a naive scheme leads to catastrophic levels of free-riding where the benefits of data sharing are completely eroded. Then, using ideas from contract theory, we introduce accuracy shaping based mechanisms to maximize the amount of data generated by each agent. These provably prevent free-riding without needing any payment mechanism.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

No-Regret Learning in Partially-Informed Auctions

Auctions with partially-revealed information about items are broadly employed in real-world applications, but the underlying mechanisms have limited theoretical support. In this work, we study a machine learning formulation of these types of mechanisms, presenting algorithms that are no-regret from the buyer's perspective. Specifically, a buyer who wishes to maximize his utility interacts repeatedly with a platform over a series of $T$ rounds. In each round, a new item is drawn from an unknown distribution and the platform publishes a price together with incomplete, "masked" information about the item. The buyer then decides whether to purchase the item. We formalize this problem as an online learning task where the goal is to have low regret with respect to a myopic oracle that has perfect knowledge of the distribution over items and the seller's masking function. When the distribution over items is known to the buyer and the mask is a SimHash function mapping $\mathbb{R}^d$ to $\{0,1\}^{\ell}$, our algorithm has regret $\tilde O((Td\ell)^{1/2})$. In a fully agnostic setting when the mask is an arbitrary function mapping to a set of size $n$ and the prices are stochastic, our algorithm has regret $\tilde O((Tn)^{1/2})$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Polynomial-Time Key Recovery Attack on the Lau-Tan Cryptosystem Based on Gabidulin Codes

This paper presents a key recovery attack on the cryptosystem proposed by Lau and Tan in a talk at ACISP 2018. The Lau-Tan cryptosystem uses Gabidulin codes as the underlying decodable code. To hide the algebraic structure of Gabidulin codes, the authors chose a matrix of column rank $n$ to mix with a generator matrix of the secret Gabidulin code. The other part of the public key, however, reveals crucial information about the private key. Our analysis shows that the problem of recovering the private key can be reduced to solving a multivariate linear system over the base field, rather than solving a multivariate quadratic system as claimed by the authors. Solving the linear system for any nonzero solution permits us to recover the private key. Apparently, this attack costs polynomial time, and therefore completely breaks the cryptosystem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Semilinear Transformations in Coding Theory: A New Technique in Code-Based Cryptography

This paper presents a new technique for disturbing the algebraic structure of linear codes in code-based cryptography. This is a new attempt to exploit Gabidulin codes in the McEliece setting and almost all the previous cryptosystems of this type have been completely or partially broken. To be specific, we introduce the so-called semilinear transformation in coding theory, which is defined through an $\mathbb{F}_q$-linear automorphism of $\mathbb{F}_{q^m}$, then apply them to construct a public key encryption scheme. Our analysis shows that this scheme can resist all the existing distinguisher attacks, such as Overbeck's attack and Coggia-Couvreur attack. Meanwhile, we endow the underlying Gabidulin code with the so-called partial cyclic structure to reduce the public key size. Compared with some other code-based cryptosystems, our proposal has a much more compact representation of public keys. For instance, 2592 bytes are enough for our proposal to achieve the security of 256 bits, almost 403 times smaller than that of Classic McEliece entering the third round of the NIST PQC project.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Two Public-Key Cryptosystems Based on Expanded Gabidulin Codes

This paper presents two public key cryptosystems based on the so-called expanded Gabidulin codes, which are constructed by expanding Gabidulin codes over the base field. Exploiting the fast decoder of Gabidulin codes, we propose an efficient algorithm to decode these new codes when the noise vector satisfies a certain condition. Additionally, these new codes have an excellent error-correcting capability because of the optimality of their parent Gabidulin codes. With different masking techniques, we give two encryption schemes by using expanded Gabidulin codes in the McEliece setting. Being constructed over the base field, these two proposals can prevent the existing structural attacks using the Frobenius map. Based on the distinguisher for Gabidulin codes, we propose a distinguisher for expanded Gabidulin codes by introducing the concept of the so-called twisted Frobenius power. It turns out that the public code in our proposals seems indistinguishable from random codes under this distinguisher. Furthermore, our proposals have an obvious advantage in public key representation without using the cyclic or quasi-cyclic structure compared to some other code-based cryptosystems. To achieve the security of 256 bits, for instance, a public key size of 37583 bytes is enough for our first proposal, while around 1044992 bytes are needed for Classic McEliece selected as a candidate of the third round of the NIST PQC project.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Multi-Source Causal Inference Using Control Variates

While many areas of machine learning have benefited from the increasing availability of large and varied datasets, the benefit to causal inference has been limited given the strong assumptions needed to ensure identifiability of causal effects; these are often not satisfied in real-world datasets. For example, many large observational datasets (e.g., case-control studies in epidemiology, click-through data in recommender systems) suffer from selection bias on the outcome, which makes the average treatment effect (ATE) unidentifiable. We propose a general algorithm to estimate causal effects from \emph{multiple} data sources, where the ATE may be identifiable only in some datasets but not others. The key idea is to construct control variates using the datasets in which the ATE is not identifiable. We show theoretically that this reduces the variance of the ATE estimate. We apply this framework to inference from observational data under outcome selection bias, assuming access to an auxiliary small dataset from which we can obtain a consistent estimate of the ATE. We construct a control variate by taking the difference of the odds ratio estimates from the two datasets. Across simulations and two case studies with real data, we show that this control variate can significantly reduce the variance of the ATE estimate.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast Algorithms for Computational Optimal Transport and Wasserstein Barycenter

We provide theoretical complexity analysis for new algorithms to compute the optimal transport (OT) distance between two discrete probability distributions, and demonstrate their favorable practical performance over state-of-art primal-dual algorithms and their capability in solving other problems in large-scale, such as the Wasserstein barycenter problem for multiple probability distributions. First, we introduce the \emph{accelerated primal-dual randomized coordinate descent} (APDRCD) algorithm for computing the OT distance. We provide its complexity upper bound $\bigOtil(\frac{n^{5/2}}{\varepsilon})$ where $n$ stands for the number of atoms of these probability measures and $\varepsilon > 0$ is the desired accuracy. This complexity bound matches the best known complexities of primal-dual algorithms for the OT problems, including the adaptive primal-dual accelerated gradient descent (APDAGD) and the adaptive primal-dual accelerated mirror descent (APDAMD) algorithms. Then, we demonstrate the better performance of the APDRCD algorithm over the APDAGD and APDAMD algorithms through extensive experimental studies, and further improve its practical performance by proposing a greedy version of it, which we refer to as \emph{accelerated primal-dual greedy coordinate descent} (APDGCD). Finally, we generalize the APDRCD and APDGCD algorithms to distributed algorithms for computing the Wasserstein barycenter for multiple probability distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding Equilibrium in Multi-Agent Games with Payoff Uncertainty

We study the problem of finding equilibrium strategies in multi-agent games with incomplete payoff information, where the payoff matrices are only known to the players up to some bounded uncertainty sets. In such games, an ex-post equilibrium characterizes equilibrium strategies that are robust to the payoff uncertainty. When the game is one-shot, we show that in zero-sum polymatrix games, an ex-post equilibrium can be computed efficiently using linear programming. We further extend the notion of ex-post equilibrium to stochastic games, where the game is played repeatedly in a sequence of stages and the transition dynamics are governed by an Markov decision process (MDP). We provide sufficient condition for the existence of an ex-post Markov perfect equilibrium (MPE). We show that under bounded payoff uncertainty, the value of any two-player zero-sum stochastic game can be computed up to a tight value interval using dynamic programming.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Neural Kernels Without Tangents

We investigate the connections between neural networks and simple building blocks in kernel space. In particular, using well established feature space tools such as direct sum, averaging, and moment lifting, we present an algebra for creating "compositional" kernels from bags of features. We show that these operations correspond to many of the building blocks of "neural tangent kernels (NTK)". Experimentally, we show that there is a correlation in test error between neural network architectures and the associated kernels. We construct a simple neural network architecture using only 3x3 convolutions, 2x2 average pooling, ReLU, and optimized with SGD and MSE loss that achieves 96% accuracy on CIFAR10, and whose corresponding compositional kernel achieves 90% accuracy. We also use our constructions to investigate the relative performance of neural networks, NTKs, and compositional kernels in the small dataset regime. In particular, we find that compositional kernels outperform NTKs and neural networks outperform both kernel methods.

0 citations0 reviewsNo code linkedOpen access