A Field Guide to Forward-Backward Splitting with a FASTA Implementation

By Tom Goldstein, Christoph Studer, Richard Baraniuk. 2014

252 citations recorded by the source corpus.

Non-differentiable and constrained optimization play a key role in machine learning, signal and image processing, communications, and beyond. For high-dimensional minimization problems involving large datasets or many unknowns, the forward-backward splitting method provides a simple, practical solver. Despite its apparently simplicity, the performance of the forward-backward splitting is highly sensitive to implementation details. This article is an introductory review of forward-backward splitting with a special emphasis on practical implementation concerns. Issues like stepsize selection, acceleration, stopping conditions, and initialization are considered. Numerical experiments are used to compare the effectiveness of different approaches. Many variations of forward-backward splitting are implemented in the solver FASTA (short for Fast Adaptive Shrinkage/Thresholding Algorithm). FASTA provides a simple interface for applying forward-backward splitting to a broad range of problems.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Hardware and Architecture

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Hardware and Architecture

Citations in the corpus

Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks (2018, methodology): “The algorithm uses a forward-backward-splitting iterative procedure [Goldstein et al., 2014].”
FreeLB: Enhanced Adversarial Training for Natural Language Understanding (2019, methodology): “(2018) demonstrated that this saddle-point problem can be solved reliably with SGD for the outer minimization and PGD (a standard method for large-scale constrained optimization, see (Combettes & Pesquet, 2011) and (Goldstein et al., 2014)), for the inner maximization.”
Big Batch SGD: Automated Inference using Adaptive Batch Sizes (2016, methodology): “The BB methods fits a quadratic model to the objective on each iteration, and a stepsize is proposed that is optimal for the local quadratic model [11].”
A Survey on Data Augmentation for Text Classification (2021, unknown): “As described by Zhu et al. [120], projected gradient descent ( PGD ) [121, 122] can be used to solve this.”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, methodology): “We also run simulations using the semideﬁnite relaxation (SDR)-based method PhaseLift [1] implemented via FASTA [38]; this is, together with PhaseCut [19], the only convex alternative to PhaseMax, but lifts the problem to a higher dimension.”
FreeLB: Enhanced Adversarial Training for Language Understanding (2019, methodology): “Nonetheless, Madry et al. (2018) demonstrated that this saddle-point problem can be solved reliably with SGD for the outer minimization and PGD (a standard method for large-scale constrained optimization, see Combettes & Pesquet (2011) and Goldstein et al. (2014)), for the inner maximization.”
Automated Inference with Adaptive Batches (2017, methodology): “Note that, in the case of deterministic gradient descent, the optimal stepsize is simply 1/⌫ (Goldstein et al., 2014).”
Transferable Clean-Label Poisoning Attacks on Deep Neural Nets (2019, methodology): “Given { x ( j ) p } kj =1 , we use forward-backward splitting (Goldstein et al., 2014) to ﬁnd the the optimal sets of coefﬁcients { c ( i ) } .”
Universal Adversarial Training (2018, methodology): “The PGD version of Madry et al. (2018) applies an initial random perturbation before multiple steps of gradient ascent and projection of perturbation onto the norm-ball of interest, and in a standard projected gradient method (Goldstein, Studer, and Baraniuk, 2014).”
Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction (2015, methodology): “For example when f is strongly convex, accelerated ADMM obtains O (1 /k 2 ) convergence (Goldstein et al., 2014a), and if we further assume D has full row rank, R-linear convergence is possible (Deng & Yin, 2012).”
A Comprehensive Survey on Poisoning Attacks and Countermeasures in Machine Learning (2022, methodology): “And they optimized this objective function via a forward-backward-splitting iterative procedure [39].”
Quantized Precoding for Massive MU-MIMO (2016, methodology): “The most prominent methods are forward-backward splitting (FBS) [64], [65] and Douglas-Rachford (DR) splitting [66], [67].”