Checking a Recommender's Low-Rank Fit Without Seeing Its Data

A platform that fills in a user-by-item ratings table (matrix completion: guessing the missing entries of a table that is assumed to have a few underlying patterns) may be asked by a regulator to show that its published predictions really come from a declared, well-behaved fitting procedure applied to the real data. The platform does not want to reveal the ratings or the model. Zero-knowledge proofs (cryptographic protocols that convince a checker a computation was done correctly while revealing nothing else) could in principle settle this. In practice they break on exactly the operations that good low-rank fitting needs: singular value decompositions and the nonlinear "shrink each singular value" steps. Proving every iteration of such a solver inside a proof system is hopeless at realistic sizes.

This note proposes not to prove the solver's run at all. Instead, the platform proves that its output satisfies a short optimality certificate. For a broad class of penalties, including the nonconvex ones that avoid the nuclear norm's uniform shrinkage of every singular value, that certificate can be checked using only matrix multiplications plus a handful of scalar function evaluations. Those are precisely the two things existing zero-knowledge tools already handle well. The cost of the proof then depends on the matrix size and the recovered rank, not on how many iterations the solver ran. Using a nonconvex penalty in place of the nuclear norm costs almost nothing extra to verify, so the auditor gets the accuracy benefit of the better penalty for free.

Core Claim

The standard convex approach replaces rank with the nuclear norm (the sum of singular values). Its update step subtracts the same amount $\lambda$ from every singular value, which shrinks the strong signal directions as much as the noise. Olsson et al. and Zhao et al. document the resulting bias. On MovieLens 100K, Zhao et al. report a test error (TRMSE) of 1.0051 at recovered rank 30 for the Transformed $L_1$ penalty (TL1), against 1.1586 at rank 59 for the nuclear norm.

Nonconvex penalties fix this by shrinking large singular values less. Generalized Singular Value Thresholding gives the key structural fact for our purposes: the proximal map of any lower-bounded penalty $g$ preserves the ordering of singular values. Proximal map here means the "shrink step" that, for each singular value $\sigma$, returns the value balancing closeness to $\sigma$ against the penalty $g$.

Ordering preservation lets us write the stationarity condition of the solver used there (generalized proximal gradient) in a verifiable form. Let $M$ be the committed observed ratings on index set $\Omega$, and let $X$ be the claimed completion with rank $k$ and factorization $X = U S V^\top$. The solver's step size is $\mu$. Define

$$Y = X - \mu\, P_\Omega(X - M),$$

where $P_\Omega$ keeps only observed entries. The fixed-point condition $X = \mathrm{prox}_{\mu g}(Y)$ holds if three things are true. First, $YV = UD$ and $U^\top Y = DV^\top$ for a diagonal $D$, with $U$ and $V$ having orthonormal columns. Second, $s_i = \mathrm{prox}_{\mu g}(d_i)$ holds entrywise. Third, the leftover part $R = Y - UDV^\top$ has spectral norm at most the zeroing threshold $\tau_g$ of the shrink step. That threshold has a closed form for TL1, the logarithmic penalty, and the minimax concave penalty (MCP).

The spectral-norm bound is certified by an extra factor $L$ with

$$\tau_g^2 I - R^\top R = L L^\top,$$

which is again a matrix-multiplication identity. Every check is therefore either a committed matrix product, of the kind zkMatrix proves with quadratic prover time, or a scalar nonlinear function evaluated about $k$ times, of the kind zkUCB already handles with piecewise-linear approximations and fixed Newton iterations.

The new element is this reduction. It turns "the platform honestly ran a rank-adaptive, bias-corrected completion on its private data" into a proof whose cost does not grow with the iteration count. We also add a perturbation analysis showing what an approximately satisfied, quantized certificate guarantees.

Research Program

The program has three parts.

The first part is the certificate itself. We will state it for the family of penalties covered by Lu et al.'s monotonicity result. Arbitrary spectral functions are beyond its reach, and SCAD is a case Lu et al. flag as violating their solver's conditions. For SCAD we will test whether the certificate still characterizes stationary points even where the solver's convergence guarantee fails. We will then derive tolerance bounds. If each identity holds only up to a residual $\epsilon$ because of fixed-point quantization, a Weyl-type singular value perturbation argument should bound the distance from $X$ to a true fixed point by a constant times $\epsilon$ divided by the gap between $\min_i d_i$ and $\tau_g$. That is the usual form of perturbation bounds for singular subspaces. This tells us how many bits the quantization needs, and we will measure whether the "quantization bonus" zkUCB observed at $2^8$ has any analogue here or whether more precision is required.

The second part is the protocol. The platform commits to $M$, $X$'s factors, $D$, and $L$, and proves the identities in zero knowledge. Optionally it also proves the recovered rank $k$ and the error on a committed held-out split. The auditor sees only these claims. This is complementary to Homomorphic Matrix Completion, which hides user vectors from an untrusted server by adding a structured low-rank mask but uses nuclear-norm completion and offers no proof that the server computed honestly. Our setting reverses the trust direction: the data holder is the party whose computation must be checked.

The third part is cost engineering. The left- and right-factor checks involve tall, thin matrices of width $k$. The leftover-part certificate is the expensive piece, at size items × items. It shrinks when the recovered rank is lower and the gap above $\tau_g$ is larger. This creates a concrete, testable link between the two directions. Because the nonconvex penalty tends to recover a smaller rank and a larger spectral gap than the nuclear norm (rank 30 against 59 in Zhao et al.), it should produce both a cheaper proof and a looser precision requirement.

Baselines

The naive reference is the nuclear-norm completion proved by the same certificate method, which is the special case $g(\sigma)=\sigma$ with $\tau_g=\mu\lambda$. Comparing against it isolates what the nonconvex penalty buys in accuracy and in proof cost under an identical verification pipeline. It counts as beaten if TL1 matches Zhao et al.'s reported accuracy advantage after quantization, with prover time no worse.

The strongest prior zero-knowledge competitor is to prove the full solver trace iteration by iteration, in the style of zkUCB. Each iteration would use zkMatrix-style products, with an in-circuit SVD approximated by fixed-count iterations. We will implement it on the same matrices with the same quantization and the same proof backend. The only reference cost we have is zkMatrix's reported figure of about 197 seconds of prover time and about 70 ms of verifier time for a single 1024 × 1024 product. No reported result was found on Lacuna for zero-knowledge proofs of any matrix completion or SVD-based procedure. The certificate approach counts as beating trace proving if its prover time is lower by at least the factor of the solver's iteration count, at equal precision.

A third baseline is fixed-rank factorization with a stationarity certificate. Here the gradient of the squared loss in $U$ and $V$ vanishes, which is checkable by matrix multiplication alone, similar to the setting of DPLMC. It is the cheapest certifiable alternative. This is also the ablation that tests whether the singular-value penalty and its leftover-part bound are worth their cost. All methods will get the same tuning budget over their regularization and rank parameters on a validation split.

Why not just…?

Why not just run the solver inside a trusted hardware enclave? This is a real competitor on cost, and we will report enclave runtimes for the same solvers. It answers a different trust question, though. AudiTEE shows that enclaves need extra indexing machinery to scale, and that they carry hardware-vendor trust and side-channel exposure. They also have limited protected memory (128 MB in legacy SGX). A proof can be checked by anyone without trusting the hardware. If a regulator accepts vendor trust, the enclave wins, and we will say so.

Why not just certify the convex nuclear-norm problem, where stationarity means global optimality? This is the strongest conceptual objection. Our nonconvex certificate proves only that the output is a stationary point of the declared objective, not the best possible one. Our response is empirical rather than rhetorical. If the nuclear-norm certificate turns out comparably cheap, the auditor faces a choice between a global-optimality guarantee with the accuracy and rank gap Zhao et al. report, and a stationarity guarantee with better accuracy. We will additionally prove held-out error, so that the quality claim does not rest on optimality alone.

Why not just fix the rank and certify a factorization? If the auditor knows the rank, this may suffice, and the ablation will show it. The cost is that a misspecified rank goes undetected, and the factorized loss has no shrinkage control. DPLMC's own analysis relies on a fixed, known rank and uniform sampling. We will test on non-uniformly sampled data, Coat, where Zhao et al. report TL1's advantage holds.

Proposed Experiments

We will use MovieLens 100K as the primary benchmark because it has a reported TL1 versus nuclear-norm reference, and the 400-movie MovieLens 10M subset because it matches the scale used by Homomorphic Matrix Completion. Coat will test sampling bias. Zhao et al.'s 500 × 500 synthetic matrices with uniform, imbalanced, and highly imbalanced sampling will let us control the rank and the spectral gap.

For each penalty (nuclear norm, TL1 with $a=100$, logarithmic, MCP) and each quantization level from $2^8$ to $2^{24}$, we will measure test error and recovered rank after quantization. We will also measure prover time, verifier time, proof size, and the fraction of honestly computed outputs that pass the certificate at the derived tolerance.

The adversarial check is whether forged outputs are rejected. These include early-stopped iterates, outputs computed on a perturbed copy of $M$, and outputs fit with a different penalty than the one declared.

Three outcomes would be decisive. The first is that the bias-corrected penalty keeps its accuracy edge after quantization. The second is that certificate cost is flat in iteration count while trace-proving cost grows linearly. The third is that lower recovered rank and larger gap translate into measurably cheaper leftover-part certificates. If the third fails, the link between the two directions is only additive, and the contribution reduces to a verification method that happens to accommodate nonconvex penalties.