OpenRaiser/Intern-Atlas huggingface dataset:
Reusability and Transferability of Macro Actions for Reinforcement Learning
Venue: arXiv cs.NE 2022
Year: 2022

Conventional reinforcement learning (RL) typically determines an appropriate primitive action at each timestep. However, by using a proper macro action, defined as a sequence of primitive actions, an agent is able to bypass intermediate states to a farther state and facilitate its learning procedure. The problem we would like to investigate is what associated beneficial properties that macro actions may possess. In this paper, we unveil the properties of reusability and transferability of macro actions. The first property, reusability, means that a macro action generated along with one RL method can be reused by another RL method for training, while the second one, transferability, means that a macro action can be utilized for training agents in similar environments with different reward settings. In our experiments, we first generate macro actions along with RL methods. We then provide a set of analyses to reveal the properties of reusability and transferability of the generated macro actions.
Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recovery
Venue: arXiv cs.LG 2022
Year: 2022

Real world data often exhibit low-dimensional geometric structures, and can be viewed as samples near a low-dimensional manifold. This paper studies nonparametric regression of Hölder functions on low-dimensional manifolds using deep ReLU networks. Suppose $n$ training data are sampled from a Hölder function in $\mathcal{H}^{s,α}$ supported on a $d$-dimensional Riemannian manifold isometrically embedded in $\mathbb{R}^D$, with sub-gaussian noise. A deep ReLU network architecture is designed to estimate the underlying function from the training data. The mean squared error of the empirical estimator is proved to converge in the order of $n^{-\frac{2(s+α)}{2(s+α) + d}}\log^3 n$. This result shows that deep ReLU networks give rise to a fast convergence rate depending on the data intrinsic dimension $d$, which is usually much smaller than the ambient dimension $D$. It therefore demonstrates the adaptivity of deep ReLU networks to low-dimensional geometric structures of data, and partially explains the power of deep ReLU networks in tackling high-dimensional data with low-dimensional geometric structures.
DoorGym: A Scalable Door Opening Environment And Baseline Agent
Venue: arXiv cs.RO 2022
Year: 2022

In order to practically implement the door opening task, a policy ought to be robust to a wide distribution of door types and environment settings. Reinforcement Learning (RL) with Domain Randomization (DR) is a promising technique to enforce policy generalization, however, there are only a few accessible training environments that are inherently designed to train agents in domain randomized environments. We introduce DoorGym, an open-source door opening simulation framework designed to utilize domain randomization to train a stable policy. We intend for our environment to lie at the intersection of domain transfer, practical tasks, and realism. We also provide baseline Proximal Policy Optimization and Soft Actor-Critic implementations, which achieves success rates between 0% up to 95% for opening various types of doors in this environment. Moreover, the real-world transfer experiment shows the trained policy is able to work in the real world. Environment kit available here: https://github.com/PSVL/DoorGym/
Circular Proofs as Session-Typed Processes: A Local Validity Condition
Venue: arXiv cs.LO 2022
Year: 2022

Proof theory provides a foundation for studying and reasoning about programming languages, most directly based on the well-known Curry-Howard isomorphism between intuitionistic logic and the typed lambda-calculus. More recently, a correspondence between intuitionistic linear logic and the session-typed pi-calculus has been discovered. In this paper, we establish an extension of the latter correspondence for a fragment of substructural logic with least and greatest fixed points. We describe the computational interpretation of the resulting infinitary proof system as session-typed processes, and provide an effectively decidable local criterion to recognize mutually recursive processes corresponding to valid circular proofs as introduced by Fortier and Santocanale. We show that our algorithm imposes a stricter requirement than Fortier and Santocanale's guard condition, but is local and compositional and therefore more suitable as the basis for a programming language.
The Price of Connectivity in Fair Division
Venue: arXiv cs.GT 2022
Year: 2022

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least $3/4$ of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most $1/2$. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.
Graphs with large total angular resolution
Venue: arXiv cs.CG 2022
Year: 2022

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with $n$ vertices and a total angular resolution greater than $60^{\circ}$ is bounded by $2n-6$. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least $60^{\circ}$ is NP-hard.
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
Venue: arXiv cs.GT 2022
Year: 2022

We consider the Arrow--Debreu exchange market model under the assumption that the agents' demands satisfy the weak gross substitutes (WGS) property. We present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands assuming the availability of a price update oracle. We exhibit specific implementations of such an oracle for WGS demands with bounded price elasticities and for Gale demand systems. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for the NSW problem with capped additive separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.
Homotopic curve shortening and the affine curve-shortening flow
Venue: arXiv cs.CG 2022
Year: 2022

We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call "homotopic curve shortening" (HCS), starts with a closed curve (which might self-intersect) in the presence of a set $P\subset \mathbb R^2$ of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and $P$ is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between ACSF and HCS generalizes the link between ACSF and convex-layer decomposition (Eppstein et al., 2017; Calder and Smart, 2020), which is restricted to convex curves. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.
MRI Reconstruction Using Deep Bayesian Estimation
Venue: arXiv cs.CV 2022
Year: 2022

Purpose: To develop a deep learning-based Bayesian inference for MRI reconstruction. Methods: We modeled the MRI reconstruction problem with Bayes's theorem, following the recently proposed PixelCNN++ method. The image reconstruction from incomplete k-space measurement was obtained by maximizing the posterior possibility. A generative network was utilized as the image prior, which was computationally tractable, and the k-space data fidelity was enforced by using an equality constraint. The stochastic backpropagation was utilized to calculate the descent gradient in the process of maximum a posterior, and a projected subgradient method was used to impose the equality constraint. In contrast to the other deep learning reconstruction methods, the proposed one used the likelihood of prior as the training loss and the objective function in reconstruction to improve the image quality. Results: The proposed method showed an improved performance in preserving image details and reducing aliasing artifacts, compared with GRAPPA, $\ell_1$-ESPRiT, and MODL, a state-of-the-art deep learning reconstruction method. The proposed method generally achieved more than 5 dB peak signal-to-noise ratio improvement for compressed sensing and parallel imaging reconstructions compared with the other methods. Conclusion: The Bayesian inference significantly improved the reconstruction performance, compared with the conventional $\ell_1$-sparsity prior in compressed sensing reconstruction tasks. More importantly, the proposed reconstruction framework can be generalized for most MRI reconstruction scenarios.
PageRank algorithm for Directed Hypergraph
Venue: arXiv cs.SI 2022
Year: 2022

During the last two decades, we easilly see that the World Wide Web's link structure is modeled as the directed graph. In this paper, we will model the World Wide Web's link structure as the directed hypergraph. Moreover, we will develop the PageRank algorithm for this directed hypergraph. Due to the lack of the World Wide Web directed hypergraph datasets, we will apply the PageRank algorithm to the metabolic network which is the directed hypergraph itself. The experiments show that our novel PageRank algorithm is successfully applied to this metabolic network.
Control of Separable Subsystems with Application to Prostheses
Venue: arXiv cs.RO 2022
Year: 2022

Nonlinear control methodologies have successfully realized stable human-like walking on powered prostheses. However, these methods are typically restricted to model independent controllers due to the unknown human dynamics acting on the prosthesis. This paper overcomes this restriction by introducing the notion of a separable subsystem control law, independent of the full system dynamics. By constructing an equivalent subsystem, we calculate the control law with local information. We build a subsystem model of a general open-chain manipulator to demonstrate the control method's applicability. Employing these methods for an amputee-prosthesis model, we develop a model dependent prosthesis controller that relies solely on measurable states and inputs but is equivalent to a controller developed with knowledge of the human dynamics and states. We demonstrate the results through simulating an amputee-prosthesis system and show the model dependent prosthesis controller performs identically to a feedback linearizing controller based on the whole system, confirming the equivalency.
Bias-Variance Games
Venue: arXiv cs.GT 2022
Year: 2022

Firms engaged in electronic commerce increasingly rely on predictive analytics via machine-learning algorithms to drive a wide array of managerial decisions. The tuning of many standard machine learning algorithms can be understood as trading off bias (i.e., accuracy) with variance (i.e., precision) in the algorithm's predictions. The goal of this paper is to understand how competition between firms affects their strategic choice of such algorithms. To this end, we model the interaction of two firms choosing learning algorithms as a game and analyze its equilibria. Absent competition, players care only about the magnitude of predictive error and not its source. In contrast, our main result is that with competition, players prefer to incur error due to variance rather than due to bias, even at the cost of higher total error. In addition, we show that competition can have counterintuitive implications -- for example, reducing the error incurred by a firm's algorithm can be harmful to that firm -- but we provide conditions under which such phenomena do not occur. In addition to our theoretical analysis, we also validate our insights by applying our metrics to several publicly available datasets.
Cooperative Distributed State Estimation: Resilient Topologies against Smart Spoofers
Venue: arXiv cs.CR 2022
Year: 2022

A network of observers is considered, where through asynchronous (with bounded delay) communications, they cooperatively estimate the states of a Linear Time-Invariant (LTI) system. In such a setting, a new type of adversary might affect the observation process by impersonating the identity of the regular node, which is a violation of communication authenticity. These adversaries also inherit the capabilities of Byzantine nodes, making them more powerful threats called smart spoofers. We show how asynchronous networks are vulnerable to smart spoofing attack. In the estimation scheme considered in this paper, information flows from the sets of source nodes, which can detect a portion of the state variables each, to the other follower nodes. The regular nodes, to avoid being misguided by the threats, distributively filter the extreme values received from the nodes in their neighborhood. Topological conditions based on strong robustness are proposed to guarantee the convergence. Two simulation scenarios are provided to verify the results.
Faster quantum and classical SDP approximations for quadratic binary optimization
Venue: arXiv cs.DS 2022
Year: 2022

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.
Inserting one edge into a simple drawing is hard
Venue: arXiv cs.CG 2022
Year: 2022

A {\em simple drawing} $D(G)$ of a graph $G$ is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge $e$ in the complement of $G$ can be {\em inserted} into $D(G)$ if there exists a simple drawing of $G+e$ extending $D(G)$. As a result of Levi's Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of $G$ can be inserted. In contrast, we show that it is NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles $\mathcal{A}$ and a pseudosegment $σ$, it can be decided in polynomial time whether there exists a pseudocircle $Φ_σ$ extending $σ$ for which $\mathcal{A}\cup\{Φ_σ\}$ is again an arrangement of pseudocircles.
Towards Intelligent Interactive Theatre: Drama Management as a way of Handling Performance
Venue: arXiv cs.AI 2022
Year: 2022

In this paper, we present a new modality for intelligent interactive narratives within the theatre domain. We discuss the possibilities of using an intelligent agent that serves as a drama manager and as an actor that plays a character within the live theatre experience. We pose a set of research challenges that arise from our analysis towards the implementation of such an agent, as well as potential methodologies as a starting point to bridge the gaps between current literature and the proposed modality.
On Communication Complexity of Fixed Point Computation
Venue: arXiv cs.CC 2022
Year: 2022

Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from $[0,1]^n$ to $[0,1]^n$, and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of $2^{Ω(n)}$ for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model. $\bullet$ Each player is given a function from $[0,1]^n$ to $[0,1]^{n/2}$, and their goal is to find an approximate fixed point of the concatenation of the functions. $\bullet$ Each player is given a function from $[0,1]^n$ to $[0,1]^{n}$, and their goal is to find an approximate fixed point of the interpolation of the functions. We show a randomized communication complexity lower bound of $2^{Ω(n)}$ for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulation $T$ of the $d$-simplex is publicly known and one player is given a set $S_A\subset T$ and a coloring function from $S_A$ to $\{0,\ldots ,d/2\}$, and the other player is given a set $S_B\subset T$ and a coloring function from $S_B$ to $\{d/2+1,\ldots ,d\}$, such that $S_A\dot\cup S_B=T$, and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of $|T|^{Ω(1)}$ for the aforementioned problem as well (when $d$ is large).
Impartial Selection with Additive Approximation Guarantees
Venue: arXiv cs.GT 2022
Year: 2022

Impartial selection has recently received much attention within the multi-agent systems community. The task is, given a directed graph representing nominations to the members of a community by other members, to select the member with the highest number of nominations. This seemingly trivial goal becomes challenging when there is an additional impartiality constraint, requiring that no single member can influence her chance of being selected. Recent progress has identified impartial selection rules with optimal approximation ratios. Moreover, it was noted that worst-case instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of the quality of impartial selection. Our positive results include two randomized impartial selection mechanisms which have additive approximation guarantees of $Θ(\sqrt{n})$ and $Θ(n^{2/3}\ln^{1/3}n)$ for the two most studied models in the literature, where $n$ denotes the community size. We complement our positive results by providing negative results for various cases. First, we provide a characterization for the interesting class of strong sample mechanisms, which allows us to obtain lower bounds of $n-2$, and of $Ω(\sqrt{n})$ for their deterministic and randomized variants respectively. Finally, we present a general lower bound of $2$ for all deterministic impartial mechanisms.
Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions
Venue: arXiv cs.DS 2022
Year: 2022

Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduced to an equivalent instance with size upper-bounded by a function of a parameter chosen in advance. Kernelization for weighted problems particularly requires to also shrink weights. Marx and Végh [ACM Trans. Algorithms 2015] and Etscheid et al. [J. Comput. Syst. Sci. 2017] used a technique of Frank and Tardos [Combinatorica 1987] to obtain polynomial-size kernels for weighted problems, mostly with additive goal functions. We characterize the function types that the technique is applicable to, which turns out to contain many non-additive functions. Using this insight, we systematically obtain kernelization results for natural problems in graph partitioning, network design, facility location, scheduling, vehicle routing, and computational social choice, thereby improving and generalizing results from the literature.
Synchronization under Dynamic Constraints
Venue: arXiv cs.FL 2022
Year: 2022

Imagine an assembly line where a box with a lid and liquid in it enters in some unknown orientation. The box should leave the line with the open lid facing upwards with the liquid still in it. To save costs there are no complex sensors or image recognition software available on the assembly line, so a reset sequence needs to be computed. But how can the dependencies of the deforming impact of a transformation of the box, such as 'do not tilt the box over when the lid is open' or 'open the lid again each time it gets closed' be modeled? We present three attempts to model constraints of these kinds on the order in which the states of an automaton are transitioned by a synchronizing word. The first two concepts relate the last visits of states and form constraints on which states still need to be reached, whereas the third concept concerns the first visits of states and forms constraints on which states might still be reached. We examine the computational complexity of different variants of the problem, whether an automaton can be synchronized with a word that respects the constraints defined in the respective concept, and obtain nearly a full classification. While most of the problems are PSPACE-complete we also observe NP-complete variants and variants solvable in polynomial time. We will also observe a drop of the complexity if we track the orders of states on several paths simultaneously instead of tracking the set of active states. Further, we give upper bounds on the length of a synchronizing word depending on the size of the input relation and show that the Cerny conjecture holds for partial weakly acyclic automata.