RESUMEN
Zeroth-order (a.k.a, derivative-free) methods are a class of effective optimization methods for solving complex machine learning problems, where gradients of the objective functions are not available or computationally prohibitive. Recently, although many zeroth-order methods have been developed, these approaches still have two main drawbacks: 1) high function query complexity; 2) not being well suitable for solving the problems with complex penalties and constraints. To address these challenging drawbacks, in this paper, we propose a class of faster zeroth-order stochastic alternating direction method of multipliers (ADMM) methods (ZO-SPIDER-ADMM) to solve the nonconvex finite-sum problems with multiple nonsmooth penalties. Moreover, we prove that the ZO-SPIDER-ADMM methods can achieve a lower function query complexity of [Formula: see text] for finding an ϵ-stationary point, which improves the existing best nonconvex zeroth-order ADMM methods by a factor of [Formula: see text], where n and d denote the sample size and data dimension, respectively. At the same time, we propose a class of faster zeroth-order online ADMM methods (ZOO-ADMM+) to solve the nonconvex online problems with multiple nonsmooth penalties. We also prove that the proposed ZOO-ADMM+ methods achieve a lower function query complexity of [Formula: see text], which improves the existing best result by a factor of [Formula: see text]. Extensive experimental results on the structure adversarial attack on black-box deep neural networks demonstrate the efficiency of our new algorithms.
RESUMEN
In the paper, we study a class of useful minimax problems on Riemanian manifolds and propose a class of effective Riemanian gradient-based methods to solve these minimax problems. Specifically, we propose an effective Riemannian gradient descent ascent (RGDA) algorithm for the deterministic minimax optimization. Moreover, we prove that our RGDA has a sample complexity of O(κ2ϵ-2) for finding an ϵ-stationary solution of the Geodesically-Nonconvex Strongly-Concave (GNSC) minimax problems, where κ denotes the condition number. At the same time, we present an effective Riemannian stochastic gradient descent ascent (RSGDA) algorithm for the stochastic minimax optimization, which has a sample complexity of O(κ4ϵ-4) for finding an ϵ-stationary solution. To further reduce the sample complexity, we propose an accelerated Riemannian stochastic gradient descent ascent (Acc-RSGDA) algorithm based on the momentum-based variance-reduced technique. We prove that our Acc-RSGDA algorithm achieves a lower sample complexity of ~O(κ4ϵ-3) in searching for an ϵ-stationary solution of the GNSC minimax problems. Extensive experimental results on the robust distributional optimization and robust Deep Neural Networks (DNNs) training over Stiefel manifold demonstrate efficiency of our algorithms.
RESUMEN
In the paper, we study a class of novel stochastic composition optimization problems over Riemannian manifold, which have been raised by multiple emerging machine learning applications such as distributionally robust learning in Riemannian manifold setting. To solve these composition problems, we propose an effective Riemannian compositional gradient (RCG) algorithm, which has a sample complexity of O(ϵ-4) for finding an ϵ-stationary point. To further reduce sample complexity, we propose an accelerated momentum-based Riemannian compositional gradient (M-RCG) algorithm. Moreover, we prove that the M-RCG obtains a lower sample complexity of Õ(ϵ-3) without large batches, which achieves the best known sample complexity for its Euclidean counterparts. Extensive numerical experiments on training deep neural networks (DNNs) over Stiefel manifold and learning principal component analysis (PCA) over Grassmann manifold demonstrate effectiveness of our proposed algorithms. To the best of our knowledge, this is the first study of the composition optimization problems over Riemannian manifold.