Variational Adaptive-Newton Method for Explorative Learning

Mohammad Emtiyaz Khan, Wu Lin, Voot Tangkaratt, Zuozhu Liu, Didrik NielsenarXiv 2017 · OpenReview

Introduction

In modern machine learning, agents must often explore their environments to acquire informative data—a challenge central to active learning and reinforcement learning (RL). While Bayesian methods provide a principled framework for exploration by maintaining a posterior distribution over parameters, they are often computationally prohibitive for large-scale problems. Conversely, standard continuous optimization methods like Stochastic Gradient Descent (SGD) or Newton's method are efficient but only provide point estimates, failing to facilitate parameter-space exploration.

The Variational Adaptive-Newton (VAN) method bridges this gap. It is a black-box optimization algorithm that enables efficient explorative learning by optimizing a variational distribution over parameters using a second-order mirror-descent approach, providing the benefits of Bayesian exploration with the efficiency of classical optimization.

The Variational Adaptive-Newton (VAN) Method

Instead of directly minimizing a loss function $f(\theta)$, VAN frames the problem as Variational Optimization (VO), minimizing the expectation of the loss over a Gaussian distribution $q(\theta|\mu, \Sigma)$:

$$\min_{\mu, \Sigma} \mathbb{E}_{q(\theta|\mu, \Sigma)} [f(\theta)]$$

Visualization of the Variational Optimization process. VAN optimizes the expectation of the function, effectively smoothing the landscape and allowing for distribution-based exploration.

VAN updates the distribution parameters using a mirror-descent algorithm with a Kullback-Leibler (KL) divergence penalty, which is equivalent to taking natural-gradient steps. The resulting update rule resembles Newton's method but utilizes a precision matrix that maintains a running sum of past averaged Hessians. To scale to deep learning, the authors introduced sVAN-D (stochastic VAN with diagonal covariance), which uses the reparameterization trick to efficiently estimate the Hessian diagonal. They also introduced sVAG (a Gauss-Newton variant) to handle non-convex problems where the Hessian might not be positive semi-definite.

Experimental Results

The authors evaluated VAN across diverse benchmarks, including Lasso regression, logistic regression, Variational Auto-Encoders (VAEs), and Reinforcement Learning.

In Reinforcement Learning, VAN-based parameter exploration (sVAN-D and sVAG-D) demonstrated significant advantages. By sampling policy weights from the learned Gaussian distribution, agents achieved rich, temporally consistent exploratory behavior. On the OpenAI Gym HalfCheetah task, VAN-based methods achieved test rewards near 5,000, vastly outperforming standard SGD and Variational SGD baselines.

Test rewards on the HalfCheetah environment. sVAN-D variants significantly outperform standard SGD and V-SGD by enabling effective parameter-space exploration.

In Active Learning on the USPS dataset, sVAN was used to query the most uncertain samples based on entropy, achieving low test loss with significantly fewer data passes than standard stochastic learning. For Lasso Regression, sVAN successfully optimized the non-differentiable objective, showing superior early-pass data efficiency compared to iterative-Ridge methods.

Discussion and Insights

A key insight of VAN is its ability to smooth the loss landscape. By optimizing the expectation of a function, VAN can handle non-differentiable objectives (like L1 penalties) and step over shallow local minima. Furthermore, VAN provides a theoretical unification of continuous optimization (Newton's method), Variational Inference (Conjugate-Computation VI), and Natural Evolution Strategies (NES).

Limitations and Future Work

The current implementation of sVAN-D relies on a diagonal approximation of the covariance matrix for high-dimensional problems. While efficient, this ignores parameter correlations, which may be important in complex landscapes. Future work includes developing versions of VAN that capture these correlations more effectively and exploring non-Gaussian distributions (e.g., Student-t or Cauchy) to encourage more aggressive exploration.

Summary updated

Abstract

We present the Variational Adaptive Newton (VAN) method which is a black-box optimization method especially suitable for explorative-learning tasks such as active learning and reinforcement learning. Similar to Bayesian methods, VAN estimates a distribution that can be used for exploration, but requires computations that are similar to continuous optimization methods. Our theoretical contribution reveals that VAN is a second-order method that unifies existing methods in distinct fields of continuous optimization, variational inference, and evolution strategies. Our experimental results show that VAN performs well on a wide-variety of learning tasks. This work presents a general-purpose explorative-learning method that has the potential to improve learning in areas such as active learning and reinforcement learning.
BibTeX
@misc{khan2017variational,
  author = {Mohammad Emtiyaz Khan and Wu Lin and Voot Tangkaratt and Zuozhu Liu and Didrik Nielsen},
  title = {{Variational Adaptive-Newton Method for Explorative Learning}},
  year = {2017},
  eprint = {1711.05560},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.05560},
}
Figure