OpenRaiser/Intern-Atlas huggingface dataset:
Guessing Cost: Bounds and Applications to Data Repair in Distributed Storage
Venue: arXiv cs.IT 2023
Year: 2023

The guesswork refers to the distribution of the minimum number of trials needed to guess a realization of a random variable accurately. In this study, a non-trivial generalization of the guesswork called guessing cost (also referred to as cost of guessing) is introduced, and an optimal strategy for finding the $ρ$-th moment of guessing cost is provided for a random variable defined on a finite set whereby each choice is associated with a positive finite cost value (unit cost corresponds to the original guesswork). Moreover, we drive asymptotically tight upper and lower bounds on the logarithm of guessing cost moments. Similar to previous studies on the guesswork, established bounds on the moments of guessing cost quantify the accumulated cost of guesses required for correctly identifying the unknown choice and are expressed in terms of Rényi's entropy. Moreover, new random variables are introduced to establish connections between the guessing cost and the guesswork, leading to induced strategies. Establishing this implicit connection helped us obtain improved bounds for the non-asymptotic region. As a consequence, we establish the guessing cost exponent in terms of Rényi entropy rate on the moments of the guessing cost using the optimal strategy by considering a sequence of independent random variables with different cost distributions. Finally, with slight modifications to the original problem, these results are shown to be applicable for bounding the overall repair bandwidth for distributed data storage systems backed up by base stations and protected by bipartite graph codes.
What Are People Asking About COVID-19? A Question Classification Dataset
Venue: arXiv cs.CL 2023
Year: 2023

We present COVID-Q, a set of 1,690 questions about COVID-19 from 13 sources, which we annotate into 15 question categories and 207 question clusters. The most common questions in our dataset asked about transmission, prevention, and societal effects of COVID, and we found that many questions that appeared in multiple sources were not answered by any FAQ websites of reputable organizations such as the CDC and FDA. We post our dataset publicly at https://github.com/JerryWeiAI/COVID-Q. For classifying questions into 15 categories, a BERT baseline scored 58.1% accuracy when trained on 20 examples per category, and for a question clustering task, a BERT + triplet loss baseline achieved 49.5% accuracy. We hope COVID-Q can help either for direct use in developing applied systems or as a domain-specific resource for model evaluation.
Revisiting Parameter Sharing in Multi-Agent Deep Reinforcement Learning
Venue: arXiv cs.LG 2023
Year: 2023

Parameter sharing, where each agent independently learns a policy with fully shared parameters between all policies, is a popular baseline method for multi-agent deep reinforcement learning. Unfortunately, since all agents share the same policy network, they cannot learn different policies or tasks. This issue has been circumvented experimentally by adding an agent-specific indicator signal to observations, which we term "agent indication". Agent indication is limited, however, in that without modification it does not allow parameter sharing to be applied to environments where the action spaces and/or observation spaces are heterogeneous. This work formalizes the notion of agent indication and proves that it enables convergence to optimal policies for the first time. Next, we formally introduce methods to extend parameter sharing to learning in heterogeneous observation and action spaces, and prove that these methods allow for convergence to optimal policies. Finally, we experimentally confirm that the methods we introduce function empirically, and conduct a wide array of experiments studying the empirical efficacy of many different agent indication schemes for image based observation spaces.
Task-Oriented Data Compression for Multi-Agent Communications Over Bit-Budgeted Channels
Venue: arXiv cs.IT 2023
Year: 2023

Various applications for inter-machine communications are on the rise. Whether it is for autonomous driving vehicles or the internet of everything, machines are more connected than ever to improve their performance in fulfilling a given task. While in traditional communications the goal has often been to reconstruct the underlying message, under the emerging task-oriented paradigm, the goal of communication is to enable the receiving end to make more informed decisions or more precise estimates/computations. Motivated by these recent developments, in this paper, we perform an indirect design of the communications in a multi-agent system (MAS) in which agents cooperate to maximize the averaged sum of discounted one-stage rewards of a collaborative task. Due to the bit-budgeted communications between the agents, each agent should efficiently represent its local observation and communicate an abstracted version of the observations to improve the collaborative task performance. We first show that this problem can be approximated as a form of data-quantization problem which we call task-oriented data compression (TODC). We then introduce the state-aggregation for information compression algorithm (SAIC) to solve the formulated TODC problem. It is shown that SAIC is able to achieve near-optimal performance in terms of the achieved sum of discounted rewards. The proposed algorithm is applied to a geometric consensus problem and its performance is compared with several benchmarks. Numerical experiments confirm the promise of this indirect design approach for task-oriented multi-agent communications.
Rethinking Assumptions in Deep Anomaly Detection
Venue: arXiv cs.LG 2023
Year: 2023

Though anomaly detection (AD) can be viewed as a classification problem (nominal vs. anomalous) it is usually treated in an unsupervised manner since one typically does not have access to, or it is infeasible to utilize, a dataset that sufficiently characterizes what it means to be "anomalous." In this paper we present results demonstrating that this intuition surprisingly seems not to extend to deep AD on images. For a recent AD benchmark on ImageNet, classifiers trained to discern between normal samples and just a few (64) random natural images are able to outperform the current state of the art in deep AD. Experimentally we discover that the multiscale structure of image data makes example anomalies exceptionally informative.
Online Versus Offline Rate in Streaming Codes for Variable-Size Messages
Venue: arXiv cs.IT 2023
Year: 2023

One pervasive challenge in providing a high quality-of-service for live communication is to recover lost packets in real-time. Streaming codes are a class of erasure codes that are designed for such strict, low-latency streaming communication settings. Motivated by applications that transmit messages whose sizes vary over time, such as live video streaming, this paper considers the setting of streaming codes under variable-size messages. In practice, streaming codes operate in an "online" setting where the sizes of the future messages are unknown. "Offline" codes, in contrast, have access to the sizes of all messages, including future ones. This paper introduces the first online rate-optimal streaming codes for communicating over a burst-only packet loss channel for two broad parameter regimes. These two online codes match the rates of optimal offline codes for the two settings despite the apparent advantage of the offline setting. This paper further establishes that online codes cannot attain the optimal rate for offline codes for all remaining parameter settings.
Multi-agent Assortment Optimization in Sequential Matching Markets
Venue: arXiv cs.GT 2023
Year: 2023

In this work, we study the multi-agent assortment optimization problem in the two-sided sequential matching model introduced by Ashlagi et al. (2022). The setting is the following: we (the platform) offer a menu of suppliers to each customer. Then, every customer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Each supplier observes the subset of customers that selected them, and choose either to match a customer or to leave the system. Therefore, a match takes place if both a customer and a supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a discrete choice model. Our goal is to choose an assortment family that maximizes the expected revenue of the matching. Given the hardness of the problem, we show a $1-1/e$-approximation factor for the heterogeneous setting where customers follow general choice models and suppliers follow a general choice model whose demand function is monotone and submodular. Our approach is flexible enough to allow for different assortment constraints and for a revenue objective function. Furthermore, we design an algorithm that beats the $1-1/e$ barrier and, in fact, is asymptotically optimal when suppliers follow the classic multinomial-logit choice model and are sufficiently selective. We finally provide other results and further insights. Notably, in the unconstrained setting where customers and suppliers follow multinomial-logit models, we design a simple and efficient approximation algorithm that appropriately randomizes over a family of nested-assortments. Also, we analyze various aspects of the matching market model that lead to several operational insights, such as the fact that matching platforms can benefit from allowing the more selective agents to initiate the matchmaking process.
Basis-Finding Algorithm for Decoding Fountain Codes for DNA-Based Data Storage
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we consider the decoding of fountain codes where the received symbols may have errors. It is motivated by the application of fountain codes in DNA-based data storage systems where the inner code decoding, which generally has undetectable errors, is performed before the outer fountain code decoding. We propose a novel and efficient decoding algorithm, namely basis-finding algorithm (BFA), followed by three implementations. The key idea of the BFA is to find a basis of the received symbols, and then use the most reliable basis elements to recover the source symbols with the inactivation decoding. Gaussian elimination is used to find the basis and to identify the most reliable basis elements. As a result, the BFA has polynomial time complexity. For random fountain codes, we are able to derive some theoretical bounds for the frame error rate (FER) of the BFA. Extensive simulations with Luby transform (LT) codes show that, the BFA has significantly lower FER than the belief propagation (BP) algorithm except for an extremely large amount of received symbols, and the FER of the BFA generally decreases as the average weight of basis elements increases.
On Frequentist Regret of Linear Thompson Sampling
Venue: arXiv cs.LG 2023
Year: 2023

This paper studies the stochastic linear bandit problem, where a decision-maker chooses actions from possibly time-dependent sets of vectors in $\mathbb{R}^d$ and receives noisy rewards. The objective is to minimize regret, the difference between the cumulative expected reward of the decision-maker and that of an oracle with access to the expected reward of each action, over a sequence of $T$ decisions. Linear Thompson Sampling (LinTS) is a popular Bayesian heuristic, supported by theoretical analysis that shows its Bayesian regret is bounded by $\widetilde{\mathcal{O}}(d\sqrt{T})$, matching minimax lower bounds. However, previous studies demonstrate that the frequentist regret bound for LinTS is $\widetilde{\mathcal{O}}(d\sqrt{dT})$, which requires posterior variance inflation and is by a factor of $\sqrt{d}$ worse than the best optimism-based algorithms. We prove that this inflation is fundamental and that the frequentist bound of $\widetilde{\mathcal{O}}(d\sqrt{dT})$ is the best possible, by demonstrating a randomization bias phenomenon in LinTS that can cause linear regret without inflation.We propose a data-driven version of LinTS that adjusts posterior inflation using observed data, which can achieve minimax optimal frequentist regret, under additional conditions. Our analysis provides new insights into LinTS and settles an open problem in the field.
Multi-Purchase Behavior: Modeling, Estimation and Optimization
Venue: arXiv cs.IR 2023
Year: 2023

We study the problem of modeling purchase of multiple products and utilizing it to display optimized recommendations for online retailers and e-commerce platforms. We present a parsimonious multi-purchase family of choice models called the Bundle-MVL-K family, and develop a binary search based iterative strategy that efficiently computes optimized recommendations for this model. We establish the hardness of computing optimal recommendation sets, and derive several structural properties of the optimal solution that aid in speeding up computation. This is one of the first attempts at operationalizing multi-purchase class of choice models. We show one of the first quantitative links between modeling multiple purchase behavior and revenue gains. The efficacy of our modeling and optimization techniques compared to competing solutions is shown using several real world datasets on multiple metrics such as model fitness, expected revenue gains and run-time reductions. For example, the expected revenue benefit of taking multiple purchases into account is observed to be $\sim5\%$ in relative terms for the Ta Feng and UCI shopping datasets, when compared to the MNL model for instances with $\sim 1500$ products. Additionally, across $6$ real world datasets, the test log-likelihood fits of our models are on average $17\%$ better in relative terms. Our work contributes to the study multi-purchase decisions, analyzing consumer demand and the retailers optimization problem. The simplicity of our models and the iterative nature of our optimization technique allows practitioners meet stringent computational constraints while increasing their revenues in practical recommendation applications at scale, especially in e-commerce platforms and other marketplaces.
Federated Learning Meets Multi-objective Optimization
Venue: arXiv cs.LG 2023
Year: 2023

Federated learning has emerged as a promising, massively distributed way to train a joint deep model over large amounts of edge devices while keeping private user data strictly on device. In this work, motivated from ensuring fairness among users and robustness against malicious adversaries, we formulate federated learning as multi-objective optimization and propose a new algorithm FedMGDA+ that is guaranteed to converge to Pareto stationary solutions. FedMGDA+ is simple to implement, has fewer hyperparameters to tune, and refrains from sacrificing the performance of any participating user. We establish the convergence properties of FedMGDA+ and point out its connections to existing approaches. Extensive experiments on a variety of datasets confirm that FedMGDA+ compares favorably against state-of-the-art.
TeslaMirror: Multistimulus Encounter-Type Haptic Display for Shape and Texture Rendering in VR
Venue: arXiv cs.HC 2023
Year: 2023

This paper proposes a novel concept of a hybrid tactile display with multistimulus feedback, allowing the real-time experience of the position, shape, and texture of the virtual object. The key technology of the TeslaMirror is that we can deliver the sensation of object parameters (pressure, vibration, and electrotactile feedback) without any wearable haptic devices. We developed the full digital twin of the 6 DOF UR robot in the virtual reality (VR) environment, allowing the adaptive surface simulation and control of the hybrid display in real-time. The preliminary user study was conducted to evaluate the ability of TeslaMirror to reproduce shape sensations with the under-actuated end-effector. The results revealed that potentially this approach can be used in the virtual systems for rendering versatile VR shapes with high fidelity haptic experience.
Taming neural networks with TUSLA: Non-convex learning via adaptive stochastic gradient Langevin algorithms
Venue: arXiv cs.LG 2023
Year: 2023

Artificial neural networks (ANNs) are typically highly nonlinear systems which are finely tuned via the optimization of their associated, non-convex loss functions. In many cases, the gradient of any such loss function has superlinear growth, making the use of the widely-accepted (stochastic) gradient descent methods, which are based on Euler numerical schemes, problematic. We offer a new learning algorithm based on an appropriately constructed variant of the popular stochastic gradient Langevin dynamics (SGLD), which is called tamed unadjusted stochastic Langevin algorithm (TUSLA). We also provide a nonasymptotic analysis of the new algorithm's convergence properties in the context of non-convex learning problems with the use of ANNs. Thus, we provide finite-time guarantees for TUSLA to find approximate minimizers of both empirical and population risks. The roots of the TUSLA algorithm are based on the taming technology for diffusion processes with superlinear coefficients as developed in \citet{tamed-euler, SabanisAoAP} and for MCMC algorithms in \citet{tula}. Numerical experiments are presented which confirm the theoretical findings and illustrate the need for the use of the new algorithm in comparison to vanilla SGLD within the framework of ANNs.
Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
Venue: arXiv cs.DM 2023
Year: 2023

In this paper, we are interested in algorithms that take in input an arbitrary graph $G$, and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of $G$ which fulfil a given property $Π$. All over this paper, we study several different properties $Π$, and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, sub-cographs and some subclasses of cographs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal independent sets of an auxiliary graph. For cographs and some subclasses , the algorithms rely on a framework recently introduced by Conte & Uno called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property $Π$ that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every "interesting" hereditary property $Π$. We extend the hardness result to some specific edge version of the extension problem.
A (Slightly) Improved Approximation Algorithm for Metric TSP
Venue: arXiv cs.DS 2023
Year: 2023

For some $ε> 10^{-36}$ we give a randomized $3/2-ε$ approximation algorithm for metric TSP.
Integrating Distributed Architectures in Highly Modular RL Libraries
Venue: arXiv cs.CV 2023
Year: 2023

Advancing reinforcement learning (RL) requires tools that are flexible enough to easily prototype new methods while avoiding impractically slow experimental turnaround times. To match the first requirement, the most popular RL libraries advocate for highly modular agent composability, which facilitates experimentation and development. To solve challenging environments within reasonable time frames, scaling RL to large sampling and computing resources has proved a successful strategy. However, this capability has been so far difficult to combine with modularity. In this work, we explore design choices to allow agent composability both at a local and distributed level of execution. We propose a versatile approach that allows the definition of RL agents at different scales through independent reusable components. We demonstrate experimentally that our design choices allow us to reproduce classical benchmarks, explore multiple distributed architectures, and solve novel and complex environments while giving full control to the user in the agent definition and training scheme definition. We believe this work can provide useful insights to the next generation of RL libraries.
Living Without Beth and Craig: Definitions and Interpolants in Description and Modal Logics with Nominals and Role Inclusions
Venue: arXiv cs.LO 2023
Year: 2023

The Craig interpolation property (CIP) states that an interpolant for an implication exists iff it is valid. The projective Beth definability property (PBDP) states that an explicit definition exists iff a formula stating implicit definability is valid. Thus, the CIP and PBDP reduce potentially hard existence problems to entailment in the underlying logic. Description (and modal) logics with nominals and/or role inclusions do not enjoy the CIP nor the PBDP, but interpolants and explicit definitions have many applications, in particular in concept learning, ontology engineering, and ontology-based data management. In this article we show that, even without Beth and Craig, the existence of interpolants and explicit definitions is decidable in description logics with nominals and/or role inclusions such as ALCO, ALCH and ALCHOI and corresponding hybrid modal logics. However, living without Beth and Craig makes this problem harder than entailment: the existence problems become 2ExpTime-complete in the presence of an ontology or the universal modality, and coNExpTime-complete otherwise. We also analyze explicit definition existence if all symbols (except the one that is defined) are admitted in the definition. In this case the complexity depends on whether one considers individual or concept names. Finally, we consider the problem of computing interpolants and explicit definitions if they exist and turn the complexity upper bound proof into an algorithm computing them, at least for description logics with role inclusions.
The algebraic structure of conjucyclic codes over F_{q^2}
Venue: arXiv cs.IT 2023
Year: 2023

Conjucyclic codes are an important and special family of classical error-correcting codes, which have been used to construct binary quantum error-correcting codes (QECCs). However, at present, the research on the conjucyclic codes is extremely insufficient. This paper will explore the algebraic structure of additive conjucyclic codes over $\mathbb{F}_{q^{2}}$ for the first time. Mainly via the trace function from $\mathbb{F}_{q^{2}}$ down $\mathbb{F}_{q}$, we will firstly build an isomorphic mapping between $q^2$-ary additive conjucyclic codes and $q$-ary linear cyclic codes. Since the mapping preserves the weight and orthogonality, then the dual structure of these codes with respect to the alternating inner product will be described. Then a new construction of QECCs from conjucyclic codes can be obtained. Finally, the enumeration of $q^2$-ary additive conjucyclic codes of length $n$ and the explicit forms of their generator and parity-check matrices will be determined.