Aug 2026· Mathematics· Vol 14, pp. 2930· 0 citations· 17 references
Abstract
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.
We settle a conjecture of Bandeira, Kennedy and Singer, arising from their analysis of approximation ratios for the little Grothendieck problem over the unitary group, by proving that the average singular value of a normalized square complex Gaussian random matrix strictly decreases with the dimension. The starting point is a recurrence relation of Abreu, derived from the Christoffel--Darboux formula and a Tur\'{a}n determinant for Laguerre polynomials. This recurrence reduces the problem to the estimation of a mixed Laguerre integral. We transform this estimate into an explicit finite inequality by expanding the relevant integrals in the orthogonal basis associated with the weight $x^{1/2}\,\mathrm{e}^{-x}$. A telescoping identity then converts the resulting inequality into a positive form. The final positivity argument combines explicit estimates for central binomial coefficients, a logarithmic lower bound, and a finite verification of small dimensions. This completes the proof that the average singular value strictly decreases with the dimension in the square complex Gaussian case. As a consequence, the same monotonicity is obtained for $N\times(N+\lambda)$ complex Gaussian matrices with fixed rectangularity $\lambda=0,1,2,\dots$.
In this work, we develop a unified matrix-level asymptotic calculus for plug-in non-parametric maximum likelihood estimators in finite Markov models. Starting from the asymptotic distribution of the estimated transition matrix, the limiting object is kept in its natural matrix form as a Gaussian random matrix, while the corresponding row-wise vector representation remains immediately available. The main point is that the stochastic constraints of the transition matrix need not be removed by a minimal parametrization: they are carried by the tangent directions and by the covariance structure of the limiting Gaussian matrix, whereas the relevant differentials are computed directly in matrix spaces. A single stochastic calculus theorem gives first-order limit distributions, finite-order developments for sufficiently differentiable functionals, and analytic expansions when the functional is analytic. This provides a common source for asymptotic formulas for matrix powers, stationary characteristics, finite-dimensional curves of Markov characteristics, additive-functional variances, entropy-type quantities and reliability indicators. The resulting covariance operators lead directly to confidence intervals, confidence regions, simultaneous finite-dimensional bands and Wald-type tests. Since the derivations are expressed through matrix products and Kronecker representations rather than coordinate-wise calculations, the method also gives substantial simplifications and, in many cases, computational gains. The second-order terms identify curvature corrections of smooth functionals and provide refined approximations whenever higher-order information is useful.
G. Gavrilopoulos, Samis Trevezas, Irène Votsi· 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.
Constructing confidence regions for stochastic gradient descent (SGD) ideally requires estimating the asymptotic covariance matrix, a severe computational bottleneck in high dimensions. Traditional cancellation-based batch means methods bypass this estimation but require inverting a sample batch covariance matrix. This introduces strict mathematical degeneracy when the parameter dimension exceeds the number of batches. To address this problem, we utilize equal batch size batch means method and propose a simultaneous, marginal-friendly framework. The proposed marginal statistics has a asymptotic Student's $t$-distribution, and eliminates the matrix inversion step, entirely circumventing high-dimensional degeneracy. To achieve valid simultaneous coverage, we present an algorithm utilizing wild bootstrap samples drawn from a statistic as a function of only the diagonals of the variance-covariance estimator, and to further incorporate the contribution of cross-dependencies, we introduce an efficient Quasi-Monte Carlo procedure utilizing a $t$-copula approximation. Additionally, we integrate a Lugsail variance estimator to aggressively correct finite-sample bias and under-coverage. The proposed methodology delivers interpretable, simultaneous hyper-rectangular confidence regions that are statistically robust, memory-efficient, and strictly scalable for high-dimensional inference. The theoretical results are supported by extensive numerical simulation analysis through various aspects of dimension, number of batches and error structure.
We study low-precision computation of C=AB with both factors quantized. We derive an exact finite-dimensional identity for the expected squared product error under independent, zero-mean entrywise errors with known variance fields; it holds exactly for non-overloading subtractive dither and for independent stochastic rounding, and we empirically assess deterministic round-to-nearest (RTN). Using the product-preserving equivalence AB=(AT)(T^{-1}B), we formulate contraction-gauge preconditioning: jointly choosing a factor representation and its sharing pattern before quantization. Preconditioning can reduce product error but may require extra transformed, quantized copies of the opposite operand: a shared transform needs one copy, a block-specific transform up to one per block. Within the bounded family of positive diagonal gauges (folds), a geometric program computes a globally optimal shared fold and a linear program decides whether the identity fold is already optimal. For other families we derive computable selection statistics -- tail index for scaling, profile spread for partitioning, coherence and weighted-Gram energy for rotations, slice-energy covariance for hierarchy depth -- with upper bounds for ranking heuristic candidates. Across twelve linear products from a trained three-block image classifier, median within-product rank correlations between dither-model predictions and deterministic-RTN errors are 0.937 at 8 bits and 0.918 at 4 bits. The GP fold cuts held-out product error over the identity fold by 18.0% (8-bit) and 20.5% (4-bit) in geometric mean, beats a SmoothQuant-style grid baseline at both precisions and on ten of twelve products, and lowers composed logit MSE by 15.4% and 26.4%. We thus provide exact stochastic product-error accounting, certified selection within the diagonal family, and a common objective for evaluating reusable transform candidates under RTN.
Piyush Sao, N. Miniskar, Pedro Valero-Lara et al.· 0 citations
A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$, uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$-SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.
