Generic Methods for Optimization-Based Modeling

Justin DomkeAISTATS 2012 · OpenReview

Abstract

Energy-based models for continuous domains are versatile tools for various machine learning tasks but often suffer from high computational costs during training. This expense stems from the need to repeatedly minimize the energy function to high accuracy. This paper proposes a modified training setting where the model is optimized based on results after a fixed, truncated number of optimization iterations. We derive "backpropagating" versions of gradient descent (GD), heavy-ball (HB), and LBFGS. These methods are generic, requiring only routines to compute the gradient of the energy with respect to the domain and parameters. Experimental results on image denoising and labeling problems demonstrate that learning with truncated optimization significantly reduces computational expense compared to traditional "full" fitting methods.

Introduction

In many computer vision tasks, such as image denoising or semantic labeling, the output is defined as the solution to an optimization problem: finding the configuration that minimizes a specific "energy" function. Training these energy-based models (EBMs) requires understanding how the final optimized output changes with respect to the model's weights.

The traditional approach, implicit differentiation, assumes the model has reached the exact minimum of the energy function. However, in large-scale problems, reaching a perfect minimum is often computationally prohibitive. When optimization is incomplete, the resulting gradients become inaccurate, frequently leading to training instability or failure. This paper addresses these challenges by introducing a framework that treats the optimization process itself as a differentiable component of the model.

The Back-Optimization Framework

Instead of assuming perfect convergence, we define the model's output as the result of exactly $N$ iterations of a specific optimization algorithm. This allows us to differentiate directly through the optimization steps—a process we call Back-Optimization.

We derive backpropagating variants for three widely used algorithms:

  1. Back-GD: Gradient Descent
  2. Back-HB: Heavy-Ball/Momentum
  3. Back-LBFGS: Limited-memory Broyden–Fletcher–Goldfarb–Shanno

A key technical contribution is the derivation of gradients for LBFGS, involving an efficient differentiation of the two-loop recursion used to estimate the inverse Hessian. These methods are highly accessible; users only need to provide first-order derivatives of the energy function. Second-order information (Hessians) is approximated using finite difference matrix-vector products, removing the need for manual derivation of complex second-order derivatives.

Experimental Evaluation

The proposed methods were evaluated on standard benchmarks, including the Berkeley Segmentation Dataset (for denoising) and the Stanford Backgrounds Dataset (for semantic segmentation).

Performance and Truncation

A primary insight is that truncation is a feature, not a bug. By training the model to perform well after exactly $N$ steps, the model learns to be effective even under strict computational limits. As shown in the performance curves, the back-optimization methods approach the performance of the theoretical implicit limit as the number of iterations $N$ increases.

Training risk and test error as a function of the number of inference iterations N. The horizontal line represents the implicit-cg baseline.

Efficiency and Reliability

In scene labeling tasks, Back-LBFGS emerged as the most efficient method. It achieved lower training risk with fewer energy gradient evaluations compared to Back-GD and Back-HB. Furthermore, back-optimization methods proved more reliable than traditional implicit differentiation (Implicit-CG). Implicit methods are highly sensitive to convergence thresholds; if the threshold is too loose, training risk can paradoxically increase as the model complexity grows.

Training risk compared across learning iterations and total energy gradient evaluations. Back-LBFGS shows superior efficiency in reaching lower risk levels.

Discussion and Conclusion

Back-optimization treats the optimization process as a differentiable layer, a concept that prefigures modern architectures like Deep Equilibrium Models. While Back-LBFGS introduces some memory overhead—requiring $O(ND)$ storage for state vectors—this is manageable for practical values of $N$.

Our results show that training by backpropagating through a truncated optimizer is not only faster but also more robust than assuming full convergence. Future work may involve treating optimization hyperparameters, such as step size and momentum, as learnable parameters, allowing the model to discover the most efficient path to its own energy minimum.

Summary updated

Abstract

Energy” models for continuous domains can be applied to many problems, but often suffer from high computational expense in training, due to the need to repeatedly minimize the energy function to high accuracy. This paper considers a modified setting, where the model is trained in terms of results after optimization is truncated to a fixed number of iterations. We derive “backpropagating” versions of gradient descent, heavy-ball and LBFGS. These are simple to use, as they require as input only routines to compute the gradient of the energy with respect to the domain and parameters. Experimental results on denoising and image labeling problems show that learning with truncated optimization greatly reduces computational expense compared to “full” fitting.
BibTeX
@inproceedings{domke2012generic,
  author = {Justin Domke},
  title = {{Generic Methods for Optimization-Based Modeling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=ghj6zStkcqM},
}
Figure