UDC 517.9

I.M. Prudnikov 111©Igor Mihailovitch Prudnikov - Scientific collaborator of
Smolensk Federal Medical University, E-mail: pim<EMAIL_ADDRESS>
Accelerated method of finding for the minimum of arbitrary Lipschitz convex
function

The goal of the paper is development of an optimization method with the
superlinear convergence rate for an arbitrary convex function. For
optimization an approximation is used that is similar to the Steklov integral
averaging. The difference is that averaging is performed over a variable-
dependent set, that is called a set-valued mapping (SVM) satisfying simple
conditions. Novelty approach is that with such an approximation we obtain
twice continuously differentiable convex functions, for optimizations of which
are applied methods of the second order. The estimation of the convergence
rate of the method is given.

Keywords: Lipschitz functions, convex functions, generalized gradients, Clark
subdifferential, Lebesgue integrals, Steklov’s integrals, generalized matrices
of second derivatives, Newton optimization methods for Lipschitz functions.

##  1 Introduction

Nonsmooth (non-differentiable) or insufficiently smooth functions are widely
used in economics, data processing, control theory, artificial intelligence
and other areas. An example of such functions is the functions obtained when
taking operations of minimum or maximum.

Nonsmooth functions may not have derivatives at some points. It is known that
the Lipschitz function is differentiable almost everywhere in $R^{n}$ [1]. The
generalized gradients are used instead of the gradients at points of non-
differentiability of a function. The optimization methods of these functions
are different from the optimization methods of smooth (differentiable)
functions.

In this paper, the author continues research related to construction of the
optimization method of Lipschitz functions using the Steklov integrals and
similar integrals, when the set, which averaging is taking on, is a function
of a variable.

This approach gives twice differentiable functions, the stationary points of
which coincide with the stationary points of an original function in contrast
to the case when averaging is doing over sets independent of $x$. For such
functions the second-order optimization methods can be used which are tested
for an arbitrary convex functions with estimation of the convergence rate.

If we have discontinuous gradients as functions of variables, then it is very
difficult to build optimization methods and estimate their convergence rates
in the general case. Using the polynomial approximation of an original
function and transition to optimization of a smooth function by known methods
[2] does not allow to solve the optimization problem, since this path leads to
the emergence of new extremum points located far from the extremum points of
the original function.

The separation of fictitious extremum points from real ones is the same
difficult task as the initial one. Therefore, the development of the theory of
nonsmooth functions went on the way of developing its own methods, based on
generalized gradients properties of the Lipschitz functions. Here it is worth
mentioning the articles by [2] \- [8] N. Z. Shor, B. N. Pshenichny, V. F.
Demyanova, E.A. Nurminsky, F. Clark, R.T. Rokafellar, L.N. Polyakova.

To build accelerated optimization methods for nonsmooth functions, it is
necessary to determine the constructions to which the second order
optimization methods are applicable. But to perform the latter it is necessary
to define such constructions for which the extremum points do not disappear
and the new ones do not appear.

The paper proposes exactly this method of smoothing nonsmooth functions. The
resulting function will be continuously differentiable. If we again apply the
averaging operation to it, then we will have twice differentiable function.

If we apply averaging over sets depending on the variable $x$, then we obtain
a continuously differentiable function, the stationary points of which
coincides with the stationary points of the original function. If we repeat
averaging procedure, we obtain twice differentiable functions, which second-
order optimization methods with accelerated convergence can be applied to.

With the help of the defined functions, it is possible to move from local
optimization of non-smooth functions to local optimization of smooth
functions, and also estimate the rate of convergence to the extremum point,
that is definitely important, because it is possible to develop accelerated
optimization methods for functions with discontinuous gradients. Similar
constructions as far as known to the author, nobody has previously proposed.

##  2 Smoothing integral functions

Let $f(\cdot):R^{n}\rightarrow R$ be a Lipschitz function with a constant $L$,
$x_{*}$ is its local minimum (maximum) in $R^{n}$. As it is known, necessary
extremum condition at the point $x_{*}$ for the Lipschitz function $f(\cdot)$
is zero belongs to the Clarke subdifferential $\partial_{CL}f(\cdot),$ ,
calculated at this point $x_{*}$ , i.e.

$0\in\partial_{CL}f(x_{*}).$

Any point for which this condition is correct is called stationary. Not all
stationary points are points of minimum or maximum.

Let us take an arbitrary convex compact set $D\subset R^{n}$,
$0\in\mbox{int}\,D$. We introduce the definition of $\varepsilon(D)$
stationary point.

Definition 1. A point $x_{\varepsilon}$ is called $\varepsilon(D)$ stationary
point of the function $f(\cdot)$ , if the set $x_{\varepsilon}+D$ includes a
stationary point of the function $f(\cdot)$.

This definition agrees with the definition of $\varepsilon$ stationary point
for the convex functions [4], because for the strongly convex functions the
distance from $\varepsilon$ stationary point to minimum can be evaluated by
difference of values of the function $f(\cdot)$ at these points.

Define the function $\varphi(\cdot):R^{n}\rightarrow R$

$\varphi(x)=\frac{1}{\mu(D)}\int_{D}f(x+y)dy,$ (1)

where $\mu(D)$ is the measure of the domain $D$, $\mu(D)>0$.

Obviously, $\varphi(\cdot)$ is a continuous function. Let us show that
$\varphi(\cdot)$ is a Lipschitz function with Lipschitz constant equaled to
Lipschitz constant of the function $f(\cdot)$. Really,

$\mid\varphi(x_{1})-\varphi(x_{2})\mid\leq\frac{1}{\mu(D)}\int_{D}\mid
f(x_{1}+y)-f(x_{2}+y)\mid
dy\leq\frac{1}{\mu(D)}\int_{D}L\|x_{1}-x_{2}\|dy\leq$ $\leq
L\|x_{1}-x_{2}\|\,\,\,\,\,\,x_{1},x_{2}\in R^{n}.$

The function $f(\cdot)$ is Lipschitz, and therefore it is almost everywhere
(a.e.) differentiable in $R^{n}$ [1]. Let $N(f)$ denote the set of points of
differentiability of the function $f(\cdot)$ in $R^{n}$. It is known that
$N(f)$ is everywhere dense in $R^{n}$ and, in particular, in $D$ , because of
$\mu(D)>0$ by assumption.

The following theorem was proved in [6].

###### Theorem 2.1

For an arbitrary Lipschitz function $f(\cdot):R^{n}\rightarrow R$ the function

$\varphi(x)=\frac{1}{\mu(D)}\int_{D}f(x+y)dy,$

where $D$ is an arbitrary domain in $R^{n},0\in intD,\mu(D)$ is the measure of
the domain $D$, $\mu(D)>0$, is a continuously differentiable function with the
derivative

$\varphi^{\prime}(x)=\frac{1}{\mu(D)}\int_{D}f^{\prime}(z+x)dz.$

###### Remark 2.1

We use here the Lebesque integration.

###### Remark 2.2

The derivatives of the function $f(\cdot)$ are taken at those points where
they exist.

It was also proved in [6] that if $f(\cdot)$ is Lipschitz, then
$\varphi^{\prime}(\cdot)$ is also Lipschitz function.

Consider the function

$\phi(x)=\frac{1}{\mu(D)}\int_{D}\varphi(x+y)dy.$

Since $\varphi(\cdot)$ is Lipschitz, we will have

$\phi^{\prime}(x)=\frac{1}{\mu(D)}\int_{D}\varphi^{\prime}(z+x)dz.$ (2)

Since $\varphi^{\prime}(\cdot)$ is continuous, $\phi(\cdot)$ is a continuously
differentiable function. As soon as $\varphi^{\prime}(\cdot)$ is Lipschitz, we
can differentiate (2). As a result, we will have

$\phi^{\prime\prime}(x)=\frac{1}{\mu(D)}\int_{D}\varphi^{\prime\prime}(z+x)dz,$
(3)

i.e. $\phi(\cdot)$ is a twice continuously differentiable function.

It can be shown [7] that the function $\phi^{\prime\prime}(\cdot)$ is
Lipschitz with a constant $\tilde{L}$, depending on the set $D$. If $D$ is a
ball or a cube in $\mathbb{R}^{n}$, then we can take
$\tilde{L}=\frac{2L}{d^{2}}$, where $d$ is the diameter of the set $D$ , $L$
is the Lipschitz constant of the function $f(\cdot)$.

###### Remark 2.3

The integration in (3) is understood, as before, in the sense of Lebesgue.

If $x$ is a point of the local maximum or minimum of the function $f(\cdot)$,
then for sufficiently small $r>0$ and $D=S^{n-1}_{r}(0)=\\{z\in
R^{n}\mid\|z\|\leq r\\}$ the point $x$ is also a local minimum or maximum
point of the function $\varphi(\cdot)$. But unlike the function $f(\cdot)$ the
function $\varphi(\cdot)$ is continuously differentiable. Similar thing is
true for the function $\phi(\cdot)$, i.e. the point $x$ is a point of local
minimum or maximum of the function $\phi(\cdot)$. But unlike the functions
$f(\cdot)$ and $\varphi(\cdot)$ the function $\phi(\cdot)$ is twice
continuously differentiable, matrix of the second mixed derivatives of which
satisfies to the Lipschitz condition. To optimize $\phi(\cdot)$ we can use the
methods of second order.

The functions $\varphi(\cdot)$ and $\phi(\cdot)$ also retain many properties
of the function $f(\cdot)$. An important property for applications of the
functions $\varphi(\cdot)$ and $\phi(\cdot)$ is that if $f(\cdot)-$ is convex
with respect to all or some variables, then $\varphi(\cdot)$ and $\phi(\cdot)$
are also convex with respect to the same variables [7].

Let us see which stationary points the function $\varphi(\cdot)$ has.
According to the formula (2), the stationary point $x_{*}$ of the function
$\varphi(\cdot)$ is such a point, for which

$\varphi^{\prime}(x_{*})=\frac{1}{\mu(D)}\int_{D}f^{\prime}(z+x_{*})dz=0.$ (4)

We will show that the stationary point of the function $f(\cdot)$ belongs to
the set $x_{*}+D$.

The integral in (4) can be represented with any degree of accuracy $\delta>0$
in the form of a sum

$\frac{1}{\mu(D)}\sum_{i=1}^{N}f^{\prime}(z_{i}+x_{*})\mu(D_{i}),$ (5)

where $N=N(\delta)$, $D_{i}\subset D,i\in 1:N,$ are subregions of the set $D$,
$\mu(D_{i})$ are their measures,

$\sum_{i=1}^{N}\mu(D_{i})=\mu(D).$

The sum (5) is the convex hull of the vectors $f^{\prime}(z_{i}+x_{*})$.
Really,

$\frac{1}{\mu(D)}\sum_{i=1}^{N}f^{\prime}(z_{i}+x_{*})\mu(D_{i})=\sum_{i=1}^{N}\frac{\mu(D_{i})}{\mu(D)}f^{\prime}(z_{i}+x_{*})=\sum_{i=1}^{N}\alpha_{i}f^{\prime}(z_{i}+x_{*}),$
(6)

where $\alpha_{i}=\frac{\mu(D_{i})}{\mu(D)},\alpha_{i}\geq 0,$ and
$\sum_{i=1}^{N}\alpha_{i}=1.$

According to the equality (4), the sum (6) can be made arbitrarily small for
large $N=N(\delta)$ (for small $\delta$ ). Since the convex hull of any
vectors is a closed set and the convex hull of generalized gradients is a
collinear vector to some generalized gradient of the function $f(\cdot)$ at a
point $x_{*}+\bar{z}\in x_{*}+D$, $\bar{z}\in D$, we obtain that the sum (6)
is a vector tending to zero generalized gradient as $N\rightarrow\infty$. In
other words, there exists a point $x_{*}+\bar{z}\in x_{*}+D$, with zero
generalized gradient of the function $f(\cdot)$.

Therefore, the stationary point $x_{*}+\bar{z}$ of the function $f(\cdot)$
belongs to the set $x_{*}+D$. Hence, by definition, $x_{*}$ is a
$\varepsilon(D)$ stationary point. Thus, the following theorem is proved.

###### Theorem 2.2

All stationary points of the function $\varphi(\cdot)$ are $\varepsilon(D)$
stationary points of the function $f(\cdot)$.

Similar reasoning is true for the function $\phi(\cdot)$.

###### Corollary 2.1

All stationary points of the function $\phi(\cdot)$ are $\varepsilon(D)$
stationary points of the function $\varphi(\cdot)$ or
$\varepsilon(2D)$stationary points of the function $f(\cdot)$.

###### Corollary 2.2

If $x_{*}$ is a local minimum point of the function $f(\cdot)$, for which
there exists a neighborhood $S,x_{*}\in\mbox{int}\,S,$ where

$f(z)\geq f(x_{*})\,\,\,\forall z\in S,$

then there exists a convex compact set $D$ and a point $y\in S$, where
$\varphi^{\prime}(y)=0$ and $x_{*}\in y+D\subset S$, i.e. the point $y$ is the
$\varepsilon(D)$ stationary point of the function $f(\cdot)$.

The same is true for the local maximum point of the function $f(\cdot)$.

To find the $\varepsilon(2D)$ stationary points of the function $f(\cdot)$, we
should apply the second-order optimization methods for the function
$\phi(\cdot)$. The numerical optimization method will be given with the rate
of convergence to a stationary point of the function $f(\cdot)$ faster than
any geometric progression.

##  3 Search algorithm for stationary points of the Lipschitz function

Let us take a sequence of sets $\\{D_{s}\\},s=1,2,\dots$ with non-empty
interior whose diameters $d(D_{s})$ tends to zero with increasing $s$. Let be
$D_{s}=B^{n}_{r_{s}}(0)=\\{v\in\mathbb{R}^{n}\mid\|v\|\leq r_{s}\\}$ for
$r_{s}\rightarrow+0$ as $s\rightarrow\infty$. We introduce a sequence of the
functions

$\varphi_{s}(x)=\frac{1}{\mu(D_{s})}\int_{D_{s}}f(x+y)dy$

and

$\Phi_{s}(x)=\frac{1}{\mu(D_{s})}\int_{D_{s}}\varphi_{s}(x+y)dy.$

Let the inequality $\|\Phi^{\prime\prime}_{s}(\cdot)\|\leq{L}_{s}$ be true for
the matrix of the second mixed derivatives of the function $\Phi_{s}(\cdot)$.
It is proved in [7] that the constant $L_{s}=\frac{L}{d(D_{s})}.$ We will
consider instead of the function $\Phi_{s}(\cdot)$ the function
$\tilde{\Phi}_{s}(\cdot):\mathbb{R}^{n}\rightarrow\mathbb{R}$:

$\tilde{\Phi}_{s}(y,x)=\Phi_{s}(y)+{L}_{s}\|y-x\|^{2},$

for any fixed point $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{n}$.

As a result, the inequality

${L_{s}}\|z\|^{2}\leq(\nabla^{2}\tilde{\Phi}_{s}(x,x)z,z)\leq
3{L}_{s}\|z\|^{2}\,\,\,\,\forall z\in\mathbb{R}^{n},$ (7)

is true where
$\nabla^{2}\tilde{\Phi}_{s}(\cdot,x)=\tilde{\Phi^{\prime\prime}}_{s}(\cdot,x)$
is the matrix of the second mixed derivatives of the function
$\tilde{\Phi}_{s}(\cdot,x)$ with respect to the variable $y$.

Note that if the function $\Phi_{s}(\cdot)$ is bounded below, then the
function $\tilde{\Phi}_{s}(\cdot,x)$ is also bounded below for any points $x$
and $y$ from $\mathbb{R}^{n}$. Also, it is clear that
$\nabla\tilde{\Phi}_{s}(x,x)=\nabla\Phi_{s}(x)$, where
$\nabla\tilde{\Phi}_{s}(x,x)$ is the gradient of the function
$\tilde{\Phi}_{s}(\cdot,x)$ at the point $y=x$.

We assume that the functions $f(\cdot)$ and $\Phi_{s}(\cdot)$ are bounded
below and reach their infimum at some points.

Search optimization method for a stationary point of Lipschitz function

Let the point $x_{k}$ at the $k$\- th step have already been built. Construct
the point $x_{k+1}$. We put by definition
$\tilde{\Phi}_{s,k}(\cdot)=\tilde{\Phi}_{s}(\cdot,x_{k})$.

1\. Calculate
$\triangle_{k}=-(\nabla^{2}\tilde{\Phi}_{s,k}(x_{k}))^{-1}\nabla\tilde{\Phi}_{s,k}(x_{k}).$

2\. Find a non-negative integer $l_{k}$ for which

$\tilde{\Phi}_{s,k}(x_{k}+2^{-l_{k}}\triangle_{k})\leq\tilde{\Phi}_{s,k}(x_{k})-2^{-2l_{k}}\frac{L_{s}}{2}\|\triangle_{k}\parallel^{2}.$
(8)

3\. We assume $x_{k+1}=x_{k}+2^{-l_{k}}\triangle_{k}$, $k=k+1$.

4\. With increasing $k$ we decrease $d(D_{s})$ such that the inequality

$\frac{3\|\triangle_{k}\|}{d(D_{s})}<\varepsilon_{k}$ (9)

holds for some sequence $\\{\varepsilon_{k}\\}$, where
$\varepsilon_{k}\rightarrow+0$. Go to the step 1.

Let us show that $\|\triangle_{k}\|\rightarrow+0$ as $k\rightarrow\infty$ and
the number $l_{k}$ mentioned in operation $1$ exists. Expand the function
$\tilde{\Phi}_{s,k}(\cdot)$ in a neighborhood of the point $x_{k}$ in the
Taylor series

$\tilde{\Phi}_{s,k}(x_{k}+\alpha\triangle_{k})=\tilde{\Phi}_{s,k}(x_{k})+\alpha(\nabla\tilde{\Phi}_{s,k}(x_{k}),\triangle_{k})+o_{s,k}(\|\alpha\triangle_{k}\|),$
(10)

where $o_{s,k}(\|\cdot\|)$ is an uniformly infinitesimal function in $k$.

As soon as
$\triangle_{k}=-(\nabla^{2}\tilde{\Phi}_{s,k}(x_{k}))^{-1}\nabla\tilde{\Phi}_{s,k}(x_{k})$,
then
$\nabla\tilde{\Phi}_{s,k}(x_{k})=-\nabla^{2}\tilde{\Phi}_{s,k}(x_{k})\triangle_{k}$.
Consequently,
$(\nabla\tilde{\Phi}_{s,k}(x_{k}),\triangle_{k})=-(\nabla^{2}\tilde{\Phi}_{s,k}(x_{k})\triangle_{k},\triangle_{k})$.
Therefore, we can rewrite (10) in the form

$\tilde{\Phi}_{s,k}(x_{k}+\alpha\triangle_{k})=\tilde{\Phi}_{s,k}(x_{k})-\alpha(\nabla^{2}\tilde{\Phi}_{s,k}(x_{k})\triangle_{k},\triangle_{k})+o_{s,k}(\|\alpha\triangle_{k}\|).$
(11)

As soon as $o_{s,k}(\|\cdot\|)$ is an uniformly infinitesimal function in $k$,
then the inequality

$o_{s,k}(\alpha\|\triangle_{k}\|)\leq\frac{\alpha\|\triangle_{k}\|}{N_{s}(\alpha\|\triangle_{k}\|)}$

is true for large $k$ where $N_{s}(\alpha\|\triangle_{k}\|)\rightarrow\infty$
as $\alpha\|\triangle_{k}\|\rightarrow 0$.

From (11) we have

$\tilde{\Phi}_{s,k}(x_{k}+\alpha\triangle_{k})\leq\tilde{\Phi}_{s,k}(x_{k})-\alpha{L_{s}}\|\triangle_{k}\|^{2}+\frac{\alpha\|\triangle_{k}\|}{N_{s}(\alpha\|\triangle_{k}\|)}=$
$=\Phi_{s,k}(x_{k})-\alpha\|\triangle_{k}\|({L_{s}}\|\triangle_{k}\|-\frac{1}{N_{s}(\alpha\|\triangle_{k}\|)}).$

The value $\frac{1}{N_{s}(\alpha\|\triangle_{k}\|)}$ tends to zero as
$\alpha\|\triangle_{k}\|\rightarrow 0$. Therefore, for small
$\|\triangle_{k}\|$ and, consequently, for small
$\|\nabla\tilde{\Phi}_{s,k}(x_{k})\|$, we get

${L_{s}}\|\triangle_{k}\|-\frac{1}{N_{s}(\alpha\|\triangle_{k}\|)}\geq\frac{L_{s}\|\triangle_{k}\|}{2}.$
(12)

It follows from here that the inequality

$\tilde{\Phi}_{s,k}(x_{k}+\alpha\triangle_{k})\leq\tilde{\Phi}_{s,k}(x_{k})-\alpha\frac{{L_{s}}}{2}\|\triangle_{k}\|^{2}$
(13)

is true for sufficiently small $\|\nabla\tilde{\Phi}_{s,k}(x_{k})\|$ and any
$\alpha\in[0,1]$. Therefore, $\|\nabla\tilde{\Phi}_{s,k}(x_{k})\|$ tends to
zero as $k\rightarrow\infty$, since otherwise, as follows from (13), the
function $\tilde{\Phi}_{s,k}(\cdot)$ would decrease in value
$\alpha\frac{{L_{s}}}{2}\|\triangle_{k}\|^{2}$ along the direction
$\triangle_{k}$ at $k$ -th step. The last thing contradicts to the lower
boundedness of the function $\tilde{\Phi}_{s,k}(\cdot)$ for all $k$ and $s$.

We will show that when the requirements of the step $4$ are fulfilled, the
function $o_{s,k}(\cdot)$ is uniformly infinitesimal in $k$ and $s$. From (10)
for $\alpha=1$ we have

$o_{s,k}(\|\triangle_{k}\|)=\tilde{\Phi}_{s,k}(x_{k}+\triangle_{k})-\tilde{\Phi}_{s,k}(x_{k})-(\nabla\tilde{\Phi}_{s,k}(x_{k}),\triangle_{k}).$
(14)

We will use the midpoint theorem. Then

$\tilde{\Phi}_{s,k}(x_{k}+\triangle_{k})-\tilde{\Phi}_{s,k}(x_{k})=(\nabla\tilde{\Phi}_{s,k}(x_{k}+\xi\triangle_{k}),\triangle_{k})$

for $\xi\in[0,1].$ Substitute the receive expression in (14). We will have

$o_{s,k}(\|\triangle_{k}\|)=(\nabla\tilde{\Phi}_{s,k}(x_{k}+\xi\triangle_{k}),\triangle_{k})-(\nabla\tilde{\Phi}_{s,k}(x_{k}),\triangle_{k}).$

We use the midpoint theorem again for the derivatives of the function
$\tilde{\Phi}_{s,k}(\cdot):$

$(\nabla\tilde{\Phi}_{s,k}(x_{k}+\xi\triangle_{k}),\triangle_{k})-(\nabla\tilde{\Phi}_{s,k}(x_{k}),\triangle_{k})=(\nabla^{2}\tilde{\Phi}_{s,k}(x_{k}+\eta\triangle_{k})\triangle_{k},\triangle_{k}).$

Therefore

$|o_{s,k}(\|\triangle_{k}\|)|\leq|\nabla^{2}\tilde{\Phi}_{s,k}(x_{k}+\eta\triangle_{k})\triangle_{k},\triangle_{k})|.$

It follows from the Lipschitz quality of the gradient $\nabla\Phi_{s}(\cdot)$
with the constant $L_{s}=\frac{L}{d(D_{s})}$ that the next evaluation

$\frac{|o_{s,k}(\|\triangle_{k}\|)|}{\|\triangle_{k}\|}\leq\frac{3\|\triangle_{k}\|}{d(D_{s})}<\varepsilon_{k}.$

is true if (7) is satisfied.

It follows from here that the functions $o_{s,k}(\cdot)$ and
$\frac{1}{N_{s}(\alpha\|\triangle_{k}\|)}$ are uniformly infinitesimal in $k$
and $s$. Therefore, for small $\|\triangle_{k}\|$ the inequality (12) will be
correct for $\alpha=1$. Consequently, the inequality (15) is satisfied for
$l_{k}=0$ and the process goes with the full step $\triangle_{k}$.

###### Theorem 3.1

Any limit point of the sequence $\\{x_{k}\\}$, constructed according to the
algorithm 1-4, is a stationary point of the function $f(\cdot)$.

Proof. We have already proved that for small $\|\triangle_{k}\|$ the process
goes with the full step $\triangle_{k}.$ Since the functions
$\tilde{\Phi}_{s,k}(\cdot)$ are bounded below in aggregate on $k,s$ and
inequality (13) is true for all $k$ and $s$ , then
$\|\triangle_{k}\|\rightarrow 0$ and
$\nabla\tilde{\Phi}_{s,k}(\cdot)\rightarrow 0$ for $s,k\rightarrow\infty$.
Therefore, the sequence $\\{x_{k}\\}$ has the limit points.

The following equalities

$\triangle_{k+1}=-(\nabla^{2}\tilde{\Phi}_{s,k+1}(x_{k+1}))^{-1}\nabla\tilde{\Phi}_{s,k+1}(x_{k+1}),\,\,\nabla\tilde{\Phi}_{s,k}(x_{k+1})=o_{s,k}(\|\triangle_{k}\|),$

are correct where all $o_{s,k}(\cdot)$ in (10) are uniformly infinitesimal in
$k,s$ .

It follows from the definition of the function ${\Phi}_{s}(\cdot)$ that the
gradient $\nabla{\Phi}_{s}(\cdot)$ is the hull of the generalized gradients of
the function $f(\cdot)$.

Taking into account what is said above about $\|\triangle_{k}\|$ and
$\nabla\tilde{\Phi}_{s,k}(\cdot)$, and also from uppersemicontinuity of the
Clarke subdifferential mapping [5], [8] we can imply that the inclusion
$0\in\partial_{CL}f(x^{*})$ is correct at a limit point $x_{*}$, i.e. $x_{*}$
is the stationary point of the function $f(\cdot)$. The theorem is
proved.$\Box$

To estimate the rate of convergence, we assume that $f(\cdot)$ is a convex
function. From [6] it follows that $\Phi_{s}(\cdot)$ is also a convex
function. Define the function

$\tilde{\Phi}_{s,k}(y,x_{k})=\Phi_{s}(y)+\tilde{L}_{k}\|y-x_{k}\|^{2}$

for each $k$ and $y\in\mathbb{R}^{n}$ where $\tilde{L}_{k}>0$ is positive
number depending on $k$ and tending to zero as $k\rightarrow\infty$. To search
for a stationary point of the function $f(\cdot)$, we use the algorithm
described below.

We first introduce the conditions of coherence, which give to us the rules of
coherent striving to infinity $k$ and $s$. We will write them briefly in the
form of dependence $s=s(k)$. Denote by $L_{s(k)}$ the constant bounding from
above the norm of the matrix
$\nabla^{2}\tilde{\Phi}_{s(k),k}(\cdot):\|\nabla^{2}\tilde{\Phi}_{s(k),k}(\cdot)\|\leq
L_{s(k)}$. During the process of optimization we satisfy to conditions of
coherence:

  1. 1.

$L_{s(k)}\|\Delta_{k}\|\rightarrow 0$ as $s(k)\rightarrow\infty$;

  2. 2.

for convergence with superlinear rate, we require that

$q_{s(k),k}=\frac{\tilde{L}_{k}^{-1}}{N_{s(k),k}(\|\Delta_{k}\|)}\rightarrow
0$

as $s(k),k\rightarrow\infty$, where
$\frac{\|\Delta_{k}\|}{N_{s(k),k}(\|\Delta_{k}\|)}$ is a upper bound of the
function $o_{s(k),k}(\cdot),$ obtained from the expansion of the function
$\tilde{\Phi}_{s,k}(\cdot)$ at the $k$-th step (10). It is clear that
$N_{s(k),k}(\|\Delta_{k}\|)\rightarrow\infty$ as $k\rightarrow\infty$.

The conditions 1 and 2 can be easy satisfied. At first the optimization
process goes on with constant $s$. As soon as the step size $\|\Delta_{k}\|$
becomes quite small, that means large enough $N_{s(k),k}(\|\Delta_{k}\|)$, we
increase $s$, decrease diameter $d(D_{s})$ and, consequently, increase
$L_{s(k)}$ so that to satisfy to the conditions of coherence 1 and 2. As we
shall see below, $q_{s(k)}$ is the coefficient of proportionality between the
steps $\|\Delta_{k+1}\|$ and $\|\Delta_{k}\|$. Therefore, we are able to
evaluate $q_{s(k)}$ by the coefficient of proportionality between
$\|\Delta_{k+1}\|$ and $\|\Delta_{k}\|$ and, therefore, to satisfy clause 2 of
the consistency conditions.

Superlinear optimization method for finding for a minimum point of an
arbitrary convex function $f(\cdot)$

Let a point $x_{k}$ already been found. Construct the pint $x_{k+1}$.

1\. Calculate the $k$-th step.

$\triangle_{k}=-(\nabla^{2}\tilde{\Phi}_{s,k}(x_{k}))^{-1}\nabla\tilde{\Phi}_{s,k}(x_{k}).$

2\. Find a non-negative integer $l_{k}$ for which

$\tilde{\Phi}_{s,k}(x_{k}+2^{-l_{k}}\triangle_{k})\leq\tilde{\Phi}_{s,k}(x_{k})-2^{-2l_{k}}\frac{\tilde{L}_{k}}{2}\|\triangle_{k}\parallel^{2}.$
(15)

3\. We put $x_{k+1}=x_{k}+2^{-l_{k}}\triangle_{k}$, $k=k+1$.

4\. Calculate for $k=k+1$

$\triangle_{k+1}=-(\nabla^{2}\tilde{\Phi}_{s,k+1}(x_{k+1}))^{-1}\nabla\tilde{\Phi}_{s,k+1}(x_{k+1}).$

5\. If

$L_{s}\|\Delta_{k+1}\|\leq\varepsilon_{k+1}$

for an arbitrarily chosen sequence
$\\{\varepsilon_{k}\\},\varepsilon_{k}\rightarrow+0$ then we increase $s$ such
that the inequality

$\|\Delta_{k+1}\|\leq q_{s,k}\|\Delta_{k}\|$

remained in force.

6\. Go to step 1 and continue until the step size becomes less than the
specified value.

Let us prove that the sequence $\\{x_{k}\\}$ converges to a minimum point of
the function $f(\cdot)$ with superlinear speed.

###### Theorem 3.2

The sequence $\\{x_{k}\\}$, constructed according to the algorithm 1-3,
converges to the unique stationary point $x_{*}$ of the function
$\Phi(\cdot)$. For large k the following estimate for the rate of convergence
of the method is correct

$\|x_{k}-x_{*}\|\leq\nu^{k}(\triangle_{k})\|x_{1}-x_{*}\|,$ (16)

where $\nu(\triangle_{k})\rightarrow_{k}0$ as
$\|\triangle_{k}\|\rightarrow_{k}0$.

Proof. As above, we are able to show that for sufficiently large k , the
process goes with a full step, i.e. $l_{k}=0$. From decomposition

$\nabla\tilde{\Phi}_{s,k}(x_{k}+\triangle_{k})=\nabla\tilde{\Phi}_{s,k}(x_{k})+\nabla^{2}\tilde{\Phi}_{s,k}(x_{k})\triangle_{k}+o_{s,k}(\|\triangle_{k}\|)$

for

$\triangle_{k}=-(\nabla^{2}\tilde{\Phi}_{s,k}(x_{k}))^{-1}\nabla\tilde{\Phi}_{s,k}(x_{k})$

we have

$\nabla\tilde{\Phi}_{s,k}(x_{k+1})=o_{s,k}(\|\triangle_{k}\|).$

It easy to check that

$\nabla\tilde{\Phi}_{s,k}(x_{k+1})-\nabla\Phi_{s}(x_{k+1})=\tilde{o}_{s,k}(\|\triangle_{k}\|).$

But it is obvious that
$\nabla\Phi_{s}(x_{k+1})=\nabla\tilde{\Phi}_{s,k+1}(x_{k+1})$. Therefore
$\nabla\tilde{\Phi}_{s,k+1}(x_{k+1})=\hat{o}_{s,k}(\|\triangle_{k}\|)$. Since
the function $\tilde{\Phi}_{s,k}(\cdot)$ has the continuous second derivative,
satisfying a Lipschitz condition, then
$o_{s,k}(\cdot),\tilde{o}_{s,k}(\cdot),\hat{o}_{s,k}(\cdot)$ are the uniformly
infinitesimal functions in $k$. From here

$\|\nabla\tilde{\Phi}_{s,k+1}(x_{k+1})\|=\|\hat{o}_{s,k}(\|\triangle_{k}\|)\|\leq\frac{\|\triangle_{k}\|}{N_{s,k}(\|\triangle_{k}\|)}.$

From the expression

$\triangle_{k+1}=-(\nabla^{2}\tilde{\Phi}_{s,k+1}(x_{k+1}))^{-1}\nabla\tilde{\Phi}_{s,k+1}(x_{k+1}).$

we have the evaluation

$\|\triangle_{k+1}\|\leq\frac{{\tilde{L}_{k}}^{-1}}{N_{s,k}(\|\triangle_{k}\|)}\|\triangle_{k}\|,$

where $N_{s,k}(\|\triangle_{k}\|)\rightarrow\infty$, as
$\|\triangle_{k}\|\rightarrow 0$. For large $k$ we achieve that the inequality

$0<\frac{{\tilde{L}_{k}}^{-1}}{N_{s,k}(\|\triangle_{k}\|)}<1.$

was correct (the condition of coherence). Therefore, the sequence
$\\{x_{k}\\}$ converges to a single point $x_{*}$ and

$\|x_{k+1}-x_{*}\|\leq\sum_{i=k+1}^{\infty}\|\triangle_{i}\|=\frac{({\tilde{L}_{k}}^{-1}/N(\|\triangle_{k}\|))\|\triangle_{k}\|}{1-{\tilde{L}_{k}}^{-1}/N(\|\triangle_{k}\|)}.$

As soon as

$\|\triangle_{k}\|\leq(\frac{{\tilde{L}_{k}}^{-1}}{N_{s,k}(\|\triangle_{k}\|)})^{k}\|\triangle_{1}\|,$

then

$\|x_{k+1}-x_{*}\|\leq\frac{({\tilde{L}_{k}}^{-1}/N_{s,k}(\|\triangle_{k}\|))^{k+1}\|\triangle_{1}\|}{1-{\tilde{L}_{k}}^{-1}/N_{s,k}(\|\triangle_{k}\|)}.$

Thus, inequality (16) is proved. $\Box$

###### Remark 3.1

. Inequality (16) proves the superlinear convergence rate of the optimization
method. Indeed, the coefficient between $\|x_{k+1}-x_{*}\|$ and
$\|x_{1}-x_{*}\|$ is equal to $q_{k}^{k}$, where $q_{k}\rightarrow 0,$ as
$k\rightarrow\infty$.

##  4 Conclusion

The methods for finding a stationary point of a Lipschitz function and a
minimum point of an arbitrary convex function are proposed in this paper. To
achieve a high rate of convergence, it is necessary to make consistent
reduction of diameter $d(D)$ of the set $D$, which the integral averaging is
doing on, with decreasing the length of step of optimization process. Rules
for consistent reduction of steps and diameters of the sets $D_{s}$ are given.

## References

  * [1] Rademacher H. Uber partielle und totale Differenzierbarkeit I. Math. Ann. 89 (1919), 340-359.
  * [2] Pshenichny B.N., Danilin Yu.M. Numerical methods in extream problems. M.:Nauka, 1975. 319 P.
  * [3] Pshenichny B.N. Convex analysis and extream problems. M.: Nauka, 1980. 320 P.
  * [4] Rocafellar, R. T. Convex analysis, New York: Willey, 1972.
  * [5] Demyanov V.F., Rubinov A.M. The basis of nonsmooth analysis The quasidifferential calculation. M.: Nauka, 1990. 432 P.
  * [6] Prudnikov I.M. $C^{2}(D)$ integral approximtion of nonsmooth functions preserving $\varepsilon(D)$ extreme ponts // Papers of Institute of mathematics and mechnics of Ural Branch RAN. 2010. P. 159 - 169.
  * [7] Prudnikov I.M. Integral approximation of Lipschitz functions // Vestnik of St. Petersburg University. ser. 10. 2010. Issue 2. P. 70-83
  * [8] Klark F. Optimization and nonsmooth analysis. M.: Nauka, 1988. 280 P.


# Meta Episodic learning with Dynamic Task Sampling for CLIP-based Point Cloud
Classification

Shuvozit Ghose  Department of Computer Science
University of Manitoba
Winnipeg, Canada
<EMAIL_ADDRESS>Yang Wang  Department of Computer Science and
Software Engineering
Concordia University
Montreal, Canada
<EMAIL_ADDRESS>
###### Abstract

Point cloud classification refers to the process of assigning semantic labels
or categories to individual points within a point cloud data structure. Recent
works have explored the extension of pre-trained CLIP to 3D recognition. In
this direction, CLIP-based point cloud models like PointCLIP, CLIP2Point have
become state-of-the-art methods in the few-shot setup. Although these methods
show promising performance for some classes like airplanes, desks, guitars,
etc, the performance for some classes like the cup, flower pot, sink,
nightstand, etc is still far from satisfactory. This is due to the fact that
the adapter of CLIP-based models is trained using randomly sampled N-way
K-shot data in the standard supervised learning setup. In this paper, we
propose a novel meta-episodic learning framework for CLIP-based point cloud
classification, addressing the challenges of limited training examples and
sampling unknown classes. Additionally, we introduce dynamic task sampling
within the episode based on performance memory. This sampling strategy
effectively addresses the challenge of sampling unknown classes, ensuring that
the model learns from a diverse range of classes and promotes the exploration
of underrepresented categories. By dynamically updating the performance
memory, we adaptively prioritize the sampling of classes based on their
performance, enhancing the model’s ability to handle challenging and real-
world scenarios. Experiments show an average performance gain of 3-6% on
ModelNet40 and ScanobjectNN datasets in a few-shot setup.

###### Index Terms:

Point cloud classification, Few shot learning, Meta Learning, Contrastive
Language-Image Pretraining

##  I Introduction

Figure 1: (a) cup (side view) (b) flower pot (side view) (c) sink (top view).
We visualize the 3d object of the corresponding point cloud for better visual
understanding.

Point cloud classification refers to the process of assigning semantic labels
or categories to individual points within a point cloud data structure. A
point cloud is a collection of 3D points that represent the surface of an
object or a scene, typically acquired through techniques like LiDAR or
structured light scanning and the objective of point cloud classification is
to extract meaningful information from 3D point cloud data. Point cloud
classification has numerous real-world applications, including stereo
reconstruction, indoor navigation, autonomous driving, augmented reality, and
robotics perception. Compared to 2D image classification, point cloud
classification presents additional challenges. While 2D images consist of
dense and regular pixel arrays, 3D point clouds are sparse and unordered,
lacking the rich texture and information found in 2D images. While early deep
learning point cloud classification methods focused on designing advanced
architectures for point cloud classification, such as PointNet[1], PointNet++
[2], RSCNN [3], DGCNN [4], CurveNet [5], the introduction of Contrastive
Language-Image Pre-training (CLIP) has opened up a new direction in computer
vision research. CLIP [6], which is trained using unlabeled image-caption
supervision, can be adapted to specific downstream tasks with minimal
additional training. Inspired by CLIP’s [6] success, recent works have
explored the extension of pre-trained CLIP to 3D recognition. In this
direction, CLIP-based point cloud models like PointCLIP [7], CLIP2Point [8]
etc have become state-of-the-art methods in the few-shot setup. In general,
the pipeline for 3D recognition using pre-trained CLIP involves projecting the
point cloud as depth maps, processing the depth maps using the pre-trained
CLIP visual encoder, and adding a small adapter network that is fine-tuned for
the specific task.

Although these methods show promising performance for some classes like
airplanes, desks, guitars, etc, the performance for some classes like the cup,
flower pot, sink, nightstand, etc is still far from satisfactory as depicted
by Fig LABEL:fig:_zero (b). This is due to the fact that the adapter of CLIP-
based models is trained using randomly sampled N-way K-shot data in the
standard supervised learning setup. But, for some classes point cloud
instances differ drastically in terms of shape and structure as depicted in
Fig. 1. In the CLIP-based point cloud classification few-shot setup, the
adapter tries to learn these various shape and structure variations through
only k-shot data but often falls short, thus overfitting on the training set
and generalizing poorly on evaluation because it is not possible for a single
adapter model to perform well on every class-specific point cloud instance.
However, another naive approach can be fine-tuning the adapter to the unseen
class-specific point cloud instances. But it requires thousands of
backpropagation gradients updates, thus requiring considerable time and
computation to get the desired result. Moreover, although fine-tuning can
solve the unseen class-specific point cloud adaptation problem to some extent,
it is not possible to fine-tune the adapter with every unseen class-specific
point cloud instance.

To solve this issue, one potential solution can be the introduction of a meta-
learning formulation for CLIP-based point cloud classification. Unlike
supervised learning, meta-learning learns novel tasks with only a few
examples, in a similar way to human beings. Just like humans learn by seeing
some examples and then using domain-specific knowledge in practical scenarios,
meta-learning adapts to a specific task by observing a few examples. The
motivation of meta-learning is to absorb information from one task and
generalize that information to unseen tasks proficiently by quickly adapting
to the new tasks from a small set of training examples given during the
testing phase. Especially, Model Agnostic Meta-learning (MAML) [9] has shown
great impact. MAML [9] tries to find a good initialization across shared
knowledge, so that small updates with task-specific data can adapt the model
to that task, thus boosting performance.

However, the standard MAML [9] has several problems in this context. Firstly,
the standard meta-learning paradigm is used to learn good initialization for
the base model which has increased model capacity, enhanced feature extractor,
and a large receptive field. In the case of CLIP based model, the adapter is a
small model with a smaller receptive field. In the standard MAML [9], the base
model learns the generalized knowledge from the randomly sampled task, whereas
for CLIP-based models, some visual knowledge has already been captured by the
CLIP Visual encoder as depicted by the Fig. 3 (a). Finally and most
importantly, the standard meta-learning gives equal importance to all the
classes and samples the N-way K-shot data accordingly. However, in the CLIP-
based models, some visual information has already been learned by the CLIP
visual encoder (e.g. airplanes, desks, guitars, etc), and the main target of
our meta-training is to encode unknown generalized class information (e.g.
cup, flower pot, sink, nightstand, etc) to the adapter. Thus, a natural
question arises, how can we encode unknown generalized class information to
the adapter so that it can achieve satisfactory results?

For this purpose, we propose a novel meta-episodic learning framework with
dynamic task sampling for CLIP-based point cloud classification. While meta-
episodic learning combines these two concepts by employing episodic training
within a meta-learning framework, dynamic task sampling ensures the sampling
of unknown classes in the related task within an episodic. For sampling
dynamic tasks within an episode, we propose a novel performance memory. The
performance memory keeps track of the class-wise performance within an episode
and samples the task according. In our approach, the CLIP-based model is
trained on episodes of related tasks, where each episode contains a set of
related examples mostly sampled from unknown classes. By learning from these
episodes, the adapter acquires a generalization ability that enables it to
quickly adapt and learn from new tasks.

In summary, the contribution of this paper is as follows: 1) we, to the best
of our knowledge for the first time, propose a novel meta-episodic learning
framework for CLIP-based point cloud classification, addressing the challenges
of limited training examples and sampling unknown classes. 2) we propose a
novel dynamic task sampling technique within the episode based on performance
memory. This sampling strategy effectively addresses the challenge of sampling
unknown classes, ensuring that the model learns from a diverse range of
classes and promotes the exploration of underrepresented categories. By
dynamically updating the performance memory, we adaptively prioritize the
sampling of classes based on their performance, enhancing the model’s ability
to handle challenging and real-world scenarios. 3) We confirm that our
framework consistently improves upon even the most recent state-of-the-art
CLIP-based point cloud models.

##  II Related Works

Deep Learning in Point Clouds:  Deep learning has made significant
advancements in point cloud classification and understanding. Following the
success of CLIP, several works have emerged that aim to extend the pre-
training framework of Contrastive Language-Image Pre-Training (CLIP) to point
cloud understanding tasks. For example, Zhang et. al. [7] presented PointCLIP
to extend CLIP for handling 3D point cloud data along with an interview
adapter. Building upon PointCLIP, Zhu et al. [10] introduced PointCLIP V2,
which focuses on efficient cross-modal adaptation. They proposed LLM-assisted
3D prompting, which leveraged a language and label mapping (LLM) module to
assist in generating informative and compact prompts for point cloud data.
Additionally, they introduced realistic shape projection to improve the cross-
modal adaptation process. Huang et al. [8] presented CLIP2Point, which
introduced a novel Dual-Path adapter and a contrastive learning framework for
transferring CLIP knowledge to the 3D domain. Yan et al. proposed PointCMT
[11], a point cloud cross-modal training framework that utilized the
advantages of color-aware 2D images and textures to acquire more
discriminative point cloud representations. They formulated point cloud
analysis as a knowledge distillation problem, transferring knowledge from 2D
images to point clouds.

Meta Learning:  Meta-learning [9], also known as learning to learn, aim to
acquire prior knowledge or meta-knowledge from the distribution of tasks and
use this knowledge to facilitate learning on new, unseen tasks. In this
direction, MAML [9] aims to learn a good initialization of model parameters
that can be easily adapted to new tasks with a few gradient steps. The key
idea behind MAML [9] is to optimize the model’s parameters in a way that they
can be fine-tuned quickly to minimize the loss of new tasks. MAML++ [12] is an
extension of the original MAML [9] algorithm that introduces several
improvements to enhance its performance. One key enhancement is the use of a
second-order approximation for computing gradients, which takes into account
the curvature of the loss landscape. By considering second-order information,
MAML++ [12] can capture more nuanced relationships between model parameters
and achieve better adaptation to new tasks. MetaSGD [13] is another
optimization-based meta-learning algorithm that addresses the challenges of
learning an effective optimization algorithm itself. The main idea behind
MetaSGD [13] is to learn a meta-optimizer that dynamically adjusts the
learning rate or optimization strategy for different tasks. Instead of
learning model parameters directly, MetaSGD [13] aims to learn the update rule
or optimization algorithm that adapts the model’s parameters.

Figure 2: The adapter learns following a bi-level optimization process. While
the adapter learns to recognize and discriminate the features of the inner
loop update, the outer loop extracts meta-features of the point clouds that
generalize across tasks. Additionally, we introduce dynamic task sampling
within the episode based on performance memory to ensure underrepresented
class sampling.

Sampling in Fewshot Learning:  Sampling plays a crucial role in few-shot
learning by shaping the training and evaluation processes, enabling effective
adaptation and generalization from limited labeled examples. Several works
have been proposed in the last few years in this direction. For example,
Pezeshkpour et. al. [14] investigated the effectiveness of active instance
selection in the context of few-shot learning and proposed a framework where
instances were selected based on their informativeness, relevance, and
diversity. Arnold et.al. [15] highlighted the importance of considering
episode difficulty and proposed a uniform sampling strategy to address this
factor in few-shot learning. Le et. al. [16] introduced a method called Poodle
that aimed to enhance few-shot learning performance by addressing the
challenge of out-of-distribution samples. Xu et. al. [17] proposed a method
for generating representative samples to improve the few-shot classification.
Xu et. al. [18] addressed the issue of sample selection bias in few-shot
learning and proposed a method to alleviate this bias by removing the
projection to the centroid. Roy et. al. [19] introduced a method called FeLMi
that improved few-shot learning by incorporating a technique called hard
mixup. The hard mixup technique involved selecting difficult samples from the
support set and blending them with other samples from different classes.

##  III Methodology

In this section, we first briefly describe baseline CLIP-based point cloud
models like PointCLIP [7], CLIP2Point [8] for point cloud classification (Sec.
III-A). Then we introduce our meta-episodic learning framework for point cloud
classification (Sec.III-B). Finally, we describe our proposed dynamic task
sampling technique based on performance memory for class instance adaptive
point cloud classification (Sec. III-C). The overall overview of our method is
depicted in Fig. 2.

Figure 3: (a) Zero-shot result of PointCLIP [7]. We can observe that CLIP’s
Visual encoder has already captured certain classes such as airplanes, desks,
guitars, etc. (b) Few-shot result of PointCLIP [7]. Some classes like the cup,
flower pot, sink, nightstand, etc., exhibit lower performance in the few-shot
setup.

###  III-A Baseline CLIP-based point cloud models

The CLIP-based point cloud models are the state-of-the-art point cloud
classification methods in the few-shot setup. In this paper, we select two
CLIP-based point cloud methods, PointCLIP [10] and CLIP2Point [8], to use as
our baseline CLIP-based point cloud models.

For completeness, we briefly summarize the outline of the CLIP-based point
cloud models. In general, they consist of three components: (a) a pre-trained
CLIP visual Encoder, $F_{V}$ (b) a pre-trained CLIP textual Encoder $F_{T}$
(c) a small trainable network called an adapter $F_{\theta}$. For $N$ class
classification, CLIP-based models use a pre-defined template: “point cloud
depth map of a [CLASS]” and the textual encoder outputs $W_{t}\in R^{N\times
C}$, where $C$ is the channel of the text embedding. To feed the Point cloud
to the CLIP’s visual encoder, point clouds are first projected into
$\\{f_{1},f_{2},\dots,f_{m}\\}$ depth maps where $m$ denotes the number of
views and $f_{i}\in W^{1\times C}$ denotes each view of the point cloud. Given
the input $\\{f_{1},f_{2},\dots,f_{m}\\}$, the CLIP’s visual encoder generates
visual feature $\\{F_{1}^{I},F_{2}^{I},\dots,F_{m}^{I}\\}$, where
$F_{i}^{I}\in R^{1\times C}$, $C$ being the channel information of the
embedding. In the zero-shot setup, there is no training stage and no adapter
is required. Each viewpoint generates a prediction by calculating the cosine
similarity between the visual feature $F_{i}^{I}$ and the textual feature
$F^{T}$. The final prediction is a weighted sum of all viewpoint-wise
predictions.

For few-shot point cloud classification, the adapter $F_{\theta}$ is trained
using randomly sampled N-way K-shot data from the training dataset in the
standard supervised learning setup. For this purpose, PointCLIP [7] proposes
an interview adapter that extracts a global visual representation by combining
multi-view features generated by the CLIP visual encoder. The global
representation obtained from the inter-view adapter serves as a higher-level
understanding of the visual input and encapsulates important information that
is shared across different views. During inference, CLIP’s visual feature
$\\{F_{1}^{I},F_{2}^{I},\dots,F_{m}^{I}\\}$ is passed through the trained
adapter network $F_{\theta}$ and the final prediction is calculated as cosine
similarity between the output adapter feature and the textual feature.

On the other hand, CLIP2Point [8] proposes a Dual-Path Adapter (DPA) that
combines the benefits of pre-training with instance-level depth maps and
category-level discrimination from CLIP pre-training knowledge. The DPA module
consists of a dual-path structure, utilizing two encoders: the pre-trained
depth encoder and the CLIP visual encoder. The combination of the two encoders
allows for a comprehensive representation of the visual data, incorporating
both instance-level depth information and category-level discrimination from
CLIP pre-training. By combining the outputs of the two encoders, the DPA
module generates the final logits. We refer the reader to [10, 8] for further
architectural details. In this paper, the adapter indicates the interview
adapter for PointCLIP and the dual-path adapter for CLIP2Point and denotes the
complete set of parameters as $\theta$.

###  III-B Meta Episodic Learning for Point Cloud Classification

Traditionally, the CLIP-based point cloud model inputs a point cloud $\rho$
and generates its corresponding class label $Y$. Conventional CLIP-based point
cloud models learn from $N$ way $K$ shot data, where N denotes the total
number of classes in the dataset and K notes the total number of instances per
class. Due to the data instance-specific training, it ignores the class-
specific shape and structure variation distribution. Henceforth, the
performance deteriorates on some point cloud classes because of poor
generalization on diverse point cloud class instances.

In contrast, we take a meta-episodic learning approach for the few-shot
learning of the adapter along with dynamic tasks to address the challenge of
CLIP-based point cloud classification. It combines the concepts of meta-
learning and episodic training to enable efficient adaptation to new tasks
with limited training examples. The goal is to encode unknown generalized
class information into the adapter, allowing it to achieve satisfactory
results. Let’s consider $W_{tr}$ and $W_{test}$ denote the disjoint training
and testing point cloud set respectively, i.e., $W_{tr}\cap W_{test}=\phi$.
The training and testing set are denoted as
$\mathcal{C}^{tr}=\\{\mathcal{C}^{tr}_{1},\mathcal{C}^{tr}_{2},\dots,\mathcal{C}^{tr}_{|W_{tr}|}\\}$
and
$\mathcal{C}^{test}=\\{\mathcal{C}^{test}_{1},\mathcal{C}^{test}_{2},\dots,\mathcal{C}^{test}_{|W_{test}|}\\}$.
Each $i$-th point cloud class in the training set has its own total of $M$
labeled point cloud instances as
$\mathcal{C}_{i}=\\{(\rho_{1},Y),(\rho_{2},Y),\cdots,(\rho_{M},Y)\\}$. In the
meta-episodic training, let each episode consists of $S$ tasks, where each
$\mathcal{T}$ consists of a support set $\mathrm{C}^{S}$ and a query set
$\mathrm{C}^{Q}$. Intuitively, our approach tries to find a good
initialization of parameters $\theta$, representing the prior or generalized
knowledge of point clouds, so that a few updates of $\theta$ using
$\mathrm{C}^{S}$ can make large improvements by reducing the error measures
and boosting the performance in $\mathrm{C}^{Q}$. To learn this optimal
initialisation parameter $\theta$, we first adapt (task-specific) $f_{\theta}$
using $\mathrm{C}^{S}$ by fine-tuning:

$\theta^{*}=\theta-\alpha\nabla_{\theta}\mathcal{L}^{inner}(\theta;\mathrm{C}^{S})$
(1)

Where $\mathcal{L}^{inner}$ denotes loss in the inner loop and $\alpha$
denotes inner loop learning rate. In the inner loop update, the adapter learns
to recognize and discriminate the patterns, features, and characteristics
relevant to the point cloud classification task. Evaluation of the adapted
model is performed on unseen examples sampled from the same task
$\mathrm{C}^{Q}$, to measure the generalization of $f_{\theta^{*}}$. This acts
as feedback for MAML [9] to adjust its initialization parameters $\theta$ to
achieve better generalization on any $\mathcal{T}$ (across-task):

$(\theta,\alpha)\leftarrow(\theta,\alpha)-\beta\nabla_{(\theta,\alpha)}\sum_{\mathcal{T}}\mathcal{L}^{outer}(\theta^{*};\mathrm{C}^{Q})$
(2)

Where $\mathcal{L}^{outer}$ denotes loss in the outer loop and $\beta$ denotes
outer loop learning rate. The primary objective of the outer loop is to
extract meta-knowledge or meta-features that generalize across tasks. However,
the standard meta-learning has several limitations for the CLIP-based Point
Cloud classification. To address these challenges, we propose novel dynamic
sampling within the episode based on performance memory.

###  III-C Dynamic Task Sampling

The standard Model Agnostic Meta-learning (MAML) [9] is not well-suited for
CLIP-based models due to several reasons. Firstly, the standard meta-learning
paradigm is used to learn good initialization for the base model which has
increased model capacity, enhanced feature extractor, and a large receptive
field. In the case of CLIP based model, the adapter is a small model with a
smaller receptive field. In the standard MAML [9], the base model learns the
generalized knowledge from the randomly sampled task, whereas for CLIP-based
models, some visual knowledge has already been captured by the CLIP Visual
encoder as depicted by the Fig. 3 (a). Finally and most importantly, the
standard meta-learning gives equal importance to all the classes and samples
the N-way K-shot data accordingly. However, in the CLIP-based models, some
visual information has already been learned by the CLIP visual encoder (e.g.
airplanes, desks, guitars, etc), and the main target of our meta-training is
to encode unknown generalized class information (e.g. cup, flower pot, sink,
nightstand, etc) to the adapter.

Algorithm 1 Training of our approach

1:Input: Training dataset
$\mathcal{C}^{tr}=\\{\mathcal{C}^{tr}_{1},\mathcal{C}^{tr}_{2},\dots,\mathcal{C}^{tr}_{|W_{tr}|}\\}$;
$\beta$ as learning rate.

2:Requires: Pre-trained CLIP visual encoder $F_{V}$, Pre-trained CLIP textual
encoder $F_{T}$

3:Initialise: Initialise Adapter $\theta$, inner learning rate $\alpha$

4:Output: Optimised meta-parameters $\\{\theta,\alpha\\}$

5:for each episode do

6: Initialize Performance Memory $P$ with keys as the class labels and values
as 0

7: for task = $1,2,\dots,S$ do

8: Sort $P$ based on values and decide classes to sample

9: Sample task $\mathcal{T}=\\{\mathrm{C}^{S},\mathrm{C}^{Q}\\}$ from the
decided classes

10: for each task $\mathcal{T}$ do

11: Evaluate inner objective: $\mathcal{L}^{inner}(\theta;\mathrm{C}^{S})$

12: Adapt:
$\theta^{*}=\theta-\alpha\nabla_{\theta}\mathcal{L}^{inner}(\theta;\mathrm{C}^{S})$

13: Compute outer objective: $\mathcal{L}^{outer}(\theta^{*};\mathrm{C}^{Q})$

14: end for

15: Update meta-parameters:
$(\theta,\alpha)\leftarrow(\theta,\alpha)-\beta\nabla_{(\theta,\alpha)}\sum_{\mathcal{T}}\mathcal{L}^{outer}(\theta^{*};\mathrm{C}^{Q})$

16: Update the class-wise accuracy in $P$

17: end for

18:end for

To address these challenges, we propose novel dynamic sampling within the
episode based on performance memory. Dynamic task sampling is a crucial
component of the proposed meta-episodic learning framework for CLIP-based
point cloud classification and performance memory plays a critical role in
guiding the task sampling process. It aims to address the challenge of
effectively sampling unknown classes within episodes, allowing the model to
learn from diverse and relevant data. Let $P$ denote performance memory and
$P[i]$ denote $i-th$ class in the performance memory. At the onset of each
episode, we initialize all the $P[i]$ equal to 0. For task sampling within an
episode, we employ a specific procedure. Initially, we sort the performance
memory in ascending order based on the recorded values. This sorting enables
us to prioritize the classes based on their performance. Consequently, we
select the first N classes from the performance memory, facilitating an N-way
task sampling. Throughout the episode, the performance memory is updated
dynamically as follows:

$P[i]=\frac{P[i]+A_{i}}{2}$ (3)

Where $A_{i}$ denotes $i-th$ class accuracy in the query set $\mathrm{C}^{Q}$
of a task. This updating process allows the performance memory to reflect the
evolving performance of each class within the episode. By incorporating
dynamic sampling within the episode based on performance memory, our proposed
approach ensures that the model is exposed to a diverse range of classes
during training. It prioritizes the sampling of classes that have performed
relatively poorly, promoting the model’s ability to learn from challenging and
underrepresented classes.

Algorithm 2 Inference of our model

1:Input: Testing dataset
$\mathcal{C}^{test}=\\{\mathcal{C}^{test}_{1},\mathcal{C}^{test}_{2},\dots,\mathcal{C}^{test}_{|W_{test}|}\\}$;
number of gradient updates $n$.

2:Requires: Pre-trained CLIP visual encoder $F_{V}$, Pre-trained CLIP textual
encoder $F_{T}$, Optimised meta-parameters $\\{\theta,\alpha\\}$

3:Sample task $\mathcal{T}=\\{\mathrm{C}^{S},\mathrm{C}^{Q}\\}$ from
$\mathcal{C}^{test}$

4:for $n$ steps do

5: Evaluate inner objective: $\mathcal{L}^{inner}(\theta;\mathrm{C}^{S})$

6: Adapt:
$\theta_{c}=\theta-\alpha\nabla_{\theta}\mathcal{L}^{inner}(\theta;\mathrm{C}^{S})$

7:end for

8:Return class instance specialised Adapter params. $\mathbf{\theta_{c}}$.

In summary, our meta-episodic learning framework leverages dynamic sampling
within the episode, guided by the performance memory. This approach
effectively addresses the challenge of sampling unknown classes, enabling the
model to learn from diverse and relevant data. The updating of the performance
memory ensures that the model adapts to the evolving performance of different
classes, enhancing its ability to handle real-world scenarios and achieve
improved performance in CLIP-based point cloud classification tasks. The
training and inference process of our approach is summarised in Algorithm 1
and 2, respectively.

##  IV Experiments

Datasets: We evaluate our proposed approach on two widely used benchmark
datasets ModelNet40 [20] and ScanObjectNN [21]. ModelNet40 is a synthetic
indoor 3D dataset that consists of 40 classes of point cloud objects. It has a
training set of 9,843 and a testing set of 2,468 point clouds respectively. As
the original ModelNet40 is not aligned in orientation, in our approach we use
the aligned version of ModelNet 40 [22]. ScanObjectNN is a real-world point
cloud dataset that has a training set of 2,321 and a testing set of 581
samples from 15 point cloud classes. Following PointCLIP [7] and CLIP2Point
[8], we train our approach on the ModelNet40 training set and test on
ModelNet40 and ScanObjectNN testing set.

Implementation Details: We implemented our framework in PyTorch [23] and
conducted experiments on a 12 GB Nvidia Titan X GPU. We train the adapter from
scratch with 100 epochs, and each epoch contains 50 meta-training episodes
according to algorithm 1. Each episode consists of 20 tasks and each task
consists of N classes with K-labeled support examples and Q query examples for
each class, which is denoted as the N-way K-shot Q-query setting. In our
approach, we use a 3-way 5-shot 5-query for our tasks. Once the meta-training
is ended, we test the network according to algorithm 2. For meta-training and
meta-testing, we used a one-step gradient update. We use ADAM as a meta-
optimizer with outer-loop learning rate $\beta$ as 0.0001, while the inner-
loop learning $\alpha$ is meta-learned during training. We use accuracy as our
evaluation metric.

###  IV-A Competitors

To the best of our knowledge, no prior research has specifically addressed
task-specific few-shot learning for CLIP-based Point cloud models. However, in
order to validate our approach, we have designed four strong baselines from
the perspective of optimization-based meta-learning. These baselines are as
follows: (i) MAML [9]:  In this baseline, we train CLIP-based models using
standard random task sampling, without employing episodes. (ii) Reptile [24]:
This baseline involves directly performing inner loop updates using a randomly
sampled support set of tasks. The models converge to initialization by
accumulating changes made during these updates across multiple tasks. (iii)
MetaSGD [13]:  Here, CLIP-based models are trained within a meta-episodic
learning framework along with random task sampling, where each parameter has
its own learning rate. (iv) Ours:  We train CLIP-based models using a MAML
approach within a meta-episodic learning framework along with dynamic task
sampling.

TABLE I: Comparison (%) of baseline and our approach on PointCLIP and CLIP2Point using the prompt ”point cloud of a big [CLASS]”. Methods | ModelNet40 | ScanobjectNN
---|---|---
| Baseline | Ours | Baseline | Ours
PointCLIP | 83.80 | 86.93 | 54.37 | 58.72
CLIP2Point | 85.10 | 88.64 | 57.49 | 63.65

###  IV-B Result Analysis and Discussion

Table I compares the baseline results with our proposed approach on PointCLIP
[7] and CLIP2Point [8] models using the prompt ”point cloud of a big [CLASS].”
For ModelNet40, our approach has outperformed the baseline model by 3.13% and
3.54% on PointCLIP [7] and CLIP2Point [8] respectively. Similarly, on the
ScanobjectNN dataset, the performance improves by 4.35% and 6.16% on PointCLIP
[7] and CLIP2Point [8] respectively. This result indicates the robustness of
our meta-episodic approach compared to the standard few-shot approach used by
CLIP-based point cloud models.

TABLE II: Performance (%) analysis with different Baselines on ModelNet40 and ScanobjectNN using prompt “point cloud of a big [CLASS]”. Methods | ModelNet40 | ScanobjectNN
---|---|---
PointCLIP Baseline | 83.80 | 54.37
PointCLIP + MAML | 84.78 | 55.69
PointCLIP + Reptile | 84.10 | 55.04
PointCLIP + MetaSGD | 84.92 | 55.85
PointCLIP + Ours | 86.93 | 58.72
CLIP2Point Baseline | 85.10 | 57.49
CLIP2Point + MAML | 86.34 | 58.56
CLIP2Point + Reptile | 85.83 | 58.24
CLIP2Point + MetaSGD | 86.36 | 58.68
CLIP2Point + Ours | 88.64 | 63.65

Table II presents a performance analysis with different Competitors on
ModelNet40 and ScanobjectNN datasets. The Competitors include PointCLIP [7]
and CLIP2Point [8] with various meta-learning algorithms such as MAML,
Reptile, and MetaSGD, as well as our proposed approach. For PointCLIP [7], our
proposed approach outperforms MAML by 2.15% and 3.03% on the ModelNet40 and
ScanobjectNN datasets, respectively. Similarly, our approach surpasses Reptile
by 2.83% and 3.68%, and MetaSGD by 2.01% and 2.87% on the same datasets. For
CLIP2Point [8], our approach demonstrates superior performance compared to the
baselines. It outperforms MAML by 2.3% and 5.09% on the ModelNet40 and
ScanobjectNN datasets, respectively. Moreover, our model surpasses Reptile by
2.81% and 5.41%, and MetaSGD by 2.28% and 4.97% on the respective datasets.
These results highlight the effectiveness of our proposed approach in
achieving better performance compared to the other competitors in the task-
specific few-shot learning setting for CLIP-based point cloud models.

TABLE III: Comparison (%) of Baseline and our approach on PointCLIP for different prompt designs on ModelNet40.  Prompts | PointCLIP | PointCLIP
---|---|---
| Baseline | \+ Ours
“a photo of a [CLASS].” | 81.78 | 84.55
“a point cloud photo of a [CLASS].” | 82.02 | 86.12
“point cloud of a [CLASS].” | 82.10 | 86.82
“point cloud of a big [CLASS].” | 83.80 | 86.93
“point cloud depth map of a [CLASS].” | 81.58 | 85.97

Table III focuses on different prompt designs for the PointCLIP [7] model on
the ModelNet40 dataset. It compares the baseline accuracy with our approach’s
accuracy for various prompt designs. Our approach consistently outperforms the
baseline in all prompt designs.

###  IV-C Ablation Study

The effect of Dynamic task sampling:  To observe the effect of dynamic task
sampling, we conduct an experiment with dynamic task sampling and random task
sampling using the prompt “point cloud of a big [CLASS]” on ModelNet40 as
shown in Tab. IV.

TABLE IV: Effect of dynamic task sampling on ModelNet40 using prompt “point cloud of a big [CLASS]”.  | PointCLIP | CLIP2Point
---|---|---
Random task sampling | 84.78 | 86.34
Dynamic task sampling | 86.93 | 88.64

From the table, it is evident that incorporating dynamic task sampling on the
few-shot pipeline improves accuracy by 2.15 %. and 2.3 % for PointCLIP [10]
and CLIP2Point [8] respectively. This is because dynamic task sampling
prioritizes the sampling of classes that have performed relatively poorly,
promoting the model’s ability to learn from challenging and underrepresented
classes.

Number of Adaptation Steps:  In Fig. 4, we experiment with varying the number
of adaptation steps during the inference process. we observe that using just a
single gradient step update, which is the most common approach in our
experiments, yields the highest performance gain. The reason behind this
result could be that the inner loop, which handles the adaptation process,
focuses too much on capturing unnecessary point cloud style details, causing
it to forget the generic prior knowledge learned by the model. As a result,
performing additional updates in the inner loop might lead to diminishing
results, as the model becomes overfit to the specific style of the training
examples and loses its ability to generalize well to new tasks.

Figure 4: Accuracy of competitors with varying adaptation steps on ModelNet40
using prompt “point cloud of a big [CLASS]”.

##  V Conclusion

In conclusion, we have proposed a novel meta-episodic learning framework for
CLIP-based point cloud classification, addressing the challenges of limited
training examples and sampling unknown classes. Our framework combines meta-
learning and episodic training, enabling the model to quickly adapt and
generalize to new tasks. Additionally, we have introduced dynamic task
sampling within the episode based on performance memory. This sampling
strategy effectively addresses the challenge of sampling unknown classes,
ensuring that the model learns from a diverse range of classes and promotes
the exploration of underrepresented categories. By dynamically updating the
performance memory, we adaptively prioritize the sampling of classes based on
their performance, enhancing the model’s ability to handle challenging and
real-world scenarios.

## References

  * [1] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in _CVPR_ , 2017.
  * [2] C. R. Qi, L. Yi, H. Su, and L. J. Guibas, “Pointnet++: Deep hierarchical feature learning on point sets in a metric space,” _NeurIPS_ , 2017.
  * [3] Y. Liu, B. Fan, S. Xiang, and C. Pan, “Relation-shape convolutional neural network for point cloud analysis,” in _CVPR_ , 2019.
  * [4] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon, “Dynamic graph cnn for learning on point clouds,” _TOG_ , 2019.
  * [5] T. Xiang, C. Zhang, Y. Song, J. Yu, and W. Cai, “Walk in the cloud: Learning curves for point clouds shape analysis,” in _CVPR_ , 2021.
  * [6] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark _et al._ , “Learning transferable visual models from natural language supervision,” in _ICML_ , 2021.
  * [7] R. Zhang, Z. Guo, W. Zhang, K. Li, X. Miao, B. Cui, Y. Qiao, P. Gao, and H. Li, “Pointclip: Point cloud understanding by clip,” in _CVPR_ , 2022.
  * [8] T. Huang, B. Dong, Y. Yang, X. Huang, R. W. Lau, W. Ouyang, and W. Zuo, “Clip2point: Transfer clip to point cloud classification with image-depth pre-training,” _arXiv_ , 2022.
  * [9] C. Finn, P. Abbeel, and S. Levine, “Model-agnostic meta-learning for fast adaptation of deep networks,” _ICML_ , 2017.
  * [10] X. Zhu, R. Zhang, B. He, Z. Zeng, S. Zhang, and P. Gao, “Pointclip v2: Adapting clip for powerful 3d open-world learning,” _arXiv_ , 2022.
  * [11] X. Yan, H. Zhan, C. Zheng, J. Gao, R. Zhang, S. Cui, and Z. Li, “Let images give you more: Point cloud cross-modal training for shape analysis,” _arXiv_ , 2022.
  * [12] A. Antoniou, H. Edwards, and A. Storkey, “How to train your maml,” _ICLR_ , 2019.
  * [13] Z. Li, F. Zhou, F. Chen, and H. Li, “Meta-sgd: Learning to learn quickly for few-shot learning,” _arXiv_ , 2017.
  * [14] P. Pezeshkpour, Z. Zhao, and S. Singh, “On the utility of active instance selection for few-shot learning,” _NeurIPS HAMLETS_ , 2020.
  * [15] S. Arnold, G. Dhillon, A. Ravichandran, and S. Soatto, “Uniform sampling over episode difficulty,” _NeurIPS_ , 2021.
  * [16] D. Le, K. D. Nguyen, K. Nguyen, Q.-H. Tran, R. Nguyen, and B.-S. Hua, “Poodle: Improving few-shot learning via penalizing out-of-distribution samples,” _NeurIPS_ , 2021.
  * [17] J. Xu and H. Le, “Generating representative samples for few-shot classification,” in _CVPR_ , 2022.
  * [18] J. Xu, X. Luo, X. Pan, Y. Li, W. Pei, and Z. Xu, “Alleviating the sample selection bias in few-shot learning by removing projection to the centroid,” _NeurIPS_ , 2022.
  * [19] A. Roy, A. Shah, K. Shah, P. Dhar, A. Cherian, and R. Chellappa, “Felmi: Few shot learning with hard mixup,” in _NeurIPS_ , 2022.
  * [20] Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang, and J. Xiao, “3d shapenets: A deep representation for volumetric shapes,” in _CVPR_ , 2015.
  * [21] M. A. Uy, Q.-H. Pham, B.-S. Hua, T. Nguyen, and S.-K. Yeung, “Revisiting point cloud classification: A new benchmark dataset and classification model on real-world data,” in _CVPR_ , 2019.
  * [22] N. Sedaghat, M. Zolfaghari, E. Amiri, and T. Brox, “Orientation-boosted voxel nets for 3d object recognition,” _arXiv_ , 2016.
  * [23] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _NeurIPS_ , 2019.
  * [24] A. Nichol and J. Schulman, “Reptile: a scalable metalearning algorithm,” _arXiv_ , vol. 2, no. 3, p. 4, 2018.