Direct-search algorithms are derivative-free optimization techniques that operate by polling the search space along specific directions forming a positive spanning set (PSS). When the variables are constrained to lie in a Riemannian manifold, feasibility dictates these directions to live in tangent spaces. Designing such Riemannian direct-search methods raises a number of questions about their convergence properties and practical efficiency.
In this talk, we provide a complexity analysis for a class of Riemannian direct-search schemes, that depends on the quality of directions used. We then investigate two strategies for building PSSs on manifolds. Projected PSSs are defined by projecting an ambient PSSs at every tangent space, whereas intrinsic PSSs are built by directly operating in the tangent space. Numerical experiments advocate for the use of intrinsic PSSs, especially when the codimension of the manifold is much larger than its intrinsic dimension. As an application, we use Riemannian direct-search methods to perform blackbox adversarial attacks on standard neural networks.