Scalable Adaptive Stochastic Optimization Using Random Projections
Adaptive stochastic gradient methods such as ADAGRAD have gained popularity in particular for training deep neural networks. The most commonly used and studied variant maintains a diagonal matrix approximation to second order information by accumulating past gradients which are used to tune the step size adaptively. In certain situations the full-matrix variant of ADAGRAD is expected to attain better performance, however in high dimensions it is computationally impractical. We present ADA-LR and RADAGRAD two computationally efficient approximations to full-matrix ADAGRAD based on randomized dimensionality reduction. They are able to capture dependencies between features and achieve similar performance to full-matrix ADAGRAD but at a much smaller computational cost. We show that the regret of ADA-LR is close to the regret of full-matrix ADAGRAD which can have an up-to exponentially smaller dependence on the dimension than the diagonal variant. Empirically, we show that ADA-LR and RADAGRAD perform similarly to full-matrix ADAGRAD. On the task of training convolutional neural networks as well as recurrent neural networks, RADAGRAD achieves faster convergence than diagonal ADAGRAD.
This paper formally proposes two algorithms: ADA-LR and RADAGRAD, which are computationally efficient approximations of ADAGRAD when using a full matrix approximation for the proximal term. The authors use ADA-FULL for this full-matrix method and use ADAGRAD to refer to the most common variant where one uses a diagonal matrix approximation. Though ADAGRAD performs well in practice, the authors argue that when data has low effective rank, the regret of ADAGRAD is substantially worse than ADA-FULL, and the problem is exacerbated in high dimensions (e.g., the combined weight vector for deep neural networks). This therefore motivates the use of their two algorithms to approximate ADA-FULL. ADA-LR is an approximation based on random projections, and RADAGRAD takes this a step further by using more randomized methods. The authors also identify additional improvements to RADAGRAD for practical performance benefits. Their experimental results on image recognition (using convolutional neural networks) and language modeling (using long short term memory networks) show that the performance of their algorithms is comparable to or superior than the state of the art.       
       I am generally impressed with this paper. The introduction gives convincing arguments for the need to modify ADAGRAD/ADA-FULL in the prevalence of low effective rank data. Then the paper introduces and describes the new algorithms as a series of matrix operations to approximate ADA-FULL. Then it provides some theoretical results (deferring proofs to the appendix) and presents three sets of experiments. This is a logical progression of the material.              In the related work section, you might wish to remove the second paragraph in favor of other references that argue about the prevalence of low effective rank data. The second paragraph, while certainly conceptually related to the paper, doesn't have anything saying its explicit relation. For instance, having something like "variance reduced SGD algorithms have vastly superior performance BUT perform extremely poorly on low effective rank data" would be helpful to understand its context. I suggest this because the paper's contribution is only going to be as good as the prevalence of low effective rank data in the real world, and this is the recurring theme that must be emphasized.              The algorithms appear useful and insightful, and involve "just" a series of matrix operations simple enough so that an alert reader should be able to code it up. It seems a little awkward to include ADA-VR when, as far as I can tell, there's virtually no reason to use it over RADAGRAD, but it makes the paper's story proceed nicely so I guess it's OK. The table in Appendix A is enormously helpful. Thank you for including this.              The experiments the authors chose to run seem reasonable to me given the research goals (and the 9-page space constraint). The first experiment is logical to include since it provides the best-case scenario for the algortihms, and they certainly perform well. The second experiment presented in Figure 2 is, to me, the most interesting one of the paper. My main concern there pertains to your comment about using RADAGRAD only for the convolutional layers. It seems like a fairer comparision would be to use RADAGRAD for everything or ADAGRAD for everything? I think more discussion about this is worthier than the earlier discussion about the implementation; there's little reason to talk about the code beyond that it was implemented in Lasagne/Theano/Python.              I am also intrigued by the third experiment due to the growing importance of LSTMs nowadays. However, the performance benefits over ADAGRAD+SVRG seem extremely minor, even when taking into account the log scale. Is there a way to explain intuitively what this extra benefit means? You might explain this and delete the second paragraph in Section 5, which doesn't seem to make sense for the paper (the forgetting schemes were never discussed earlier).              Despite some nitpicks over the experiments, as mentioned earlier I have a positive impression on this paper, and lean towards its acceptance to NIPS. It introduces an important extension to the widely-used ADAGRAD function and argues that these algorithms are needed when we have low effective rank data. While it is not as groundbreaking as the original ADAGRAD paper, I believe the research contribution is substantial enough to warrant consideration to NIPS.              Minor comments:       In line 108, you might wish to say "borrowing the $g_{1:T,j}$ notation" or something like that, because the notation is never explicitly defined in this paper, but is used later (e.g., in Equation 2).       In lines 124 through 128 and including Equation 2, I am unable to derive the first part of Equation 2. I am also unsure why you assume $g_t \propto Mx_t$, because M is later revealed to be a scalar, so why the need for the proportional symbol? That constant can be absorbed into M. I once thought it should be something like $\|g_t\|_2 \le M\|x_t\|_2$ but perhaps the authors could clarify.       In line 145, did you mean to say "applicable in this low-dimensional *space*"?       In line 192, "it's" should be "its".       In Figure 1, please be consistent and use ADA-FULL instead of ADA-F, since the former is used throughout the paper's text.       In Figure 1(b), you might consider using the same number of principal components for RADAGRAD and ADA-LR. I think one has 21 and another has 28, and I believe these values come from the top $\tau$ singular values, so you might want to make them equal, or otherwise explain your choice for $\tau$. I'm not sure why there's a difference right now. I'm assuming $\tau$ is just chosen heuristically?       In line 268, "A the end" should be "At the end".       In line 397 (in Appendix), the title of C.1 is misleading, it should be the regret bound for ADA-LR, not RADAGRAD.