Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEffects for Efficiency: Asymptotic Speedup with First-Class Control
77
0
0.0
(
0
)
Added by
Daniel Hillerstr\\\"om
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the fundamental efficiency of delimited control. Specifically, we show that effect handlers enable an asymptotic improvement in runtime complexity for a certain class of functions. We consider the generic count problem using a pure PCF-like base language $lambda_b$ and its extension with effect handlers $lambda_h$. We show that $lambda_h$ admits an asymptotically more efficient implementation of generic count than any $lambda_b$ implementation. We also show that this efficiency gap remains when $lambda_b$ is extended with mutable state. To our knowledge this result is the first of its kind for control operators.
rate research
Read More
Context-Oriented Programming (COP) is a programming paradigm to encourage modularization of context-dependent software. Key features of COP are layers---modules to describe context-dependent behavioral variations of a software system---and their dynamic activation, which can modify the behavior of multiple objects that have already been instantiated. Typechecking programs written in a COP language is difficult because the activation of a layer can even change objects interfaces. Inoue et al. have informally discussed how to make JCop, an extension of Java for COP by Appeltauer et al., type-safe. In this article, we formalize a small COP language called ContextFJ$_{<:}$ with its operational semantics and type system and show its type soundness. The language models main features of the type-safe version of JCop, including dynamically activated first-class layers, inheritance of layer definitions, layer subtyping, and layer swapping.
Weak-head normalization is inconsistent with functional extensionality in the call-by-name $lambda$-calculus. We explore this problem from a new angle via the conflict between extensionality and effects. Leveraging ideas from work on the $lambda$-calculus with control, we derive and justify alternative operational semantics and a sequence of abstract machines for performing head reduction. Head reduction avoids the problems with weak-head reduction and extensionality, while our operational semantics and associated abstract machines show us how to retain weak-head reductions ease of implementation.
With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, employing diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry.
We investigate the qubit in the hierarchical environment where the first level is just one lossy cavity while the second level is the N-coupled lossy cavities. In the weak coupling regime between the qubit and the first level environment, the dynamics crossovers from the original Markovian to the new non-Markovian and from no-speedup to speedup can be realized by controlling the hierarchical environment, i.e., manipulating the number of cavities or the coupling strength between two nearest-neighbor cavities in the second level environment. And we find that the coupling strength between two nearest-neighbor cavities and the number of cavities in the second level environment have the opposite effect on the non-Markovian dynamics and speedup evolution of the qubit. In addition, in the case of strong coupling between the qubit and the first level environment, we can be surprised to find that, compared with the original non-Markovian dynamics, the added second level environment cannot play a beneficial role on the speedup of the dynamics of the system.
Asynchronous and parallel implementation of standard reinforcement learning (RL) algorithms is a key enabler of the tremendous success of modern RL. Among many asynchronous RL algorithms, arguably the most popular and effective one is the asynchronous advantage actor-critic (A3C) algorithm. Although A3C is becoming the workhorse of RL, its theoretical properties are still not well-understood, including the non-asymptotic analysis and the performance gain of parallelism (a.k.a. speedup). This paper revisits the A3C algorithm with TD(0) for the critic update, termed A3C-TD(0), with provable convergence guarantees. With linear value function approximation for the TD update, the convergence of A3C-TD(0) is established under both i.i.d. and Markovian sampling. Under i.i.d. sampling, A3C-TD(0) obtains sample complexity of $mathcal{O}(epsilon^{-2.5}/N)$ per worker to achieve $epsilon$ accuracy, where $N$ is the number of workers. Compared to the best-known sample complexity of $mathcal{O}(epsilon^{-2.5})$ for two-timescale AC, A3C-TD(0) achieves emph{linear speedup}, which justifies the advantage of parallelism and asynchrony in AC algorithms theoretically for the first time. Numerical tests on synthetically generated instances and OpenAI Gym environments have been provided to verify our theoretical analysis.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
