9/27/18 | 4:15pm | E51-335
Reception to follow.

David Goldberg

Associate Professor
Cornell University 

Abstract: The fundamental problems of pricing high-dimensional path-dependent options and optimal stopping are central to applied probability, financial engineering, operations research, and stochastic control. Modern approaches, often relying on ADP, simulation, and/or duality, typically have limited rigorous guarantees, which may scale poorly and/or require previous knowledge of good basis functions. A key difficulty with many approaches is that to yield stronger guarantees, they would necessitate the computation of deeply nested conditional expectations, with the depth scaling with the time horizon T.

We overcome this fundamental obstacle by providing an algorithm which can trade-off between the guaranteed quality of approximation and the level of nesting required in a principled manner. We develop a novel pure-dual approach, inspired by a connection to network flows. This leads to a representation for the optimal value as an infinite sum for which : 1. each term is the expectation of an elegant recursively defined infimum; 2. the first k terms only require k levels of nesting; and 3. truncating at the first k terms yields a (normalized) error of 1/k. This enables us to devise simple randomized and data-driven algorithms and stopping strategies whose runtimes are effectively independent of the dimension, beyond the need to simulate sample paths of the underlying process. Our method allows one to elegantly trade-off between accuracy and runtime through a parameter epsilon controlling the associated performance guarantee (analogous to the notion of PTAS in the theory of approximation algorithms), with computational and sample complexity both polynomial in T (and effectively independent of the dimension) for any fixed epsilon, in contrast to past methods typically requiring a complexity scaling exponentially. Joint work with Ph.D. student Yilun Chen.

Bio: David A. Goldberg is an Associate Professor in Cornell's ORIE department. Previously, he was the A. Russell Chandler III Associate Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. He received his Ph.D. in Operations Research at MIT in 2011, and his B.S. in Computer Science (minors in Operations Research and Applied Math) from Columbia University in 2006. Goldberg’s research is in applied probability, on topics including optimal stopping and options pricing, inventory and queueing models, combinatorial optimization, robust optimization, and multi-arm bandits. His work has been recognized with accolades including an NSF CAREER award, 2015 Nicholson Competition first place, 2015 JFIG Competition second place, and 2014 MSOM and 2010 Nicholson Competitions finalist. He is also an associate editor for the journals Operations Research and Queueing Systems.