  We propose and analyze a randomized zeroth-order approach based on
approximating the exact gradient byfinite differences computed in a set of
orthogonal random directions that changes with each iteration. A number
ofpreviously proposed methods are recovered as special cases including
spherical smoothing, coordinate descent, as wellas discretized gradient
descent. Our main contribution is proving convergence guarantees as well as
convergence ratesunder different parameter choices and assumptions. In
particular, we consider convex objectives, but also possiblynon-convex
objectives satisfying the Polyak-{\L}ojasiewicz (PL) condition. Theoretical
results are complemented andillustrated by numerical experiments.
