2 citations · 2 across the 1 of their papers we have counts for
8 papers
Contracts under Moral Hazard and Adverse Selection
Guru Guruganesh, Jon Schneider, Joshua Wang
In the classical principal-agent problem, a principal must design a contract to incentivize an agent to perform an action on behalf of the principal. We study the classical princip…
Recursive Sketches for Modular Deep Learning
Badih Ghazi, Rina Panigrahy, Joshua R. Wang
We present a mechanism to compute a sketch (succinct summary) of how a complex modular deep network processes its inputs. The sketch summarizes essential information about the inpu…
On the Computational Power of Online Gradient Descent
Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang
We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results impl…
An Optimal Algorithm for Online Unconstrained Submodular Maximization
Tim Roughgarden, Joshua R. Wang
We consider a basic problem at the interface of two fundamental fields: submodular optimization and online learning. In the online unconstrained submodular maximization (online USM…
Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
Rad Niazadeh, Tim Roughgarden, Joshua R. Wang
In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. Thi…
Deterministic Time-Space Tradeoffs for k-SUM
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang +1
Given a set of numbers, the -SUM problem asks for a subset of numbers that sums to zero. When the numbers are integers, the time and space complexity of -SUM is generally…