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 tuning is difficult because interacting hyperparameters lack acceptance-rate diagnostics. HyperMC combines multi-fidelity budget allocation with KSD evaluation, and experiments plus theory show competitive tuning outcomes, more stable Robust HyperMC results, and high-probability near-optimal selection under stated conditions.

  • Problem

    SGMCMC performance depends on interacting hyperparameters, but these methods generally lack acceptance-rate diagnostics and are often tuned heuristically or by costly grid search.

    Source: §1 · p. 2, §1.1.2 · p. 2

  • Method

    HyperMC uses Hyperband-style multi-fidelity allocation with KSD evaluation to successively eliminate SGMCMC configurations under a fixed computational budget.

    Source: §3 · p. 6, §6.1 · p. 28

  • Results

    Experiments show lower or competitive KSD values and improved predictive calibration, while Robust HyperMC produces more stable and reproducible tuning outcomes; theory gives a high-probability near-optimality guarantee.

    Source: §6.1 · pp. 28–29

  • Takeaways & Limitations

    The framework supports budget-aware tuning with evaluation metrics chosen for posterior approximation or predictive objectives rather than requiring acceptance rates.

    Source: §6.1 · p. 29

    Finite SGMCMC output introduces Monte Carlo variability, stochastic-gradient noise, and discretization bias into candidate-quality estimates used by the elimination process.

    Source: §6.2 · p. 29

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

HyperMC addresses the difficulty of tuning SGMCMC without acceptance-rate diagnostics by combining KSD evaluation with multi-fidelity resource allocation. Its Robust extension improves stability, while theoretical guarantees support near-optimal selection under finite, noisy evaluations.

1 Introduction

  • The introduction frames hyperparameter tuning as essential for practical MCMC performance and identifies acceptance-based diagnostics, unavailable in SGMCMC, as the central methodological gap.KSD offers a posterior-quality criterion without normalized target densities or reference samples.Source: §1 · pp. 1–2
  • SGMCMC tuning is challenging because missing Metropolis–Hastings corrections prevent acceptance-rate diagnostics, while interacting step size, batch size, friction, and leapfrog parameters affect performance.Existing alternatives include heuristics, optimization-inspired adaptation, discrepancy criteria, and MAMBA’s successive-halving approach.Source: §1 · p. 2, §1.1.2 · pp. 2–3

1.1.1 MCMC Tuning

  • Classical MCMC tuning uses acceptance-rate theory and adaptive proposal updates, while gradient-based samplers automate trajectory and step-size choices through methods such as NUTS and AutoMALA.These approaches motivate the contrast with SGMCMC, where acceptance-based tuning is unavailable.Source: §1.1.1 · p. 2

1.1.2 SGMCMC Tuning

  • SGMCMC research has progressed from heuristic schedules and calibration toward adaptive mechanisms and KSD-based discrepancy evaluation, but broadly applicable automatic tuning remains open.MAMBA combines KSD with successive halving under a fixed computational budget.Source: §1.1.2 · pp. 2–3

1.1.3 Hyperparameter Optimization

  • Hyperparameter-optimization methods motivate HyperMC by allocating small budgets broadly before concentrating resources on promising configurations through successive halving, Hyperband, or BOHB.These multi-fidelity strategies suit SGMCMC because reliable configuration evaluation requires substantial sampler computation.Source: §1.1.3 · p. 3

1.2 Contributions

  • HyperMC introduces multiple successive-halving brackets over continuous and discrete hyperparameter spaces, enabling flexible, algorithm-agnostic SGMCMC tuning beyond MAMBA’s fixed grid.The framework jointly handles step sizes, mini-batch sizes, friction parameters, and leapfrog counts.Source: §1.2 · p. 3
  • Robust HyperMC uses global grid initialization and elite-guided local refinement to reduce sensitivity to random candidates and noisy evaluations, producing more stable and reproducible choices.It retains multiple elite configurations while progressively refining step sizes around them with mini-batch size and leapfrog count fixed.Source: §1.2 · pp. 3–4
  • Under finite-resource approximation and KSD concentration conditions, successive halving selects a near-optimal sampled configuration with high probability and admits a sufficient budget bound.The bound depends on KSD estimation error and performance gaps between candidates.Source: §1.2 · p. 4

2 Background

The background introduces SGLD as a scalable discretized Langevin sampler using unbiased mini-batch gradients, and KSD as a computable Stein-based measure for evaluating empirical samples against a target distribution.

2.1 Stochastic Gradient Langevin Dynamics

  • SGLD approximates Langevin diffusion with a discrete update that replaces the full gradient by an unbiased mini-batch estimator, reducing per-iteration cost for large datasets.The mini-batch has size n much smaller than N and is sampled uniformly without replacement.Source: §2.1 · pp. 4–5
  • SGLD serves as the framework’s basic example, but the adaptive tuning approach also applies to other SGMCMC methods, including stochastic gradient Hamiltonian Monte Carlo.The broader SGMCMC class is given a unified formulation by Ma et al. (2015).Source: §2.1 · p. 5

2.2 Kernel Stein Discrepancy

  • KSD evaluates the discrepancy between samples’ empirical distribution and the target distribution by kernelizing a Stein discrepancy into a closed-form computable criterion.The construction uses a positive definite kernel and avoids the direct supremum over the Stein function class.Source: §2.2 · p. 5
  • The analysis requires a suitable Stein set and positive definite kernel; the implementation uses an inverse multi-quadratic kernel, which detects non-convergence when c > 0 and β ∈(−1, 0).Gaussian and Matérn kernels are also identified as commonly used positive definite kernels.Source: §2.2 · pp. 5–6

3 Hyperparameter Optimization for SGMCMC

HyperMC frames SGMCMC tuning as multi-fidelity selection under a fixed computational budget, using KSD to evaluate configurations and Hyperband-style successive halving to allocate resources. It supports continuous and discrete algorithmic hyperparameters while progressively focusing computation on promising posterior approximations.

3 Hyperparameter Optimization for SGMCMC

  • HyperMC evaluates many SGMCMC hyperparameter configurations with small budgets, successively discards poor performers, and allocates larger budgets to promising configurations using KSD.The framework applies to parameters including step size, mini-batch size, friction, momentum, and leapfrog steps.Source: §3 · p. 6, §3.2 · p. 7

3.1 Hyperband

  • Hyperband balances exploration and exploitation by evaluating many configurations cheaply before concentrating resources on fewer promising configurations under a limited budget.It treats resource allocation as a decision variable rather than assigning every candidate the maximum evaluation budget.Source: §3.1 · p. 6
  • Successive halving promotes only the best 1/η fraction after equal-budget evaluation, then repeats evaluation with larger budgets until the maximum level or few candidates remain.Hyperband combines multiple brackets with different initial candidate counts and resource levels to emphasize either exploration or accurate evaluation.Source: §3.1 · pp. 6–7

3.2 Tuning SGMCMC with Hyperband (HyperMC)

  • HyperMC instantiates Hyperband for SGMCMC by comparing candidate samplers across computational budgets and selecting configurations with better posterior approximation quality according to KSD.The procedure is illustrated with SGLD parameters h and n but is intended for other SGMCMC samplers as well.Source: §3.2 · p. 7

12 end

HyperMC uses multiple Hyperband brackets, KSD-based successive halving, and resource reallocation to search SGMCMC hyperparameters under a common computational budget. Robust HyperMC replaces independent bracket initialization with global grid exploration and shrinking elite-guided local refinement, while preserving the original budget schedule.

3.2.1 Initialize brackets and configurations

  • HyperMC constructs brackets that trade off broad low-resource exploration against fewer high-resource evaluations, then reallocates discarded configurations’ resources to survivors through successive halving.As active configurations shrink by approximately η, each survivor receives proportionally more resource, avoiding full evaluation of every candidate.Source: §3.2.1 · p. 8, §3.2.3 · p. 9

3.2.2 Evaluate and promote configurations

  • HyperMC evaluates sampled SGMCMC configurations with KSD, repeatedly retains the smallest-discrepancy candidates, and returns the best KSD observed across all brackets.KSD requires samples and log-posterior gradients, and the implementation returns the configuration with the smallest KSD seen so far.Source: §12 · p. 7, §3.2.2 · p. 8, §3.2.3 · p. 9

3.3.1 Choice of resource budget

  • The resource budget is wall-clock time, with R as the maximum level and η controlling pruning aggressiveness; η = 3 is the default choice.Wall-clock allocation reflects differing costs from mini-batch sizes and leapfrog-step counts, while iteration- and gradient-based budgets remain alternatives.Source: §3.3.1 · p. 9

3.3.2 Estimating KSD during tuning

  • KSD is the default tuning metric because it assesses posterior approximation without the target normalizing constant, using thinned samples and, when feasible, full-data gradients for stability.Full-data gradients are used only during tuning; subsampled-gradient KSD is possible but adds ranking variability.Source: §3.3.2 · p. 10, §3.3.3 · p. 10

3.3.3 Choice of evaluation metric

  • KSD is the primary criterion for posterior approximation, but HyperMC’s budget-allocation mechanism can instead use task-specific metrics such as predictive accuracy or calibration.The paper reports that FSSD-selected hyperparameters were less accurate than KSD-selected ones in the logistic-regression comparison, while emphasizing that metric choice should follow the final objective.Source: §3.3.3 · pp. 10–11

3.4 Robust HyperMC

  • Robust HyperMC keeps Hyperband’s successive-halving schedule but initializes the first bracket with a global grid and later brackets with elite-centered stochastic refinements whose log-step radii halve across brackets.Mini-batch size and leapfrog steps are inherited from selected centers, and the refinement adds no SGMCMC evaluations beyond the original Hyperband budget.Source: §3.4 · pp. 11–13

3.5.3 HyperMC

  • Comparisons use grid search, a step-size heuristic, MAMBA, and HyperMC under aligned evaluation settings, with HyperMC ranking candidates by thinned full-batch-gradient KSD across multiple brackets.Grid-search and heuristic baselines use a mini-batch size equal to 10% of the dataset, while all samplers are initialized near the MAP estimate with perturbation for grid search.Source: §3.5.1 · pp. 13–14, §3.5.3 · pp. 14–15, §3.5.2 · p. 14

4 Theoretical Analysis

The analysis establishes finite-horizon guarantees for KSD-based successive halving by controlling finite-resource bias and statistical estimation error. Under stated concentration, fidelity, resolution, and budget conditions, the method selects an approximately optimal sampled configuration and reaches global near-optimality when candidate generation is sufficiently good.

Error control

  • The guarantee separates finite-resource fidelity error from stochastic KSD estimation error and combines them into a uniform confidence radius over configurations and resource levels.The fidelity envelope need not make the finite-resource objective monotone; it only requires deviation from the full-resource objective to contract with resources.Source: §4 · pp. 15–16

Concentration analysis

  • Under the two assumptions, a uniform high-probability event controls every KSD score queried by successive halving, despite random active sets and multiple evaluation rounds.Independence is required only among score contributions within each fixed estimator, not across configurations or rounds.Source: §4 · pp. 16–18

Finite-horizon guarantee

  • Under Theorem 4’s assumptions, sufficient terminal KSD-estimate resolution places full-resource statistical uncertainty below the target accuracy, ruling out an irreducible estimation-error floor at resource level R.The budget condition ensures the geometric schedule allocates enough resources to resolve every configuration before its elimination becomes necessary.Source: §4 · p. 18

Adaptive allocation

  • Successive halving adapts resource allocation by discarding configurations with large KSD gaps at low fidelity and reserving most computation for near-best candidates.Larger gaps imply smaller elimination scales, enabling earlier elimination of clearly inferior configurations.Source: §4 · pp. 18–19

Global optimization

  • If the candidate set contains a configuration within ε/2 of the global optimum, the method returns an ε-optimal configuration with probability at least 1 −δ.Thus, the within-bracket guarantee transfers to the global hyperparameter objective when candidate generation supplies a sufficiently good configuration.Source: §4 · p. 19

5 Experimental Studies

Across logistic regression, probabilistic matrix factorization, and Bayesian neural networks, HyperMC generally improves posterior approximation or calibration over competing tuning methods, while Robust HyperMC consistently reduces run-to-run tuning variability. The experiments evaluate six SGMCMC samplers and compare multi-bracket allocation with elite-guided refinement under fixed computational budgets.

5 Experimental Studies

  • Across all three models, HyperMC-KSD generally achieves the lowest or near-lowest posterior discrepancy or calibration error, while Robust HyperMC reduces tuning variability across repeated runs.The experiments cover six SGMCMC samplers and assess posterior approximation or predictive calibration under fixed budgets, alongside reproducibility of selected hyperparameters.Source: §5 · p. 19, §5.1 · p. 22, §5.2 · p. 25

5.1 Logistic Regression

  • HyperMC-KSD attains the smallest or tied-smallest final KSD for all six logistic-regression samplers, while remaining competitive on posterior-standard-deviation error and predictive accuracy.It ties the exhaustive KSD grid search for SGHMC and SGNHT-CV, and its strongest gains include SGLD, SGLD-CV, SGHMC-CV, and SGNHT.Source: §5.1 · p. 22

5.2 Probabilistic Matrix Factorization

  • In probabilistic matrix factorization, HyperMC-KSD achieves the lowest final KSD for all six samplers and combines competitive posterior-moment accuracy with strong predictive performance.It has the smallest moment error for SGLD, SGLD-CV, SGNHT, and SGNHT-CV, while predictive baselines can have lower moment error for SGHMC and SGHMC-CV despite substantially larger KSD.Source: §5.2 · pp. 23, 25

5 Experimental Studies

  • Robust HyperMC consistently narrows repeated-run distributions across the three models, reducing sensitivity to random candidate generation and noisy finite-budget evaluations without uniformly improving median performance.Its central KSD or ECE is lower or comparable for several samplers, while original HyperMC can retain lower medians for some samplers but with greater dispersion.Source: §5.1 · p. 21, §5.2 · p. 24, §5.3 · p. 27

5.3 Bayesian Neural Network

  • For the Bayesian neural network, HyperMC-KSD obtains the smallest or tied-smallest ECE across all six samplers and the most favorable MCE values, with competitive classification accuracy.Predictive baselines can achieve higher accuracy for some thermostat samplers while producing less favorable calibration.Source: §5.3 · pp. 27–28

6 Discussion and Future Work

HyperMC provides budget-aware, KSD-based multi-fidelity tuning for SGMCMC without Metropolis–Hastings acceptance rates, while Robust HyperMC improves reproducibility through elite-guided refinement. The discussion reports empirical and theoretical support, broader metric applicability, and four directions for future work.

6.1 Discussion

  • HyperMC combines multi-fidelity allocation with KSD evaluation to tune continuous and discrete SGMCMC hyperparameters across samplers without sampler-specific adaptation rules.Its multiple Hyperband brackets balance broad exploration against increasingly accurate evaluation under a fixed computational budget.Source: §6.1 · p. 28
  • Robust HyperMC reduces sensitivity to random candidate generation and noisy finite-budget KSD estimates by globally initializing candidates and refining neighborhoods around elite configurations without extra SGMCMC evaluations.The original successive-halving schedule remains unchanged during refinement.Source: §6.1 · p. 28
  • HyperMC generally achieves lower or competitive KSD and improved predictive calibration across three Bayesian tasks, while Robust HyperMC yields more stable and reproducible tuning outcomes.Theoretical analysis also gives a high-probability near-optimality guarantee for sampled configurations and a sufficient budget condition for reliable selection.Source: §6.1 · pp. 28–29
  • The framework can replace KSD with validation log-likelihood, predictive accuracy, or calibration error when predictive objectives matter, while retaining its resource-allocation structure.KSD is particularly suitable for posterior approximation because it requires neither normalized target densities nor reference posterior samples.Source: §6.1 · p. 29

6.2 Future Work

  • Future work should reduce KSD’s computational bottleneck for long chains or high-dimensional models through scalable discrepancies such as sliced or random-feature-based Stein measures.Current experiments mitigate KSD cost using thinned samples with full-batch gradients.Source: §6.2 · p. 29
  • Future research should develop informed candidate sampling, refined error-aware theory, and extensions beyond SGMCMC to other costly Monte Carlo algorithms.These directions target prior- or model-based sampling, interactions among Monte Carlo variability, stochastic-gradient noise, discretization bias, and Hyperband elimination, and applications to Hamiltonian, tempered, or sequential Monte Carlo.Source: §6.2 · p. 29

Appendix A. Additional Experimental Results … A.1.5 HyperMC

The appendix details the logistic-regression experiments, comparing four core tuning methods across all six SGMCMC samplers and adding KSD-based grid search as an alternative. It specifies the search grids, successive-halving procedures, and HyperMC’s joint hyperparameter search space.

Appendix A. Additional Experimental Results

  • The logistic-regression experiments compare HyperMC-KSD, MAMBA-KSD, log-loss grid search, and a heuristic baseline, with grid search-KSD added for logistic regression.These methods are evaluated across the six SGMCMC samplers.Source: Appendix A · p. 30

A.1.1 Model

  • The logistic-regression model uses binary responses, covariates in a design matrix, and a zero-mean Gaussian prior θ ∼ N(0_d, 10I_d).Source: §A.1.1 · p. 30

A.1.2 Grid search

  • Log-loss grid search evaluates 14 step sizes on the log10 scale, fixes mini-batches at 10% of the dataset, and considers leapfrog counts 5 and 10 for SGHMC.Configurations are initialized from perturbed MAP estimates and run for 5,000 iterations.Source: §A.1.2 · p. 30
  • Figure 7 reports step-size grid-search test log loss for six SGMCMC samplers, jointly selecting SGHMC and SGHMC-CV configurations over L = 5 and L = 10.The selected step size is indicated by the red dashed line.Source: §A.1.2 · p. 30, Figure 7 · p. 31

A.1.3 Grid Search with KSD

  • KSD-based grid search uses the same 14 log10 step sizes, four mini-batch ratios, and leapfrog values 5 and 10 for SGHMC and SGHMC-CV.The configuration with the best KSD on a test dataset is selected.Source: §A.1.3 · pp. 31–32

A.1.4 MAMBA

  • MAMBA applies successive halving to the six SGMCMC samplers, progressively discarding less competitive configurations until a final configuration is selected.Figure 9 highlights the selected trajectory.Source: §A.1.4 · p. 32, Figure 9 · p. 32

A.1.5 HyperMC

  • HyperMC searches log10 h ∈ [−8, −1] and mini-batch sizes of 100%, 10%, 1%, or 0.1%, additionally selecting 5 or 10 leapfrog steps for SGHMC and SGHMC-CV.Table 1 summarizes this logistic-regression hyperparameter search space.Source: §A.1.5 · p. 33, Table 1 · p. 33

A.1.6 Results … A.2.4 HyperMC

The paper evaluates tuning methods on logistic regression and develops a probabilistic matrix factorization setup comparing grid search, MAMBA, and HyperMC search spaces. The PMF experiments examine predictive performance, KSD behavior, and computationally allocated hyperparameter selection across six SGMCMC samplers.

A.1.6 Results

  • Logistic-regression comparisons report standard-deviation relative error, KSD, predictive accuracy, and sample counts across tuning methods and samplers.The evaluation also includes time-budgeted grid search using KSD while tuning batch size and step size.Source: Table 3 · p. 34

A.2.1 Model

  • The PMF model uses MovieLens ratings from 943 users and 1,682 movies, with five predefined 80%/20% train-test splits for cross-validation.The observed rating matrix is modeled through d-dimensional latent user and movie factors.Source: §A.2.1 · pp. 34–35
  • The PMF posterior assigns priors to user and movie latent factors, with parameters θ=(U, µU, ΛU, V, µV, ΛV) and latent dimension d=20 in all experiments.Experimental hyperparameters are fixed at τ=(α, µ0, a0, b0)=(3, 0, 4, 5).Source: §A.2.1 · p. 35

A.2.2 Grid Search

  • Grid search evaluates step sizes over a log10-scale candidate grid, using 2,000 iterations from perturbed MAP initialization and L=5 or 10 for SGHMC.For SGHMC and SGHMC-CV, the globally best configuration is selected across both leapfrog settings.Source: §A.2.2 · p. 35
  • In PMF, grid-search optima differ across samplers, while standard and control-variate variants show broadly similar predictive performance.Figure 10 compares test MSE across candidate step sizes, with lower values indicating better predictive performance.Source: §A.2.2 · p. 35, Figure 10 · p. 36

A.2.3 MAMBA

  • MAMBA uses a 10-second maximum budget, searches batch ratios of 100%, 10%, and 1%, and evaluates L=5 or 10 for SGHMC.Its successive-halving procedure allocates larger budgets to stronger candidates and eliminates less competitive configurations.Source: §A.2.3 · p. 36
  • Across six PMF samplers, MAMBA’s selected configurations generally achieve lower or more stable KSD as computational resources increase.The highlighted trajectory identifies the ultimately selected configuration, with metrics displayed on the log10(1+Metric) scale.Source: §A.2.3 · p. 36, Figure 11 · p. 37

A.2.4 HyperMC

  • HyperMC searches log10 h∈[−8,−2] with batch sizes of 100%, 10%, or 1%, additionally using L∈{5,10} for SGHMC and SGHMC-CV.The same search ranges are applied to each standard sampler and its corresponding control-variate variant.Source: §A.2.4 · p. 37, Table 4 · p. 38

A.2.5 Results … A.3.4 HyperMC

The experiments cover PMF tuning results and a Bayesian neural-network classification study on MNIST. The neural-network evaluation compares grid search, MAMBA, and HyperMC-related configurations across SGMCMC samplers using predictive or discrepancy-based criteria.

A.2.5 Results

  • For PMF, tuning methods and samplers are compared using standard-deviation relative error, test-set RMSE, and sample count.Table 6 reports the best result for each sampler and metric in bold; Table 5 specifies the associated batch-size hyperparameters.Source: Table 5 · p. 38, Table 6 · p. 39

A.3.1 Model

  • The neural-network experiment uses MNIST to train a two-layer Bayesian neural network with 100 hidden variables on 60,000 images and evaluate classification on 10,000 test images.Each image has 28×28 grayscale pixels, and the task has ten digit classes.Source: §A.3.1 · p. 39
  • The model represents ten-class labels with a categorical likelihood and uses a softmax transformation of the network outputs.Parameters are sampled with SGMCMC and comprise matrices or vectors associated with the two-layer network; independent Gaussian priors are assigned to their elements.Source: §A.3.1 · p. 40

A.3.2 Grid search

  • Grid search evaluates negative test accuracy over candidate step sizes for six SGMCMC samplers, selecting lower-valued configurations and optimizing SGHMC variants across L = 5 and L = 10.The selected step size is marked by a red dashed line in Figure 12.Source: §A.3.2 · pp. 40–41, Figure 12 · p. 40

A.3.3 MAMBA

  • MAMBA uses successive halving to discard configurations with relatively poor KSD values while allocating increasing budgets to promising candidates.In the neural-network experiment, the maximum budget is R = 10 seconds, and candidates vary in step size, mini-batch proportion, and, for SGHMC, leapfrog steps.Source: §A.3.3 · p. 41, Figure 13 · p. 42

A.3.4 HyperMC

  • HyperMC searches log10 h ∈[−8, −2] and mini-batch sizes of 100%, 10%, or 1%, with SGHMC and SGHMC-CV additionally searching L ∈{5, 10}.The same search ranges are used for each standard sampler and its corresponding control-variate variant.Source: §A.3.4 · p. 42, Table 7 · p. 43

A.3.5 Results

The neural-network results compare tuning methods across samplers using calibration, accuracy, and sampling metrics. The associated hyperparameter specification defines batch size as a percentage of the total dataset.

Hyperparameter setup

  • The batch size is defined by τ as a percentage of the total data, with n = ⌊τN/100⌋.Source: Table 8 · p. 43

Neural-network comparison

  • The neural-network experiment compares tuning methods for each sampler.The reported metrics identify the best result for each sampler and metric in bold.Source: Table 9 · p. 44

Evaluation metrics

  • Performance is evaluated using ECE and MCE percentages, test accuracy, and number of samples.Source: Table 9 · p. 44

A.4 Empirical Comparison of KSD and FSSD · Appendix B. Proofs · B.1 Proof of Lemma 1

In logistic regression, FSSD makes discrepancy estimation cheaper but generally selects worse SGMCMC hyperparameters than KSD, so KSD remains the primary tuning criterion. Appendix B then establishes the theoretical lemmas, with Lemma 1 proved by two-sided tail bounds culminating in (4.10).

A.4 Empirical Comparison of KSD and FSSD

  • FSSD reduces discrepancy-estimation cost through finitely many test locations, whose number is fixed in the linear-in-sample computational regime.Under suitable conditions, population FSSD remains identifying, vanishing if and only if candidate and target distributions coincide.Source: §A.4 · p. 44
  • Finite test locations can weaken FSSD’s discrepancy signal through their placement, number, and kernel bandwidth, while optimized locations add tuning complexity and may lose testing power in high dimensions.Unlike convergence-determining KSDs based on slowly decaying kernels, standard FSSD theory does not provide the same general weak-convergence control.Source: §A.4 · p. 45
  • FSSD-selected configurations have higher mean KSD than KSD-selected configurations for five of six samplers, while SGLD is broadly comparable.Figure 14 evaluates all resulting samplers using KSD, with smaller values indicating closer posterior approximation; no systematic evidence shows FSSD improves selection.Source: §A.4 · p. 45, Figure 14 · p. 45
  • Because FSSD is at best comparable for one sampler and worse for the others, the study uses KSD for primary tuning and recommends independent validation when FSSD is used under prohibitive KSD cost.FSSD test locations and kernel parameters should be selected carefully.Source: §A.4 · pp. 45–46

Appendix B. Proofs

  • Appendix B supplies proofs for the lemmas and theorems presented in Section 4.Source: Appendix B · p. 46

B.1 Proof of Lemma 1

  • The proof of Lemma 1 fixes x, r, and t, bounds upper and lower tails with exponential Markov arguments, and applies independence plus Assumption 2.The upper-tail exponent is optimized at λ = t/σ2, and the lower-tail argument uses Assumption 2 with parameter −λ.Source: §B.1 · pp. 46–47
  • Applying the union bound to the two one-sided estimates completes Lemma 1 and yields exactly inequality (4.10).Source: §B.1 · pp. 47–48

B.2 Proof of Lemma 2

The proof controls all score estimates by considering every possible arm–resource pair across all resource levels, then applies a union bound. On the resulting high-probability event, concentration holds for evaluated pairs, and the triangle-inequality argument establishes (4.11).

Union-bound construction

  • The proof indexes at most n arm indices across the s + 1 resource levels, forming the potential pair set I of all arm–resource combinations.Actually evaluated pairs form a subset of I because the algorithm evaluates only surviving arms.Source: §B.2 · p. 48
  • Applying Lemma 1 to each deterministic pair and using a union bound requires no independence among the corresponding events.The argument may expose only survivor-set entries from a conceptual table containing estimates for every pair in I.Source: §B.2 · p. 49

High-probability event

  • With probability at least 1 −δ, the concentration inequality holds simultaneously for every potential pair and therefore for every actually evaluated pair.This event is denoted E0 and supplies the uniform control needed for the remainder of the proof.Source: §B.2 · p. 49

Completion of the proof

  • On E0, applying Assumption 1 and the triangle inequality after adding and subtracting ℓ_rk(X_i) yields the definition of ψ_n,δ and proves (4.11).The argument holds for every resource level k and every surviving arm i ∈ S_k.Source: §B.2 · p. 49

B.3 Proof of Theorem 4

The proof adapts the three-case SuccessiveHalving argument to finite-horizon resources and a high-probability KSD envelope. On the concentration event, it establishes that the best configuration is retained or all survivors are ε/2-optimal, while respecting the budget cap.

B.3 Proof of Theorem 4

  • The proof caps geometric resources at R and replaces the deterministic envelope with the high-probability KSD envelope ψn,δ, ensuring all elimination scales are finite.The resulting procedure never exceeds the stated budget cap.Source: §B.3 · p. 50
  • On the event from Lemma 2, all remaining arguments are deterministic, and each configuration’s empirical KSD obeys the required envelope.This event has probability at least 1−δ.Source: §B.3 · p. 50
  • When the first excluded global rank is separated from the best configuration by at least ε/2, the best configuration cannot be eliminated.The strict empirical-KSD inequality also removes dependence on the tie-breaking rule.Source: §B.3 · p. 51

Case 2: suppose

  • The three-case analysis shows that every retained or later-surviving configuration is ε/2-optimal relative to configuration 1, yielding the sufficient budget bound and completing the proof.If configuration 1 is eliminated, this occurs only under Case 2, after which all subsequent survivors remain ε/2-optimal.Source: Case 2: suppose · p. 52

Related papers

Loading 2609.02138v1…