Timezone: »
Derivative Free Optimization (DFO) is attractive when the objective function's derivatives are not available and evaluations are costly. Moreover, if the function evaluations are noisy, then approximating gradients by finite differences is difficult. This paper gives quantitative lower bounds on the performance of DFO with noisy function evaluations, exposing a fundamental and unavoidable gap between optimization performance based on noisy evaluations versus noisy gradients. This challenges the conventional wisdom that the method of finite differences is comparable to a stochastic gradient. However, there are situations in which DFO is unavoidable, and for such situations we propose a new DFO algorithm that is proved to be near optimal for the class of strongly convex objective functions. A distinctive feature of the algorithm is that it only uses Boolean-valued function comparisons, rather than evaluations. This makes the algorithm useful in an even wider range of applications, including optimization based on paired comparisons from human subjects, for example. Remarkably, we show that regardless of whether DFO is based on noisy function evaluations or Boolean-valued function comparisons, the convergence rate is the same.
Author Information
Kevin G Jamieson (University of Wisconsin)
Rob Nowak (Wisconsin)
Benjamin Recht (UW-Madison)
More from the Same Authors
-
2016 Poster: Finite Sample Prediction and Recovery Bounds for Ordinal Embedding »
Lalit Jain · Kevin Jamieson · Rob Nowak -
2015 Workshop: Multiresolution methods for large-scale learning »
Inderjit Dhillon · Risi Kondor · Rob Nowak · Michael O'Neil · Nedelina Teneva -
2015 Poster: NEXT: A System for Real-World Development, Evaluation, and Application of Active Learning »
Kevin G Jamieson · Lalit Jain · Chris Fernandez · Nicholas J. Glattard · Rob Nowak -
2015 Spotlight: NEXT: A System for Real-World Development, Evaluation, and Application of Active Learning »
Kevin G Jamieson · Lalit Jain · Chris Fernandez · Nicholas J. Glattard · Rob Nowak -
2013 Workshop: Large Scale Matrix Analysis and Inference »
Reza Zadeh · Gunnar Carlsson · Michael Mahoney · Manfred K. Warmuth · Wouter M Koolen · Nati Srebro · Satyen Kale · Malik Magdon-Ismail · Ashish Goel · Matei A Zaharia · David Woodruff · Ioannis Koutis · Benjamin Recht -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2013 Poster: Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis »
Nikhil Rao · Christopher R Cox · Rob Nowak · Timothy T Rogers -
2013 Spotlight: Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis »
Nikhil Rao · Christopher R Cox · Rob Nowak · Timothy T Rogers -
2012 Poster: Factoring nonnegative matrices with linear programs »
Benjamin Recht · Christopher Re · Joel A Tropp · Victor Bittorf -
2012 Spotlight: Factoring nonnegative matrices with linear programs »
Benjamin Recht · Christopher Re · Joel A Tropp · Victor Bittorf -
2011 Poster: Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent »
Benjamin Recht · Christopher Re · Stephen Wright · Feng Niu -
2011 Poster: Active Ranking using Pairwise Comparisons »
Kevin G Jamieson · Rob Nowak -
2010 Poster: Transduction with Matrix Completion: Three Birds with One Stone »
Andrew B Goldberg · Jerry Zhu · Benjamin Recht · Junming Sui · Rob Nowak -
2010 Poster: Practical Large-Scale Optimization for Max-norm Regularization »
Jason D Lee · Benjamin Recht · Russ Salakhutdinov · Nati Srebro · Joel A Tropp -
2009 Poster: Noisy Generalized Binary Search »
Rob Nowak -
2009 Session: Oral Session 1: Information Theory and Estimation »
Rob Nowak -
2008 Poster: Human Active Learning »
Jerry Zhu · Rui M Castro · Timothy T Rogers · Rob Nowak · Ruichen Qian · Chuck Kalish -
2008 Poster: Unlabeled data: Now it helps, now it doesn't »
Aarti Singh · Rob Nowak · Jerry Zhu -
2008 Oral: Unlabeled data: Now it helps, now it doesn't »
Aarti Singh · Rob Nowak · Jerry Zhu -
2006 Poster: Inferring Network Structure from Co-Occurrences »
Michael Rabbat · Mario T Figueiredo · Rob Nowak