  We propose a novel data-driven framework for algorithmic recourse that offers
users interventions to change their predicted outcome. Existing approaches to
compute recourse find a set of points that satisfy some desiderata -- e.g. an
intervention in the underlying causal graph, or minimizing a cost function.
Satisfying these criteria, however, requires extensive knowledge of the
underlying model structure, often an unrealistic amount of information in
several domains. We propose a data-driven, computationally efficient approach
to computing algorithmic recourse. We do so by suggesting directions in the
data manifold that users can take to change their predicted outcome. We present
Stepwise Explainable Paths (StEP), an axiomatically justified framework to
compute direction-based algorithmic recourse. We offer a thorough empirical and
theoretical investigation of StEP. StEP offers provable privacy and robustness
guarantees, and outperforms the state-of-the-art on several established
recourse desiderata.
