SGB: Stochastic Gradient Bound Method for Optimizing Partition Functions

Jing Wang, Anna Choromanska

Abstract

This paper addresses the problem of optimizing partition functions in a stochastic learning setting. We propose a stochastic variant of the bound majorization algorithm that relies on upper-bounding the partition function with a quadratic surrogate. The update of the proposed method, that we refer to as Stochastic Partition Function Bound (SPFB), resembles scaled stochastic gradient descent where the scaling factor relies on a second order term that is however different from the Hessian. Similarly to quasi-Newton schemes, this term is constructed using the stochastic approximation of the value of the function and its gradient. We prove sub-linear convergence rate of the proposed method and show the construction of its low-rank variant (LSPFB). Experiments on logistic regression demonstrate that the proposed schemes significantly outperform SGD. We also discuss how to use quadratic partition function bound for efficient training of deep learning models and in non-convex optimization.

Introduction: The Partition Function Challenge

In machine learning, probability distributions must be normalized to sum to one. This normalization factor, known as the partition function, is often the most computationally expensive part of training models like logistic regression or deep neural networks. While traditional "batch" methods like bound majorization offer stability, they are impractical for large-scale datasets. This work introduces a stochastic approach to bridge the gap between stable bound-based optimization and the efficiency of mini-batch processing.

Stochastic Partition Function Bound (SPFB)

The core innovation is the Stochastic Partition Function Bound (SPFB). It adapts the principle of bound majorization—where a complex objective is optimized via a simpler quadratic upper-bound surrogate—to a stochastic setting.

The Update Mechanism

The SPFB update rule resembles a scaled version of Stochastic Gradient Descent (SGD): $$\theta_{t+1} = \theta_t - \eta_t \Sigma_t^{-1} g_t$$ Here, $\Sigma_t$ is a second-order term derived from the quadratic bound. Unlike the Hessian used in Newton's method, $\Sigma_t$ ensures that the surrogate function remains a global upper bound of the true objective at each step. This provides a level of stability that local approximations often lack.

Training loss on the KMNIST dataset. The inset highlights the smooth convergence of SPFB compared to the noisier SGD baseline.

Efficiency via Low-Rank Approximation (LSPFB)

To handle high-dimensional feature spaces where inverting a $d \times d$ matrix is prohibitive ($O(d^3)$), the authors propose LSPFB. By utilizing a low-rank approximation ($k \ll d$) and the Woodbury matrix identity, the computational cost is reduced to $O(k^3)$, making the method competitive with first-order optimizers in terms of per-iteration speed while retaining second-order-like convergence properties.

Empirical Evaluation

The proposed methods were tested against standard SGD on three benchmark datasets for $\ell_2$-regularized logistic regression: Adult, KMNIST, and Fashion-MNIST.

Key Results

The experimental results consistently show that SPFB and LSPFB outperform SGD in both convergence speed and final accuracy across all metrics.

Comprehensive performance comparison of SPFB, LSPFB, and SGD across Adult, Fashion-MNIST, and KMNIST datasets.

As seen in the figure above, SPFB (blue) and LSPFB (orange) converge significantly faster than SGD (green). Notably, even the low-rank variant (LSPFB) maintains a substantial lead over SGD, demonstrating that the quadratic bound captures essential curvature information even with limited rank. The stability of the bounding approach is evident in the smoother, more rapid descent compared to the baseline.

Conclusion and Future Directions

SPFB offers a robust alternative to SGD for problems involving partition functions. While currently demonstrated on convex logistic regression, the authors suggest its potential for deep learning. By applying per-layer quadratic bounds, the method could potentially bias training toward "wide valleys" in the loss landscape, improving generalization in non-convex neural networks. Future work will explore super-linear convergence in batch settings and large-scale deep learning applications.

Summary updated

Abstract

This paper addresses the problem of optimizing partition functions in a stochastic learning setting. We propose a stochastic variant of the bound majorization algorithm that relies on upper-bounding the partition function with a quadratic surrogate. The update of the proposed method, that we refer to as Stochastic Partition Function Bound (SPFB), resembles scaled stochastic gradient descent where the scaling factor relies on a second order term that is however different from the Hessian. Similarly to quasi-Newton schemes, this term is constructed using the stochastic approximation of the value of the function and its gradient. We prove sub-linear convergence rate of the proposed method and show the construction of its low-rank variant (LSPFB). Experiments on logistic regression demonstrate that the proposed schemes significantly outperform SGD. We also discuss how to use quadratic partition function bound for efficient training of deep learning models and in non-convex optimization.
BibTeX
@misc{wang2020sgb,
  author = {Jing Wang and Anna Choromanska},
  title = {{SGB: Stochastic Gradient Bound Method for Optimizing Partition Functions}},
  year = {2020},
  eprint = {2011.01474},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.01474},
}
Figure