summaries: The paper studies the performance of the classic Relative Entropy Policy Search (REPS) algorithm of Peters et al. (2010) in the context of tabular reinforcement learning, focusing on the effect of optimization errors on the quality of the policy extracted from the solution. REPS is based on formulating the policy optimization problem as a regularized linear optimization problem which is equivalent to an unconstrained convex optimization problem, and calculating policy updates via approximately minimizing the dual function. The current paper sets out to understand the optimization issues surrounding solving these problems, and provides the following contributions:  - Showing that the policy suboptimality can be controlled in terms of the gradient norm associated with the approximate solution and some problem-dependent constants. - Showing that the dual REPS objective is smooth, which implies that bounds on the additive optimization errors can be translated to bounds on the gradient norm at the approximate solution. - Providing concrete performance bounds for an accelerated gradient descent method when the gradients of the objective can be evaluated exactly. This setting is rather unrealistic, but the results are insightful in that they shed light on the best attainable performance to be expected from this approach.  - Providing concrete performance bounds for a stochastic gradient descent method that uses a generative model to obtain estimates of the gradients. The challenge here is that one cannot straightforwardly obtain unbiased gradient estimates, and one has to take several sample transitions to make sure that the bias in the updates is small enough. The authors address this challenge thoroughly and obtain guarantees that are polynomial in the desired accuracy level.

summaries: The paper studies the convergence of the relative entropy policy search (REPS) method for solving LP-formulated MDP problems. The authors first assume the exact computation of gradients and prove the sublinear convergence of REPS regarding the regularized primal objective function and the policy. Second, the authors propose to estimate gradients using samples and prove the convergence or sample-complexity of sample-based REPS.  The main contribution is a convergence theory of REPS in both exact and stochastic settings.

summaries: In this paper the authors the sample complexity of the relative entropy policy search (REPS). This algorithm aims at finding the optimal policy in an MDP using linear programming formulation. First the authors consider the planning setting where they assume access to the exact model of the environment. For this result they show that near stationary policies result in a near optimal policy. Next they provide the convergence when the updates are being performed by biased stochastic gradients.

summaries: This paper goes back to a well known algorithm, Relative Entropy Policy Search (REPS) and provides convergence guarantees for REPS by exploiting its relationship of RL via duality. Recently, there has been a surge of work exploiting the dual formulation of RL objectives, and this paper exploits that relation to performance convergence analysis of the REPS algorithm. Besides, very recently, a number of works has provided convergence of policy search and policy gradient algorithms - and the contributions of this work can be seen in light of recent works. The major contributoon of this work is to provide convergence guarantees for the dual objective of REPS, relying solely on on-policy samples and using accelerated gradient ascent on the dual formulation (whereas prior works exploiting duality often need to rely on off-policy samples, estimating distribution ratios).

abstractText: Since its introduction a decade ago, relative entropy policy search (REPS) has demonstrated successful policy learning on a number of simulated and real-world robotic domains, not to mention providing algorithmic components used by many recently proposed reinforcement learning (RL) algorithms. While REPS is wellknown in the community, there exist no guarantees on its performance when using stochastic, gradient-based solvers. In this paper we aim to fill this gap by providing guarantees and convergence rates for the sub-optimality of a policy learned using first-order optimization methods applied to the REPS objective. We first consider the setting in which we are given access to exact gradients and demonstrate how near-optimality of the objective translates to near-optimality of the policy. We then consider the setting of stochastic gradients and introduce a technique that uses generative access to the underlying Markov decision process to compute parameter updates that maintain favorable convergence to the optimal regularized policy.

authors:
A. Abdolmaleki
R. Lioutikov
J.R. Peters
N. Lau
L.P. Reis
G. Neumann

title: Modelbased relative entropy stochastic search

venue: In Advances in Neural Information Processing Systems,

authors:
A. Abdolmaleki
J.T. Springenberg
Y. Tassa
R. Munos
N. Heess
M. Riedmiller

title: Maximum a posteriori policy optimisation

venue: arXiv preprint arXiv:1806.06920,

authors:
Z. Allen-Zhu
L. Orecchia

title: Linear coupling: An ultimate unification of gradient and mirror descent

venue: arXiv preprint arXiv:1407.1537,

authors:
J. Bas-Serrano
G. Neu

title: Faster saddle-point optimization for solving large-scale markov decision processes

venue: arXiv preprint arXiv:1909.10904,

authors:
A. Beck
M. Teboulle

title: Mirror descent and nonlinear projected subgradient methods for convex optimization

venue: Operations Research Letters,

authors:
B. Belousov
J. Peters

title: f-divergence constrained policy improvement

venue: arXiv preprint arXiv:1801.00056,

authors:
A. Boularias
J. Kober
J. Peters

title: Relative entropy inverse reinforcement learning

venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,

authors:
Y. Chen
M. Wang

title: Stochastic primal-dual methods and sample complexity of reinforcement learning

venue: arXiv preprint arXiv:1612.02516,

authors:
Y. Chen
L. Li
M. Wang

title: Scalable bilinear ⇡ learning using state and action features

venue: arXiv preprint arXiv:1804.10328,

authors:
Cheng
C.-A
R.T. Combes
B. Boots
G. Gordon

title: A reduction from reinforcement learning to no-regret online learning

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
C. Daniel
G. Neumann
J. Peters

title: Hierarchical relative entropy policy search

venue: In Artificial Intelligence and Statistics,

authors:
R. Fox
A. Pakman
N. Tishby

title: Taming the noise in reinforcement learning via soft updates, 2017

authors:
M. Geist
B. Scherrer
O. Pietquin

title: A theory of regularized markov decision processes

venue: arXiv preprint arXiv:1901.11275,

authors:
T. Haarnoja
A. Zhou
K. Hartikainen
G. Tucker
S. Ha
J. Tan
V. Kumar
H. Zhu
A. Gupta
P Abbeel

title: Soft actor-critic algorithms and applications

venue: arXiv preprint arXiv:1812.05905,

authors:
S.R. Howard
A. Ramdas
J. McAuliffe
J. Sekhon

title: Uniform, nonparametric, nonasymptotic confidence sequences

venue: arXiv preprint arXiv:1810.08240,

authors:
Y. Jin
A. Sidford

title: Efficiently solving mdps with stochastic mirror descent

venue: In International Conference on Machine Learning,

authors:
I. Kostrikov
O. Nachum
J. Tompson

title: Imitation learning via off-policy distribution matching, 2019

authors:
O. Nachum
B. Dai

title: Reinforcement learning via fenchel-rockafellar duality

venue: arXiv preprint arXiv:2001.01866,

authors:
O. Nachum
M. Norouzi
K. Xu
D. Schuurmans

title: Bridging the gap between value and policy based reinforcement learning

authors:
O. Nachum
B. Dai
I. Kostrikov
Y. Chow
L. Li
D. Schuurmans

title: Algaedice: Policy gradient from arbitrary experience, 2019

authors:
G. Neu
A. Jonsson
V. Gómez

title: A unified view of entropy-regularized markov decision processes

venue: arXiv preprint arXiv:1705.07798,

authors:
J. Peters
K. Mülling
Y. Altun

title: Relative entropy policy search

title: Markov decision processes: discrete stochastic dynamic programming

authors:
J. Schulman
S. Levine
P. Abbeel
M. Jordan
P. Moritz

title: Trust region policy optimization

venue: In International conference on machine learning,

authors:
N. Vieillard
T. Kozuno
B. Scherrer
O. Pietquin
R. Munos
M. Geist

title: Leverage the average: an analysis of regularization in rl

venue: arXiv preprint arXiv:2003.14089,

title: Primal-dual ⇡ learning: Sample complexity and sublinear run time for ergodic markov decision problems

venue: arXiv preprint arXiv:1710.06100,

title: Randomized linear programming solves the discounted markov decision problem in nearly-linear (sometimes sublinear) running time

venue: arXiv preprint arXiv:1704.01869,

heading: 1 Introduction

text:
Introduced by Peters et al. [23], relative entropy policy search (REPS) is an algorithm for learning agent policies in a reinforcement learning (RL) context. REPS has demonstrated successful policy learning in a variety of challenging simulated and real-world robotic tasks, encompassing table tennis [23], tether ball [12], beer pong [1], and ball-in-a-cup [8], among others. Beyond these direct applications of REPS, the mathematical tools and algorithmic components underlying REPS have inspired and been utilized as a foundation for a number of later algorithms, with their own collection of practical successes [13, 25, 20, 22, 15, 2, 18, 21].
At its core, the REPS algorithm is derived via an application of convex duality [22, 19], in which a Kullback Leibler (KL)-regularized version of the max-return objective in terms of state-action distributions is transformed into an logsumexp objective in terms of state-action advantages (i.e., the difference of the value of the state-action pair compared to the value of the state alone, with respect to some learned state value function). If this dual objective is optimized, then the optimal policy of the original primal problem may be derived as a softmax of the state-action advantages. This basic derivation may be generalized, using any number of entropic regularizers on the original primal to yield a dual problem in the form of a convex function of advantages, whose optimal values may be transformed back to optimal regularized policies [7].
While the motivation for the REPS objective through the lens of convex duality is attractive, it leaves two main questions unanswered regarding the theoretical soundness of using such an approach. First, in practice, the dual objective in terms of advantages is likely not optimized fully. Rather, standard gradient-based solvers only provide guarantees on the near-optimality of a returned candidate solution. While convex duality asserts a relationship between primal and dual variables at the exact optimum,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
it is far from clear whether a near-optimal dual solution will be guaranteed to yield a near-optimal primal solution, and this is further complicated by the fact that the primal candidate solution must be transformed to yield an agent policy.
The second of the two main practical difficulties is due to the form of the dual objective. Specifically, the form of the dual objective as a convex function of advantages frustrates the use of gradient-based solvers in stochastic settings. That is, the advantage of a state-action pair consists of an expectation over next states – an expectation over the transition function associated with the underlying Markov decision process (MDP). In practical settings, one does not have explicit knowledge of this transition function. Rather, one only has access to stochastic samples from this transition function, and so calculation of unbiased gradients of the REPS objective is not directly feasible.
In this paper, we provide solutions to these two main difficulties. To the first issue, we present guarantees on the near-optimality of a derived policy from dual variables optimized via a first-order gradient method, relying on a key property of the REPS objective that ensures near-optimality in terms of gradient norms. To the second issue, we propose and analyze a stochastic gradient descent procedure that makes use of a plug-in estimator of the REPS gradients. Under some mild assumptions on the MDP, our estimators need only sample transitions from a behavior policy rather than full access to a generative model (where one can uniformly sample transitions). We combine these results to yield high-probability convergence rates of REPS to a near-optimal policy. In this way, we show that REPS enjoys not only favorable practical performance but also strong theoretical guarantees.

heading: 2 Related Work

text:
As REPS is a popular and influential work, there exist a number of previous papers that have studied its performance guarantees. These previous works predominantly study REPS as an iterative algorithm, where each step comprises of an exact optimization of the REPS objective and then the derived policy is used as the reference distribution for the KL regularization of the next step. This iterative scheme may be interpreted as a form of mirror descent or similar proximal algorithms [6], and this interpretation can provide guarantees on convergence to a near-optimal policy [29, 22]. However, because this approach assumes the ability to optimize the REPS objective exactly, it still suffers from the practical limitations discussed above; specifically (1) translation of near-optimality of advantages to near-optimality of the policy and (2) ability to compute unbiased gradients when one does not have explicit knowledge of the MDP dynamics. Our analysis attacks these issues head-on, providing guarantees on first-order optimization methods applied to the REPS objective. To maintain focus we do not consider iterative application of REPS, although extending our guarantees to the iterative setting is a promising direction for future research.
In a somewhat related vein, a number of works use REPS-inspired derivations to yield dynamic programming algorithms [13, 14, 26] and subsequently provide guarantees on the convergence of approximate dynamic programming in these settings. Our results focus on the use of REPS in a convex programming context, and optimizing these programs via standard gradient-based solvers.
The use of convex programming for RL in this way has recently received considerable interest. Works in this area typically propose to learn near-optimal policies through saddle-point optimization [9, 28, 10, 4, 11, 17]. Instead of solving the primal or dual max-return problem directly, these works optimize the Lagrangian in the form of a min-max bilinear problem. The Lagrangian form helps to mitigate the two main issues we identify with advantage learning, since (1) the candidate primal solution can be used to derive a policy in a significantly more direct fashion than using the candidate dual solution, and (2) the bilinear form of the Lagrangian is immediately amenable to stochastic gradient computation. In contrast to these works, our analysis focuses on learning exclusively in the dual (advantage) space. The first part of our results is most comparable to the work of [4], which proposes a saddle-point optimization with runtime O(1/✏), assuming access to known dynamics. While our results yield a O(1/✏2) rate, we show that it can be achieved via optimizing the dual objective alone.
More similar to our work is the analysis of Bas-Serrano et al. [5], which considers an objective similar to REPS, but which is in terms of Q-values as opposed to state (V ) values. Beyond these structural differences, our proof techniques also differ. For example, our result on the suboptimality of the policy derived from dual variables (Lemma 4), is arguably simpler from the analogous result in Bas-Serrano et al. [5], which uses a two-step process to first connect suboptimality of the dual variables to constraint violation in the primal, and then connects this to suboptimality of the policy.

heading: 3 Contributions

text:
The main contributions of this paper are the following:
1. We prove several structural results regarding entropy regularized objectives for reinforcement learning and leverage them to prove convergence guarantees for Accelerated Gradient Descent on the dual (REPS) objective under mild assumptions on the MDP (see Theorem 2). For discounted MDPs we show that an ✏-optimal policy can be found after O(1/(1 )2✏2) steps and an ✏ optimal regularized policy can be found in O(1/(1 )2✏) steps.
2. Similarly we show that a simple version of stochastic gradient descent using biased plug-in gradient estimators can be used to find an ✏ optimal policy after O(1/(1 )8✏8) iterations (see Theorem 3) and an ✏-optimal regularized policy in O(1/(1 )8✏4) steps. Although our rates are short of the ones achievable by alternating optimization methods, we are the first to show meaningful convergence guarantees for a purely dual approach based on on-policy access to samples from the underlying MDP.
3. In Appendix I, we extend our results beyond the REPS objective and consider the use of Tsallis Entropy regularizers. Similar to our results for the REPS objective we show that for discounted MDPs an ✏ optimal policy can be found after O(1/(1 )2✏2) steps and an ✏ optimal regularized policy can be found in O(1/(1 )2✏) steps.

heading: 4 Background

text: In this section we review the basics of Markov decision processes and their Linear Programming primal and dual formulations (see section 4.1) and some facts about the geometry of convex functions.

heading: 4.1 RL as an LP

text:
We consider a discounted Markov decision process (MDP) described by a tuple M = (S,A, P, r,µ, ), where S is a finite state space, A is a finite action space, P is a transition probability matrix, r is a reward vector, µ is an initial state distribution, and 2 (0, 1) is a discount factor. We make the following assumption regarding the reward values {rs,a}. Assumption 1 (Unit rewards). For all s, a 2 S ⇥A, the rewards satisfy, rs,a 2 [0, 1].
The agent interacts with M via a policy ⇡ : S ! A. The agent is initialized at a state s0 sampled from an initial state distribution µ and at time k = 0, 1, . . . it uses its policy to sample an action ak ⇠ ⇡(sk). The MDP provides an immediate reward rsk,ak and transitions randomly to a next state sk+1 according to probabilities Pa(sk+1|sk). Given a policy ⇡ we define its infinite-horizon discounted reward as V⇡ := E⇡ ⇥P1 k=0 krsk,ak ⇤ , where we use E⇡ to denote the expectation over trajectories induced by the MDP M and policy ⇡. In RL, the agent’s objective is to find an optimal policy ⇡?; that is, find a policy maximizing V⇡ over all policy mappings ⇡ : S ! A. We denote the optimal policy as ⇡? := argmax⇡ V⇡ .
We now review the definitions of state value functions and visitation distributions: Definition 1. We define the value vector v⇡ 2 R|S| of a policy ⇡ as v⇡s := E⇡ ⇥P1
k=0 k rsk,ak |s0 = s
⇤ .
Definition 2. Given a policy ⇡ we define its state-action visitation distribution ⇡ 2 R|S|⇥|A| as, ⇡s,a := (1 )E⇡ ⇥P1 k=0 k1(sk = s, ak = a) ⇤ . Notice that by definition P s,a s,a = 1.
We note that any vector of nonnegative entries may be used to define a policy ⇡ as:
⇡ (a|s) := s,aP
a02A s,a0 . (1)
Note that ⇡ ⇡ = ⇡, while the visitation distribution ⇡ of ⇡ is not necessarily . Definition 3. Given a policy ⇡ we define its state visitation distribution as, ⇡s := (1 )E⇡ ⇥P1 k=0 k1(sk = s) ⇤ . Notice that ⇡s = P a ⇡ s,a and ⇡ s,a = ⇡ s · ⇡(a|s).
The optimal visitation distribution ⇤ is defined as ⇤ := argmax ⇡ P
s,a ⇡ s,ars,a. It can be
shown [24, 9] that solving for the optimal visitation distribution is equivalent to the following linear program:
max s,a2 S⇥A
X
s,a
s,ars,a, s.t. X
a
s,a = (1 )µs + X
s0,a
Pa(s|s0) s0,a 8s 2 S. (Primal- )
Where we write P 2 R|S||A|⇥|S| to denote the transition operator. Specifically, the |S| constraints of Primal- restrict any feasible to be the state-action visitations for some policy ⇡ (given by ⇡ ). The dual of this LP is given by,
min v
(1 ) X
s2S µsvs, s.t. 0 A v s,a 8s 2 S, a 2 A, (Dual-v)
where Avs,a = rs,a vs + P s0 Pa(s 0 |s)vs0 is the advantage evaluated at s, a 2 S ⇥A. It can be shown [24, 9] that the unique primal solution ⇤ is exactly ⇡⇤ and the unique dual solution v⇤ is v⇡⇤ .
We finalize this section by defining the notion of suboptimality satisfied by the final policy produced by the algorithms that we propose. Definition 4. Let ✏ > 0. We say that policy ⇡ is ✏-optimal if maxs2S |v⇡s v⇡?s |  ✏.
Our objective is to design algorithms such that for any ✏ > 0, can return an ✏ optimal policy.

heading: 4.2 Regularized Policy Search

text:
Following Belousov & Peters [7], we consider regularizing Primal- with a convex function F : |S|⇥|A| ! R [ {1}. The resulting regularized LP is given by,
max s,a2 S⇥A
X
s,a
s,ars,a F ( ) := JP ( ), s.t. X
a
s,a = (1 )µs + X
s0,a
Pa(s|s 0) s0,a.
(PrimalReg- ) Henceforth we denote the primal objective function as JP ( ) = P s,a s,ars,a F ( ). Any feasible
that satisfies the |S| constraints in this regularized LP is the (true) state-action visitation distribution for some policy ⇡; therefore, the optimal ⇤ of this problem can be used to derive an optimal F - regularized max-return policy ⇡F,⇤ := ⇡ ⇤ . To simplify our derivations, we introduce the definition of the convex conjugate of a convex function, oftentimes referred to as the Fenchel conjugate: Definition 5 (Fenchel Conjugate). Let F : D ! R be a convex function over a convex domain D ✓ Rd. We denote its D constrained Fenchel conjugate as F ⇤ : Rn ! R defined as F ⇤(u) = maxx2D hx,ui F (x).
The dual JD of the regularized problem is given by the following optimization problem [7, 19]:
min v
JD(v) := (1 ) X
s
vsµs + F ⇤ (Av) , (2)
where F ⇤ is the S⇥A-constrained Fenchel conjugate of F . The vector quantity inside F ⇤ is known as the advantage. That is, it quantifies the advantage (the difference in estimated value) of taking an action a at s, with respect to some state value function v. Using Fenchel-Rockafellar duality, the optimal solution v⇤ of the dual function JD may be used to derive an optimal primal solution ⇤ as:
⇤ 2 rF ⇤ ⇣ Av ? ⌘ . (3)
Algorithm 1 Relative Entropy Policy Search [Sketch]. Input: Initial iterate v0, accuracy level ✏ > 0, gradient optimization algorithm O.
1. Optimize the objective in 2 using O to yield a candidate dual solution v̂⇤ where F satisfies Equation 4.
2. Use the candidate dual solution to derive a candidate primal solution ̂ ⇤ using 3.
3. Extract a candidate policy ⇡̂⇤ from ̂ ⇤
via Equation 1. Return: ⇡̂⇤ .
Relative Entropy Policy Search (REPS) is derived by setting F ( ) := DKL( kq), the KL-divergence of from some reference distribution q 2 |S||A|. The reader should think of q as the visitation distribution of a behavior policy. As we can see, the derivation we provide here further generalizes to arbitrary regularizers F . We focus on a specific F given by
F ( ) := 1
⌘
X
s,a
s,a
✓ log ✓ s,a qs,a ◆ 1 ◆ , (4)
for some scalar ⌘ > 0. In this case F ⇤ : R|S|⇥|A| ! R equals F ⇤(u) = 1 ⌘ log ⇣P s,a exp (⌘us,a)qs,a ⌘ + 1⌘ , its gradient satisfies [rF ⇤(u)]s,a = exp(⌘us,a)qs,aP
s0,a0 exp(⌘us0,a0 )qs0,a0
and therefore the dual function equals:
JD(v) := (1 ) X
s
vsµs + 1
⌘ log
X
s,a
exp ⌘Avs,a qs,a
! + 1
⌘ , (DualReg-v)
And the dual problem equals the unconstrained minimization problem:
min v JD(v) (5)
The objective of REPS is to find the minimizer v? of DualReg-v (with regularization level ⌘).
Algorithm 1 raises two practical issues discussed in Section 1. Specifically, optimization algorithms applied to REPS will typically only give guarantees on the near-optimality of v̂⇤. We will need to translate near-optimality of v̂⇤ to near-primal-optimality (w.r.t. JP ( ?)) of ̂ ⇤ , and then translate that to near-optimality of the final returned policy ⇡̂⇤ . Secondly, first-order optimization of the REPS objective requires access to a gradientrvJD(v), which involved computingrF ⇤(Av). Exact computation of this quantity is often infeasible in practical scenarios where one does not have access to P, but rather only stochastic generative access to samples from P. We show how to compute approximate (biased) gradients of JD(v) using samples from a distribution qs,a (here thought of as a behavior policy) and how to use them to derive convergence rates for Relative Entropy Policy Search.

heading: 5 Relative Entropy Policy Search

text:
We start by deriving some general results regarding the geometry of regularized linear programs. Our first result (Lemma 2) characterizes the smoothness properties of a regularized LP. This will prove crucial in later sections where we make use of this result to derive convergence rates for the REPS objective. We start by recalling the definitions of both strong convexity and smoothness of a function.
Definition 6. A function f : Rn ! R is strongly convex w.r.t norm k · k if f(x) f(y) + hrf(y),x yi+ 2 kx yk 2.
Let’s also define smoothness: Definition 7. A function h is ↵ smooth1 w.r.t. norm k · k? if:
h(u)  h(w) + hrh(w),u wi+ ↵
2 ku wk2?. (6)
We will now characterize the smoothness properties of the dual of a regularized linear program. Let’s start by considering the generic linear program:
max 2D hr, i, s.t. E = b,
where r 2 Rn, E 2 Rm⇥n, and b 2 Rm and D is a convex domain. Let’s regularize this objective using a function F that is -strongly convex with respect to norm k · k:
max 2D hr, i F ( ), s.t. E = b. (RegLP)
1Smoothness is independent of the convexity properties of h.
The Lagrangian of problem RegLP is given by gL( ,v) = hr, i F ( )+ Pm
i=1 vi (bi (E )i) . Therefore, the dual function gD : Rm ! R with respect to the original primal regularized LP is,
gD(v) = hv,bi+max 2D h , r v>Ei F ( ) = hv,bi+ F ⇤(r v>E),
where the last equality follows from the definition of the Fenchel conjugate of F . It is possible to relate the smoothness properties of F ⇤ with the strong convexity of F . A crucial result that we will use in our results is the following: Lemma 1. If F is -strongly convex w.r.t. k · k over D then F ⇤ is 1 -smooth w.r.t the dual k · k?.
Definitions 6 and 7 are stated in terms of a generic norm k · k and its dual k · k?. When applied to the REPS objective in Equation 2, using these general norm definitions of smoothness and strong convexity allow us to obtain guarantees with a milder dependence on S and A than would be possible if we were to use their `2 norm characterization instead. We can use the result of Lemma 1 to characterize the smoothness properties of the dual function JD of a generic regularized LP. Lemma 2. Consider the regularized LP RegLP with r 2 Rn, E 2 Rm⇥n, b 2 Rm, and where F is strongly convex w.r.t. norm k · k. The dual function gD : Rm ! R of this regularized LP is kEk2·,? -smooth w.r.t. to the dual norm k · k?, where we use kEk·,? to denote the k · k norm over the k · k? norm of E0s rows.
As a consequence of Lemma 2 we can bound the smoothness parameter of JD in the REPS objective: Lemma 3. The dual function JD(v) is (|S|+ 1)⌘-smooth in the k · k1 norm.

heading: 5.1 Structural results for the REPS objective

text:
Armed with Lemma 2 we are ready to derive some useful structural properties of the REPS objective. In this section we present two main results. First we show that under some mild assumptions it is possible to relate the gradient magnitude of any candidate solution to JD with its suboptimality gap and second, we show an l1 bound for the norm of the optimal dual solution v?. For most of the analysis we make the following assumptions: Assumption 2. There is > 0 such that qs,a 8s, a 2 S ⇥A.
We introduce the following assumption on the discounted state visitation distribution of arbitrary policies ⇡ in the MDP, paraphrased from Wang [27]: Assumption 3. There exists ⇢ > 0 such that for any policy ⇡, the discounted state visitation distribution ⇡ defined as ⇡s = P a ⇡ s,a satisfies ⇡ s ⇢ for all states s 2 S .
Suppose we have a candidate dual solution ev forJD(v) in DualReg-v with its corresponding candidate primal solution e = exp(⌘A
ṽ)·q eZ
where the operators exp and · act pointwise and eZ = P a,s exp(⌘A
ṽ)qs,a. We denote the corresponding candidate policy (computed using Equation 1) associated with ev as e⇡(a|s). This candidate policy induces a discounted visitation distribution e⇡ that may be substantially different from e . We now show that it is possible to control the deviation of primal objective value of e⇡ from JP ( ) in terms of krJD(ev)k1: Lemma 4. Let ev 2 R|S| be arbitrary and let e be its corresponding candidate primal variable. If krvJD(ev)k1  ✏ and Assumptions 2 and 3 hold then whenever |S| 2:
JP ( e⇡) JP ( ? ⌘) ✏
✓ 1 + c
1 + kevk1
◆ ,
where c = 1+log( 1 ⇢3 )
⌘ and ? ⌘ is the JP optimum.
We finish this section by proving a bound on the norm of the dual variables. This bound will inform our optimization algorithms as it will allow us to set up the right constraints. Lemma 5. Under Assumptions 1, 2 and 3, the optimal dual variables are bounded as
kv⇤k1  1
1
1 + log |S||A| ⇢ ⌘
! =: D. (7)
From now on we use the notation D to refer to the quantity on the RHS of Equation 7.

heading: 5.2 Convergence rates

text:
As a warm up we derive convergence rates for the case when we have access to exact knowledge of the transition dynamics P and therefore exact gradients. We analyze the effects of using Accelerated Gradient Descent (see Section F for a full description of the algorithm) on the REPS objective JD(v). Theorem 1 (Accelerated Gradient Descent for general norms. Theorem 4.1 in Allen-Zhu & Orecchia [3]). Let D? be an upper bound to kx0,x?k22. Given an ↵ smooth function h w.r.t. the k · k? norm over domain D, then T iterations of Algorithm 4 ensure h(yt) h(x?)  4↵D⇤T 2 .
We want to find almost optimal solutions (in function value). Let’s define an ✏ optimal solution: Definition 8. Let ✏ > 0. We say that x is an ✏ optimal solution of an ↵ smooth function h : Rd ! R if h(x) h(x?)  ✏, where h(x?) = minx2Rd h(x).
We can also show the following bound on the gradient norm for any ✏ optimal solutions of h. Lemma 6. If x is an ✏ optimal solution for the ↵ smooth function h : Rd ! R w.r.t. norm k · k? then the gradient of h at x satisfies krh(x)k  p 2↵✏.
When h = JD the DualReg-v function in the reinforcement learning setting, we set k · k? = k · k1 and k · k = k · k1. We are ready to prove convergence guarantees for Algorithm 4 when applied to the objective JD.
Lemma 7. Let Assumptions 1, 2 and 3 hold. Let D = {v s.t. kvk1  D} and c0 = log |S||A| ⇢
⌘ . After T steps of Algorithm 4, the objective function JD evaluated at the iterate vT = yT satisfies:
JD(vT ) JD(v ⇤)  4⌘(|S|+ 1)2
(1 + c0)2
(1 )2T 2 ,
Proof. This result follows simply by invoking the guarantees of Theorem 1, making use of the fact that JD is (|S|+ 1)⌘ smooth as proven by Lemma 3, observing that as a consequence of Lemma 5, v? 2 D and using the inequality kxk22  |S|kxk21 for x 2 R|S|.
Lemma 7 can be easily turned into the following guarantee on the final dual function value:
Corollary 1. Let ✏ > 0. If Algorithm 4 is ran for at least T rounds where T 2⌘1/2(|S|+1) (1+c 0)
(1 ) p ✏
then vT is an ✏ optimal solution for the dual objective JD.
If T satisfies the conditions of Corollary 1 a simple use of Lemma 6 allows us to bound the k · k1 norm of the dual function’s gradient at vT :
krJD(vT )k1  p 2(|S|+ 1)⌘✏
If we denote as ⇡T to be the policy induced by vT , and ?⌘ is the candidate dual solution corresponding to v?. A simple application of Lemma 4 yields:
JP ( ⇡T ) JP ( ? ⌘)
p 2(|S|+ 1)⌘✏
1
2 +
1 + log |S||A| 2⇢4
⌘
!
The following is the equivalent version of optimality for regularized objectives:
Definition 9. Let ✏ > 0. We say ⇡̃ is an ✏ optimal regularized policy if JP ( e⇡) JP ( ?⌘) ✏.
This leads us to the main result of this section: Corollary 2. For any ⇠ > 0, and let c00 = 1+log |S||A| 2⇢4
⌘ . If T 4⌘ (|S|+ 1) 3/2 (2+c00) 2
(1 )2⇠ then JP ( ⇡T ) JP ( ? ⌘) ⇠.
Thus Algorithm 4 achieves an O(1/(1 )2✏) rate to an ✏ optimal regularized policy. We proceed to show that an appropriate choice for ⌘ can be leveraged to obtain an ✏ optimal policy.
Theorem 2. For any ✏ > 0, let ⌘ = 1 2✏ log( |S||A| )
. If T (|S| + 1)3/2 (2+c 00)2
(1 )2✏2 , then ⇡T is an
✏ optimal policy.
The main difficulty in deriving the guarantees of Theorem 2 lies in the need to translate the function value optimality guarantees of Accelerated Gradient Descent into ✏-optimality guarantees for the candidate policy ⇡T . This is where our results from Lemma 4 have proven fundamental. It remains to show that it is possible to obtain an ✏ optimal policy when access to the true model is only via samples.

heading: 6 Stochastic Gradients

text:
In this section we show how to obtain stochastic (albeit biased) gradient estimators brvJD(v) for rvJD(v) (see Algorithm 2). We use brvJD(v) to perform biased stochastic gradient descent steps on JD(v) (see Algorithm 3). In Lemma 8 we prove guarantees for the bias and variance of this estimator and show rates for convergence in function value to the optimum of JD(v) in Lemma 10. We turn these results into guarantees for ✏ optimality of the final candidate policy in Theorem 3. Let’s start by noting that:
(rvJD(v))s = (1 )µs + E(s0,a,s00)⇠q⇥Pa(·|s0) h Bvs0,a ( 1(s 00 = s) 1(s0 = s)) i ,
Where Bvs,a = exp(⌘Avs,a) Z and Z = P s,a exp ⌘Avs,a qs,a. We will make use of this characterization to devise a plug-in estimator for this quantity:
Algorithm 2 Biased Gradient Estimator Input Number of samples t. Collect samples {(s`, a`, s0`)} t `=1 such that (s`, a`) ⇠ q while s 0 ` ⇠ Pa`(·|s`) for (s, a) 2 S ⇥A do Build empirical estimators bAv(t) 2 R|S|⇥|A| and bq(t) 2 R|S|⇥|A|. Compute estimators bBvs,a(t) = exp(⌘ bAvs,a(t)) bZ(t) .
Where bZ(t) = P
s,a exp(⌘ bAvs,a(t))bqs,a(t).
end Produce a final sample (st+1, at+1) ⇠ q and s0t+1 ⇠ Pat+1(·|st+1). Compute brvJD(v) such that: ⇣ brvJD(v) ⌘
s = (1 )µs + bBst+1,at+1 (t)
⇣ 1(s0t+1 = s) 1(st+1 = s) ⌘ .
Output: brvJD(v).
We now proceed to bound the bias of this estimator: Lemma 8. Let , ⇠ 2 (0, 1) with ⇠  min( , 14 ). With probability at least 1 for all t 2 N such that tln ln(2t) 120(ln 41.6|S||A| +1) ⇠2 max 480⌘2 2kvk21, 1 , the plugin estimator brvJD(v) satisfies:
max u2{1,2,1}
kĝ Et+1[ĝ]ku  8 ; max
u2{1,2,1} kEt+1[ĝ] gku  8⇠ ;
E h kĝ Et+1[ĝ]k22 bBv(t) i  8 ,
where ĝ = brvJD(v), g = rvJD(v), and Et+1[·] = Est+1,at+1,s0t+1 [·|bB v(t)].
We will now make use of Lemma 8 along with the following guarantee for projected Stochastic Gradient Descent to prove convergence guarantees for Algorithm 3.
Algorithm 3 Biased Stochastic Gradient Descent Input Desired accuracy ✏, learning rates {⌧t}1t=1, and number-of-samples function n : N! N . Initialize v0 = 0 for t = 1, · · · , T do
Get brvJD(v) with n(t) samples via Algorithm 2. Perform update: v0t vt ⌧t brvJD(v); vt ⇧D(v0t), where ⇧D denotes the projection to D = {v s.t. kvk1  D}.
end Output: vT .
The following holds: Lemma 9. Let f : Rd ! R be an L smooth function. We consider the following update:
x0t+1 = xt ⌧ (rf(xt) + ✏t + bt) ; xt+1 = ⇧D(x 0 t+1).
If ⌧  2L then:
f(xt+1) f(x?)  kxt x?k2 kxt+1 x?k2
2⌧ + 2⌧krf(xt)k2 + 5⌧kbtk2 + 5⌧k✏tk2
+ kbtk1kxt x?k1 h✏t,xt x?i.
Lemma 8 implies the following guarantee for the following projected stochastic gradient algorithm with biased gradients brvJD(v)R:
Lemma 10. We assume ⌘ 4 . Set ⇠t = 8|S|⌘Dp t and ⌧t = 116|S|⌘pt . If we take t gradient steps using n(t) samples from q⇥P (possibly reusing the samples for multiple gradient computations) with n(t)
satisfying n(t) 525t
✓ ln 100|S||A|t 2 +1 ◆3
|S|2 . Then for all t 1 we have that with probability at least
1 3 and simultaneously for all t 2 N such that t 64|S| 2⌘2D2 :
JD
✓ 1
t
Pt `=1 v` ◆  JD(v?) + eO ✓ D
2 |S|⌘ p t
◆ .
Lemma 10 implies that making use of N samples it is possible to find a candidate v̄N such that JD(v̄N )  JD(v?) + eO ⇣ D2⌘ p N ⌘ . This in turn implies by a simple use of Lemma 6 that krJD(v̄N )k1  eO ⇣ |S|1/2D⌘p N1/4 ⌘ . If we denote as ⇡̄N to the policy induced by v̄N , a simple application of Lemma 4 yields:
JP ( ⇡̄N ) JP ( ? ⌘) eO
✓ |S| 1/2 D⌘
(1 ) p N1/4
◆
Thus Algorithm 3 achieves an O(1/(1 )8✏4) rate of convergence to an ✏ optimal regularized policy. We proceed to we can set ⌘ to obtain an ✏ optimal policy:
Theorem 3 (Informal). For any ✏ > 0 let ⌘ = 1 2✏ log( |S||A| )
. If N eO ⇣
1 ✏8(1 )8 2
⌘ , then with
probability at least 1 it is possible to find a candidate v̄N such that ⇡̄N is an ✏ optimal policy.

heading: 7 Conclusion

text:
This work presents an analysis of first-order optimization methods for the REPS objective in reinforcement learning. We prove convergence rates of O(1/✏2) for accelerated gradient descent on the dual of the KL-regularized max-return LP in the case of a known transition function with convergence rate. For the unknown case, we propose a biased stochastic gradient descent method relying on samples from behavior policy and show that it converges to an optimal policy with rate O(1/✏8). There are several interesting questions that remain open. First, while directly optimizing the dual via gradient methods is convenient from an algorithmic perspective, prior unregularized saddle-point methods have been shown to achieve a faster O(1/✏) convergence [4]. An important open direction is thus to understand if faster rates are possible in order to bridge this gap, or if optimizing the regularized dual directly is fundamentally limited. Second, we only considered MDPs with finite state and action spaces. It is therefore of interest to see if these ideas readily extend to infinite or very large spaces through function approximation.
Acknowledgments and Disclosure of Funding
This research was supported by the Google-BAIR Commons program. JL is supported by NSF GRFP.

title: Near Optimal Policy Optimization via REPS


summaries: This paper measures the sensitivity of various point cloud classification networks (like PointNet, PointNet++, DGCNN) to rotation, translation, scale, and local 3D structure. It also proposes ways to measure the 3D smoothness of a network. Based on these analyses, the work provides various insights. One of the main insights being that the DNNs don’t handle rotation very well. Another insight is that training with adversarial perturbations helps.

summaries: At a higher level, this paper is proposing several ways to measure the sensitivity and smoothness of representations learnt by 3D point cloud networks. This paper presents several ways to measure the sensitivity of point cloud networks to rotation, scale, translation and local structure. The Paper also proposes different metrics to evaluate the smoothness of encoded local 3d structures and the complexity of representations learnt by the network. The analysis is done using several point-based neural networks trained on the ModelNet40 classification task and shapenet part segmentation task.

summaries: This paper introduces metrics that reflect the representation quality, and properties, acquired by a deep-net that is applied in 3D Point-Cloud (PC) processing tasks. Concretely, the authors introduce six novel metrics that in aggregate capture different types of regional sensitivities e.g., the sensitivity of the DNN in rotations on specific regions/rotation-angles of the input PC. They further explore the extent that modern architectures in standard benchmarks acquire “spatial smoothness” --  do nearby points have ‘similar’ effects/importance for the end task? And finally, they explore the acquired representation complexity of the DNN by adapting a 'multi-order interaction' metric to PC data.    These metrics are being applied on a well-selected subset of modern PC-DNN architectures such PointNet++ or DGCNN when these are trained either for PC-object classification, or part-based object-segmentation. The analysis of the metrics in these tasks/architectures highlights a number of interesting points that oftentimes are very simple/intuitive: e.g., PointNet fails to encode local 3D structures (e.g., compared to PointNet++) — or includes results that are more subtle, but still highly intuitive & rich: e.g., adversarially training a PC-DNN with rotation/translation attacks; will force it to learn more global PC structures compared to standard training; which is intuitive as the local structures, per the new metrics, are those that on average are more susceptible to rotations.

summaries: This paper studies how to understand the quality of knowledge representations encoded in point cloud DNNs. Based upon the Shapley value, the paper presents six metrics to evaluate the model vulnerability toward different types of input variations. In addition, it presents an analysis regarding the smoothness and multi-order interactions of these attributions, pointing out the restrictions of current point DNNs. The paper makes interesting observations and draws useful conclusions, supported by a range of experimental evaluations.

abstractText: In this paper, we evaluate the quality of knowledge representations encoded in deep neural networks (DNNs) for 3D point cloud processing. We propose a method to disentangle the overall model vulnerability into the sensitivity to the rotation, the translation, the scale, and local 3D structures. Besides, we also propose metrics to evaluate the spatial smoothness of encoding 3D structures, and the representation complexity of the DNN. Based on such analysis, experiments expose representation problems with classic DNNs, and explain the utility of the adversarial training. The code will be released when this paper is accepted.

authors:
Marco Ancona
Cengiz Oztireli
Markus Gross

title: Explaining deep neural networks with a polynomial time algorithm for shapley value approximation

venue: Proceedings of the 36th International Conference on Machine Learning,

authors:
Song Bai
Xiang Bai
Zhichao Zhou
Zhaoxiang Zhang
Longin Jan Latecki

title: Gift: A real-time and scalable 3d shape search engine

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Yizhak Ben-Shabat
Michael Lindenbaum
Anath Fischer

title: 3d point cloud classification and segmentation using 3d modified fisher vector representation for convolutional neural networks

venue: arXiv preprint arXiv:1711.08241,

authors:
Javier Castro
Daniel Gómez
Juan Tejada

title: Polynomial calculation of the shapley value based on sampling

venue: Computers & Operations Research,

authors:
Aditya Chattopadhay
Anirban Sarkar
Prantik Howlader
Vineeth N Balasubramanian

title: Grad-cam++: Generalized gradient-based visual explanations for deep convolutional networks

venue: IEEE Winter Conference on Applications of Computer Vision (WACV),

authors:
J. Demantké
C. Mallet
N. David
B. Vallet

title: Dimensionality Based Scale Selection in 3d LIDAR Point Clouds

venue: ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences,

authors:
Alexey Dosovitskiy
Thomas Brox

title: Inverting visual representations with convolutional networks

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Ruth C Fong
Andrea Vedaldi

title: Interpretable explanations of black boxes by meaningful perturbation

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
C. Frye
Damien de Mijolla
T. Begley
Laurence Cowton
Megan Stanley
Ilya Feige

title: Shapley explainability on the data manifold

venue: In ICLR,

authors:
Ankit Goyal
Hei Law
Bowei Liu
Alejandro Newell
Jia Deng

title: Revisiting point cloud shape classification with a simple and effective baseline

venue: arXiv preprint arXiv:2106.05304,

authors:
Michel Grabisch
Marc Roubens

title: An axiomatic approach to the concept of interaction among players in cooperative games

venue: International Journal of game theory,

authors:
S. Guinard
L. Landrieu

title: Weakly supervised segmentation-aided classification of urban scenes from 3d lidar point clouds. The International Archives of the Photogrammetry

venue: Remote Sensing and Spatial Information Sciences,

authors:
Qingyong Hu
Bo Yang
Linhai Xie
Stefano Rosa
Yulan Guo
Zhihua Wang
Niki Trigoni
Andrew Markham

title: Randla-net: Efficient semantic segmentation of large-scale point clouds

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Asako Kanezaki
Yasuyuki Matsushita
Yoshifumi Nishida

title: Rotationnet: Joint object categorization and pose estimation using multiviews from unsupervised viewpoints

authors:
Pieter-Jan Kindermans
Kristof T Schütt
Maximilian Alber
Klaus-Robert Müller
Dumitru Erhan
Been Kim
Sven Dähne

title: Learning how to explain neural networks: Patternnet and patternattribution

venue: arXiv preprint arXiv:1705.05598,

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial examples in the physical world, 2017

authors:
Loic Landrieu
Martin Simonovsky

title: Large-scale point cloud semantic segmentation with superpoint graphs

authors:
Yangyan Li
Rui Bu
Mingchao Sun
Wei Wu
Xinhan Di
Baoquan Chen

title: Pointcnn: Convolution on x-transformed points

venue: In Advances in Neural Information Processing Systems,

authors:
Yongcheng Liu
Bin Fan
Shiming Xiang
Chunhong Pan

title: Relation-shape convolutional neural network for point cloud analysis

authors:
Scott Lundberg
Su-In Lee

title: A unified approach to interpreting model predictions

venue: arXiv preprint arXiv:1705.07874,

authors:
Scott M Lundberg
Gabriel G Erion
Su-In Lee

title: Consistent individualized feature attribution for tree ensembles

venue: arXiv preprint arXiv:1802.03888,

authors:
Aravindh Mahendran
Andrea Vedaldi

title: Understanding deep image representations by inverting them

venue: In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition,

authors:
Jiageng Mao
Xiaogang Wang
Hongsheng Li

title: Interpolated convolutional networks for 3d point cloud understanding

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
Charles R Qi
Hao Su
Kaichun Mo
Leonidas J Guibas

title: Pointnet: Deep learning on point sets for 3d classification and segmentation

authors:
Charles R Qi
Or Litany
Kaiming He
Leonidas J Guibas

title: Deep hough voting for 3d object detection in point clouds

authors:
Charles Ruizhongtai Qi
Li Yi
Hao Su
Leonidas J Guibas

title: Pointnet++: Deep hierarchical feature learning on point sets in a metric space

authors:
Marco Túlio Ribeiro
Sameer Singh
Carlos Guestrin

title: why should I trust you?": Explaining the predictions of any classifier

venue: In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,

authors:
Ramprasaath R Selvaraju
Michael Cogswell
Abhishek Das
Ramakrishna Vedantam
Devi Parikh
Dhruv Batra

title: Grad-cam: Visual explanations from deep networks via gradient-based localization

venue: In Proceedings of the IEEE international conference on computer vision,

title: A value for n-person games

venue: Contributions to the Theory of Games,

authors:
Wen Shen
Binbin Zhang
Shikun Huang
Zhihua Wei
Quanshi Zhang

title: 3d-rotation-equivariant quaternion neural networks

venue: In Computer Vision–ECCV 2020: 16th European Conference,

authors:
Wen Shen
Zhihua Wei
Shikun Huang
Binbin Zhang
Panyue Chen
Ping Zhao
Quanshi Zhang

title: Verifiability and predictability: Interpreting utilities of network architectures for point cloud processing

authors:
Yiru Shen
Chen Feng
Yaoqing Yang
Dong Tian

title: Mining point cloud local structures by kernel correlation and graph pooling

authors:
K Simonyan
A Vedaldi
A Zisserman

title: Deep inside convolutional networks: visualising image classification models and saliency maps

venue: arXiv preprint arXiv:1312.6034,

authors:
Karen Simonyan
Andrea Vedaldi
Andrew Zisserman

title: Deep inside convolutional networks: Visualising image classification models and saliency maps

authors:
Mukund Sundararajan
Amir Najmi

title: The many shapley values for model explanation

authors:
Mukund Sundararajan
Kedar Dhamdhere
Ashish Agarwal

title: The shapley taylor interaction index

authors:
Hugues Thomas
Charles R Qi
Jean-Emmanuel Deschaud
Beatriz Marcotegui
François Goulette
Leonidas J Guibas

title: Kpconv: Flexible and deformable convolution for point clouds

authors:
Lei Wang
Yuchun Huang
Yaolin Hou
Shenman Zhang
Jie Shan

title: Graph attention convolution for point cloud semantic segmentation

authors:
Weiyue Wang
Ronald Yu
Qiangui Huang
Ulrich Neumann

title: Sgpn: Similarity group proposal network for 3d point cloud instance segmentation

authors:
Yue Wang
Justin M Solomon

title: Deep closest point: Learning representations for point cloud registration

authors:
Yue Wang
Yongbin Sun
Ziwei Liu
Sanjay E Sarma
Michael M Bronstein
Justin M Solomon

title: Dynamic graph cnn for learning on point clouds

venue: ACM Transactions on Graphics (TOG),

title: Probabilistic values for games. The Shapley Value

venue: Essays in Honor of Lloyd S. Shapley,

authors:
Wenxuan Wu
Zhongang Qi
Li Fuxin

title: Pointconv: Deep convolutional networks on 3d point clouds

authors:
Zhirong Wu
Shuran Song
Aditya Khosla
Fisher Yu
Linguang Zhang
Xiaoou Tang
Jianxiong Xiao

title: 3d shapenets: A deep representation for volumetric shapes

authors:
Guandao Yang
Xun Huang
Zekun Hao
Ming-Yu Liu
Serge Belongie
Bharath Hariharan

title: Pointflow: 3d point cloud generation with continuous normalizing flows

authors:
Yaoqing Yang
Chen Feng
Yiru Shen
Dong Tian

title: Foldingnet: Point cloud auto-encoder via deep grid deformation

authors:
Li Yi
Vladimir G. Kim
Duygu Ceylan
I-Chao Shen
Mengyan Yan
Hao Su
Cewu Lu
Qixing Huang
Alla Sheffer
Leonidas Guibas

title: A scalable active framework for region annotation in 3d shape collections

venue: SIGGRAPH Asia,

authors:
Jason Yosinski
Jeff Clune
Anh Nguyen
Thomas Fuchs
Hod Lipson

title: Understanding neural networks through deep visualization

venue: arXiv preprint arXiv:1506.06579,

authors:
Lequan Yu
Xianzhi Li
Chi-Wing Fu
Daniel Cohen-Or
Pheng-Ann Heng

title: Pu-net: Point cloud upsampling network

authors:
Matthew D Zeiler
Rob Fergus

title: Visualizing and understanding convolutional networks

venue: In European Conference on Computer Vision,

authors:
Hao Zhang
Xu Cheng
Yiting Chen
Quanshi Zhang

title: Game-theoretic interactions of different orders

venue: arXiv preprint arXiv:2010.14978,

authors:
Yue Zhao
Yuwei Wu
Caihua Chen
Andrew Lim

title: On isometry robustness of deep 3d point cloud models under adversarial attacks

authors:
Tianhang Zheng
Changyou Chen
Junsong Yuan
Bo Li
Kui Ren

title: Pointcloud saliency maps

authors:
Bolei Zhou
Aditya Khosla
Agata Lapedriza
Aude Oliva
Antonio Torralba

title: Object detectors emerge in deep scene cnns

title: Learning deep features for discriminative localization

heading: 1 Introduction

text:
Deep neural networks (DNNs) have exhibited superior performance in various tasks, but the blackbox nature of DNNs hampers the analysis of knowledge representations. Previous studies on explainable AI mainly focused on the following two directions. The first is to explain the knowledge encoded in a DNN, e.g. visualizing patterns encoded by a DNN [24, 36, 50] and estimating the saliency/importance/attribution of input variables w.r.t. the network output [20, 30, 57]. The second is to evaluate the representation power of a DNN, e.g. the generalization and robustness of feature representations.
This paper focuses on the intersection of the above two directions, i.e. analyzing the quality of knowledge representations of DNNs for 3D point cloud processing. Specifically, we aim to design metrics to illustrate properties of feature representations for different point cloud regions, including various types of regional sensitivities, the spatial smoothness of encoding 3D structures, and the representation complexity of a DNN. These metrics provide new perspectives to diagnose DNNs for 3D point clouds. For example, unlike the image processing relying on color information, the processing of 3D point clouds usually exclusively uses 3D structural information for classification. Therefore, a well-trained DNN for 3D point cloud processing is supposed to just use scale information and 3D structures for inference, and be robust to the rotation and translation.
Regional sensitivities. We first propose six metrics to disentangle the overall model vulnerability into the regional rotation sensitivity, the regional translation sensitivity, the regional scale sensitivity, and three types of regional structure sensitivity (sensitivity to edges, surfaces, and masses), so that we can use such sensitivity metrics to evaluate the representation quality of a DNN (as Fig. 1 (a-b) shows). Each sensitivity metric (let us take the rotation sensitivity for example) is defined as the vulnerability of the regional attribution when we rotate the 3D point cloud with different angles. The regional attribution is computed as the Shapley value, which is widely used as a unique unbiased estimation of an input variable’s attribution [11, 20, 31, 37] from the perspective of game theory. ∗This work was done when Wen Shen was an intern at Shanghai Jiao Tong University. †Quanshi Zhang is the corresponding author. This study was done under the supervision of Dr. Quanshi Zhang. He is with the John Hopcroft Center and the MoE Key Lab of Artificial Intelligence, AI Institute, at the Shanghai Jiao Tong University, China.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
high low sensitivity sensitivity high rotation sensitivity low translation sensitivity scale sensitivity sensitivity to edges sensitivity to surfaces sensitivity to masses (a)
high
low
sensitivity
sensitivity
Based on the sensitivity metrics, we have discovered the following new insights, which have exposed problems with classic DNNs.
• Insight 1. Rotation robustness is the Achilles’ heel of most DNNs for point cloud processing. The rotation sensitivities of PointNet [26], PointNet++ [28], DGCNN [43], the non-dynamic version of DGCNN (referred to as GCNN in this paper) [43], and PointConv [45] are much higher than other sensitivities (see Fig. 1 (a)).
• Insight 2. It is usually difficult for DNNs to extract rotation-robust features from 3D points at edges and corners. These points are usually vulnerable to rotation-based attacks.
• Insight 3. What’s worse, DNNs usually cannot ignore features of such points at edges and corners. Instead, such rotation-sensitive points usually have large regional attributions.
• Insight 4. PointNet fails to model local 3D structures, because convolutional operations in PointNet encode each point independently. Thus, PointNet has low sensitivity to local 3D structures.
Spatial smoothness. Beyond the sensitivity metrics, we also evaluate the spatial smoothness of knowledge representations of DNNs. We define the spatial smoothness of knowledge representations as the similarity among the neighboring regions’ attributions to network output. Most widely-used benchmark datasets for point cloud classification [46, 49] only contain objects with simple 3D structures (e.g. a bed mainly composed of a few surfaces in Fig. 1 (c)), in which adjacent regions usually have similar 3D structures. Therefore, most adjacent regions are supposed to have similar attributions to the network output. We also find that the adversarial training increases the spatial smoothness of knowledge representations.
Representation complexity. Besides regional sensitivities, we further extend the metric of multiorder interaction [53] to evaluate the representation complexity of a DNN, i.e. the maximum complexity of 3D structures that can be encoded in a DNN. The interaction of the m-th order measures the additional benefits brought by collaboration between two point cloud regions i, j under the contexts of other m regions, where m reflects the contextual complexity of the collaboration between regions i and j. High-order interactions usually represent global and complex 3D structures, corresponding to the collaboration between point cloud regions i, j and massive other regions. Loworder interactions usually describe local and simple 3D structures, without being influenced by many contextual regions (see Fig. 1 (d)). Based on such interactions, we have discovered the following new insights.
• Insight 5. Most DNNs fail to encode high-order interactions. I.e. most DNNs mainly focus on local structures and do not extract many global and complex structures from normal samples.
• Insight 6. Rotation-sensitive regions usually activate abnormal high-order interactions (global and complex structures). The very limited global structures modeled by the DNN are usually over-fitted to training samples. Thus, when the sample is rotated, the activated global and complex structures usually appear as abnormal patterns.
• Insight 7. Besides, in terms of model robustness, adversarial training based on adversarial samples w.r.t. using rotations/translations for attack is a typical way to improve the robustness to rotation and translation. Thus, we use the proposed sensitivity metrics to explain the inner mechanism of how and why the adversarially trained DNN is robust to rotation and translation. We find that (1) the adversarial training shifts the attention from the global orientations and positions to the structural information, thereby boosting the sensitivity to local 3D structures. (2) The adversarial training usually increases both the quantity and the complexity of 3D structures (high-order interactions from normal samples) modeled in a DNN, which boosts the robustness to the rotation and translation.

heading: 2 Related work

text:
Deep learning on 3D point clouds: Recently, a series of studies directly used DNNs to process 3D point clouds and have achieved promising performance in various 3D tasks [26, 51, 42, 13, 27, 47, 41, 18, 10, 32, 33]. PointNet [26] was the pioneer to use point-wise multi-layer perceptron to process point clouds and aggregate all individual point features into a global feature. To further extract information from local 3D structures, PointNet++ [28] recursively applied PointNet to capture hierarchical 3D structures. Likewise, Relation-Shape CNN [19] and PointCNN [18] also focused on hierarchical structures and improved the ability to extract contextual information. Due to the irregularity of 3D point clouds, some approaches considered the point set as a graph and further defined graph convolutions. DGCNN [43] dynamically constructed local graphs and conducted feature extraction via the EdgeConv operation. SPG [17] built a superpoint graph to process largescale point clouds. GACNet [40] introduced an attention mechanism in graph convolutional networks. KCNet [34] proposed kernel correlation and graph pooling to aggregate contextual information. In addition, many approaches have been proposed to apply convolution operators to the point clouds. PointConv [45] and KPConv [39] utilized nonlinear functions to construct convolution weights from the input 3D coordinates. InterpCNN [23] interpolated features of 3D points to the discrete kernel weights coordinates, so as to implement the discrete convolution operator to point clouds. Instead of designing new architectures, our study focuses on the analysis of representation quality of existing classic DNNs for point cloud processing.
Visualization or diagnosis of representations: It is intuitive to interpret DNNs by visualizing the feature representations encoded in intermediate layers of DNNs [52, 35, 50, 22, 7], and estimating the pixel-wise saliency/importance/attribution of input variables w.r.t the network output [29, 15, 8, 57, 30, 5, 56]. Similarly, in the 3D domain, PointNet [26] visualized the subset of 3D points (namely the critical subset) that directly affected the network output. Additionally, Zheng et al. [55] specified the critical subset via building a gradient-based saliency map. In comparison, our study proposes to evaluate the representation quality of different point cloud regions.
Quantitative evaluation of representations: The quantitative evaluation of the representations of DNNs provides a new perspective for explanations. The Shapley value [31] estimates the attribution distribution over all players in a game and has been applied to quantitative evaluation of the representations of DNNs [1, 9, 20]. Based on Shapley values, some studies have investigated the interaction between input variables of a DNN [11, 21, 38, 53]. In comparison, our study aims to illustrate distinctive properties of 3D point cloud processing.

heading: 3 Analyzing feature representations of DNNs for 3D point cloud processing

text:
We propose six metrics to measure regional sensitivities to rotation, translation, scale, and three types of local 3D structures, respectively, so as to exhibit the representation property of each specific point cloud region. Beyond these metrics, we can further analyze the representation quality from the following two perspectives, i.e. the spatial smoothness of knowledge representations, and the contextual complexity of 3D structures encoded by a DNN.
Preliminaries: quantifying the regional attribution using Shapley values. The Shapley value was originally introduced in game theory [31]. Considering a game with multiple players, each player aims to pursue a high award for victory. The Shapley value is widely considered as a unique unbiased approach that allocates the total reward to each player fairly, which satisfies axioms of linearity, nullity, symmetry, and efficiency [44] as the theoretical foundation. Please see our supplementary materials for details.
Given a point cloud with n regions1, N = {1, 2, · · · , n}, the Shapley value can be used to measure the attribution of each input region. We can consider the prediction process of a DNN as a game v, and each region in a point cloud as a player i. Let 2N def= {S | S ⊆ N} denote all the possible subsets of N . Let xS denote the point cloud only containing regions in S, in which regions in N\S are removed. For a DNN learned for multi-category classification, we use v(S) to denote the network output given the input xS . v(S) is calculated as log p1−p , where p = p(y = y
truth | xS) denotes the probability of the ground-truth category given xS . Note that the number of input points for each DNN is a fixed value. Therefore, in order to make the DNN successfully handle the point cloud xS without regions in N\S, we reset coordinates of points in regions of N\S to the center of the entire point cloud to remove the information of these points, instead of simply deleting these points [55]. Note that the reason for not simply deleting these points is that the number of input points must be greater than the number of points required for specific layerwise operations of DNNs used in this paper. Specifically, the sampling operation at the first layer of PointNet++ and PointConv requires the minimum number of input points to be greater than 512 points. The k-NN-based grouping [43] operation of DGCNN and GCNN requires the number of input points to be greater than 20 points. However, the computation of Shapley values requires to make inference on a point cloud fragment with a single region i (i.e., x{i}), which may have less than 20 points. Therefore, for such DNNs, we can not simply delete 3D points from the point cloud, in order to allow DNNs to work normally. To this end, for a fair comparison, we choose the alternative way, i.e., placing all points, which are supposed to be masked, to the center of the point cloud. In this way, the numerical attribution of the i-th region to the overall prediction score is estimated by the Shapley value φ(i), as follows.
φ(i) = ∑
S⊆N\{i} |S|!(n− |S| − 1)! n! (v(S ∪ {i})− v(S)), (1)
The computation of Equation (1) is NP-hard. Therefore, we use the sampling-based method in [4] to approximate φ(i).

heading: 3.1 Quantifying the representation sensitivity of a DNN

text:
To analyze the quality of knowledge representations of a DNN, we define different types of sensitivities using the above regional attribution φ(i). Specifically, we measure six types of sensitivities, including the rotation sensitivity, translation sensitivity, scale sensitivity, and three types of sensitivity to local 3D structures (edge-like structures, surface-like structures, and mass-like structures). Given an input point cloud x, the Shapley value φ(i) measures the attribution of region i to the network output. The rotation/translation/scale/local-structure sensitivity of this region is quantified as the range of changes of this region’s attribution φ(i) among all potential transformations {T} of the rotation/translation/scale/local 3D structure, as follows.
∀ i ∈ N = {1, 2, · · · , n}, ai(x) = 1
Z (max T φx′=T (x)(i)−min T φx′=T (x)(i)), (2) where Z = ET [ ∑ i∈N |φx′=T (x)(i)|] is computed for normalization. Thus, the average sensitivity to all potential transformations {T} among all input point clouds x ∈ X is formulated as follows.
sensitivity = Ex∈X [ Ei∈N [ai(x)] ] (3)
In implementation, six types of sensitivities are computed as follows.
Rotation sensitivity quantifies the vulnerability of the inference caused by the rotation of 3D point clouds. Given an input point cloud x, we enumerate all rotations θ = [θ1, θ2, θ3]> from the range of [−π4 , π 4 ], i.e. given θ, we sequentially rotate the point cloud around the three axes of the 3D coordinates system, thereby obtaining a set of new point clouds {x′ = Trotation(x|θ)}. Translation sensitivity quantifies the vulnerability of the inference caused by the translation of 3D point clouds. Given an input point cloud x, we enumerate all translations ∆x = [∆x1,∆x2,∆x3]> from the range of [−0.5, 0.5] along the three axes of the 3D coordinates system, thereby obtaining a set of new point clouds {x′ = Ttranslation(x) = x+ ∆x}.
1There are many ways to segment a 3D point cloud to regions. In our experiments, we first used the farthest point sampling [26] to select n points from each point cloud as centers of n regions. Then, we partitioned the point cloud to n regions by assigning each remaining point to the nearest center point among the selected n center points.
(b) Ill stration of the spatial smoothness.
high attrib tion
lo attrib tion
not smooth
smooth
Scale sensitivity quantifies the vulnerability of the inference caused by the scale of 3D point clouds. Given an input point cloud x, we enumerate all scales α from the range of [0.5, 2], thereby obtaining a set of new point clouds {x′ = Tscale(x) = αx}. Then, we focus on other three sensitivity metrics for three types of local 3D structures, i.e. sensitivity to linearity (edge-like structures), sensitivity to planarity (surface-like structures), and sensitivity to scattering (mass-like structures). According to [12, 6], the significance of a point cloud to be edge-like structures/surface-like structures/mass-like structures is defined as follows.
linearity = λ1 − λ2 λ1 ; planarity = λ2 − λ3 λ1 ; scattering = λ3 λ1 ; (4)
where λ1 ≥ λ2 ≥ λ3 denote three eigenvalues of the covariance matrix of a region’s points. Without loss of generality, we take the linearity for example to introduce the way to enumerate a region’s all values of linearity. Given a region, we use the gradient ascent/descent method to modify the 3D coordinates p ∈ R3 of each point in this region, so as to increase/decrease the linearity, i.e. pnew = p + η ∂linearity∂p . As Fig. 2 (a) shows, we enumerate all regions’ linearity at the same time. The enumeration is implemented under the following two constraints. (1) Each value of λ1 needs to be within the range of λ1 ± γ, so as the λ2 and λ3. (2) ‖pfinal − pori‖ ≤ d, where ‖·‖ denotes the L2-norm. In this way, we obtain a set of point clouds with different degrees of local edge-like structures. In real implementation, we set η = 0.001, γ = 0.003, and d = 0.03.

heading: 3.2 Quantifying the spatial smoothness of knowledge representations

text:
Besides the analysis of representation sensitivity, we also evaluate the spatial smoothness of feature representations encoded by a DNN. Because most benchmark 3D datasets [46, 49] only contain objects with simple 3D structures (see Fig. 1 (c)), except for special regions (e.g. edges), most adjacent regions of such simple objects usually have similar local 3D structures (e.g. surfaces). Therefore, most adjacent regions are supposed to have similar regional attributions, i.e. high smoothness. In this way, high spatial smoothness indicates reliable feature representations. We quantify the smoothness of the regional attribution between neighboring regions, as follows.
non-smoothness = Ex∈XETEiEj∈N (i) [ |φx′(i)− φx′(j)|
Zsmooth
∣∣∣ x′=T (x) ] (5)
whereN (i) denotes a set of nearest point cloud regions (determined by the ball-query search [28]) of region i; Zsmooth = ET [|vx′(N)− vx′(∅)|x′=T (x)] is computed for normalization; vx′(N) denotes the network output given the entire point cloud x′, and vx′(∅) denotes the network output when we mask all regions in x′ by setting all points to the center coordinates of the point cloud.

heading: 3.3 Quantifying the interaction complexity of a DNN

text:
In addition, we also quantify the representation complexity of a DNN, i.e. the complexity of 3D structures encoded by a DNN. To this end, the 3D structures encoded by a DNN is represented using the interaction between different 3D point cloud regions. Here, input regions of a DNN do not work individually, but collaborate with each other to construct a specific 3D structure for inference. Zhang et al. [53] defined the multi-order interactions between two input variables. Given two input regions i and j, the interaction of the m-th order measures the additional attribution brought by collaborations
between i and j under the context of m regions. I(m)(i, j) = ES⊆N\{i,j},|S|=m [ v(S ∪ {i, j})− v(S ∪ {i})− v(S ∪ {j}) + v(S) ] , (6)
I(m)(i, j) > 0 indicates that the presence of region j increases the attribution of region i, φ(i). I(m)(i, j) < 0 indicates that the presence of region j decreases the value of φ(i). I(m)(i, j) ≈ 0 indicates that region j and region i are almost independent of each other. Please see our supplemental materials for details about the meaning of multi-order interaction and the linearity, nullity, commutativity, symmetry, and efficiency axioms of the multi-order interaction.
Here, we could consider the order m as the number of contextual regions involved in the computation of interactions between region i and region j. For example, as Fig. 2 (b) shows, regions i and j (in red), and other m regions (in blue) work together to construct a 3D structure to classify the earphone.
High-order interactions measure the effects of global collaborations among massive regions, i.e. representing complex and large-scale 3D structures. Low-order interactions measure the effects of collaborations between a few regions, i.e. usually representing simple and small-scale 3D structures. Then, we use the following metric to quantify the average strength of the m-th order interactions as the significance of the m-order complex 3D structures.
I(m) = Ex∈X [∣∣Ei,j [I(m)x (i, j)]∣∣]. (7)
If the I(m) of a low order is significantly larger than that of a high order, then the representation complexity of the DNN is limited to representing simple and local 3D structures.

heading: 4 Comparative studies

text:
In this section, we conducted comparative studies to analyze properties of different point cloud regions of different DNNs. Ideally, a well-trained DNN for 3D point cloud processing was supposed to be robust to the rotation and translation, and the DNN was supposed to mainly use the scale and local 3D structures for inference. Besides, considering the 3D structures of objects in benchmark 3D datasets [46, 49] were usually simple, most adjacent regions in an object had continuous and similar 3D structures. Therefore, a well-trained DNN was supposed to have similar regional attributions among these neighboring regions. We also analyzed how complex is the 3D structure that can be encoded by a classic DNN.
We used our method to analyze five classic DNNs for 3D point cloud processing, including the PointNet [26], the PointNet++ [28], the DGCNN [43], the non-dynamic version of DGCNN (i.e. GCNN), and the PointConv [45]. All DNNs were learned based on the ModelNet10 dataset [46] and the ShapeNet part2 dataset [49]. We followed [26] to only use 1024 points of each point cloud to train all DNNs. Each point cloud was partitioned to n = 32 regions1 for the computation of all metrics.
Note that all DNNs used in our paper were well-trained. The testing accuracy was shown in Table 1.We also reported the testing accuracy of other DNNs trained on the ModelNet10 dataset, including RotationNet [14], 3DmFV-Net [3], KCNet [34], and GIFT [2]. These four DNNs obtained the 1st, 4th, 7th, and 10th testing accuracy according the ModelNet10 Benchmark Leaderboard3.
In particular, the previous study [54] has discovered that people could use rotations to attack DNNs for 3D point cloud processing. Therefore, we used the adversarial training to learn a GCNN4 w.r.t. the attacks based on rotations and translations of point clouds, so as to improve the GCNN’s robustness to the rotation and translation. We extended the method in [16] to generate such adversarial examples to attack the GCNN. Please see our supplemental materials for details. The objective function
2We only used part of the ShapeNet part dataset due to the time limitation. Please see our supplemental materials for details.
3Data from https://modelnet.cs.princeton.edu/. 4In tables, adv-GCNN denoted the adversarially trained GCNN.
was minw Ex [ maxT Loss(x′ = T (x), ytruth;w) ] , where w denoted the parameter of the GCNN. Comparative studies have revealed the following effects of the adversarial training (using rotations and translations for attack, instead of using perturbations) on knowledge representations. The adversarial training shifted the attention of DNN from orientations and positions to structural information (including global structures in normal samples, see Fig. 5), thereby increasing the sensitivity to 3D structures (see Table 2 and Fig. 3 (a)). The adversarial training also decreased the correlation between the regional sensitivity and the regional attribution (see Table 3), and increased the spatial smoothness of knowledge representations (see Table 4).
Comparative study 1, explaining the regional sensitivity of DNNs. Table 2 shows six types of regional sensitivities of six DNNs learned on the ModelNet10 dataset and the ShapeNet part dataset. In terms of translation sensitivity, PointNet was relatively sensitive to the translation, because PointNet extracted features from global coordinates of points, thereby being sensitive to the translation. In contrast, PointNet++ and PointConv were robust to translation, because these two DNNs encoded relative coordinates. Particularly, PointConv did not use global coordinates during the inference process, thereby yielding the lowest translation sensitivity (see the point cloud with the darkest blue in the second row of Fig. 3 (a)). In terms of scale sensitivity, PointNet++ was relatively sensitive to the scale, because PointNet++ encoded features of neighborhood with fixed scales. Besides, because adversarial training forced the GCNN to remove attention from rotation-sensitive features and translation-sensitive features, the adversarially trained GCNN paid more attention to structural information. Therefore, compared with the original GCNN, the adversarially trained GCNN had higher sensitivity to local 3D structures. Furthermore, we also obtained the following conclusions.
• Rotation robustness was the Achilles’ heel of classic DNNs for 3D point cloud processing. As Table 2 and Fig. 3 (a) show, all DNNs were sensitive to rotations except for the adversarially trained GCNN.
• PointNet failed to encode local 3D structures. In terms of sensitivity to local 3D structures, PointNet was the least sensitive DNN (see Table 2). It was because convolution operations of the PointNet encoded the information of each point independently, i.e. the PointNet did not encode the information of neighboring points/regions. This conclusion is also verified by the phenomenon that PointNet had darker blue point clouds than other DNNs (see the last three rows of Fig. 3 (a)).
• Most DNNs usually failed to extract rotation-robust features from 3D points at edges and corners. Given a point cloud x, we selected the most rotation-sensitive region i∗ (shown as black boxes in Fig. 3 (b)). We rotated the point cloud x to the orientations that maximized and minimized the
边缘结构敏感度
平⾯结构敏感度
团状结构敏感度
attribution of region i∗, i.e. θ1 = arg maxθ φx′(i∗) and θ2 = arg minθ φx′(i∗). Fig. 3 (b) visualizes regional attributions of point clouds rotated by θ1 and θ2. We found that rotation-sensitive regions were usually distributed on the edges and corners, which verified our conclusion.
• Most DNNs usually could not ignore features of rotation-sensitive points at edges and corners. Table 3 shows that the Pearson correlation coefficient [25] between each region’s average strength of attribution over different rotations (i.e. Eθ[|φx′(i)|], s.t. x′ = Trotation(x|θ)) and this region’s rotation sensitivity ai(x) is much larger than Pearson correlation coefficients between the attribution and other sensitivities. This means that rotation-sensitive regions (which were usually distributed on the edges and corners) usually had large regional attributions, which verified our conclusion. Besides, Table 3 also shows that the adversarial training reduced the correlation between the regional sensitivity and the regional attribution. Fig. 4 (a) visualizes the positive correlation between the regional rotation sensitivity and the regional attribution of the PointNet.
Comparative study 2, explaining the spatial smoothness of knowledge representations. Table 4 shows the non-smoothness of knowledge representations encoded by different DNNs. Note that the adversarially trained GCNN was significantly biased to the knife category. In other words, the
adversarially trained GCNN classified the empty input as the knife category with a high confidence (please see our supplementary materials for details). Therefore, to enable fair comparisons, we also reported the spatial non-smoothness of the adversarially trained GCNN on all other categories except the knife. We discovered that without considering the biased knife category, adversarial training increased the spatial smoothness of knowledge representations. Fig 4 (b) also verified this conclusion.
Comparative study 3, explaining the interaction complexity of DNNs. Fig. 5 shows multi-order interactions of different DNNs. From this figure, we discovered the following new insights.
• Most DNNs failed to encode high-order interactions (i.e. global and large-scale 3D structures). As Fig. 5 (a) shows, no matter given normal samples or adversarial samples5, classic DNNs encoded extremely low-order interactions. This indicated that most DNNs did not extract complex and large-scale 3D structures from normal samples.
• The adversarial training (using rotations and translations for attack, instead of using perturbations) increased the effects of extremely high-order interactions. As Fig. 5 (a) shows, the adversarially trained GCNN encoded extremely low-order interactions and extremely high-order interactions (i.e. the global structures of objects) from normal samples. Because the GCNN was forced to sophisticatedly select relatively complex rotation-robust features among all potential features.
• Rotation sensitivity of regions with out-of-distribution high-order interactions (i.e. abnormal complex and large-scale 3D structures) were larger than the average sensitivity over all regions. In fact, there are two types of high-order interactions. Unlike the above two insights describing whether or not a DNN encoded high-order interactions on normal samples, this insight mainly focused on abnormal out-of-distribution high-order interactions in a DNN. When a point cloud was attacked by adversarial rotations5, the adversarial rotation5 would generate out-of-distribution high-order interactions (i.e. abnormal complex and large-scale 3D structures) to attack the DNN. We measured interactions between the most rotation-sensitive region i∗ and its neighbors j ∈ N (i∗) among all input point clouds, i.e. Ex∈X [ |Ej∈N (i∗)[I (m) x (i∗, j)]| ] . As Fig. 5 (b) shows, rotation-sensitive regions usually encoded relatively more high-order interactions than the overall interaction distribtuion over all regions. This indicates that compared to most other regions, rotation-sensitive regions paid more attention to high-order interactions, although low-order interactions of rotation-sensitive regions increased too.
Broad applicability of the proposed metrics. We also conducted experiments on an AutoEncoder for 3D point cloud reconstruction task and rotation-invariant DNNs for 3D point cloud classification, in order to further demonstrate the broad applicability of the proposed metrics.
For the AutoEncoder for 3D point cloud reconstruction task, we used all layers before the fullyconnected layers in PointNet [26] as the encoder and used the decoder in the FoldingNet [48] as the decoder. We took v(S) = (z(N)−z(∅))
>(z(S)−z(∅)) ||z(N)−z(∅)||2 as the reward score in Equation (1), where
z(S) denotes the output vector of the encoder given the input point cloud consisting of regions in S. This reward score measures the utility of the encoder output z(S) given regions in S along the direction of z(N) − z(∅). The AutoEncoder was learned based on the ModelNet10 dataset. We measured the rotation sensitivity (0.099±0.043), the translation sensitivity (0.152±0.086), and the scale sensitivity (0.045±0.042) of the AutoEncoder. Compared with results in Table 2, we found that (1) the AutoEncoder for reconstruction was also sensitive to rotation; (2) the AutoEncoder for 3D
5Here, we used rotations for attack, instead of using perturbations.
point cloud reconstruction was more sensitive to translation than the DNN for classification; (3) the AutoEncoder for reconstruction was sensitive to the scale change.
Besides, we followed [32] to revise PointNet++ and DGCNN to be rotation-invariant DNNs. We measured the rotation sensitivity of the rotation-invariant PointNet++ (0.002±0.001) and DGCNN (0.010±0.004). Compared with results in Table 2, we found that rotation-invariant DNNs were much more robust to rotations than traditional DNNs (even the adversarially-trained DNN).
Effects of data augmentation on sensitivities. We conducted comparative studies to explore the effects of data augmentation on sensitivities, including translation augmentation, scale augmentation, rotation augmentation around the y-axis, and rotation augmentation around a random axis. We conducted experiments on PointNet and DGCNN. To explore the effects of each of the above augmentation on sensitivities, we learned two versions of each network architecture, i.e. one network with the specific augmentation and the other network without the specific augmentation. Please see our supplementary materials for more details about different versions of each network architecture. All DNNs were learned based on the ModelNet10 dataset. Table 5 shows that rotation/translation/scale augmentation decreased the rotation/translation/scale sensitivity of a DNN.
Besides, we compared the effects of rotation augmentation around a random axis and the effects of adversarial training on the rotation sensitivity. We conducted experiments on DGCNN and GCNN. We trained two versions of DGCNN and GCNN, one with rotation augmentation around a random axis (DGCNN, 0.052 ±0.021; GCNN, 0.048±0.024) and one with the adversarial training using rotations for attack (DGCNN, 0.036±0.015; GCNN, 0.028±0.016). We found that compared with the rotation augmentation, the adversarial training w.r.t. rotation-based attacks had a greater impact on the rotation sensitivity.

heading: 5 Conclusion

text:
In this paper, we have measured six types of regional sensitivities, the spatial smoothness, and the contextual complexity of feature representations encoded by DNNs. Comparative studies have discovered several new insights into classic DNNs for 3D point cloud processing. We have found that most DNNs were extremely sensitive to the rotation. Rotation-sensitive regions were usually distributed on the edges and corners of objects, had large attributions to network output, and usually paid more attention to abnormal large-scale structures. In addition, most DNNs failed to extract complex and large-scale 3D structures from normal samples, while the adversarial training could encourage the DNN to extract global structures from normal samples.
Acknowledgments and Disclosure of Funding
This work is partially supported by the National Nature Science Foundation of China (No. 61906120, U19B2043), Shanghai Natural Science Fundation (21JC1403800,21ZR1434600), Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102). This work is also partially supported by Huawei Technologies Inc.

title: Interpreting Representation Quality of DNNs for 3D Point Cloud Processing