The Role of Memory in Stochastic Optimization
The choice of how to retain information about past gradients dramatically affects the convergence properties of state-of-the-art stochastic optimization methods, such as Heavy-ball, Nesterov's momentum, RMSprop and Adam. Building on this observation, we use stochastic differential equations (SDEs) to explicitly study the role of memory in gradient-based algorithms. We first derive a general continuous-time model that can incorporate arbitrary types of memory, for both deterministic and stochastic settings. We provide convergence guarantees for this SDE for weakly-quasi-convex and quadratically growing functions. We then demonstrate how to discretize this SDE to get a flexible discrete-time algorithm that can implement a board spectrum of memories ranging from short- to long-term. Not only does this algorithm increase the degrees of freedom in algorithmic choice for practitioners but it also comes with better stability properties than classical momentum in the convex stochastic setting. In particular, no iterate averaging is needed for convergence. Interestingly, our analysis also provides a novel interpretation of Nesterov's momentum as stable gradient amplification and highlights a possible reason for its unstable behavior in the (convex) stochastic setting. Furthermore, we discuss the use of long term memory for second-moment estimation in adaptive methods, such as Adam and RMSprop. Finally, we provide an extensive experimental study of the effect of different types of memory in both convex and nonconvex settings.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
CaMKII activation supports reward-based neural network optimization through Hamiltonian sampling
Synaptic plasticity is implemented and controlled through over thousand different types of molecules in the postsynaptic density and presynaptic boutons that assume a staggering array of different states through phospory…
Memory-Driven Metaheuristics: Improving Optimization Performance
Metaheuristics are stochastic optimization algorithms that mimic natural processes to find optimal solutions to complex problems. The success of metaheuristics largely depends on the ability to effectively explore and ex…
Stochastic OptimizationLattice-based stochastic models motivate non-linear diffusion descriptions of memory-based dispersal
The role of memory and cognition in the movement of individuals (e.g. animals) within a population, is thought to play an important role in population dispersal. In response, there has been increasing interest in incorpo…
Stochastic Optimization for Deep CCA via Nonlinear Orthogonal Iterations
Deep CCA is a recently proposed deep neural network extension to the traditional canonical correlation analysis (CCA), and has been successful for multi-view representation learning in several domains. However, stochasti…
Representation LearningStochastic OptimizationGeometry and Determinism of Optimal Stationary Control in Partially Observable Markov Decision Processes
It is well known that for any finite state Markov decision process (MDP) there is a memoryless deterministic policy that maximizes the expected reward. For partially observable Markov decision processes (POMDPs), optimal…