summaries: This work studies the question to what extend a reparametrization of an optimization problem, i.e. representing the original parameters w to optimize for as a function of some other parameters theta, can accelerate the convergences of the gradient flow / gradient descent for nonconvex optimization problems. It studies the dynamics of the flow via eigenvectors of a matrix M formed as the expectation over the outer product of the gradient of the loss with itself to reveal 'slow' and 'fast' modes of the evolution. It subsequently derives sufficient conditions for the reparametrization (which is chosen to be linear but time varying) to balance the decay on all modes. After discussing an efficient approximation of the theoretically derived scheme, numerical results demonstrate the effectiveness of the proposed reparametrization in two exemplary applications.

summaries: This paper proposes a reparameterization of non-linear non-convex optimization problems. This reparameterization amounts to a linear map (i.e., "optimization params = linear operation of a different set of parameters). These linear maps are interpreted as a graph convolution network. The experimental results are validated on "Kuramoto models" and "persistent homology models".

summaries: The authors derive a neural reparameterization of non-convex optimization problems in order to accelerate their convergence. They do this by deriving how the slowest components of the optimization variables can have their convergence rate improved by preconditioning with a NTK-based matrix. They make connections between this approach and Group Convolutional Networks. Experimentally, they show this approach improves upon baseline gradient-based optimization on a two datasets.

summaries: This work proposed a neural reparametrization scheme to accelerate a large class of nonconvex nonlinear optimization problems. The proposed method is grounded on analysis that the dynamics of gradient ﬂow are related to the condition number of the system. More specifically, by reparametrizing the optimization problem with a graph convolutional network (GNN), the proposed method can modify the condition number and obtain convergence speed up, the acceleration is demonstrated on optimizing synchronization problems and persistent homology of point-clouds.

abstractText: We tackle the problem of accelerating non-linear non-convex optimization problems. We discover that reparametrizing the optimization variables as the output of a neural network can lead to significant speedup. We examine the dynamics of gradient flow of such neural reparametrization. We find that to obtain the maximum speed up, the neural network architecture needs to be a specially designed graph convolutional network (GCN). The aggregation function of the GCN is constructed from the gradients of the loss function and reduces to the Hessian in early stages of the optimization. We show the utility of our method on two optimization problems: network synchronization and persistent homology optimization, and find an impressive speedup, with our method being 4 ∼ 80× faster.

authors:
Sanjeev Arora
Nadav Cohen
Elad Hazan

title: On the optimization of deep networks: Implicit acceleration by overparameterization

venue: In International Conference on Machine Learning,

title: Iterative solution methods

venue: Cambridge university press,

authors:
Abraham Berman
Robert J Plemmons

title: Nonnegative matrices in the mathematical sciences

authors:
Michael M Bronstein
Joan Bruna
Yann LeCun
Arthur Szlam
Pierre Vandergheynst

title: Geometric deep learning: going beyond euclidean data

venue: IEEE Signal Processing Magazine,

authors:
Mathieu Carriere
Frédéric Chazal
Marc Glisse
Yuichi Ike
Hariprasad Kannan
Yuhei Umeda

title: Optimizing persistent homology based functions

authors:
Nima Dehmamy
Albert-László Barabási
Rose Yu

title: Understanding the representation power of graph neural networks in learning graph topology

venue: Advances in Neural Information Processing Systems,

authors:
John Duchi
Elad Hazan
Yoram Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

venue: Journal of machine learning research,

authors:
Herbert Edelsbrunner
John Harer

title: Persistent homology-a survey

venue: Contemporary mathematics,

authors:
Rickard Brüel Gabrielsson
Bradley J Nelson
Anjan Dwaraknath
Primoz Skraba

title: A topology layer for machine learning

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: In Proceedings of the thirteenth international conference on artificial intelligence and statistics,

authors:
Palash Goyal
Emilio Ferrara

title: Graph embedding techniques, applications, and performance: A survey

venue: Knowledge-Based Systems,

authors:
Stephan Hoyer
Jascha Sohl-Dickstein
Sam Greydanus

title: Neural reparameterization improves structural optimization

venue: arXiv preprint arXiv:1909.04240,

authors:
Arthur Jacot
Clément Hongler
Franck Gabriel

title: Neural tangent kernel: Convergence and generalization in neural networks

venue: In NeurIPS,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907,

authors:
John Michael Kosterlitz
David James Thouless

title: Ordering, metastability and phase transitions in two-dimensional systems

venue: Journal of Physics C: Solid State Physics,

title: Self-entrainment of a population of coupled non-linear oscillators

venue: In International symposium on mathematical problems in theoretical physics,

title: Chemical turbulence. In Chemical Oscillations, Waves, and Turbulence, pp. 111–140

authors:
Roland Lauter
Christian Brendel
Steven JM Habraken
Florian Marquardt

title: Pattern phase diagram for two-dimensional arrays of coupled limit-cycle oscillators

venue: Physical Review E,

authors:
Nina Otter
Mason A Porter
Ulrike Tillmann
Peter Grindod
Heather A Harrington

title: A roadmap for the computation of persistent homology

venue: EPJ Data Science,

authors:
Arkady Pikovsky
Jurgen Kurths
Michael Rosenblum
Jürgen Kurths

title: Synchronization: a universal concept in nonlinear sciences

venue: Number 12. Cambridge university press,

authors:
Yousef Saad
Henk A Van Der Vorst

title: Iterative solution of linear systems in the 20th century

venue: Journal of Computational and Applied Mathematics,

authors:
Mrinal Sarkar
Neelima Gupte

title: Phase synchronization in the two-dimensional kuramoto model: Vortices and duality

authors:
Ivan Sosnovik
Ivan Oseledets

title: Neural networks for topology optimization

venue: Russian Journal of Numerical Analysis and Mathematical Modelling,

authors:
Salma Tarmoun
Guilherme Franca
Benjamin D Haeffele
Rene Vidal

title: Understanding the dynamics of gradient flow in overparameterized linear models

authors:
Tijmen Tieleman
Geoffrey Hinton

title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude

venue: COURSERA: Neural networks for machine learning,

authors:
Zonghan Wu
Shirui Pan
Fengwen Chen
Guodong Long
Chengqi Zhang
Philip S Yu

title: A comprehensive survey on graph neural networks

authors:
Ziwei Zhang
Peng Cui
Wenwu Zhu

title: Deep learning on graphs: A survey

venue: arXiv preprint arXiv:1812.04202,

heading: 1 INTRODUCTION

text:
Gradient-based optimization lies at the heart of machine learning. For non-linear, non-convex largescale optimization problems, gradient-based optimization can suffer from slow convergence and significant computational bottleneck. In linear systems, preconditioning Axelsson (1996); Saad & Van Der Vorst (2000) can accelerating convergence by multiplying a symmetric positive-definite preconditioner matrix to the original problem. In effect, preconditioning re-scales the loss landscape to have more circle-like level sets, hence changing the condition number of the system. Adaptive gradient optimizers such as AdaGrad Duchi et al. (2011) and Adam Kingma & Ba (2014) uses the same idea but updates the preconditioner during iterative optimization with adaptive step size, which leads to great improvement in convergence speed.
Our goal is to improve the convergence of non-convex optimization further. First, we examine the dynamics of the gradient flow and identify the condition number that dictates the speed of convergence. We discover that changing the condition number naturally requires the reparametrization to be a type of graph neural networks (GNN). Based on the analysis, we introduce a novel neural reparametrization scheme, which generalizes preconditioning to non-linear systems. Note that our method is complementary to existing gradient-based optimization algorithms and can be used in conjunction with any adaptive gradient optimizer (e.g. Adam). We test our hypothesis on two highly nonlinear optimization problems and obtain impressive speedups.
A few earlier work Sosnovik & Oseledets (2019); Hoyer et al. (2019) have demonstrated that convolutional neural networks can serve as priors to improve the parameterization of a class of structural optimization problems. But the theoretical foundation behind these techniques are not well understood. Concurrently, the implicit acceleration of over-parametrization in linear neural networks have been analyzed in Arora et al. (2018); Tarmoun et al. (2021). Specifically, Arora et al. (2018) shows that reparametrizing the linear weights with deep linear networks impose a pre-conditioning scheme on gradient descent. Tarmoun et al. (2021) further exploits the conservation laws in gradient flow and derive convergence rate for two-layer linear networks.
In contrast, our method applies to highly nonlinear problems, guided by theoretical insights. Our contributions can be summarized as follows
1. We analyze the dynamics of the gradient flow and derive how a neural reparametrization (NR) can lead to a speedup.
2. We prove that maximum speedup is achieved if the NR is a special GCN which uses gradient of the loss in its aggregation function.
3. For early steps, we show that the NR should use the Hessian of the loss, leading to an efficient hybrid implementation.
4. We showcase NP on two optimization tasks: network synchronization and persistent homology and observe consistent speedup.
Our method also demonstrates a novel usage and unique perspective for GNN, specifically GCN (Kipf & Welling, 2016). The majority of literature treat GNNs as a representation learning tool for graph-structure data (see surveys and the references in Bronstein et al. (2017); Zhang et al. (2018); Wu et al. (2019); Goyal & Ferrara (2018)). However, our analysis shows that GNN can be used to modify optimization dynamics in problems without explicit graph data.

heading: 2 METHODOLOGY

text:
We consider the problem of minimizing a smooth, lower-bounded loss function L(w) ∈ R on abounded variable w ∈ Rn:
argminwL(w)
When the optimization variables are matrices or tensors, w represents a flattened vector containing all variables. w can also represent all trainable parameters in a deep neural network. For supervised learning with a dataset Z = {(xi,yi)Ni=1}, the loss function L(w) becomes L(w;Z). The dataset and the model class (e.g. architecture of a neural network) together define a loss landscape as a function of the optimization variables w.
Gradient-based optimization updates the variables w by taking repeated steps in the direction of the steepest descent wt+1 = wt−ε ∂L∂wt for a learning rate ε. With very small time steps δt, we examine the dynamics of w(t) ∈ Rn during the optimization process, treating t as a continuous time. Using steepest descent for the optimization, dw/dt follows the gradient flow:
dwi dt = −εii ∂L ∂wi , (1)
where denote the learning rate ε as a diagonal matrix of learning rates, because modern optimizers such as RMSProp (Tieleman et al., 2012) or Adam (Kingma & Ba, 2014) choose ε adaptively for each wi. Specifically, in Adam and RMSProp, which we use in experiments, we have
εij(∇L, t) ≈ η√
Et[(∇iL)2] + ξ δij (2)
where δij is the Kronecker delta, and η and ξ are small numbers. The expected value E is calculated using stochastic samples for ∇iL over multiple iteration steps, with more weights given to more recent steps. Equation 1 is also an ordinary differential equation (ODE). The local minima of L(w) correspond to the stationary solutions of the ODE, i.e. dw/dt = 0.
Convergence rate We are interested in the expected convergence rate E[dL/dt] of the loss function. This expectation can be either approximated in a fashion similar to adaptive gradient optimizers (i.e. exponential time average) or be over random initializations under a distribution P (w(0)). We will assume the expectation value for ε and E[dL/dt] are evaluated with the same method, meaning we assume E[ε] = ε. The convergence rate is then given by
E [ dL(w) dt ] = E [∑ i ∂L ∂wi dwi dt ] = −Tr [ εM ] , M ij ≡ E [ ∂L ∂wi ∂L ∂wj ] (3)
where we used our assumption to get E[εM ] = εE[M ], with Mij = ∇iL∇jL being the “square gradients” matrix and M = E[M ]. With this definition, equation 2 becomes ε = η/ √ diag[M ] + ξ.
Note that M is time-dependent and can change during optimization.
Estimating M If we know the distribution P (w(t)) for some t, we can approximate M . One way to do this is similar to Adam as a weighted average over the past few steps. Also, if we know the distribution of the initialization P (w(0)), we can evaluate M for early stages, which is what we
will use in the current paper. When using Xavier initialization (Glorot & Bengio, 2010), we have w(0) ∼ N (0, n−1/2). In this case we can show (see appendix A.1)
M ij(t→ 0) = ∑ k,l E[wkwl] ∂2L ∂wk∂wi ∂2L ∂wl∂wj +O(n−2) = 1 n [ H2 ] ij ∣∣∣ w→0 +O(n−2), (4)
whereHij(w) ≡ ∂2L(w)/∂wi∂wj is the Hessian of the loss at t = 0.
The eigenvectors of M with zero eigenvalue are modes that do not evolve during optimization. As gradients are zero in these directions, GD can never find and explore those directions. Therefore, we may exclude them from the beginning and claim that M is full rank.
The rate dwi/dt can be different along different directions of the parameter space, with fast and slow modes. Next, we quantify this difference in rates and suggest ways for acceleration.

heading: 2.1 FAST AND SLOW DYNAMICS OF GRADIENT FLOW

text:
M is positive semi-definite because for any vector v ∈ Rn we have vTMv = E [( vT∇L )2] ≥ 0. Thus, M is Hermitian with a spectral expansion M = ∑ imiψiψ T i . Using equation 1, we can show that the dynamics of w along different ψi are orthogonal to each other
E [( ψTi dw
dt
)( ψTj dw
dt
)] = ε2ψTi Mψj = εiεjmiδij . (5)
If ε is constant and not adaptive, w evolves faster along modes ψi with larger eigenvalues mi, since if mi > mj we have
ε2mi = E [( ψTi dw
dt
)2] > E [( ψTj dw
dt
)2] = ε2mj (6)
This is precisely what optimizers such as Adam try to address. Ideally, having εi = η/ √ mi would make up for the rate difference, resulting in a uniform GD where no mode ψi is evolving more slowly than others. However, calculating mi is O(n3) and can be quite expensive during optimization, hence the approximate version equation 2 is used. We show here that in many cases it is worthwhile to do a full correction to GD using M , at least in early stages of the optimization.
The eigenvalues of M determine the rate of evolution of the overlaps along each of its eigenvectors. In particular, if some eigenvalue mslow meani[mi] is much smaller than the mean, the evolution of w along ψslow will be much slower than other directions. Therefore, we will refer to all ψslow as the slow modes of the optimization problem. Conversely, the ψfast where mfast meani[mi] will be referred to as the fast modes.
When running GD, the maximum change in w is bounded to ensure numerical stability. Because of the orthogonality in equation 5, we can enforce a numerical bound η via
max i
E [( ψTi dw
dt
)2] ≤ η2 ⇒ εmax ≤
η √ mmax , E
[( ψTi dw
dt
)2] ≤ η2 mi
mmax . (7)
where mmax = maximi is the largest eigenvalue of M . Therefore, the learning rate ε is bounded by the largest eigenvalues (fastest modes). Thus, in order to speed up convergence, we need to focus on the slow modes, which can be achieve with a reparametrization of w.

heading: 2.2 NEURAL PARAMETRIZATION OF OPTIMIZATION PROBLEMS

text:
Using neural networks to reparametrize optimization problems have been suggested in (Hoyer et al., 2019; Sosnovik & Oseledets, 2019). The idea is that the optimization variable w can be defined as the output of a deep neural network w(θ) ≡ f(θ) with trainable parameters θ. Then, rather than optimizing over the original variables w directly, we can instead optimize over the neural network parameters θ. We will take this idea further and analyze the type of neural network architectures that can accelerate the optimization.
Modified convergence rate The neural reparametrization of the variables w(θ) leads the following updating rule for θ:
dθa dt = −ε̂a ∂L ∂θa = −ε̂a ∑ i ∂L ∂wi ∂wi ∂θa
(8)
The convergence rate is then given by
dL dt = ∑ i,a ∂L ∂wi ∂wi ∂θa dθa dt = − ∑ i,j ∂L ∂wi ∂L ∂wj ∑ a εa ∂wi ∂θa ∂wj ∂θa
= − ∑ i,j MijKij = −Tr [ MKT ] , Kij ≡ ∑ a ε̂a ∂wi ∂θa ∂wj ∂θa . (9)
Here K is the neural tangent kernel (NTK) (Jacot et al., 2018) of w(θ), and Mij is the squared gradients. Note, we have absorbed ε̂a into K for convenience of notation.
Expected convergence rates The expected convergence rate E[dL/dt] equation 3 depended on M = E[M ], the reparametrized one from equation 9 depends on E[MK]. In order to quantify any improvements in E[dL/dt] from equation 9, we need to be able to express E[MK] in terms of E[M ], which is not possible for a general K.
If we assume M and K to be independent from each other, i.e. E[MK] becomes E[M ]E[K]. Since M is a function of w, K must not be a function of w. One way is to have w = σ(Aθ + b) or any other similar neural network. We will discuss explicit choices for w below in sec. 2.3. In summary, an important constraint that we will put on w(θ) is that it yields a K independent of w
choose w(θ) s.t.: E[MK] = E[M ]E[K] (10) Now we can compute the expected rate of change of w(θ) along the previous fast and slow mode eigenvectors ψi of M , similar to equation 6. Using equation 9 and equation 8 we have
ψTi dw
dt = ψTi ∑ a ∂w ∂θa dθa dt = −ψTi ∑ a ε̂a ∂w ∂θa ∑ j ∂wj ∂θa ∂L ∂wj = −ψTi K ∂L ∂w (∈ R) (11)
where ∂L/∂w = ∇wL is the gradient vector. Multiplying equation 11 by its transpose, denoting K ≡ E[K], and using equation 10 the expected value becomes
E [( ψTi dw
dt
)2] = ψTi K M K T ψi = ∑ j mj ( ψTi Kψj )2 . (12)
which shows how the neural reparametrization may speed up the convergence.
First, note that NR changes the rate of evolution of modes ψi in equation 7. We can quantify this change when [K,M ] = 0. In this case, K and M can be diagonalized simultaneously with shared eigenvectors ψi. Plugging the spectral expansion K = ∑ i kiψiψ T i into equation 12 and using
ε < η/ √ mmax (equation 7) we have
if: [ K,M ] = 0 ⇒ E [∥∥∥∥ψTi dwdt ∥∥∥∥2 ] = k2imi < η 2 mik 2 i mmax . (13)
Thus, one way to speed up the convergence, is to have [K,M ] = 0 and have K increase the slowest rates ‖ψslowdw/dt‖, while keeping the fastest rate mostly unchanged. As a result, we have:
Theorem 1. With a neural reparametrization yielding [ K,M ] = 0, to make all modes ψi reach the ideal maximum rate maxi ‖ψTi dw/dt‖ < η, we need to have
K ≈ ( M
mmax
)−1/2 (14)
Proof. This is because plugging k2i ≈ mmax/(mi + ξ) (ξ 1) into equation 13 makes the r.h.s. equal to η2.
Next, we discuss how we can achieve this in practice. Specifically, we derive what architecture for the neural network w(θ) = f(θ) will result in a K satisfying the condition in equation 14.

heading: 2.3 PRACTICAL IMPLEMENTATION

text:
To find a neural network model that satisfies equation 14, we need to consider the fact thatM(w(t)) changes during optimization. To minimize the overhead from constructing w(θ) (and hence K) as a function of M , the architecture has to be as simple as possible and involve steps which do not increase the time complexity of each iteration significantly. We will now discuss when such neural reparametrization is feasible and how to implement equation 14 in practice.
Hybrid optimization To use equation 14 at points other than the initial steps, we need to dynamically estimate and updateM . Though estimatingM(t) efficiently with ideas from Adam is possible, in the current work we focus on the speeding up at early stages using equation 4. Thus, our main proposal is to use a two stage hybrid optimization: 1) use the Hessian to reparametrize w(θ) in early stages for some number of iterations and then 2) switch to the original optimization over w.
Simple implementation Because M may depend on w(θ), as in equation 10, we need a K that is independent of θ to ensure E[MK] = E[M ]E[K]. The simplest architecture is a linear model wi = ∑ a κiaθa, which yields K = κκ
T ≈ (M/mmax)−1/2. We need K to be a full rank matrix, meaning that κ needs to be at least n×n. Since we need the least computationally expensive K, we choose θ ∈ Rn, and let κ be a symmetric n × n matrix. This way, κ = √ K = (M/mmax)
−1/4. For the initial stages, where M ≈ H2/n we have κ = (H/hmax)−1/2, withH being the Hessian.
Per-step time complexity Since w ∈ Rn, the complexity of computing L(w) is O(np) where p depends on the sparsity structure of L. M is an n × n matrix and computing M−1/2 is O(n3) , which is very expensive when n 1. The eigenvaluemmax can be estimated iteratively inO(qn2). Hence, computing K by exactly following equation 14 is not feasible, unless M is fixed and can be calculated offline. Even then, evaluating M −1/2 only makes sense if the expected GD steps for convergence is more than O(n), otherwise we don’t gain any speedup. We may instead try to approximate M−1/2 and mmax iteratively with complexity O(qn2) where q n is the number of iterations. Hence we note that using equation 14 to speedup the optimization may generally be useful if the the per step complexity of GD on L has a time complexity of least O(qn2).
Implementation constraints In summary, we have the following constraints on the structure of the neural network w(θ)
1. Computing w(θ) ∈ Rn must be at most O(qn2) with q n
2. To have K independent of M , ∂w/∂θ must be independent of w and hence, only linear maps w(θ) = κθ are allowed, with κ independent of w. 3. θ ∈ Rm with m ≥ n. We choose m = n, which yields κ = √ K = (M/mmax) −1/4
4. Instead of κ = (M/mmax)−1/4, which is O(n3), we should use O(qn2) approximations.
Relation to GCN Since both θ ∈ Rn and w ∈ Rn, our linear w = κθ architecture is essentially a Graph Convolutional Network (GCN) (Kipf & Welling, 2016) with the aggregation rule κ = (M/mmax)
−1/4, or a weighted adjacency matrix. In fact, all of our derivations remain unchanged if w ∈ Rn×d and θ ∈ Rn×m (i.e. if there are d and m features per node in w and θ). Thus, our claim is that we can speed up the optimization process by reparametrizing w using a GCN with linear activation, as w = κθ, where θ are trainable and κ is the aggregation function derived from the loss gradients. However, evaluating this κ during GD can be quite expensive (O(n3)) for large n (GD steps ∼ O(n2)). Ideally we want an approximation for κ which is O(qn2) with q ∼ O(1).
Computationally efficient implementation We will focus on speeding up the early stages, in which we use the HessianH in M ≈ H2/n. Define H ≡ (1− ξ)H/hmax, where hmax = √ mmax and ξ 1. To get an O(qn2) approximation for κ = (M/mmax)−1/4 = H−1/2 we can take the first q terms in the binomial expansion (see Appendix A.2). A rough estimate would be
H−1/2 ≈ I − 1 2 (I −H)− 3 4 (I −H)2. (15)
Since H is positive semi-definite and its largest eigenvalue is 1 − ξ < 1, the sum in equation 15 can be truncated after q ∼ O(1) terms. The first q terms of equation 25 can be implemented as a q layer GCN with aggregation function f(M) = I −M0 and residual connections. We choose q to be as small as 1 or 2, as larger q may actually slow down the optimization. Note that computing f(M0)
qθ is O(qn2) because we do not need to first compute f(M)q (which is O(qn3)) and instead use vi+1f(M)vi (O(n2)) q times with v1 = θ.
Lastly, to evaluate M0 we need to estimate the leading eigenvalue mmax. Given any vector v ∈ Rn and using spectral expansion, we have
Hqv = ∑ i m q/2 i (ψ T i v)ψi ⇒ hmax ≈ 1TH21 1TH1 = ∑ ij H2ij∑ ij Hij
(16)
where, sinceH is positive semi-definite, for q > 1 the leading eigenvector ψmax quickly dominates the sum and we have Hqv ≈ hqmax(ψmaxv)ψmax. Here we chose q = 2 to get a crude approximation for hmax. The generalized Perron-Frobenius theorem (Berman & Plemmons, 1994), state the components of the leading eigenvector ψmax should be mostly positive. Therefore, we chose v = 1/ √ n, where 1 = (1, . . . , 1), which should be close to the actual ψmax.
If we think of M as the weighted adjacency matrix of a graph with n vertices, the vector component Di = [H1]i = ∑ j Hij is the weighted degree of node i. Hence equation 16 states H/mmax ≈(∑
iDi/‖D‖2 ) H. This is similar to the graph diffusion operatorD−1H andD−1/2HD−1/2 which
are used as the aggregation functions in GCN (here Dij = Diδij is the degree matrix).
When using modern optimizers, the adaptove learning rates is a term within K. This will interfere with the optimal choice for κ and hence our GCN aggregation function. Therefore, in practice, we do not fix the coefficients for H and H2 in our GCN. Instead, we use single or two layer GCN with aggregation function f(H) = D−1/2HD−1/2.

heading: 3 EXPERIMENTS

text: We showcase the acceleration effect of neural reparametrization on two non-convex optimization problems: network of Kuramoto oscillators which are widely-used for modeling synchronization phenomena; and persistent homology, a mathematical tool that computes the topology features of data that persist across scales . We use Adam Kingma & Ba (2014) optimizer and compare different reparameterization models. We implemented all models with Pytorch.

heading: 3.1 NETWORK OF KURAMOTO OSCILLATORS

text:
Kuramoto model Kuramoto (1975; 1984) are widely used for synchronization problems, which have profound impact on engineering, physics and social systems (Pikovsky et al., 2003). As shown in Fig. 3(right), Kuramoto model describes the behavior of a large set of coupled oscillators. Each
oscillator is defined by an angle θi = ωit + φi, where ωi is the frequency and φi is the phase. We consider the case where ωi = 0. The coupling strength is represented by a graph adjacency matrix with elements Aij ∈ R. Defining ∆ij ≡ φi− φj , the dynamics of the phases φi(t) in the Kuramoto model follows
dφi dt = −ε n∑ j=1 Aji sin ∆ij , L(φ) = n∑ i,j=1 Aji cos ∆ij . (17)
Hopf-Kuramoto (HK) model Lauter et al. (2015) is a more general version of the Kuramoto model. It includes second neighbor interactions. HK has a rich phase space with qualitatively different solutions. The phase space includes regions where simulations becomes slow and difficult. We use the HK model to showcase our method in more complex and nonlinear scenarios. The HK model’s dynamics follows
dφi dt = c ∑ j Aji [cos ∆ij − s1 sin ∆ij ]
+ s2 ∑ k,j (AijAjk [sin (∆ji + ∆jk)− sin (∆ji −∆jk)] +AijAik sin (∆ji + ∆ki)) . (18)
with the following loss function
L = c ε ∑ i,j Aji [sin ∆ij + s1 cos ∆ij ] + s2 2ε ∑ i,k,j AijAjk [cos (∆ji + ∆jk) + cos (∆ji −∆jk)]
(19) Our goal is to minimize the phase drift dφi/dt to synchronize the oscillators. Existing numerical methods directly optimize the loss L(φ) with gradient-based algorithms, which we refer to as linear. We apply our method to reparametrize the phase variables φ and speed up convergence towards synchronization.
Implementation. For early stages, we use a GCN with the aggregation function derived from the Hessian which for the Kuramoto model simply becomes Hij(0) = ∂2L/∂φi∂φj |φ→0 = Aij −∑ k Aikδij = −Lij , where L = D −A is the graph Laplacian of A. We found that NR in the early stages of the optimization gives more speed up. We implemented the hybrid optimization described earlier, where we reparemtrize the problem in the first 100 iterations and then switch to the original linear optimization for the rest of the optimization.
We experimented with three Kuramoto oscillator systems with different coupling structures: square lattice, circle graph, and tree graph. For each system, the phases are randomly initialized between 0 and 2π from uniform distribution. We let the different models run until the loss converges (10 patience steps for early stopping, 10−15 loss fluctuation limit).
Results of Kuramoto Model. Figure 2 shows the results of Kuramoto model on a square lattice. Additional results on circle graph, and tree graph can be found in Appendix B. Figure 2 (a) shows that NR with one-layer GCN (GCN-1) and GCN with residual connection (RGCN-1) achieves significant speedup. In particular, we found 3.6± .5 speed improvement for the lattice, 6.1± .1 for the
circle graph and 2.7± .3 for tree graphs. We also experimented with two layer (GCN/RGCN-2) and three layer (GCN/RGCN-3) GCNs. As expected, the overhead of deeper GCN models slows down optimization and offsets the NR speedup gains. Figure 2 (b) visualizes the evolution of the oscillator phase φi on a square lattice over iterations. We can see that even though different reparametrization models reach the same loss value, the final solutions are quite different. The linear version (without NR) arrives at the final solution smoothly, while GCN models form dense clusters at the initial steps and reach an organized state before 100 steps. To quantify the level of synchronization, we measure a quantity ρ known as the “global order parameter” (Sarkar & Gupte (2021)): ρ = 1N
∣∣∣∑j eiφj ∣∣∣. Figure 2 (c) shows the convergence of the global order parameter over time. We can see that one-layer GCN and RGCN gives the highest amount of acceleration, driving the system to synchronization.
Results of Hopf-Kuramoto Model. We report the comparison of NR models on synchronizing Hopf-Kuramoto dynamics. According to the Lauter et al. (2015) paper, we identify two different main patterns on the phase diagram Fig. 9(b): ordered (small s2/c, smooth patterns) and disordered (large s2/c, noisy) phases. In all experiments we use the same lattice size 50×50, with the the same stopping criteria (10 patience steps and 10−10 loss error limit) and switch between the Linear and GCN model after 100 iteration steps. Fig. 3 (a) shows the loss at convergence versus the speedup. We compare different GCN models and observe that GCN with A2 as the propagation rule achieves the highest speedup. Also, we can see that we have different speedups in each region, especially in the disordered phases. Furthermore, we observed that the Linear and GCN models converge into a different minimum state in a few cases. However, the patterns remain the same. (b) shows how the level of ordering changes region by region. If the global order parameter is closer to 0, we have more of a disordered phase while the parameter is closer to 1, meaning it is a more organized pattern.
We know that running dynamics in a large lattice are computationally expensive, especially close to the phase transition points where difficult to separate the slow and fast modes.

heading: 3.2 PERSISTENT HOMOLOGY

text:
Persistent homology Edelsbrunner et al. (2008) is an algebraic tool for measuring topological features of shapes and functions. It provides precise definition of qualitative features, is computable with linear algebra and robust to perturbation of input data (Otter et al., 2017), see more details in Appendix B.3. An example of persistent homology is point cloud optimization Gabrielsson et al. (2020); Carriere et al. (2021). Given a random point cloud w that lacks any observable characteristics, we aim to produce persistent homological features by optimizing the position of data points.
L(w) = − ∑ p∈D ‖p− π∆(p)‖2∞ + n∑ i=1 ‖wi − r‖2 (20)
where p ∈ D = {(bi, di)}i∈Ik denotes the homological features in the the persistence diagram D, consisting of all the pairs of birth bi and death di filtration values of the set of k-dimensional homological features Ik. π∆ is the projection onto the diagonal ∆ and ∑ i d(φi, S) constrains the points within the a square centered at the origin with length 2r (denote r as range of the point cloud). Carriere et al. (2021) optimizes the point cloud positions directly with gradient-based optimization.
We will refer theirs as the baseline linear model. In contrast, we integrate GCN and reparameterize the point cloud positions, and will refer ours as the GCN model.
Implementation. To measure the speed-up of GCN model, we used the same Gudhi library for computing persistence diagram as Gabrielsson et al. (2020); Carriere et al. (2021). The runtime of learning persistent homology is dominated by computing persistence diagram in every iteration, which has the time complexity of O(n3). Thus, the runtime per iteration for GCN model and linear model are very similar, and we demonstrate that the GCN model can reduce convergence time by a factor of ∼ 4. We ran the experiments for point cloud of 100,200,300 points, with ranges of 0.5,1.0,2.0,4.0. The hyperparameters of the GCN model are kept constant, including network dimensions. The result for each setting is averaged from 5 consecutive runs.
Results. Fig. 4 and 5(a) show that the speedup of the GCN model is related to point cloud density. Training converges faster as the point cloud becomes more sparse, but the speedup gain saturates as point cloud density decreases. On the other hand, time required for initial point cloud fitting increases significantly with the range of point cloud. Consequently, the overall speedup peaks when the range of point cloud is around 4 times larger than what is used be in Gabrielsson et al. (2020); Carriere et al. (2021), which spans over an area 16 times larger. Further increase in point cloud range causes the speedup to drop as the extra time of initial point cloud fitting outweighs the reduced training time. The loss curve plot in Fig. 4 shows the convergence of training loss of the GCN model and the baseline model in one of the settings when GCN is performing well. Fig. 5 shows the initial random point cloud and the output from the GCN model. In the Appendix B.3, we included the results of GCN model hyperparameter search and a runtime comparison of the GCN model under all experiment settings.
Conclusion We propose a neural reparametrization scheme to accelerate a large class of optimization problems. Our method is grounded on analysis that the dynamics of gradient flow are related to the condition number of the system. By reparametrizing the optimization problem with a graph convolutional network, we can modify the condition number and obtain the maximum speed up. The aggregation function of the GCN is constructed from the gradients of the loss function and reduces to the Hessian in early stages of the optimization. We demonstrate our method on optimizing synchronization problems and persistent homology of pointclouds. Depending on the experiment, we obtain a best case speedup that ranges from 4 to 80.


summaries: In this work auhors proposed an ensemble of multiple SVM classifiers setup in a hierarchical way (somewhat similar to neural networks). Each SVM is trained is a small patch or window from the input imagery and some classifiers can be eliminated from contributing to the predictions. Results show better performance by the model in the small data regime compared with larger convolutional neural networks trained from scratch.

summaries: The paper describes the use of SVM classifiers trained independently using local receptive fields of images, outputting class probabilities for each pixel that are organized in channels. New independent SVM classifiers are trained over the class probabilities and their results are combined using voting to perform the final prediction. The authors report experiments on two datasets, comparing with versions of ResNet trained from scratch, in which SVMNet shows better results than ResNet when using fewer training examples, For one of the datasets, the ResNet could not converge, while SVMNet obtained up to 80%.

summaries: The paper argues that one of the major drawbacks for deep convolutional neural networks (DCNNs) is the need for large annotated training sets. To address this drawback, the paper proposes a new architecture, SVMnet, which is designed to achieve relatively high accuracy  (compared to DCNNs) in settings of small training sets.  The SVMnet architecture is composed of one or more stacked "SVM layers". Each SVM layer is composed of a set of independent svm classifiers, where the input to each svm is a patch in the image and the output is a probability estimate for the image class. For example, given a grayscale h X w input image, an SVMnet with 5x5 kernels and stride of 5 would have a 2d “array” of h/5 X w/5 svms, each one trains on a patch of 5x5 pixels whichis flattened to a vector of 25 features. Each svm i is then trained directly to predict the class of the image, based on the 5x5 window, thus resulting in a probability vector for the 5x5 patch. From the validation step, we also obtain the average accuracy of each svm i, denoted by Ai, from which we can compute its weight when aggravating the predictions from all svms. In general each svm layer will have k X l svms, and thh output of the svm layer can be formulated either as a 2d array of k X l predictions or a 3d array of k X l X c of probabilities for each class (where c is the number of classes). When stacking a second SVM layer, the input to that layer is then the k X l X c probability map which is treated as a feature map. Finally, the predictions from the last SVM layer are tallied to produce a majority vote for the image. When training on images with multiple channels, for example RGB images, the channels are flattened to one vector, for example: a 3x5x5 patch would be flattened to a 75 dimensional feature vector.   To demonstrate the applicability of the proposed method, the paper compares SVMnet to ResNet on 3 publicly available datasets and claims to achieve superior performance to resnet in settings of limited training data as well as faster training time.

summaries: One of the weakness of traditional DCNNs is it needs large clean-labeled dataset. In this paper, the author proposes SVMNET, a deep learning architecture which includes a layered structure of Support Vector Machine (SVM) ensembles. The result shows that the SVMNET outperforms other deep convolutional neural networks such as ResNet-50 with less training time for cases in which the number of labeled training samples is small.

abstractText: Deep convolutional neural networks (DCNNs) have demonstrated superior power in their ability to classify image data. However, one of the downsides of DCNNs for supervised learning of image data is that their training normally requires large sets of labeled “ground truth” images. Since in many real-world problems large sets of pre-labeled images are not always available, DCNNs might not perform in an optimal manner in all real-world cases. Here we propose SVMnet – a method based on a layered structure of Support Vector Machine (SVM) ensembles for non-parametric image classification. By utilizing the quick learning of SVMs compared to neural networks, the proposed method can reach higher accuracy than DCNNs when the training set is small. Experimental results show that while “conventional” DCNN architectures such as ResNet-50 outperform SVMnet when the size of the training set is large, SVMnet provides a much higher accuracy when the number of “ground truth” training samples is small.

authors:
Léon Bottou
Chih-Jen Lin

title: Support vector machine solvers

venue: Large scale kernel machines,

authors:
Evgeny Byvatov
Uli Fechner
Jens Sadowski
Gisbert Schneider

title: Comparison of support vector machine and artificial neural network systems for drug/nondrug classification

venue: Journal of chemical information and computer sciences,

authors:
Chih-Chung Chang
Chih-Jen Lin

title: Libsvm: a library for support vector machines

venue: ACM transactions on intelligent systems and technology (TIST),

authors:
Wun-Hwa Chen
Sheng-Hsun Hsu
Hwang-Pin Shen

title: Application of svm and ann for intrusion detection

venue: Computers & Operations Research,

authors:
Muhammad E.H. Chowdhury
Tawsifur Rahman
Amith Khandakar
Rashid Mazhar
Muhammad Abdul Kadir
Zaid Bin Mahbub
Khandakar Reajul Islam
Muhammad Salman Khan
Atif Iqbal
Nasser Al Emadi
Mamun Bin Ibne Reaz
Mohammad Tariqul Islam

title: Can ai help in screening viral and covid-19 pneumonia

venue: IEEE Access,

authors:
Vincent Dumoulin
Francesco Visin

title: A guide to convolution arithmetic for deep learning, 2018

authors:
Ezz El-Din Hemdan
Marwa A. Shouman
Mohamed Esmail Karar

title: COVIDX-Net: A Framework of Deep Learning Classifiers to Diagnose COVID-19 in X-Ray Images

venue: arXiv e-prints, art

authors:
Li Fei-Fei
Rob Fergus
Pietro Perona

title: One-shot learning of object categories

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Cedric Gangloff
Sonia Rafi
Guillaume Bouzillé
Louis Soulat
Marc Cuggia

title: Machine learning is the key to diagnose covid-19: a proof-of-concept study

venue: Scientific Reports,

authors:
Hunter Goddard
Lior Shamir

title: A catalog of broad morphology of pan-starrs galaxies based on deep learning

venue: The Astrophysical Journal Supplement Series,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

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

authors:
Asifullah Khan
Anabia Sohail
Umme Zahoora
Aqsa Saeed Qureshi

title: A survey of the recent architectures of deep convolutional neural networks

venue: Artificial Intelligence Review,

authors:
Fahad Shahbaz Khan
Shida Beigpour
Joost Van de Weijer
Michael Felsberg

title: Painting-91: a large scale database for computational painting categorization

venue: Machine Vision and Applications,

authors:
Gregory Koch
Richard Zemel
Ruslan Salakhutdinov

title: Siamese neural networks for one-shot image recognition

venue: In ICML deep learning workshop,

authors:
Srinivas Mukkamala
Guadalupe Janoski
Andrew Sung

title: Intrusion detection using neural networks and support vector machines

venue: In Proceedings of the 2002 International Joint Conference on Neural Networks. IJCNN’02 (Cat. No. 02CH37290),

authors:
Sameer A Nene
Shree K Nayar
Hiroshi Murase

title: Columbia object image library (coil-100)

authors:
Joana S Paiva
João Cardoso
Tânia Pereira

title: Supervised learning methods for pathological arterial pulse wave differentiation: a svm and neural networks approach

venue: International Journal of Medical Informatics,

authors:
Tawsifur Rahman
Amith Khandakar
Yazan Qiblawey
Anas Tahir
Serkan Kiranyaz
Saad Bin Abul Kashem
Mohammad Tariqul Islam
Somaya Al Maadeed
Susu M. Zughaier
Muhammad Salman Khan
Muhammad E.H. Chowdhury

title: Exploring the effect of image enhancement techniques on covid-19 detection using chest x-ray images

venue: Computers in Biology and Medicine,

authors:
Lior Shamir
Nikita Orlov
D Mark Eckley
Tomasz Macura
Josiah Johnston
Ilya G Goldberg

title: Wndchrm–an open source utility for biological image analysis

venue: Source Code for Biology and Medicine,

authors:
Kyung-Shik Shin
Taik Soo Lee
Hyun-jung Kim

title: An application of support vector machines in bankruptcy prediction model

venue: Expert Systems with Applications,

authors:
Oriol Vinyals
Charles Blundell
Timothy Lillicrap
Daan Wierstra

title: Matching networks for one shot learning

venue: Advances in Neural Information Processing Systems,

authors:
Lior Wolf
Tal Hassner
Yaniv Taigman

title: The one-shot similarity kernel

venue: IEEE 12th International Conference on Computer Vision,

authors:
Ansi Zhang
Shaobo Li
Yuxin Cui
Wanli Yang
Rongzhi Dong
Jianjun Hu

title: Limited data rolling bearing fault diagnosis with few-shot learning

heading: 1 INTRODUCTION

text:
Deep convolutional neural networks (DCNNs) are powerful tools for multiple tasks of automatic image analysis, demonstrating paramount success and consequently gaining substantial popularity over the past decade. By analyzing the pixels directly, CNNs can be applied to various types of image content without the need to develop task-specific algorithms, and can easily be applied to a broad range of domains with excellent performance (Khan et al., 2020).
One of the major weaknesses of modern DCNNs is their dependence on a large set of examples for training. Cutting-edge DCNNs can have hundreds of layers, each with thousands of trainable parameters. For instance, the common ResNet-50 (He et al., 2016) contains over 2·106 artificial neurons. Therefore, to achieve meaningful performance and avoid underfitting, DCNNs normally rely on relatively large training sets.
Training DCNNs normally requires large datasets of labeled ground truth images. Commonly used datasets include benchmarks such as the Modified National Institute of Standards and Technology (MNIST) or ImageNet. These benchmark datasets provide tens of thousands of images with highquality annotations for training deep CNNs and are commonly used for testing their performance. However, in many cases of real-world image classification problems, large datasets of clean, labeled ground truth are not available.
A common solution to increasing the size of the training set is data augmentation, in which different modifications of the images in the original dataset can create more training samples. However, that strategy can also lead to biases by overusing the same examples. In some cases transfer learning can be used to fine-tune neural networks using pre-trained models, but for domains with very small datasets for fine-tuning, the pre-trained models may remain too sensitive to their original task.
In many real-world cases large datasets are not available. For instance, in the biomedical domain the acquisition and annotation of each image requires the use of costly medical instrumentation, technicians, and medical staff who can annotate each sample manually. Additionally, human protection procedures and protocols are required for the acquisition of each sample, making the preparation of large datasets less practical. Therefore, biomedical image datasets are normally far smaller than the
modern datasets commonly used to train DCNNs. Rare cases can also make it difficult to acquire a suitable training set (Zhang et al., 2019). The need for a large number of training samples is a practical downside of DCNNs, making it difficult to use optimally in many real-world cases.
The problem of small training sets has been addressed in the past by using previous knowledge for a few shot training (Zhang et al., 2019) and even one-shot training (Fei-Fei et al., 2006; Wolf et al., 2009; Koch et al., 2015; Vinyals et al., 2016; Bender et al., 2018). This paper explores a new form of image classification in cases when the number of samples is limited. Based on an ensemble composition of support vector machines (SVMs), the method can work with no prior knowledge, in a similar manner to “standard” supervised machine learning. Inspired by CNN architecture, SVMnet utilizes a large number of small SVMs to quickly analyze image patches, structured in layers that allow for stacking or custom ensemble techniques. An SVM (Cortes & Vapnik, 1995) is less sensitive to high-dimensionality feature spaces (Chen et al., 2005; Mukkamala et al., 2002), and has the advantage of learning from a relatively small number of training samples (Shin et al., 2005; Byvatov et al., 2003; Paiva et al., 2018) compared to other supervised machine learning approaches.

heading: 2 ARCHITECTURE OF SVMNET

text:
The proposed SVMnet1 architecture is designed as a stacked ensemble of numerous simple SVM classifiers organized into one or more layers. Each layer is an array of SVMs which functions similarly to a convolutional layer in a CNN. Each SVM in a layer is independent and all are assigned an equal-sized patch of the layer’s input, referred to as a window. Variable stride length and padding, as described in Chapter 2 of Dumoulin & Visin (2018), are specified as hyperparameters. Each input to the following layer is the output of one SVM.
When a layer is evaluated, each SVM in the layer is trained on ground truth labels. The input to the SVM is the flattened portion of each input image that is within the SVM’s window. Each pixel channel within the window is essentially treated as one input feature. For instance, a 5 × 5 window would create a 25-feature SVM for grayscale input and a 75-feature SVM for 3-channel RGB input. During this step, the SVMs may be given weights based on the accuracy of the fit, used for ensemble classification. Each SVM then predicts a class label or a vector of class probabilities for its window of each input, creating an input tensor for the next layer.
Figure 1 shows a simple layer in SVMnet. Each node in the layer is one SVM, trained using the ground truth labels for the input samples. The weights are determined based on the classification accuracy of the SVM compared to the ground truth of the training set. The weight function is configurable and will be described later in this Section.
To produce one class label for each input, SVMnet may perform a weighted vote after the final layer. This vote combines the results of the final layer by treating each value as a vote for that class label. If the final layer is weighted, these are used to weigh the votes in favor of SVMs with higher accuracy.
1SVMnet is not a ”network” in the same sense as CNNs and are named as such mostly due to analogy.
Sc = Σiη(Ai)[Pi = c] (1)
The total voting score Sc of each class c is calculated by Equation 1, where Ai is the accuracy score of SVM i in the final layer, η is the weight function, and Pi is the class label predicted by SVM i. That is, if the predicted label Pi of SVM i is class c, the weighted score η(Ai) is added to the vote for that class. The weight function emphasizes the predictions of the SVMs with higher accuracy during training. The class that has the highest score Sc is chosen as the predicted label by the model for the given sample. The weight function η is configurable and in our experiments is defined as η(x) = x2, where x is the classification accuracy of the SVM determined during training.
While the layers support arbitrary estimators, here we use only support vector machines (SVM), hence the name SVMnet. The SVMs are trained with a Radial Basis Function (RBF) kernel (Chang & Lin, 2011) and scaling gamma value, and they continue to iterate until convergence with a 0.001 tolerance. The ability to choose different estimators in each layer can be compared to the ability to use different activation functions in the layers of neural networks.
Figure 2 illustrates one possible two-layer SVMnet architecture. Each SVM in the first layer analyzes a specific patch of each image and is fitted independently against ground truth labels. These SVMs then produce a vector of class probabilities for the same pixel region which forms the input matrix for the following layer. The SVMs in the second layer are fitted on a region of these probabilities and predict a class label for the image. These labels are then tallied in a final vote to produce one label for the input. The motivation for multiple layers is that secondary layers can in essence learn which of the SVMs in their window are more accurate or ”trustworthy”, as their predictions are being compared to ground truth labels in each layer.

heading: 2.1 DROPOUT

text:
Not every patch is expected to produce a well-informed SVM. Some regions of the images, particularly towards the edge, often lack the details necessary to distinguish samples from each other. This can cause the outputs of these SVMs to act as noise in a vote tally. Even with the expected low accuracy score of the SVM depressing the weight of its vote, if the low-information regions are large then enough inaccurate votes may overwhelm the more accurate votes. To help prevent this, a dropout system is implemented for the vote tally.
When using dropout, which SVMs to drop are calculated when fitting SVMnet. First, the SVMs are ordered from the highest weight to the lowest. Votes are then cumulatively tallied one SVM at a time with the accuracy of the votes measured between each tally. SVMnet then finds the global maximum accuracy of the cumulative tally. This marks the point where including the votes of the less-accurate SVMs lowers the overall accuracy of the tally, so those SVMs are marked for dropout and are not included in the final vote.

heading: 3 EXPERIMENTAL RESULTS

text:
To test the efficacy of SVMnet compared to a “conventional” CNN, several experiments were performed using common, relatively small datasets. The purpose of SVMnet is not to outperform CNNs
in the general case, but to achieve higher accuracy when the number of labeled training images is limited. Therefore, the experiments were made with different sizes of training sets to compare the classification accuracy as the training set increases.
The performance of the SVMnet was compared to the performance of residual network, or ResNet, models with 18, 34, and 50 layers (He et al., 2016). ResNet is a powerful architecture that was designed to reduce the number of required training samples for deep learning tasks and has demonstrated excellent efficacy in image classification. Each ResNet model was compared when trained from scratch and when fine-tuned using pretrained ImageNet weights. Following the practice in He et al. (2016), the final convolutional layer is followed by a global average pooling layer, then by a single fully-connected layer with softmax activation and as many units as class labels in the respective task. Models were trained using stochastic gradient descent (SGD) optimization with a linearly decaying learning rate (given by 0.999(1 − s/2) + 0.001 where s is the training step) and Nesterov momentum of 0.9. The models were trained for a maximum of 200 epochs but were stopped early if the loss on the validation dataset did not improve by at least 0.01 over 20 epochs. The number of epochs is limited in order to keep the ResNet training times comparable to SVMnet. The resulting accuracy and training time for each model was averaged over 5 repetitions of each experiment.
While the height and width of inputs can be adjusted for ResNet, the architecture always expects 3-channel RGB color images. Grayscale images were modified for use by ResNet by duplicating the pixel values into three equal channels. This approach was used in Section 3.3 and Section 3.4. Before training and classification by ResNet, images were also passed through a preprocessing filter provided by the Keras library to prepare the data for ResNet models. All inputs were normalized by dividing by the mean and subtracting the variance before being used to train SVMnet. For RGB color inputs, the images were normalized per-channel.
All experiments and analysis presented in this section used the same hardware environment. SVMnet was parallelized across 16 cores of Intel Xeon Gold 6130 CPUs, and ResNet models were trained on an nVidia GeForce GTX 2080 GPU.

heading: 3.1 COIL-100 OBJECT RECOGNITION

text:
Columbia Object Image Library (COIL-100) is a common dataset used for basic object recognition (Nene et al., 1996). It contains RGB color images of 100 different objects, each photographed 72 times at 5 deg increments about the vertical axis. Background details were removed in all images and the objects are centered and enlarged to fill the frame. Some objects contained in this dataset include coffee mugs, small toy cars, and various fruits and vegetables.
The SVMnet in this experiment used one layer with a 25 × 25 window (giving each SVM 1875 input features) and a stride length of 7, followed by a weighted vote with dropout. The SVMnet and ResNet models were fitted with 100-500 training images in increments of 100, each controlled to have an equal number of samples from each object. A separate subset of 200 images was used as validation data for ResNet models.
Figure 3 shows the results of this experiment. When fitted on the smallest training set, containing only one example per object, SVMnet correctly predicted labels for over 60% of the remaining images. With the same training set, ResNet-50 showed about the same accuracy and only pretrained ResNet-34 exceeded SVMnet; however, SVMnet was significantly faster to train in all cases.

heading: 3.2 IMAGENETTE

text:
Imagenette is a fairly small, 10-class subset of the ImageNet dataset (Howard). Several versions of this dataset exist; here we use version 2 of the 160 px dataset with noiseless labels. Many of these images are rectangular with their shortest side scaled to 160 px. In this experiment, we symmetrically zero-pad each image along its shorter axis to make it square, then downscale the images to have the same dimensions of 160 × 160 px. The SVMnet used here contains one layer with a window size of 22 and stride length 7, followed by a weighted vote with no dropout. Imagenette is pre-divided into training and testing subsets containing 9,469 and 3,925 images, respectively. Models were trained using 20, 40, 80, 160, and
320 images from the provided training set and evaluated using the provided testing set. An additional 100 images were selected from the training set as validation data for the ResNet models.
Figure 4 shows the results of this experiment. SVMnet achieved higher accuracy than all ResNet models for all training sets except the largest, where the ResNet-50 model pretrained with ImageNet weights improved drastically. The generally low accuracy of these models could be explained by the method used to conform each image to the same dimensions, which introduces a significant amount of empty space in many images. However, even under these conditions, SVMnet attained the highest accuracy in the least time for the smaller training sets.

heading: 3.3 COVID-19 RADIOGRAPHY

text:
During the COVID-19 pandemic, machine learning techniques have been applied to various kinds of data to assist the medical community in making accurate diagnoses (El-Din Hemdan et al., 2020; Gangloff et al., 2021; Li et al., 2020). During the early stages of a disease outbreak, diagnostic data is expected to be limited or sparse, making it difficult to train most kinds of machine learning models. A type of model capable of learning from a small number of samples would be the most effective in this time frame.
Here we apply SVMnet to a database of chest x-ray images from healthy patients and patients diagnosed with COVID-19 (Chowdhury et al., 2020; Rahman et al., 2021). In this experiment, only the images labeled as ”Normal” and ”COVID” are used. Images were downscaled to 128×128 pixels (approx. 43% of the original size). An equal number of images were selected from each class, totaling 7232 samples. Models were fitted with 10, 20, 50, 100, and 200 training samples, with 50 separate images used as validation data for the ResNet models. The SVMnet uses two layers: the first with window size 19, stride 7, and class probability outputs; the second with window size 5 and stride 5, followed by an unweighted vote. During the architecture experiments described in Section 3.7, the 2-layer SVMnet was shown to outperform the 1-layer models for this dataset.
Figure 5 shows the results of this experiment. SVMnet was able to correctly label between 64% and 78% of unseen x-rays depending on the number of training samples, but most ResNet models failed to make significantly accurate predictions. Only the 18- and 34-layer ResNet models trained from scratch approached the accuracy of SVMnet. Additionally, SVMnet was several times faster to train.

heading: 3.4 ASTRONOMICAL IMAGE DATA

text:
To test the performance of SVMnet on a current real-world image classification problem, a dataset of galaxy images from the Panoramic Survey Telescope and Rapid Response System (Pan-STARRS) was used. The dataset is made of galaxies separated into elliptical and spiral morphology. The galaxy images were taken from the catalog of Pan-STARRS galaxies classified by their morphological type (Goddard & Shamir, 2020).
An equal number of images were selected of each morphological type, totaling 26,732 samples. Each image is grayscale and has a dimension of 120 × 120 px. SVMnet and ResNet models were fitted with 10, 20, 40, 80, 160, and 320 training samples, with 200 separate images used as validation data for the ResNet models. The SVMnet uses one layer with a window size of 22 and stride 5, followed by a weighted vote with dropout.
Figure 6 shows the results of this experiment. As the graph shows, SVMnet outperformed almost every ResNet model when trained with a relatively small dataset. The models generally improve as the training set grows, with several ResNets slightly overtaking SVMnet with the largest training set. In all cases, SVMnet finished training many times faster than all ResNet models.

heading: 3.5 WND-CHARM

text: To test a ”traditional” approach of using an SVM after extracting image features, we used the WNDCHARM open source feature set (Shamir et al., 2008) combined with an SVM with linear kernel implemented through SVMLib. Table 1 compares the test set accuracy of WND-CHARM and SVMnet using the experimental datasets described earlier in this Section. WND-CHARM was trained on equal sized training subsets and consistently showed lower classification accuracy than SVMnet under the same conditions.

heading: 3.6 COMPUTATIONAL COMPLEXITY

text:
The complexity of fitting an SVM is asymptotic and polynomial. For a training set containing n samples, the algorithm is dominated by either an n2 term or an n3 term based on the formulation of the problem (Bottou & Lin, 2007). Therefore, training a large number of SVMs can be a computationally demanding task, and can lead to substantial computational complexity during training.
The number of SVMs N in a layer receiving rectangular input with width Ix and height Iy is given by Equation 2. The window size W (equivalent to the kernel size in other CNN literature), stride length S, and padding amount P in their respective dimensions follow from standard convolutional arithmetic.
N =
( Ix + 2Px −Wx
Sx + 1
) · ( Iy + 2Py −Wy
Sy + 1
) (2)
Fitting a layer in SVMnet requires fitting N SVMs - a polynomial time operation. If the layer includes weights, then the SVMs must predict a class label for each input during the fit step, which scales linearly with the number of samples n. When using dropout as described in Section 2.1, SVMnet performs an additional step during training that scales linearly with n. Thus, fitting SVMnet is dominated by the polynomial fit time of the SVMs.
CNNs can theoretically be trained infinitely, but there is a definitive point at which the SVMs within SVMnet converge. This places a soft upper bound on the training time of SVMnet based on the tolerance parameter of the SVMs. Additionally, a firm upper bound may be placed on the number of iterations of the SVM algorithm, allowing for a shortened training time at the expense of some accuracy.
SVMnet trains multiple SVMs simultaneously using process-based parallelism and shared memory, greatly increasing its speed on typical multicore computers with minimal overhead. While this
allows SVMnet to run quite easily on relatively inexpensive systems, the potential performance gain from extra hardware is minimal compared to the extreme optimization of CNNs for GPU devices.

heading: 3.6.1 INFERENCE TIME OF IMAGE CLASSIFICATION

text:
Predicting a single class label of an image using SVMnet typically requires a large number of individual SVMs to predict a label followed by a vote tally. Despite its affinity for parallelization, this process is expected to take longer than the highly optimized matrix operations of a CNN. Table 2 compares the inference time of SVMnet and ResNet on images in the COIL-100 dataset.
The comparison shows that SVMnet is significantly slower than ResNet for classifying samples, but the speed of classification is still practical for many real-world systems. The parallelization of SVMnet greatly reduces the time needed to make predictions, but the overhead of shared memory operations is significant in the case of few samples.

heading: 3.7 ARCHITECTURE COMPARISON

text:
As with CNNs, SVMnet can be configured into a variety of architectures which are expected to differ in performance depending on the classification task. Due to the high number of possible models, determining which is the most effective for a single task is non-trivial. In this section we show how a variety of SVMnet configurations were tested on the COIL-100 dataset to inform the choice of model used in Section 3.1. Similar methods were used to select the models for other datasets. SVMnet models with multiple layers were tested in the same manner.
Figure 7 shows how the performance of a one-layer SVMnet changes with the window size, stride length, voting method, and number of training samples when fitted to COIL-100. Prediction accuracy improves in all cases as the window size increases but with diminishing returns. Increasing the stride length tends to lower accuracy when the window is small but incurs little to no penalty when the window is large. When the vote of an SVM is weighted, model accuracy improves in all cases compared to an unweighted vote; performance increases further when using dropout as described in Section 2.1. This effect is more significant when the window size is small.

heading: 4 CONCLUSION

text:
Deep convolutional neural networks provide excellent performance in automatic classification of image data while eliminating the need to develop and tailor algorithms for specific image classification problems. With the availability of libraries, DCNNs have become the de facto first solution to image classification.
Here we explore one of the primary weaknesses of DCNNs, which is the need of a relatively high number of labeled “ground truth” samples for effective training of the network. While DCNNs are often tested on relatively large datasets such as MNIST or ImageNet, in many real-world problems a very large number of clean labeled samples that can be used for training is not available.
In many other cases labeled training samples are not available. For instance, when analyzing archaeological artifacts, the number of training samples are limited by the number of available artifacts, which is a hard limit that cannot be easily changed. Using computer vision to analyze art (Khan et al., 2014) is limited by the number of paintings each artists created, which can be a firm limit, especially when the painter is no longer alive.
SVMnet aims at providing an effective solution for the numerous real-world situations in which the number of labeled image samples that can be used for training is limited. SVMnet utilizes the ability of an SVM to learn from a smaller number of samples compared to other machine learning approaches. The flexible structure of SVMnet allows it to learn directly from the pixel values, and to utilize different layers that correspond to the convolutional and fully connected layers in “conventional” deep neural networks. Like DCNNs, SVMnet does not require the design of specific algorithm for a specific image classification problem.
The proposed approach is structured as a network to take advantage of the stronger signal from neighboring pixels, similar to the core idea in the basis of CNNs. SVMs are known for their ability to learn quickly from relatively few training samples. By training many SVMs on small pixel regions across an image, this quick learning can be leveraged to extract much information from small sets of images in less time than it would take to fully train a deep neural network.
Complexity analysis shows that the training time for SVMnet scales more quickly with the number of input samples than DCNNs, suggesting that SVMnet might take substantial computational resources when trained using large datasets. However, SVMnet is designed for situations in which the labeled training set is relatively small. As shown in our experiments, the training time might not be a practical obstacle in many real-world situations in which SVMnet can be used. While computing is an available resource, and training SVMnet with a few hundred training samples scales within reasonable response time, annotated clean or rare training samples might in many cased be much more difficult to obtain.
The underlying structure used to create SVMnet is very flexible, allowing other kinds of machine learning algorithms to be used rather than solely SVMs. Constructing the layers with classifiers such as random forests or logistic regression may result in better performance for some datasets. These layers can be mixed in the same model as well, i.e. using one layer of SVMs followed by a layer of random forests. These possibilities present a promising avenue for future related work.
SVMnet is not designed to become a general solution that can outperform deep convolutional neural networks such as ResNet-50, but experimental results show that it is an effective solution for cases in which the number of labeled training samples is small. Since such cases are not rare, SVMnet can complement “conventional” deep neural networks by providing image classification in the cases where not many labeled training samples are available.

heading: ACKNOWLEDGEMENTS

text: The research was funded by NSF grant number XXXXXX.

title: SVMNET: NON-PARAMETRIC IMAGE CLASSIFICATION BASED ON CONVOLUTIONAL SVM ENSEMBLES FOR SMALL TRAINING SETS