Aug 2026· SIAM Journal on Scientific Computing· 0 citations· 7 references
Abstract
Abstract.
We propose an adaptive randomized truncation estimator for Krylov subspace methods that optimizes the trade-off between the solution variance and the computational cost while remaining unbiased. The estimator solves a constrained optimization problem to compute the truncation probabilities on the fly with minimal computational overhead. The problem has a closed-form solution when the improvement of the deterministic algorithm satisfies a diminishing returns property. We prove that obtaining the optimal adaptive truncation distribution is impossible in the general case. Without the diminishing return condition, our estimator provides a suboptimal but still unbiased solution. We present experimental results in Gaussian process (GP) hyperparameter training and competitive physics-informed neural networks problems to demonstrate the effectiveness of our approach.
Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/RockyL7/AdaptivelySubsampledKrylov.jl and in the supplementary materials ( AdaptivelySubsampledKrylov_jl-master.zip [14.5KB]). [Formula: see text]
Resolvent Monte Carlo estimates eigenvalues of large matrices by sampling Markov chains and reading the target value off a truncated resolvent quotient, trading exact arithmetic for a stochastic error that the almost-optimal sampling scheme is designed to suppress. This paper studies when that error vanishes outright. An exact closed-form identity is derived for the variance of the moment estimators of a general, possibly signed matrix, and is used to isolate a hierarchy of zero-variance notions ranging from the most local, which constrains only the first draws, through the finite-truncation regime that a practical run can certify, to the global regime in which every moment estimator is deterministic. Determinism of the estimator is separated from correctness of the eigenvalue it reports, and the exact conditions under which each notion holds are exhibited, together with the examples that separate them. A single edgewise condition, termed the eigen-triple condition, forces the truncated quotient to equal the target eigenvalue in finite samples; the associated moment and quotient variances are second order in the maximal edge defect and vanish at the eigen-triple. A linear-time procedure certifies the condition.
Tsvetelina Kostadinov, I. Dimov· Mathematics· 0 citations
In this paper, we propose a novel tamed stochastic gradient Hamiltonian Monte Carlo (tSGHMC) algorithm for sampling and stochastic optimization problems with superlinearly growing stochastic gradients. Under a certain continuity in average condition and a strong convexity condition, we establish a non-asymptotic error bound in Wasserstein-2 distance for tSGHMC with the rate of convergence equal to $1/4$. Then, we derive an upper estimate for the associated expected excess risk, which provides a theoretical guarantee for the performance of tSGHMC. To illustrate the effectiveness of the proposed algorithm, we apply tSGHMC to practical examples, including a newsvendor problem and a Conditional Value-at-Risk minimization problem, using synthetic and real-world datasets. Numerical results support our theoretical findings. Furthermore, we compare tSGHMC with its first-order counterpart, namely, the tamed unadjusted stochastic Langevin algorithm. Simulation results demonstrate that tSGHMC achieves lower root mean square error and expected excess risk across a range of tasks.
The approach proposed in this paper enables a more capable DDDAS paradigm by improving the efficiency of the data-model-optimization loop by extracting a generalization bound based on Rademacher complexity that reveals the role of the $k-neighborhoods and related parameters.
This paper proposes a tractable stochastic approach based on an entropic regularization of the distributionally robust value function, which makes it possible to compute stochastic gradient estimators, and the combination of these estimators with a stochastic Frank-Wolfe algorithm, allowing us to optimize the regularized robust objective while naturally handling constraints.
Theoretical analysis demonstrates that the proposed estimator is unbiased, attains finite variance, and satisfies a central limit theorem, and the results demonstrate that in large-scale applications, the unbiased algorithm can be 2–3 orders of magnitude more efficient than the “gold-standard” randomized Hamiltonian Monte Carlo.
Neil K. Chada, B. Leimkuhler, Daniel Paulin et al.· Annals of Statistics· 0 citations
Numerical experiments demonstrate that the bilevel RKHS method provides a more stable and competitive alternative to classical L-curve and generalized cross-validation strategies and that the adaptive RKHS norm is more accurate and robust than Lρ2- and ℓ2-norms for regularization.