Adaptive Stochastic Optimisation of Nonconvex Composite Objectives

K are sparsity promoting, such as the black-box adversarial attack [4], model agnostic methods for explaining machine learning models [37] and sparse cox regression [34]. Despite the low dimensional structure restricted by r and K, standard stochastic mirror descent methods [27] and the conditional gradient methods [19] have oracle complexity depending linearly on d and are not optimal for high dimensional problems. The gradient descent algorithm is dimensionality independent when the first-order information is available [38]. For black-box objective functions, stronger dependence of the oracle complexity on dimensionality is caused by the biased gradient estimation [21]. In [50], the authors have proposed a LASSO-based gradient estimator for zerothorder optimisation of unconstrained convex objective functions.