- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the computational complexity of evaluating a ReLU neural network. Let L, d, and B denote the number of layers, the uniform width, and the input batch size, respectively. Evaluating this network requires O(BLd^2) operations when each input is processed independently. This paper aims to reduce this computational complexity by exploiting the structure of the ReLU activation function. It proposes a method that separates the evaluation problem into two components: (1) identifying the activation region containing each input and (2) applying the corresponding affine transformation. The paper derives upper bounds on the computational complexity of the proposed method.
Critical strengths
Computational complexity improvement: The paper shows that the affine transformations associated with the ReLU activation function can be reused across input batches when the inputs belong to a small number of activation regions. In this case, the evaluation cost can be reduced by a factor of when the activation patterns are known. This result quantitatively characterizes the computational benefits of shared activation patterns.
Identifying the main computational bottleneck: The paper separates the hardness of identifying activation regions and that of applying affine transformations. It shows that when the activation regions of the inputs are known, one can reuse affine transformations across inputs. However, determining the activation region of each input could be computationally expensive. This identifies detecting the activation regions as the key challenge in coming up with a faster evaluation.
Critical weaknesses
Restrictive assumptions for computational improvements: In Theorem 3.1, the speedup of can be achieved when the activation patterns are known and the batch size is sufficiently large (). However, identifying these activation patterns can itself be a computationally expensive task. Even though the paper proposes a certificate-based approach to resolve this issue, its guarantees may require an exponentially large batch size with respect to the input dimension. Hence, the theorem’s practical applicability is limited.
Lack of experimental validation: The paper does not evaluate its proposed method in experiments to investigate the claimed speedup in real applications. It is not clear that the proposed method can outperform the standard evaluation methods already existing in realistic applications.
Questions for authors
Theoretical novelty: In Theorem 3.1, can the authors explain the new technique exploited in it beyond the known piecewise-affine structure of the ReLU activation function when activation patterns are known?