PaperlayerView exact revision on arXiv

Source-linked AI summary

HyperMC: Multi-Fidelity Hyperparameter Tuning for Stochastic Gradient MCMC

Ming Tan, Xiyun Jiao

arXiv:2609.02138v1stat.MLcs.LGstat.CO

TL;DR

SGMCMC lacks acceptance-rate diagnostics even though its performance depends strongly on interacting hyperparameters. HyperMC combines multi-fidelity Hyperband allocation with KSD evaluation, while Robust HyperMC adds global-grid and elite-guided refinement. Experiments report competitive or improved posterior and calibration outcomes, with more stable Robust HyperMC tuning and theoretical near-optimality guarantees under stated conditions.

  • Problem

    SGMCMC tuning lacks directly applicable acceptance-rate diagnostics and must address several interacting hyperparameters affecting performance.

  • Method

    HyperMC combines multiple Hyperband successive-halving brackets with KSD-based evaluation, while Robust HyperMC uses global-grid initialization and elite-guided local refinement.

  • Results

    Across logistic regression, probabilistic matrix factorization, and Bayesian neural networks, HyperMC generally achieves lower or competitive KSD values and improved predictive calibration, while Robust HyperMC yields more concentrated outcome distributions.

  • Takeaways & Limitations

    The framework supports budget-aware tuning across SGMCMC algorithms and can substitute task-specific predictive or calibration metrics when posterior approximation is not the primary objective.

  • Takeaways & Limitations

    KSD can remain a computational bottleneck for very long chains or high-dimensional models, motivating more scalable discrepancy measures.

Abstract

from arXiv · show

Stochastic gradient Markov chain Monte Carlo (SGMCMC) methods enable scalable Bayesian inference, but their performance depends strongly on hyperparameters such as the step size, mini-batch size, and number of leapfrog steps. Since most SGMCMC algorithms lack a Metropolis-Hastings acceptance rate, standard acceptance-based tuning methods are not directly applicable. We propose HyperMC, a multi-fidelity tuning framework that combines Hyperband-style resource allocation with kernel Stein discrepancy (KSD) evaluation. By running multiple successive-halving brackets, HyperMC balances broad exploration of a continuous hyperparameter space with increasingly accurate evaluation of promising configurations under a fixed computational budget. We further introduce Robust HyperMC, which uses global grid initialization followed by elite-guided local refinement to reduce sensitivity to random candidate generation and noisy finite-budget evaluations. Under suitable approximation and concentration conditions for the estimated KSD, we establish that the successive-halving component selects a near-optimal configuration among the sampled candidates with high probability and derive a sufficient computational budget for successful selection. Experiments on logistic regression, probabilistic matrix factorization, and Bayesian neural networks show that HyperMC improves posterior approximation or predictive calibration relative to MAMBA, grid search, and heuristic baselines, while Robust HyperMC yields more stable and reproducible tuning results.

1 Introduction

SGMCMC tuning is difficult because acceptance-rate diagnostics are unavailable and several interacting hyperparameters govern performance. HyperMC addresses this gap with multi-fidelity search, while Robust HyperMC improves initialization and refinement stability.

  • SGMCMC methods lack Metropolis–Hastings acceptance corrections, so classical acceptance-rate tuning cannot be directly applied.
  • SGMCMC performance depends on interacting choices including step size, mini-batch size, friction or momentum parameters, and leapfrog steps.
  • HyperMC introduces Hyperband-based multi-fidelity allocation for SGMCMC tuning, exploring multiple successive-halving brackets under a fixed computational budget.
  • HyperMC samples step sizes continuously and jointly handles continuous and discrete hyperparameters across different SGMCMC algorithms.
  • Robust HyperMC uses deterministic global-grid initialization, elite-guided local refinement, and multiple retained elites to improve stability across runs.
  • Under finite-resource approximation and concentration conditions, successive halving selects a near-optimal sampled configuration with high probability given a sufficient computational budget.

2 Background

The background develops stochastic-gradient Langevin sampling as a scalable approximation to posterior simulation and introduces Stein discrepancies for evaluating its output. KSD supplies a computable criterion based on samples and target-gradient information.

  • Posterior sampling targets a density π(θ), with the potential function and likelihood-prior decomposition defining the unnormalized posterior.
  • Langevin diffusion has the target posterior as its stationary distribution, while practical algorithms use a time-discretized approximation with step size h.
  • SGLD replaces expensive full gradients with unbiased mini-batch gradient estimates for large-scale inference.
  • The framework uses SGLD as an example but also applies to other stochastic-gradient MCMC algorithms.
  • KSD kernelizes Stein discrepancy into a closed-form, computable criterion for comparing empirical samples with a target distribution.
  • KSD requires a positive definite kernel, with Gaussian and Matérn kernels among the stated choices and the inverse multi-quadratic kernel used here.

3 Hyperparameter Optimization for SGMCMC

HyperMC treats SGMCMC tuning as a multi-fidelity selection problem: many configurations receive small initial budgets, and successive halving concentrates resources on promising candidates. Multiple brackets balance exploration with more accurate evaluation.

  • HyperMC evaluates SGMCMC hyperparameter configurations using KSD within a Hyperband-style fixed-budget framework.
  • The method initially evaluates many candidates with small budgets, discards poor configurations, and progressively increases resources for survivors.
  • Multiple brackets use different initial candidate counts and resource levels to balance broad exploration against reliable evaluation.
  • HyperMC is illustrated with SGLD parameters such as step size and mini-batch size, while supporting broader SGMCMC parameterizations.
  • Algorithm 1 defines the HyperMC procedure and uses η as the successive-halving downsampling factor, with η = 3 as the stated default.
  • Each sampler is run for a resource budget and evaluated by KSD during the tuning process.

12 end

HyperMC implements bracketed successive halving with KSD-based ranking and resource reallocation, then returns the lowest observed discrepancy. Its budget and metric choices trade evaluation fidelity against computational cost and can be adapted to predictive objectives.

  • Candidate generation, KSD evaluation, and top-k selection form the core operational functions of the procedure.
  • Brackets vary candidate counts and initial resources, combining broad exploration with more reliable evaluation of promising configurations.
  • Within each bracket, configurations are ranked by KSD, poor performers are discarded, and surviving configurations receive proportionally larger resources.
  • HyperMC returns the configuration with the smallest KSD observed across all completed brackets.
  • Wall-clock time is the implementation’s resource variable, although iterations or gradient evaluations are also possible with different cost-accounting implications.
  • KSD evaluation can use full-data gradients on thinned samples, but subsampled gradients add variability to configuration ranking.
  • HyperMC can replace KSD with validation or calibration metrics when predictive performance or uncertainty calibration is the primary objective.
  • Robust HyperMC begins with a global grid and subsequently concentrates candidates around promising regions from the preceding bracket.

4 Theoretical Analysis

The analysis establishes high-probability guarantees for KSD-based successive halving by controlling finite-resource and stochastic estimation errors. Under resolution, concentration, and budget conditions, the selected configuration is near-optimal among sampled candidates and globally when near-optimal candidates are included.

  • Error control: The guarantee separates finite-resource fidelity error from stochastic KSD estimation error and controls both through uniform assumptions.The fidelity envelope contracts with resource, while sub-Gaussian concentration provides a common confidence radius across queried configurations and resource levels.
  • Uniform control: A uniform high-probability event bounds every KSD score queried across configurations and successive-halving rounds.The analysis lifts a pointwise concentration bound to all potential configuration–resource pairs and combines it with the finite-resource envelope.
  • Finite-horizon guarantee: Theorem 4 guarantees near-optimal selection when the terminal estimate has sufficient resolution and the geometric schedule allocates enough budget before elimination.The guarantee is instance-dependent and uses configuration-specific KSD gaps to determine elimination scales.
  • Adaptive allocation: Successive halving discards configurations with substantially larger full-resource KSD at low fidelity and reserves most computation for configurations near the best sampled value.Larger KSD gaps yield smaller elimination scales, allowing early elimination of clearly suboptimal configurations.
  • Global implication: If the sampled candidate set contains a configuration within ε/2 of the global optimum, the procedure returns an ε-optimal configuration with probability at least 1 −δ.This global statement follows by combining candidate-set coverage with the within-bracket guarantee.

5 Experimental Studies

Across logistic regression, probabilistic matrix factorization, and Bayesian neural networks, HyperMC generally delivers strong posterior-discrepancy or calibration performance across six SGMCMC samplers. Robust HyperMC consistently reduces run-to-run tuning variability, although it does not always improve median performance.

  • Posterior approximation: HyperMC achieves the lowest or near-lowest KSD across six samplers in logistic regression and probabilistic matrix factorization.The advantage is especially pronounced for SGLD, SGLD-CV, SGHMC, and SGHMC-CV, where competing configurations can produce very large discrepancies.
  • Multi-fidelity search: Multiple Hyperband brackets balance broad continuous step-size exploration against increasingly accurate evaluation of promising configurations.This flexibility is useful when sampler performance depends jointly on step size, mini-batch size, and leapfrog steps.
  • Reproducibility: Robust HyperMC produces narrower interquartile ranges and shorter whiskers than HyperMC across repeated logistic-regression and matrix-factorization runs.Its principal benefit is reduced sensitivity to random candidate generation and noisy finite-budget evaluations, rather than uniformly lower medians.
  • Quantitative comparisons: HyperMC-KSD achieves the smallest or tied-smallest final KSD for all six logistic-regression samplers and the smallest final KSD for all six matrix-factorization samplers.KSD remains competitive with posterior-moment accuracy and predictive performance, while predictive accuracy alone can fail to distinguish sampling quality.
  • Predictive calibration: In the Bayesian neural network, HyperMC attains the lowest or near-lowest ECE over most of the evaluation horizon across the six samplers.The result is notable because calibration is sensitive to interacting hyperparameters, including step size and leapfrog count.
  • Predictive calibration: Robust HyperMC substantially lowers repeated-run ECE variability for all six Bayesian-neural-network samplers.For several samplers, greater stability also accompanies lower central ECE; for SGHMC and SGHMC-CV, original HyperMC may have a lower median but greater dispersion.

6 Discussion and Future Work

HyperMC combines multi-fidelity allocation with KSD-based evaluation for budget-aware SGMCMC tuning, while Robust HyperMC improves stability. The discussion identifies computational, sampling, and theoretical limitations and suggests extensions beyond SGMCMC.

  • Discussion: HyperMC tunes SGMCMC under a fixed computational budget using multiple Hyperband brackets and KSD-based evaluation.It handles continuous and discrete hyperparameters across different SGMCMC samplers without sampler-specific adaptation rules.
  • Discussion: Multiple brackets balance broad candidate exploration against more accurate evaluation of promising configurations.Robust HyperMC further reduces variability from independent candidate generation and noisy finite-budget KSD estimates.
  • Discussion: Experiments show generally lower or competitive KSD, improved predictive calibration, and more stable tuning outcomes across three Bayesian models.Robust HyperMC produces more concentrated KSD or ECE distributions but does not always attain the lowest median for every sampler.
  • Discussion: Theoretical analysis provides a high-probability near-optimality guarantee and a sufficient computational-budget condition for KSD-based successive halving.The guarantee applies among sampled configurations under the stated approximation and concentration framework.
  • Discussion: KSD is suitable for posterior approximation, while validation log-likelihood, predictive accuracy, or calibration error can support prediction-oriented tuning.The same resource-allocation framework can therefore use criteria matched to the scientific objective.
  • Future Work: KSD computation may remain a bottleneck for very long chains or high-dimensional models despite thinning and full-batch gradients.The paper suggests sliced or random-feature-based Stein discrepancies as more scalable alternatives.
  • Future Work: Uniform sampling from a predefined search space does not use information from previous experiments or earlier brackets.Prior-informed or model-based sampling is proposed as a way to improve sample efficiency while preserving Hyperband’s structure.
  • Future Work: Current theory does not fully quantify interactions among Monte Carlo variability, stochastic-gradient noise, discretization bias, and Hyperband elimination.A refined analysis could characterize the budget needed for high-probability near-optimal selection.

Appendix A. Additional Experimental Results

The appendix details logistic-regression tuning setups using grid search, KSD-based grid search, and MAMBA successive halving across six SGMCMC samplers. It specifies candidate grids, evaluation criteria, initialization, and figure-based selection procedures.

  • Methods: The appendix compares HyperMC-KSD, MAMBA-KSD, grid search with log-loss, a heuristic, and logistic-regression grid search with KSD.These methods are used across the three models, with the KSD grid-search variant added only for logistic regression.
  • Logistic Regression: The logistic-regression grid search uses 14 log10-scale step-size candidates and selects configurations by test log-loss.SGHMC additionally varies leapfrog steps over 5 and 10, while mini-batch size is fixed at 10% for grid search and the heuristic.
  • Logistic Regression: Each logistic-regression grid configuration starts from a perturbed MAP estimate and runs for 5,000 iterations.The perturbation adds Gaussian noise with scale σ = 0.2.
  • Logistic Regression: Figure 7 evaluates test log loss across step sizes and marks the selected value, jointly optimizing leapfrog settings for SGHMC variants.For SGHMC and SGHMC-CV, both L = 5 and L = 10 are considered.
  • KSD Grid Search: KSD grid search uses the same 14-step log10 grid while varying mini-batch ratios and, for SGHMC variants, leapfrog steps 5 and 10.The selected configuration minimizes KSD on a test dataset.
  • MAMBA: Figure 9 depicts MAMBA’s successive-halving process, where weaker configurations are progressively discarded and the highlighted trajectory is selected.
  • HyperMC: The general HyperMC search space covers log10 h ∈[−8, −1] and mini-batch ratios {100%, 10%, 1%, 0.1%}, with SGHMC also varying {5, 10} leapfrog steps.

A.1.6 Results

The PMF appendix specifies the MovieLens model and compares tuning procedures over step size, mini-batch size, and leapfrog settings. Figures describe grid-search and successive-halving selection, while tables organize search spaces and evaluation metrics.

  • Setup: The PMF experiment uses 100,000 MovieLens ratings for 1,682 movies from 943 users with five-fold 80%/20% cross-validation.
  • Model: The model represents users and movies with d-dimensional latent factors and sets d = 20 throughout the experiments.
  • Grid Search: Figure 10 evaluates test MSE over candidate step sizes, selecting the globally best configuration across L = 5 and L = 10 for SGHMC variants.Optimal step sizes differ across samplers.
  • MAMBA: MAMBA progressively allocates larger budgets to better candidates and eliminates weaker ones through successive halving.The displayed metric uses the log10(1+Metric) scale, with the highlighted trajectory denoting the selected configuration.
  • Search Space: The PMF search space uses log10 h ∈[−8, −2], mini-batch ratios {100%, 10%, 1%}, and SGHMC leapfrog choices {5, 10}.The same ranges apply to each standard sampler and its control-variate counterpart.

A.2.5 Results

The neural-network appendix evaluates SGMCMC tuning on MNIST with a two-layer Bayesian neural network. It documents the model, search space, grid-search metrics, and MAMBA’s successive-halving procedure.

  • Setup: The MNIST task uses grayscale 28×28 digit images in a two-layer Bayesian neural network with 100 hidden variables.Training uses 60,000 images to classify ten digit categories.
  • Model: The network parameters include A, B, a, and b with dimensions 100×10, 784×100, 1×10, and 1×100.
  • Grid Search: Figure 12 evaluates negative test accuracy across step sizes, selecting the lower-valued configuration and jointly considering L = 5 and L = 10 for SGHMC variants.
  • MAMBA: Figure 13 shows successive-halving rounds in which poor-KSD configurations are discarded and promising candidates receive increasing computational budgets.Curves represent candidate configurations and vertical dashed lines mark the rounds.
  • Search Space: The neural-network search space uses log10 h ∈[−8, −2], mini-batch ratios {100%, 10%, 1%}, and SGHMC leapfrog choices {5, 10}.The same ranges apply to standard and control-variate sampler variants.

A.3.5 Results

The neural-network results compare tuning methods and samplers using calibration, accuracy, and sampling-effort metrics.

  • Table 8 specifies neural-network hyperparameters, with batch size determined by the percentage parameter τ.The batch size is n = floor(τN/100).
  • Table 9 reports ECE, MCE, test accuracy, and number of samples for each tuning method and sampler.ECE and MCE are percentages, and bold indicates the best result for each sampler and metric.

A.4 Empirical Comparison of KSD and FSSD

FSSD lowers discrepancy-estimation cost but can select worse SGMCMC hyperparameters than KSD, motivating KSD as the primary criterion in the experiments.

  • FSSD has linear sample-cost scaling with a fixed number of test locations, whereas KSD evaluates the complete Stein witness function.FSSD’s cheaper computation comes from evaluating the witness function at finitely many test locations.
  • FSSD’s assessment can depend on test-location placement, test-location count, and kernel bandwidth, weakening discrepancy detection.Its theory also lacks the same general weak-convergence control available for convergence-determining KSDs.
  • Figure 14 compares FSSD- and KSD-selected hyperparameters for six SGMCMC samplers using KSD, where smaller values indicate closer posterior approximation.The common evaluation metric is KSD, not the selection criterion used to choose each configuration.
  • For SGLD, MAMBA-FSSD and MAMBA-KSD produce broadly comparable mean KSD curves, unlike the other reported samplers.The cited comparison identifies SGLD as the sampler with comparable FSSD- and KSD-based outcomes.
  • FSSD-selected configurations perform worse for the remaining samplers, so the experiments use KSD primarily while recommending independent validation when FSSD is used.The stated boundary is that FSSD may remain useful when KSD’s quadratic cost is prohibitive, but its test locations and kernel parameters require careful selection.

B.2 Proof of Lemma 2

The proof of Lemma 2 constructs a finite collection of potential arm-resource pairs and applies concentration bounds uniformly across them.

  • The proof defines at most n arm indices at each of the s + 1 resource levels.The potential-pair collection is I = {(i, k): i ∈ {1, …, n}, k ∈ {0, …, s}}.
  • Random survivor evaluation is handled by viewing actually evaluated pairs as a subset of the deterministic collection I.This representation preserves the algorithm’s distribution and avoids ambiguity from random survivor sets.
  • For every potential arm-resource pair, Lemma 1 supplies a concentration estimate, and a union bound yields simultaneous control with probability at least 1 − δ.No independence among the pairwise events is required for the union bound.
  • The resulting uniform bound applies in particular to every pair actually evaluated by the algorithm.The proof first establishes the event for all potential pairs and then restricts it to evaluated pairs.

B.3 Proof of Theorem 4

Theorem 4’s proof adapts the SuccessiveHalving argument to capped resources and a high-probability KSD envelope, showing that the best configuration survives within the stated budget.

  • Proof setup: The proof modifies the original Hyperband argument by capping geometric resources at R and replacing a deterministic envelope with ψn,δ.The terminal-resolution condition ensures that every elimination scale is finite.
  • Budget: The proof concludes that the algorithm never exceeds the stated budget cap and establishes the simpler sufficient budget bound.The bound follows by maximizing over configurations and multiplying by ηL_n.
  • Case analysis: On the concentration event, configuration 1 has strictly larger empirical KSD than configuration i once its elimination scale is reached.The strict inequality removes dependence on the tie-breaking rule.
  • Case analysis: When the excluded global rank is separated from the best configuration by at least ε/2, the best configuration cannot be eliminated.This is the key survivor conclusion used by the three-case argument.
  • Case analysis: If the best configuration is eliminated in the remaining case, every retained and later surviving configuration is already ε/2-optimal relative to it.Later stages only remove configurations, preserving this invariant.
Loading 2609.02138v1…