A Pruned Shortest Path Algorithm for L_0 Optimization Problems with Rockafellian Perturbations
Date:
In this presentation we propose an optimization-based approach to timeseries breakpoint detection and attribution, where the target time-series is a function of an arbitrary number of “feature” timeseries. We tackle this problem by first introducing a general loss function with $L_0$ regularization along with a dual formulation. We then reformulate the dual into a shortest path problem which we solve by developing several specialized lazy path finding algorithms. We conclude with some theoretical analysis of the efficiency of our proposed algorithms along with a use case in marketing strategy