← 研踪 PaperTrailarXiv:2610.35531 · v1
One Loss Resolves Signed Rank-One Gradient Fibers: Exact Decoding on Cycle and Theta Blocks
首次提交 2026-10-26 22:45
版本更新 2026-10-26 22:45
雷达观测 2026-10-29 00:35
摘要
For masked rank-one least squares with unrestricted signs, gradients reveal weighted margins and the loss reveals the target's squared norm. We prove that this one scalar resolves the gradient ambiguity on bipartite cycle and length-three parallel-path blocks: every target fixed before sampling and nonzero on cycle edges is identified almost surely by one legal positive query drawn from an absolutely continuous law. On six-cycle flowers, open target and query sets retain $3^r$ bounded gradient candidates. A common algebraic witness excludes cross-block energy cancellation. Cactus masks admit explicit exception certificates and target-uniform finite-grid bounds; theta blocks admit an existence guarantee. For nondegenerate cactus reductions, an exact decoder returns complete actual real lists, with bit cost polynomial in input length, the cycle-degree product $D$ and the optional budget parameter $2^κ$. Energy-coordinate propagation certifies singletons without a product join. The product $D$ can grow exponentially in cycle count. Exponential certificate-degree and output bounds, and weak NP-hardness at a fixed uniform query, characterize distinct costs of exact decoding.
作者备注：41 pages, 3 figures. Includes appendices and supplementary material
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-26 22:45 · 最新观测版本
One Loss Resolves Signed Rank-One Gradient Fibers: Exact Decoding on Cycle and Theta Blocks
For masked rank-one least squares with unrestricted signs, gradients reveal weighted margins and the loss reveals the target's squared norm. We prove that this one scalar resolves the gradient ambiguity on bipartite cycle and length-three parallel-path blocks: every target fixed before sampling and nonzero on cycle edges is identified almost surely by one legal positive query drawn from an absolutely continuous law. On six-cycle flowers, open target and query sets retain $3^r$ bounded gradient candidates. A common algebraic witness excludes cross-block energy cancellation. Cactus masks admit explicit exception certificates and target-uniform finite-grid bounds; theta blocks admit an existence guarantee. For nondegenerate cactus reductions, an exact decoder returns complete actual real lists, with bit cost polynomial in input length, the cycle-degree product $D$ and the optional budget parameter $2^κ$. Energy-coordinate propagation certifies singletons without a product join. The product $D$ can grow exponentially in cycle count. Exponential certificate-degree and output bounds, and weak NP-hardness at a fixed uniform query, characterize distinct costs of exact decoding.
查看此版本解读 →查看此版本原文 ↗