- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper solve the problem that If the hard min/max operations in dynamic programming are replaced with differentiable softmin/softmax, can the originally complex structured inference be implemented using smaller neural networks or computational circuits? They prove the conclusion via proof and experiments.
Critical strengths
The conclusion of this paper is important. I like the proof structure. The paper is relatively easy to follow.
Critical weaknesses
The main lower bound transfer theorem requires that the approximation error of the smooth network is sublinear along every fractional ray. However, the corollary establishing the exponential lower bound for the regularized linear-code inference layer does not restate this critical approximation condition in its statement. Without this condition, the claimed lower bound does not hold for circuits arbitrarily constructed from admissible operators. The authors should explicitly state the assumptions within this corollary, and carefully distinguish the exact lower bound for pure min-plus circuits from its transfer to approximate, smooth implementations.
Experiments are primarily conducted on synthetic linear codes and truncated trellis architectures. It is difficult to assess the extent to which the conclusions characterize more general learnable DAG architectures or real-world structured prediction tasks. The authors should clarify whether the reported quantity is the global supremum or the empirical maximum over sampled inputs, and provide stronger validation beyond fixed trellis truncation.
Questions for authors
See Weakness.