Author name cluster

Larry Rudolph

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

ICLR Conference 2020 Conference Paper

A Closer Look at Deep Policy Gradients

Andrew Ilyas
Logan Engstrom
Shibani Santurkar
Dimitris Tsipras
Firdaus Janoos
Larry Rudolph
Aleksander Madry

We study how the behavior of deep policy gradient algorithms reflects the conceptual framework motivating their development. To this end, we propose a fine-grained analysis of state-of-the-art methods based on key elements of this framework: gradient estimation, value prediction, and optimization landscapes. Our results show that the behavior of deep policy gradient algorithms often deviates from what their motivating framework would predict: surrogate rewards do not match the true reward landscape, learned value estimators fail to fit the true value function, and gradient estimates poorly correlate with the "true" gradient. The mismatch between predicted and empirical behavior we uncover highlights our poor understanding of current methods, and indicates the need to move beyond current benchmark-centric evaluation methods.

Details

ICLR Conference 2020 Conference Paper

Implementation Matters in Deep RL: A Case Study on PPO and TRPO

Logan Engstrom
Andrew Ilyas
Shibani Santurkar
Dimitris Tsipras
Firdaus Janoos
Larry Rudolph
Aleksander Madry

We study the roots of algorithmic progress in deep policy gradient algorithms through a case study on two popular algorithms: Proximal Policy Optimization (PPO) and Trust Region Policy Optimization (TRPO). Specifically, we investigate the consequences of "code-level optimizations:" algorithm augmentations found only in implementations or described as auxiliary details to the core algorithm. Seemingly of secondary importance, such optimizations turn out to have a major impact on agent behavior. Our results show that they (a) are responsible for most of PPO's gain in cumulative reward over TRPO, and (b) fundamentally change how RL methods function. These insights show the difficulty, and importance, of attributing performance gains in deep reinforcement learning.

Details

TCS Journal 1990 Journal Article

A complexity theory of efficient parallel algorithms

Clyde P. Kruskal
Larry Rudolph
Marc Snir

This paper outlines a theory of parallel algorithms that emphasizes two crucial aspects of parallel computation: speedup the improvement in running time due to parallelism, and efficiency, the ratio of work done by a parallel algorithm to the work done by a sequential algorithm. We define six classes of algorithms in these terms; of particular interest is the class, EP, of algorithms that achieve a polynomial speedup with constant efficiency. The relations between these classes are examined. We investigate the robustness of these classes across various models of parallel computation. To do so, we examine simulations across models where the simulating machine may be smaller than the simulated machine. These simulations are analyzed with respect to their efficiency and to the reduction in the number of processors. We show that a large number of parallel computation models are related via efficient simulations, if a polynomial reduction of the number of processors is allowed. This implies that the classes EP is invariant across all these models. Many open problems motivated by our approch are listed.

Details DOI

TCS Journal 1989 Journal Article

Techniques for parallel manipulation of sparse matrices

Clyde P. Kruskal
Larry Rudolph
Marc Snir

New techniques are presented for the manipulation of sparse matrices on parallel MIMD computers. We consider the following problems: matrix addition, matrix multiplication, row and column permutation, matrix transpose, matrix vector multiplication, and Gaussian elimination.

Details DOI

FOCS Conference 1986 Conference Paper

Competitive Snoopy Caching

Anna R. Karlin
Mark S. Manasse
Larry Rudolph
Daniel Dominic Sleator

In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. For several of the proposed models of snoopy caching, we present new on-line algorithms which decide, for each cache, which blocks to retain and which to drop in order to minimize communication over the bus. We prove that, for any sequence of operations, our algorithms' communication costs are within a constant factor of the minimum required for that sequence; for some of our algorithms we prove that no on-line algorithm has this property with a smaller constant.

Details

FOCS Conference 1984 Conference Paper

Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers

Ravindran Kannan
Gary L. Miller
Larry Rudolph

The advent of practical parallel processors has caused a reexamination of many existing algorithms with the hope of discovering a parallel implementation. One of the oldest and best known algorithms is Euclid's algorithm for computing the greatest common divisor (GCD). In this paper we present a parallel algorithm to compute the GCD of two integers. The two salient features of the algorithm are: the observation based on the pigeon hole principle that we can easily find an integer combination of the two integers A and B which has fewer bits than n and the idea of working in phases so as to perform arithmetics on n-bit integers only once every phase, the more frequent operations being performed on O(log/sup 2/n)-bit integers. It appears that yet another approach is needed if the GCD is to be computed in poly-log parallel time.

Details