DEEP FRANK-WOLFE FOR NEURAL NETWORK OPTIMIZATION
Learning a deep neural network requires solving a challenging optimization problem: it is a high-dimensional, non-convex and non-smooth minimization problem with a large number of terms. The current practice in neural network optimization is to rely on the stochastic gradient descent (SGD) algorithm or its adaptive variants. However, SGD requires a hand-designed schedule for the learning rate. In addition, its adaptive variants tend to produce solutions that generalize less well on unseen data than SGD with a hand-designed schedule. We present an optimization method that offers empirically the best of both worlds: our algorithm yields good generalization performance while requiring only one hyper-parameter. Our approach is based on a composite proximal framework, which exploits the compositional nature of deep neural networks and can leverage powerful convex optimization algorithms by design. Specifically, we employ the Frank-Wolfe (FW) algorithm for SVM, which computes an optimal step-size in closed-form at each time-step. We further show that the descent direction is given by a simple backward pass in the network, yielding the same computational cost per iteration as SGD. We present experiments on the CIFAR and SNLI data sets, where we demonstrate the significant superiority of our method over Adam, Adagrad, as well as the recently proposed BPGrad and AMSGrad. Furthermore, we compare our algorithm to SGD with a hand-designed learning rate schedule, and show that it provides similar generalization while often converging faster. The code is publicly available at https://github.com/oval-group/dfw.
Dual Block-Coordinate Frank-Wolfe (Dual-BCFW) has been widely used in the literature of non-smooth and strongly-convex stochastic optimization problems, such as (structural) Support Vector Machine. To my knowledge, the submission is the first sound attempt to adapt this type of Dual-based algorithm for optimization of Deep Neural Network, which employs a proximal-point method that linearizes not the whole loss function but only the DNN (up to the logits) to form a convex subproblem and then deal with the loss part in the dual.
The attempt is not perfect (actually with a couple of issues detailed below), but the proposed approach is inspiring and I personally would love it published to encourage more development along this thread.  The following points out a couple of items that could probably help further improve the paper.
*FW vs BCFW*
The algorithm employed in the paper is actually not Frank-Wolfe (FW) but Block-Coordinate Frank-Wolfe (BCFW), as it minimizes w.r.t. a block of dual variables belonging to the min-batch of samples.
*Batch Size*
Though the algorithm can be easily extended to the min-batch case, the author should discuss more how the batch size is interpreted in this case (i.e. minimizing w.r.t. a larger block of dual variables belonging to the batch of samples) and the algorithmic block (Algorithm 1) should be presented in a way reflecting the batch size since this is the way people use an algorithm in practice (to improve the utilization rate of a GPU).
*Convex-Conjugate Loss*
The Dual FW algorithm does not need to be used along with the hinge loss (SVM loss). All convex loss function can derive a dual formulation based on its convex-conjugate. See [1,2] for examples. It would be more insightful to compare SGD vs dual-BCFW when both of them are optimizing the same loss functions (either hinge loss or cross-entropy loss) in the experimental comparison.
[1] Shalev-Shwartz, Shai, and Tong Zhang. "Stochastic dual coordinate ascent methods for regularized loss minimization." JMLR (2013)
[2] Tomioka, Ryota, Taiji Suzuki, and Masashi Sugiyama. "Super-linear convergence of dual augmented Lagrangian algorithm for sparsity regularized estimation." JMLR (2011).
*BCFW vs BCD*
Actually, (Lacoste-Julien, S. et al., 2013) proposes Dual-BCFW to optimize structural SVM because the problem contains exponentially many number of dual variables. For typical multiclass hinge loss problem the Dual Block-Coordinate Descent that minimizes w.r.t. all dual variables of a sample in a closed-form update converges faster without extra computational cost. See the details in, for example, [3, appendix for the multiclass hinge loss case].
[3] Fan, Rong-En, et al. "LIBLINEAR: A library for large linear classification." JMLR (2008).
*Hyper-Parameter*
The proposed dual-BCFW still contains a hyperparameter (eta) due to the need to introduce a convex subproblem, which makes its number of hyperparameters still the same to SGD.