More Like this

1. Randomized Nyström Preconditioning

   https://doi.org/10.1137/21M1466244  

   Frangella, Zachary; Tropp, Joel A.; Udell, Madeleine (June 2023, SIAM Journal on Matrix Analysis and Applications)
2. Randomized Automatic Differentiation

   Oktay, Deniz; McGreivy, Nick; Aduol, Joshua; Beatson, Alex; Adams, Ryan P. (January 2021, International Conference on Learning Representations (ICLR))

   null (Ed.)

   The successes of deep learning, variational inference, and many other fields have been aided by specialized implementations of reverse-mode automatic differentiation (AD) to compute gradients of mega-dimensional objectives. The AD techniques underlying these tools were designed to compute exact gradients to numerical precision, but modern machine learning models are almost always trained with stochastic gradient descent. Why spend computation and memory on exact (minibatch) gradients only to use them for stochastic optimization? We develop a general framework and approach for randomized automatic differentiation (RAD), which can allow unbiased gradient estimates to be computed with reduced memory in return for variance. We examine limitations of the general approach, and argue that we must leverage problem specific structure to realize benefits. We develop RAD techniques for a variety of simple neural network architectures, and show that for a fixed memory budget, RAD converges in fewer iterations than using a small batch size for feedforward networks, and in a similar number for recurrent networks. We also show that RAD can be applied to scientific computing, and use it to develop a low-memory stochastic gradient method for optimizing the control parameters of a linear reaction-diffusion PDE representing a fission reactor. 

   more » « less
3. Randomized Gradient Boosting Machine

   https://doi.org/10.1137/18M1223277  

   Lu, Haihao; Mazumder, Rahul (January 2020, SIAM Journal on Optimization)

   null (Ed.)
4. Randomized weakly admissible meshes

   https://doi.org/10.1016/j.jat.2022.105835  

   Xu, Yiming; Narayan, Akil (January 2023, Journal of Approximation Theory)
5. Selectable Set Randomized Kaczmarz

   https://doi.org/10.1002/nla.2458  

   Yaniv, Yotam; Moorman, Jacob D.; Swartworth, William; Tu, Thomas; Landis, Daji; Needell, Deanna (June 2022, Numerical Linear Algebra with Applications)

   Abstract The Randomized Kaczmarz method (RK) is a stochastic iterative method for solving linear systems that has recently grown in popularity due to its speed and low memory requirement. Selectable Set Randomized Kaczmarz is a variant of RK that leverages existing information about the Kaczmarz iterate to identify an adaptive “selectable set” and thus yields an improved convergence guarantee. In this article, we propose a general perspective for selectable set approaches and prove a convergence result for that framework. In addition, we define two specific selectable set sampling strategies that have competitive convergence guarantees to those of other variants of RK. One selectable set sampling strategy leverages information about the previous iterate, while the other leverages the orthogonality structure of the problem via the Gramian matrix. We complement our theoretical results with numerical experiments that compare our proposed rules with those existing in the literature. 

   more » « less