Fetching the paper…
Reading the bibliography…
In this paper we study the limitations of parallelization in convex optimization.
Parallelism in comparison problems
Leslie G Valiant · 1975
Earlier work this paper cites.
Parallelism in random access machines
Steven Fortune and James Wyllie · 1978
Earlier work this paper cites.
A unified approach to models of synchronous parallel machines
Leslie M. Goldschlager · 1978
Earlier work this paper cites.
Time bounded random access machines with parallel processing
Walter J. Savitch and Michael J. Stimson · 1979
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadii Nemirovski and David Borisovich Yudin · 1983
Earlier work this paper cites.
Lower bounds on communication complexity
Pavol Duris, Zvi Galil, and Georg Schnitger · 1984
Earlier work this paper cites.
Communication complexity
Christos H Papadimitriou and Michael Sipser · 1984
Earlier work this paper cites.
Parallel merge sort
Richard Cole · 1988
Earlier work this paper cites.
Rounds in communication complexity revisited
Noam Nisan and Avi Widgerson · 1991
Earlier work this paper cites.
On parallel complexity of nonsmooth convex optimization
Arkadi Nemirovski · 1994
Earlier work this paper cites.
Information-theoretic lower bounds on the oracle complexity of convex optimization
Alekh Agarwal, Martin J Wainwright, Peter L Bartlett, and Pradeep K Ravikumar · 2009
Earlier work this paper cites.
Compressive distilled sensing: Sparse recovery using adaptivity in compressive measurements
Jarvis D Haupt, Richard G Baraniuk, Rui M Castro, and Robert D Nowak · 2009
Earlier work this paper cites.
Adaptive sensing for sparse signal recovery
Jarvis Haupt, Robert Nowak, and Rui Castro · 2009
Earlier work this paper cites.
Information complexity of black-box convex optimization: A new look via feedback information theory
Maxim Raginsky and Alexander Rakhlin · 2009
Earlier work this paper cites.
On the power of adaptivity in sparse recovery
Piotr Indyk, Eric Price, and David P Woodruff · 2011
Earlier work this paper cites.
Information-based complexity, feedback and dynamics in convex programming
Maxim Raginsky and Alexander Rakhlin · 2011
Cited alongside, same era.
Hogwild: A lock-free approach to parallelizing stochastic gradient descent
Benjamin Recht, Christopher Ré, Stephen J. Wright, and Feng Niu · 2011
Cited alongside, same era.
Randomized smoothing for stochastic optimization
John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright · 2012
Cited alongside, same era.
Optimal distributed online prediction using mini-batches
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao · 2012
Cited alongside, same era.
Introductory lectures on convex optimization: A basic course
Yurii Nesterov · 2013
Cited alongside, same era.
Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes
Ohad Shamir and Tong Zhang · 2013
Minimizing a submodular function from samples
Eric Balkanski and Yaron Singer · 2017
Later among the works it cites.
The sample complexity of optimizing a convex function
Eric Balkanski and Yaron Singer · 2017
Later among the works it cites.
An adaptivity hierarchy theorem for property testing
Clement Canonne and Tom Gur · 2017
Later among the works it cites.
Settling the query complexity of non-adaptive junta testing
Xi Chen, Rocco A Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie · 2017
Later among the works it cites.
Is interaction necessary for distributed private learning?
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay · 2017
Later among the works it cites.
Non-monotone submodular maximization in exponentially fewer iterations
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Convex optimization: Algorithms and complexity
Sébastien Bubeck et al · 2015
Cited alongside, same era.
Parallel algorithms for select and partition with noisy comparisons
Mark Braverman, Jieming Mao, and S Matthew Weinberg · 2016
Cited alongside, same era.
The power of optimization from samples
Eric Balkanski, Aviad Rubinstein, and Yaron Singer · 2016
Cited alongside, same era.
Batched bandit problems
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg, et al · 2016
Cited alongside, same era.
Tight complexity bounds for optimizing composite objectives
Blake E Woodworth and Nati Srebro · 2016
Cited alongside, same era.
Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons
Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna · 2017
Cited alongside, same era.
Eric Balkanski, Adam Breuer, and Yaron Singer · 2018
Closest in time.
Eric Balkanski, Aviad Rubinstein, and Yaron Singer · 2018
Closest in time.
The adaptive complexity of maximizing a submodular function
Eric Balkanski and Yaron Singer · 2018
Closest in time.
Approximation guarantees for adaptive sampling
Eric Balkanski and Yaron Singer · 2018
Closest in time.
Submodular function maximization in parallel via the multilinear relaxation
Chandra Chekuri and Kent Quanrud · 2018
Closest in time.
Minimax bounds on stochastic batched convex optimization
John Duchi, Feng Ruan, and Chulhee Yun · 2018
Closest in time.
Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time
Alina Ene and Huy L Nguyen · 2018
Closest in time.
Submodular maximization with optimal approximation, adaptivity and query complexity
Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam · 2018
Closest in time.
Learning to optimize combinatorial functions
Nir Rosenfeld, Eric Balkanski, Amir Globerson, and Yaron Singer · 2018
Closest in time.
Graph oracle models, lower bounds, and gaps for parallel stochastic optimization
Blake Woodworth, Jialei Wang, Brendan McMahan, and Nathan Srebro · 2018
Closest in time.