Abstract

 Adaptive stochastic gradient methods such as A DAG RAD 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 A DAG RAD is expected to attain better performance, however in high dimensions it is computationally impractical. We present A DA LR and R ADAG RAD two computationally efficient approximations to full-matrix A DAG RAD based on randomized dimensionality reduction. They are able to capture dependencies between features and achieve similar performance to full-matrix A DAG RAD but at a much smaller computational cost. We show that the regret of A DA LR is close to the regret of full-matrix A DAG RAD which can have an up-to exponentially smaller dependence on the dimension than the diagonal variant. Empirically, we show that A DA LR and R ADAG RAD perform similarly to full-matrix A DAG RAD. On the task of training convolutional neural networks as well as recurrent neural networks, R ADAG RAD achieves faster convergence than diagonal A DAG RAD.