Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions (2021-04-27T00:00:00.000000Z)

TL;DR

This work establishes matrix-based conditions under which the effect of older observations diminishes over time, in a manner analogous to Polyak’s heavy ball momentum, and develops a novel optimization algorithm that considers the entire history of gradients and Hessians when forming an update.

Abstract

To minimize the average of a set of log-convex functions, the stochastic Newton method iteratively updates its estimate using subsampled versions of the full objective’s gradient and Hessian. We contextualize this optimization problem as sequential Bayesian inference on a latent state-space model with a discriminatively-specified observation process. Applying Bayesian filtering then yields a novel optimization algorithm that considers the entire history of gradients and Hessians when forming an update. We establish matrix-based conditions under which the effect of older observations diminishes over time, in a manner analogous to Polyak’s heavy ball momentum. We illustrate various aspects of our approach with an example and review other relevant innovations for the stochastic Newton method.

Authors

Michael C. Burkhart

3 papers

TL;DR

Abstract

Authors

References81 items

The Discriminative Kalman Filter for Bayesian Filtering with Nonlinear and Nongaussian Observation Models

A Stochastic Line Search Method with Expected Complexity Analysis

BehaveNet: nonlinear embedding and Bayesian neural decoding of behavioral videos

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates

A Probabilistic Incremental Proximal Gradient Method

Sub-sampled Newton methods

Robust Closed-Loop Control of a Cursor in a Person with Tetraplegia using Gaussian Process Regression

A Subsampling Line-Search Method with Second-Order Results

Particle Filtering Methods for Stochastic Optimization with Application to Large-Scale Empirical Risk Minimization

A Discriminative Approach to Bayesian Filtering with Applications to Human Neural Decoding

Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods

Adaptive Sampling Strategies for Stochastic Optimization

An investigation of Newton-Sketch and subsampled Newton methods

Stochastic Gradient Descent as Approximate Bayesian Inference

Exact and Inexact Subsampled Newton Methods for Optimization

Sub-sampled Newton Methods with Non-uniform Sampling

Optimization Methods for Large-Scale Machine Learning

Second-Order Stochastic Optimization for Machine Learning in Linear Time

Efficient Second Order Online Learning by Sketching

Convergence rates of sub-sampled Newton methods

Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence

Sketching, Embedding, and Dimensionality Reduction for Information Spaces

Probabilistic Line Searches for Stochastic Optimization

A Filtering Approach to Stochastic Variational Inference

New Insights and Perspectives on the Natural Gradient Method

SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

A particle system for global optimization

Bayesian Filtering and Smoothing

On the importance of initialization and momentum in deep learning

Stochastic variational inference

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Krylov Subspace Descent for Deep Learning

On the Use of Stochastic Hessian Information in Optimization Methods for Machine Learning

Hybrid Deterministic-Stochastic Methods for Data Fitting

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

Online Learning for Latent Dirichlet Allocation

Deep learning via Hessian-free optimization

Stochastic global optimization as a filtering problem

Discriminative Learning for Dynamic State Prediction

Comparative Gene Prediction using Conditional Random Fields

Conditional Random People: Tracking Humans with CRFs and Grid Filters

Elements of Information Theory

Generalized Linear Models

Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes

A survey of truncated-Newton methods

Maximum Entropy Markov Models for Information Extraction and Segmentation

Inference of population structure using multilocus genotype data.

Gaussian filters for nonlinear filtering problems

Adaptive stochastic approximation by the simultaneous perturbation method

Natural Gradient Works Efficiently in Learning

New extension of the Kalman filter to nonlinear systems

Incremental least squares methods and the extended Kalman filter

Fast Exact Multiplication by the Hessian

Novel approach to nonlinear/non-Gaussian Bayesian state estimation

Acceleration of stochastic approximation by averaging

Generalized Linear Models, 2nd Edn.

Efficient Estimations from a Slowly Convergent Robbins-Monro Process

Matrix analysis

On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix

Monte Carlo techniques to estimate the conditional expectation in multi-stage non-linear filtering†

Approximations to optimal nonlinear filters

A Stochastic Approximation Method

Sufficient statistics and intrinsic accuracy

On distributions admitting a sufficient statistic

A Mean-Field Optimal Control Formulation for Global Optimization

Supplementary Material for Stochastic Inference for Scalable Probabilistic Modeling of Binary Matrices

Large-Scale Machine Learning with Stochastic Gradient Descent

Latent Dirichlet Allocation

Elements of information theory (2. ed.)

Gene Prediction with Conditional Random Fields

Sigma-point kalman filters for probabilistic inference in dynamic state-space models

A New Approach to Linear Filtering and Prediction Problems

Simplified neuron model as a principal component analyzer

Minimization of functions having Lipschitz continuous first partial derivatives.