Preconditioned Truncated Single-Sample Estimators for Scalable Stochastic Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910028563218432 |
|---|---|
| author | Xu, Tianshi Cai, Difeng Huang, Hua Chow, Edmond Xi, Yuanzhe |
| author_facet | Xu, Tianshi Cai, Difeng Huang, Hua Chow, Edmond Xi, Yuanzhe |
| contents | Many large-scale stochastic optimization algorithms involve repeated solutions of linear systems or evaluations of log-determinants. In these regimes, computing exact solutions is often unnecessary; it is more computationally efficient to construct unbiased stochastic estimators with controlled variance. However, classical iterative solvers incur truncation bias, whereas unbiased Krylov-based estimators typically exhibit high variance and numerical instability. To mitigate these issues, we introduce the Preconditioned Truncated Single-Sample (PTSS) estimators--a family of stochastic Krylov methods that integrate preconditioning with truncated Lanczos iterations. PTSS yields low-variance, stable estimators for linear system solutions, log-determinants, and their derivatives. We establish theoretical results on their mean, variance, and concentration properties, explicitly quantifying the variance reduction induced by preconditioning. Numerical experiments confirm that PTSS achieves superior stability and variance control compared with existing unbiased and biased alternatives, providing an efficient framework for stochastic optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24587 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Preconditioned Truncated Single-Sample Estimators for Scalable Stochastic Optimization Xu, Tianshi Cai, Difeng Huang, Hua Chow, Edmond Xi, Yuanzhe Numerical Analysis 60G15, 65F08, 65F10, 68W25 Many large-scale stochastic optimization algorithms involve repeated solutions of linear systems or evaluations of log-determinants. In these regimes, computing exact solutions is often unnecessary; it is more computationally efficient to construct unbiased stochastic estimators with controlled variance. However, classical iterative solvers incur truncation bias, whereas unbiased Krylov-based estimators typically exhibit high variance and numerical instability. To mitigate these issues, we introduce the Preconditioned Truncated Single-Sample (PTSS) estimators--a family of stochastic Krylov methods that integrate preconditioning with truncated Lanczos iterations. PTSS yields low-variance, stable estimators for linear system solutions, log-determinants, and their derivatives. We establish theoretical results on their mean, variance, and concentration properties, explicitly quantifying the variance reduction induced by preconditioning. Numerical experiments confirm that PTSS achieves superior stability and variance control compared with existing unbiased and biased alternatives, providing an efficient framework for stochastic optimization. |
| title | Preconditioned Truncated Single-Sample Estimators for Scalable Stochastic Optimization |
| topic | Numerical Analysis 60G15, 65F08, 65F10, 68W25 |
| url | https://arxiv.org/abs/2510.24587 |