Rethinking 3D Convolution in $\ell_p$-norm Space

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-02 17:38:52

Abstract: Convolution is a fundamental operation in the 3D backbone. However, under certain conditions, the feature extraction ability of traditional convolution methods may be weakened. In this paper, we introduce a new convolution method based on  $\ell_p$-norm. 
For theoretical support, we prove the universal approximation theorem for $\ell_p$-norm based convolution, and analyze the robustness and feasibility of  $\ell_p$-norms in 3D point cloud tasks. Concretely, $\ell_{\infty}$-norm based convolution is prone to feature loss. $\ell_2$-norm based convolution is essentially a linear transformation of the traditional convolution.  $\ell_1$-norm based convolution is an economical and effective feature extractor. We propose customized optimization strategies to accelerate the training process of $\ell_1$-norm based Nets and enhance the performance. Besides, a theoretical guarantee is given for the convergence by \textit{regret} argument. We apply our methods to classic networks and conduct related experiments. Experimental results indicate that our approach exhibits competitive performance with traditional CNNs, with lower energy consumption and instruction latency.

Main paper: 
  
 Appendix:  


Decision: The  paper introduced a new convolution method based on ℓp-norm. For theoretical support, it proved the universal approximation theorem for ℓp-norm based convolution, and analyze the robustness and feasibility of ℓp norms in 3D point cloud tasks. The paper received the recommendations of 2XAccept, 1XStrong Accept and 1XBorderline Accept. Given the consistent recommendations, I think the paper could be accepted. The authors are requested to revise the paper as per the rebuttal.

Reviews: review: paper_summary: paper_summary: This paper introduces a new convolution method based on the \( L_p \)-norm. The authors provide a theoretical foundation by proving the universal approximation theorem for \( L_p \)-norm networks and analyzing the robustness and feasibility of \( L_p \)-norms in 3D tasks. Several key findings are highlighted in this work: 

1. \( L_\infty \)-norm convolution is prone to feature loss. 
2. \( L_2 \)-norm convolution essentially performs a linear transformation in traditional CNNs. 
3. \( L_1 \)-norm convolution is an economical and effective method for feature extraction. 

To further enhance the capabilities of \( L_1 \)-norm based networks, the paper proposes a series of customized training and optimization strategies.

In the experimental section, the authors apply their methods to classical 3D networks such as PointNet and PointNet++, achieving competitive performance at a lower cost. In summary, the \( L_1 \)-norm network can achieve similar performance to traditional convolutional networks but with reduced computational cost and lower instruction latency.
strength_weakness: strength_weakness: There are some weakness/concerns need to be discussed:

--Noise distribution is an interesting issue, but this paper only analyzes the impact of Gaussian noise when considering random noise. How do the authors solve other noise distribution conditions？

--In this paper, how to come up with the idea of the \( L_p \)-norm convolution  is not discussed in detail, although its mechanism is well  illustrated.
questions: questions: --This paper claim that \( L_p \)-norm are more robust than that based on inner product, however, why only \( L_2 \)-norm  is proved? how about the other cases when $p$ differs?

--In Table 2, the results from \( L_2 \)-norm Net is also competitive, why not choose the \( L_2 \)-norm Net for the further study but  \( L_1 \)-norm?

--In Sec 3.1, the proposed Universal Approximation, I wonder why  the second part is presented through integration? this is confusing compared with other works such as  "Multilayer feedforward networks universal approximator"？

Overall, I have some questions about the theory and motivation above, which hopes to be answered.
limitations: limitations: N/A
paper_summary: paper_summary: This paper addresses the challenge of enhancing the representational capacity of traditional convolution methods. To tackle this issue, the authors introduce a novel convolution approach based on $\ell_p$-norm and offer customized optimization strategies to expedite the training process. Extensive theoretical and empirical results have verified that the proposed algorithms demonstrate competitive performance compared to other baselines.
strength_weakness: strength_weakness: 1. The writing of this paper requires improvement, particularly in providing additional details regarding the proposed method. The current version of this manuscript may lead to reader confusion.

2. The role of the theoretical results presented in this paper is unclear. There appears to be a gap between the theoretical guarantees and the empirical evidence provided.
questions: questions: 1. The authors ought to include a formal definition of the "$\ell_p$ norm space" concept in the title of this paper.

2. The formulation of the proposed convolution operator in Eq. 2 on the 35th line of page 2 lacks an intuitive explanation, which may confuse the reader.

3. What precisely is the definition of $\mathcal{P}(S)$ in Eq. 3? Additionally, the primary method proposed in this paper is only briefly introduced in the introduction without further detailed description, making it less reader-friendly.

4. It appears that the proposed training strategy "Dynamic Learning rate Controller" is seemingly unrelated to the $\ell_p$ convolution method, if I haven't overlooked anything.

5. There are several errors are evident in theorem 2. Initially, the mismatch between the subscripts $k$ and $t$ in the statement "we could show that for any convex functions $\lbrace h_k \rbrace_{t=1}^{T^*}$ " is notable. Furthermore, it would be beneficial if the authors could clarify the significance of $h$. Moreover, although this theorem addresses convex functions, it is crucial to acknowledge that numerous deep learning tasks entail non-convex functions. In conclusion, the reasoning behind the authors' choice to include a regret analysis in theorem 2 within this paper lacks clarity.

6. Building on the previous point, it is advisable for the authors to undertake a conventional convergence analysis for the proposed optimization algorithms. This recommendation stems from the availability of numerous well-established mathematical tools designed for assessing convergence in offline optimization, particularly under non-convex or unbounded gradient conditions. These tools are often better suited for the intricacies of deep learning environments.

7. In the experimental section, it is recommended that the authors provide a comprehensive outline of the setup for the online learning tasks they consider, particularly detailing how data arrives sequentially. Additionally, the experimental section overlooks sequential decision tasks or time series tasks. Therefore, I suggest that the authors include these related tasks to further strengthen the justification for providing a regret guarantee in theorem 2. Besides, as this paper is affiliated with the learning theory track, the empirical results presented seem somewhat disconnected from the theoretical findings. Specifically, while theorem 2 offers a regret guarantee for the proposed method, the metric used in the experimental section does not measure regret.

8. In comparing the proposed method with baseline methods, the authors appear to have neglected to consider recent online learning methods, such as online non-convex learning using follow-the-perturbed-leader [1,2].

[1] Suggala, Arun Sai, and Praneeth Netrapalli. "Online non-convex learning: Following the perturbed leader is optimal." Algorithmic Learning Theory. PMLR, 2020.

[2] Suggala, Arun, and Praneeth Netrapalli. "Follow the perturbed leader: Optimism and fast parallel algorithms for smooth minimax games." Advances in Neural Information Processing Systems 33 (2020): 22316-22326.
limitations: limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
paper_summary: paper_summary: The paper proposes for using the $\ell_{p}$ norm in 3D convolution as a substitute for the inner product. Out of different choices, the authors pick the $\ell_{1}$-norm because it's faster and uses less energy than the inner product. This is because the $\ell_{1}$-norm relies on addition, which is simpler computationally. To optimize the $\ell_{1}$-norm-based convolution models, they propose a tailored optimization approach leveraging Mixed Gradient Strategy and Dynamic Learning Rate Controller. Finally, the method is evaluated on ModelNet10 and ModelNet40 datasets, showcasing its usage in learning point cloud features for object classification.
strength_weakness: strength_weakness: 1 )  The baseline models should be detailed introduced, including the model structure, integration (i.e., replacing) method of the proposed method, just as Table 8 from Ablation Experiments.

2 ) The layout of Table 5 needs to be further optimized, such as splitting it into two independent tables for parallel layout.
questions: questions: 1 )  Is there any basis for the authors to assume that the mean of data **X** is 0 when discussing robustness?

2 )  The authors discuss regret without detailed motivation, How does it works? I wonder if it is necessary to introduce the regret. 

3 ) There are many symbols in this article, it is recommended to add more explanations  in a separate section.
limitations: limitations: See weakness and questions.
paper_summary: paper_summary: The paper proposes using the \( \ell_p \)-norm, specifically the \( \ell_1 \)-norm, to replace the classic squared \( \ell_2 \)-norm convolution in 3D tasks. The \( \ell_1 \)-norm kernel function relies on addition, reducing computational cost. Initial gradient implementation revealed insufficient gradient values. To address this, the authors gradually transition the significant gradient from \( \ell_2 \) to \( \ell_1 \) as training progresses and employ momentum updates and learning rate scheduling. By replacing traditional 3D networks with their \( \ell_1 \)-norm networks, the paper demonstrates competitive performance on ModelNet classification and S3DIS semantic segmentation tasks at significantly lower costs.
strength_weakness: strength_weakness: Minor typos error:

i) In L-651, it should be "The *\ell_p*-norm" rather than ""The \ell_p norm""

ii) Very few words require consistent capitalization.

iii) Formulas in separate rows may have missing order numbers, it is recommended to unify this style.

iv) The reference format is not uniform enough.
questions: questions: i)  The current experiments seem to be on small datasets. Does the current method perform well on larger datasets? 

ii)  During training, The key idea of this paper is to use the $\ell_2$ gradient. As far as I am concerned, another potential way is to use $\ell-_\infty$ gradients.  The dual space of $\ell__\infty$ is the $\ell_1$ norm; Thus, the gradients of $\ell_ _\infty$ will be sparse. Why did the authors not try this idea and speed up the training time?

iii)  The \ell-p-norm Space measurement can be also seen in other filed, such as  image analysis[1], Inpainting[2] , the author claim that "these method can't be **directly** applied into 3D tasks", why?

iv)  The proposed lower bound and upper bound are Eq(13) and Eq(14), why the authors design the bounds as these?



[1] Generalized 2-D principal component analysis by Lp-norm for image analysis.

[2] Rank-One Matrix Approximation With ℓ*p*-Norm for Image Inpainting.
limitations: limitations: More generalization experiments on other datasets can be considered.

Comments: title: Official Comment by Authors of Paper 1528.
Official Comment
Official Comment by Reviewer VAmn
comment: Thank you for your reply. Regarding the issue you are concerned about, we will further clarify it below: 

----

① Firstly, non-convex functions present significant challenges in theoretical analysis due to the limited tools available for studying their behavior. However, since most commonly used loss functions are either convex or can be approximated by convex functions, our theoretical results offer valuable insights and practical guidance.

----
② Here, we also provide the proof of the convergence theorem using conventional concentration inequalities under ***non-convex function*** and Hölder continuous assumption conditions (refer to Appendix C for notation definitions):

**Assumption 1**. Let $\alpha \in (0, 1]$ and $L > 0$, we assume that the gradient of $f(x)$ is $\alpha$-Hölder continuous in the sense that:

$\begin{aligned}\Vert \nabla f(x_l)-\nabla f(x^*) \Vert \leq L \Vert x_l-x^* \Vert _2^\alpha,\quad\forall x_l,x^*\in\mathbb{R}^n\end{aligned}$

As demonstrated in [1], for any function $f(x): \mathbb{R}^n \mapsto \mathbb{R}$ with Hölder continuous gradients, we have the popular lemma playing an important role in our analysis. Our proof based on our algorithms provides a quantitative measure on the accuracy of approximating $f(x)$ with its first-order approximation.

**Lemma 1.** Let $ f : \mathbb{R}^n \mapsto \mathbb{R} $ be a differentiable function. Let $ \alpha \in (0, 1] $ and $ L > 0 $. If for all $ x_t, x^* \in \mathbb{R}^n$

$\Vert \nabla f(x_t)-\nabla f(x^*) \Vert _2\leq L \Vert x_t-x^* \Vert _2^\alpha,$

then, we have

$f(x^*) - f(x_t) \leq \langle x^* - x_t, \nabla f(x_t) \rangle + \frac{L}{1 + \alpha} \Vert x^* - x_t \Vert _2^{1 + \alpha}.$

Let  $( \mathcal{F} \subseteq \mathbb{R}^n )$ be a feasible set satisfying Assumption 1, and $f \in \mathcal{F}$, we have:
$$f(x^*) - f(x_t) \leq \langle x^* - x_t, g_t \rangle + \frac{L}{1 + \alpha} \Vert x^* - x_t \Vert _2^{1 + \alpha}$$
Next, by calculating and combining equation 25 in Appendix C, since  $m_t$  is gradually approaching the optimal  $m^*$, it is reasonable to believe that  $x_t$  is also approaching the optimal  $x^*$. So for some large $t = T$, we have:

$T\cdot(f(\mathbf{x} _ t)-f(\mathbf{x}^*))\leq\sum _ {t=1}^T\left(\langle g _ t,x _ t-x*\rangle\right)+\sum _ {t=1}^T\frac{L}{1+\alpha} \Vert x^*-x _ t \Vert _ 2^{1+\alpha}$

$=\sqrt{T}\cdot\left(\frac{B_{\infty}^{2}\cdot n\cdot p_{1}^{-1}}{2(1-q_{1})}\cdot(1+2q_{0}q)+\frac{2\cdot\alpha_{2}(1)B_{2}^{2}}{1-q_{1}}\right) -\frac{\alpha_{2}(1)B_{2}^{2}}{1-q_{1}}+\frac{L}{1+\alpha}\sum_{t=1}^{T}\left(\sum_{i=1}^{n}\alpha(t)^{1/2}(x^{*}(i)-x_{t}(i))\right)^{2+2\alpha}$

Combine the argument above and notice that $\alpha(t)^{-1} \leq p^{-1}_1 \cdot \sqrt{T}$, we have:

$\Vert f(\mathbf{x} _ {t})-f(\mathbf{x}^{*}) \Vert \leq\frac{1}{\sqrt{T}}\cdot\left(\frac{B _ {\infty}^{2}\cdot n\cdot p _ {1}^{-1}}{2(1-q_{1})}\cdot(1+2q _ {0}q)+\frac{2\cdot\alpha _ {2}(1)B _ {2}^{2}}{1-q _ {1}}+\frac{B _ {\infty}^{2}\cdot n^{2+2\alpha}\cdot L}{(1+\alpha)\cdot p _ {1}}\right)=O(\frac{1}{\sqrt{T}})$

Therefore, for any $\alpha$-Hölder continuous functions, our proof of convergence still holds. This is also a proof where the regret method can be applied. However, for some singular non-convex $f$, this proof may not hold. Nevertheless, under the online learning regret framework in our paper, it can still assist us in understanding the convergence.

# Reference 
[1] Unregularized online learning algorithms with general loss functions. *Applied and Computational Harmonic Analysis 2017*.

----
③ In practice,  the experiments demonstrate that the proposed network integrated with the proposed optimization strategy retains its convergence properties. This is supported by the Sec.5 and Sec.E.

----
If our rebuttals do not address your concerns to some extent, we would be happy to have further discussions.
Your feedback is an important reference for us to improve the quality of our paper, and we attach great importance to it. Thank you again for your time and effort. We look forward to your reply.
I appreciate the authors for addressing most of my concerns. However, I am still confused about the choice to conduct the theoretical analysis on a convex assumption, especially considering the well-established body of analysis that relies solely on smoothness for non-convex optimization. Therefore, I will maintain my current score.
I appreciate the authors addressing my concerns. 
The analysis presented in the Q1(the mean of data $X$ can be 0) and Q2 are valuable, as it allows the readers to understand that the theory and motivation more clearly. Now I do not have further questions for the authors. I agree that the current work is significant enough to justify acceptance.
Thanks for the clarifications. As the authors have clearly addressed my concerns, I'd like to increase my score ,and I'm happy to recommend it for acceptance.
Dear Reviewers,

We greatly appreciate your time and effort in reviewing our paper. Your constructive comments and insightful perspectives have been invaluable to our team's research. We have carefully considered each of your concerns and have addressed them below. 

Besides, We are encouraged by the comments of the reviewers on the **Novelty** (Reviewers 4SD1, VAmn), **Competitive performance** (Reviewer 4SD1), **A well-organized draft** (Reviewers dtmU, 4SD1), **Good theoretical proof** (Reviewers dtmU, VAmn), **Intriguing and flexible method** (Reviewer uudN), **Sufficient experiments** (Reviewer 4SD1), and **Extensibility** (Reviewer 4SD1). 

We are sincerely grateful for your constructive criticism and valuable insights, which have significantly contributed to the refinement and improvement of our work. **We hope our team's study can inspire future research on 3D models with low power consumption and low instruction latency.**

Best regards,

Authors of Paper 1528.