Error Analysis of Parameter Prediction via Gaussian Process Regression and Its Application to Weighted Jacobi Iteration

1. Problem Statement

The Weighted Jacobi Iteration (WJI) is a classical method for solving linear systems $Ax = b$, where convergence speed is governed by the spectral radius of the iteration matrix. The optimal convergence rate depends on the relaxation parameter ($\omega$), which is theoretically determined by the minimum and maximum eigenvalues ($\lambda_{min}, \lambda_{max}$) of the matrix $D^{-1}A$ (where $D$ is the diagonal of $A$).

The Core Challenge:
For large-scale linear systems, computing the exact spectral radius or eigenvalues is computationally prohibitive. Consequently, determining the optimal $\omega$ in practice is difficult. While data-driven approaches like Gaussian Process Regression (GPR) have been used to predict optimal parameters, there is a lack of rigorous theoretical frameworks linking GPR prediction errors directly to the convergence guarantees of the resulting iterative algorithms. Existing probabilistic error bounds are often difficult to integrate into the deterministic convergence analysis of numerical algorithms.

2. Methodology

The authors propose a unified framework that combines a novel theoretical error analysis of GPR with the convergence analysis of the Weighted Jacobi Iteration.

A. Novel Theoretical Framework for GPR Error Bounds

Instead of relying solely on standard probabilistic bounds, the authors introduce a function-space decomposition approach:

• Decomposition Strategy: The true function $f(z)$ is decomposed into two components:
  1. A projection term onto a finite-dimensional subspace spanned by basis functions $\{p_i\}$.
  2. A global correction term orthogonal to this subspace within the Reproducing Kernel Hilbert Space (RKHS).
• Deterministic Bound Derivation: By leveraging this decomposition, the authors derive a deterministic error bound for the GPR prediction $f^*(z)$ relative to the true function $f(z)$.
• Key Result: They prove that the squared error is bounded by the variance of the prediction:
  $$|f(z) - f^*(z)|^2 \leq C \cdot \text{Var}(f^*(z))$$
  where $C$ is a non-negative constant related to the norm of the true function in the RKHS. This result is extended to noisy observations and cases involving kernel misspecification (using Sobolev space embeddings).

B. Application to Weighted Jacobi Iteration

• Algorithm: The authors replace the unknown optimal $\omega_{opt}$ with a GPR-predicted parameter $\omega^*$.
• Convergence Analysis: Using the derived error bounds, they establish sufficient conditions for the convergence of the WJI.
  • They prove that if the prediction error (bounded by the GPR variance) is sufficiently small relative to the eigenvalue gap of $D^{-1}A$, the spectral radius $\rho(I - \omega^* D^{-1}A)$ remains less than 1.
  • Specifically, convergence is guaranteed if:
    $$C_\omega \cdot \text{Var}(f^*) \leq \frac{2\lambda_{min}}{\lambda_{max}(\lambda_{max} + \lambda_{min})}$$
  • This analysis allows the integration of various GPR error bounds (deterministic or probabilistic) into the convergence criteria.

C. Complexity Analysis

• GPR Training: $O(M^3)$ where $M$ is the size of the training set (typically $M \ll N$, the system size).
• Prediction: $O(M^2)$.
• Iteration: Each WJI step is $O(N^2)$.
• Total Complexity: $O(M^3 + kN^2)$, where $k$ is the number of iterations. Since $M$ is small, the overhead is negligible compared to the acceleration gained in $k$.

3. Key Contributions

1. New Proof Method for GPR Error Bounds: The paper introduces a function-space decomposition technique that provides a clear, deterministic link between GPR prediction variance and the absolute error of the predicted function.
2. Rigorous Convergence Conditions: It establishes the first set of convergence conditions for WJI that explicitly incorporate GPR prediction errors, bridging the gap between machine learning prediction and numerical linear algebra convergence theory.
3. Generalizability: The framework is designed to be compatible with different kernel functions and noise scenarios, allowing it to be combined with existing GPR error bounds.
4. Practical Validation: The method is tested on 2D Laplace and 3D convection-diffusion equations, demonstrating significant performance gains.

4. Numerical Results

The authors tested the method on three scenarios using MATLAB:

• 2D Laplace Equation (Neumann BCs):
  • Compared against standard Jacobi Iteration (JI).
  • Result: WJI with GPR-predicted $\omega$ reduced iteration counts from ~25,000 (JI) to ~3,000 (WJI+GPR) across various grid sizes ($n=60$ to $120$).
  • Kernel Performance: Gaussian, Periodic, and Additive kernels were tested. While the Periodic kernel showed the lowest variance, the Additive kernel often yielded the best CPU time, suggesting that minimizing variance is not the sole factor for performance (likely due to the $L_\infty$ norm of the true function).
• 3D Convection-Diffusion Equation (Dirichlet BCs):
  • Result: Similar to the 2D case, WJI+GPR significantly outperformed JI. For $n \geq 100$, JI required massive CPU time, while WJI+GPR converged in seconds.
  • Small Matrix Case: For very small matrices ($n=60$), the overhead of GPR prediction slightly increased CPU time despite fewer iterations, highlighting a trade-off for small-scale problems.
• 3D Convection-Diffusion (Small Diffusion Coefficient):
  • Result: Standard JI failed to converge within 500,000 iterations for $n \geq 80$. WJI+GPR converged in under 1,000 iterations.
  • Kernel Sensitivity: The Periodic kernel provided the best acceleration and lowest variance for this specific problem type, validating the importance of kernel selection based on the underlying physics of the parameter function.

5. Significance and Future Work

• Theoretical Impact: The paper provides a rigorous mathematical justification for using "black-box" machine learning models (GPR) to tune parameters in classical numerical algorithms. It moves beyond empirical observation to provide provable convergence guarantees.
• Practical Impact: It offers a robust strategy for accelerating stationary iterative methods in large-scale scientific computing without the need for expensive eigenvalue computations.
• Future Directions:
  • Extending the framework to Successive Over-Relaxation (SOR) methods where the parameter is embedded in the matrix inverse.
  • Applying GPR to parameter prediction in Krylov subspace methods (preconditioners).
  • Investigating parallel and mixed-precision strategies to further accelerate WJI.
  • Exploring strategies for nonlinear problems.

In conclusion, this work successfully bridges the gap between data-driven parameter prediction and classical numerical analysis, proving that GPR can not only predict optimal parameters but also guarantee the convergence of the resulting iterative schemes under specific, verifiable conditions.