MPC Quantized Machine Learning——Jacobi SVD

[BingLiu0]

Pull Request

What problem does this PR solve?

Issue Number: Fixed #

Possible side effects?

• Performance:

• Backward compatibility:

[BingLiu0]

I have read the CLA Document and I hereby sign the CLA

[rivertalk]

/gemini review

[gemini-code-assist]

Code Review

The pull request introduces a Jacobi SVD implementation for secure multi-party computation (MPC) using the SPU framework. It includes the core algorithm, an emulation script for testing, and a unit test. Overall, the code is well-structured and addresses the task of implementing Jacobi SVD in a privacy-preserving setting.

Summary of Findings

• Potential Convergence Issues: The jacobi_svd function relies on a fixed number of iterations (max_iter). For larger matrices or matrices with certain properties, the algorithm might not converge within the specified number of iterations, leading to inaccurate results. Consider adding a check for convergence based on the change in singular values between iterations.
• Numerical Stability: The code calculates tau in jacobi_rotation and uses it to compute t, c, and s. When A[p, q] is close to zero, tau can become very large, potentially leading to numerical instability. Consider adding a small constant to the denominator to prevent division by zero or using an alternative approach to compute the rotation parameters.
• Testing with Different Matrix Types: The current test case uses a random symmetric matrix. It would be beneficial to add more test cases with different types of matrices (e.g., diagonal, orthogonal, ill-conditioned) to ensure the algorithm's robustness and accuracy under various conditions.

Merge Readiness

The pull request introduces a new Jacobi SVD implementation with supporting emulation and tests. While the code appears functional, there are potential issues related to convergence and numerical stability that should be addressed before merging. I recommend addressing the convergence and numerical stability concerns before merging. I am unable to directly approve this pull request, and other reviewers should also review this code before merging.

[gemini-code-assist]

When A[p, q] is close to zero, tau can become very large, potentially leading to numerical instability. Consider adding a small constant to the denominator to prevent division by zero or using an alternative approach to compute the rotation parameters.

Suggested change

	tau = (A[q, q] - A[p, p]) / (2 * A[p, q])
	t = jnp.sign(tau) / (jnp.abs(tau) + jnp.sqrt(1 + tau**2))
	tau = (A[q, q] - A[p, p]) / (2 * A[p, q] + 1e-12)
	t = jnp.sign(tau) / (jnp.abs(tau) + jnp.sqrt(1 + tau**2))

[gemini-code-assist]

The documentation mentions adjusting max_iter for different matrix sizes. However, it does not provide guidance on how to choose an appropriate value. Consider adding a heuristic or a formula to help users determine a suitable max_iter based on the matrix dimension or other relevant factors. Also, the algorithm might not converge within the specified number of iterations, leading to inaccurate results. Consider adding a check for convergence based on the change in singular values between iterations.

[gemini-code-assist]

The condition max_off_diag < tol only checks if the maximum off-diagonal element is below the tolerance. It does not guarantee that the singular values have converged. Consider adding a check based on the change in singular values between iterations to ensure convergence.

[gemini-code-assist]

The test case uses a random symmetric matrix. It would be beneficial to add more test cases with different types of matrices (e.g., diagonal, orthogonal, ill-conditioned) to ensure the algorithm's robustness and accuracy under various conditions.