A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning

Abstract

In this paper, we show how to transform any optimization problem that arises from fitting a machine learning model into one that (1) detects and removes contaminated data from the training set while (2) simultaneously fitting the trimmed model on the uncontaminated data that remains. To solve the resulting nonconvex optimization problem, we introduce a fast stochastic proximal-gradient algorithm that incorporates prior knowledge through nonsmooth regularization. For datasets of size $n$, our approach requires $O(n^{2/3}/\epsilon )$ gradient evaluations to reach $\epsilon$-accuracy and, when a certain error bound holds, the complexity improves to $O(\kappa n^{2/3}\log (1/\epsilon ))$. These rates are $n^{1/3}$ times better than those achieved by typical, full gradient methods.

33 pages, 5 figures

References in corpus (5)

• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• Non-smooth Variable Projection

Cited by in corpus (7)

• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Non-smooth Variable Projection
• Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth Optimization
• Robust Learning of Trimmed Estimators via Manifold Sampling