اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدEffects for Efficiency: Asymptotic Speedup with First-Class Control
77
0
0.0
(
0
)
نشر من قبل
Daniel Hillerstr\\\"om
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 dyna
mic 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$-cal
culus 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, bu
t 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 dynamic
s 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 asynchronou
s 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
