A Globally Convergent Algorithm for Neural Network Parameter Optimization Based on Difference-of-Convex Functions
Authors: Daniel Tschernutter
Mathias Kraus
Stefan Feuerriegel
Venue: Accepted by TMLR ()

Abstract: We propose an algorithm for optimizing the parameters of single hidden layer neural networks.
Specifically, we derive a blockwise difference-of-convex (DC) functions representation
of the objective function. Based on the latter, we propose a block coordinate descent (BCD)
approach that we combine with a tailored difference-of-convex functions algorithm (DCA).
We prove global convergence of the proposed algorithm. Furthermore, we mathematically
analyze the convergence rate of parameters and the convergence rate in value (i.e., the training
loss). We give conditions under which our algorithm converges linearly or even faster
depending on the local shape of the loss function. We confirm our theoretical derivations
numerically and compare our algorithm against state-of-the-art gradient-based solvers in
terms of both training loss and test loss.

Published in Transactions on Machine Learning Research (01/2024)
A Globally Convergent Algorithm for Neural Network Param- eter Optimization Based on Difference-of-Convex Functions
Daniel Tschernutter
dtschernutterretha..ch
ETH Zurich
Mathias Kraus
mathiaa.krauss@oou..
PAU
& ETH Zurich
Stefan Feuerriegel
feuerricgel@lmaa.de
Munich Center for Machine Learning 8 LMU Munich
Reviewed on OpenReview: https: // openreview. net/ forum? id= EDqCY6shbr
Abstract
We propose an algorithm for optimizing the parameters of single hidden layer neural net- works. Specifically, derive blockwise lffference-of-convee (DC) functions representation of the objective function. Based on the latter, we propose a block coordinate descent (BCD) approach that we combine with a tailored difference-of-convex functions algorithm (DCA). We prove global convergence of the proposed algorithm. Furthermore, we mathernatical ically analyze the convergence rate of parameters and the convergence rate in value (i. e., the train- ing loss). We give conditions under which our algorithm converges lincarly or even faster depending the local shape of the loss function. We confirm theoretical derivations numerically and compare algorithm against satt--of-theaan gradient tradient-based solvers in terms of both training loss and test loss.
1 Introduction
Neural networks have emerged as powerful machine lcarning models for applications in operations rescarch and management science. A particular class of neural networks are single hidden layer feedforward neural networks (SLFNss). This class offers large flexibility in modeling relationships between input and output and, therefore, is used in several domains such as transportation (Celikoglu Silgu 2016), risk analysis (Sirignano & Giesecke 2019), pricing (Haugh & Kogan 2004), and healthcare (Lee al. 2013).
SLFNs have several properties that make them relevant for both machine learning practice and theory. In machine learning practice, they have been found to be effective in tasks with mid-sized datasets (i.e., hundreds or thousands of samples). In machine learning theory, SLFNs entail favorable properties. For instance, SLFNs have been shown to be universal approximators. As such, SLFNs are able to approximate continuuu functions arbitrarily well on compact sets given a sufficient. number of hidden neurons (Hornik SLFNs in regression tasks has been investigated further,
et al. 1989). Only recently, the expressiveness and it was shown that there always exists a set of parameters such that the empirical mean squared error is zero, as long as the number of hidden neurons is larger than a finite bound depending solely on the number of training examples and the number of covariates (Zhang et al., 2021p. The simple structure of SLFNs oflentimes also allows to derive theoretical properties in downstream tasks. For instance, in option pricing, SLENs can be used for approximating value functions in approximate dynamic programming to derive tight bounds for option prices (Haugh & Kogan 2004). In financial risk analysis, SLFNs can be used to predict conditional transition probabilities in discrete-time models, where SLFNs allow one to derive a law of large numbers and a central limit theorem for pool-level risks (Sirignano Giesocke 2019

---

Published in Transactions on Machine Learning Research (01/2024)
This work considers the parameter optimization in single hidden layer feedforward neural networks with activation function o(-) max and N hidden units to predict target variables Vj E IR from samples 2j E I2,, j= ....,, m. The parameters are determined via the optimization problem
m Σ
inf W.D.
(Wa + b)) uz)² + Reg(a, W,,), ==1
(PNN)
MT
where the objective is to find optimal parameters E RN W E RNN, and b E RN. The first term in PNNN represents the mean squared error, while Reg is a regularization term with regularization parameter 7 0. In machine learning, a common regularization technique is weight decay, e., Reg favors smaller weights. The activation function allows for feature selection by activating or deactivating neurons in the hidden layer. In particular, the rectified linear unit (ReLU), as defined by a, results in sparse feature representations GGloro et al.] 20011, which has shown to improve predictive performance, making common choice machine learning practice (LeCun et al., 2015). From a theoretical point of view, the above optimization problem entails the following characteristics: (i) The objective function is highly non-convex; (ii) the objective function is non-differentiable; and (iii) the optimization problem is nigh--dimensionll. These characteristics make the optimization problem difficult to solve.
Previous optimization methods for the above task have primarily been gradient-based; see Section 2 for an overview. Foremost, stochastic gradient descent (SGD) and variants thereof (e. g., using momentum) are appliod to optimize noural networks. However, gradient-based methods do not have general convergence guarantees, and require expert knowledge during training due to many hyperparameters (e. 8-, initial learning rate, momentum). Only recently, methods that do not rely on gradient information have been proposed
(e. g.g Lau et al. 2018 Zeng et al. 2019 Zhang & Brand 2017). Here, optimization methods based on block coordinate descent (BCD) and alternating direction method of multipliers (ADMM) have been proposed for optimizing parameters in neural networks. However, previous approaches merely optimize over surrogate losses instead of the original loss or lack convergence guarantees.
In this paper, we propose a globally-convergent algorithm for parameter optimization in SLFNs. Our al- gorithm named DCON builds upon differrence-o-cconvex (DC) functions optimization and further follows block coordinate descent approach, where, on each block, the objective function is decomposed as a difference of convex functions. Optimizing over these blocks results in subproblemss, which are either already convex or can be approached with a tailored difference-of-convee functions algorithm (DCA). For an introduction to DCA, see Le An & Tao (005). We provide a theoretical analysis of our algorithm. First, we prove global convergence in value and to siniting-critical points (under additional assumptions). Second, we derive theoretical convergence rates, and, third, we give conditions under which our algorithm DCON converges against global minima. We want to point out that global convergence does not mean convergence to global minima. Global convergence is the convergence independent of starting points and, hence, in case, independent of weight. inilialization. See also Lanckriet & Sriperumbudur (2009) for the definition of global convergence.
Our work contributes to machine learning theory in the following ways:
1. We show that our algorithm converges globally ei. independently of weight initial- izations) in value and, under additional assumptions, to limiting-crilical points.
2. We give conditions under which the training loss converges with order q N. That is, the training loss defined in (PNN) can achieve very fast convergence depending the local shape of the loss function.
3. We compare DCON against Adam (Kingma Ba 2014h as a slate-of-the-ard gradient- based optimizer. Our evaluation on nine datasets from the UCI machine learning repository and the MNIST datasct shows that DCON achieves superior prodiction performance.
DCON offers key benefit for machine learning practice. DCON works without any hyperparameters during training. In particular, hyperparameters that are ot common in gradient- solvers (e. g-, learning
2

---

Published in Transactions on Machine Learning Research (01/2024)
rates, number of training epochs, momentum) are absent. Hence, given the number of hidden neurons and the regularization parameter in the SLFN, one can perform the training task in completely automated manner. Nevertheless, future work is needed to scale DCON to larger datasets in practice. We point to potential research directions in our discussion.
The rest of the paper is structured as follows. In Section 2 we discuss previous research on optimization
methods for neural networks. Section 3 analyzes the optimization problem in (PNN) with regard to neces- introduces our novel training algorithm DCON, while, in Section [ we derive global convergence results and theoretical properties of DCON. In Section D we perform nu- merical experiments to compare DCON against statc-of-the-art optimization methods and demonstrate the convergence behavior. Finally, Section 7 concludes.
sary optimality conditions. Section g
2 Background
We contextualize our contribution within the literature on optimization methods for (PNN) Previous research can be loosely grouped into methods for (i) direct loss optimization and (ii) surrogate loss optimization.
Direct loss optimization: Algorithms that directly optimize the loss function can be divided into gradient- based and gradient- frree methods.
Gradient-based mothods make use of backpropagation (Rumelhart et al. 1986) to compute gradients of the loss function. The underlying basis is given by stochastic gradienl descent (SGD) proposed by Robbins &
Monro [951]. Several adaptive variants of vanilla SGD have been developed in recent years. Examples
are Adam KKngmaa & Ba. 2014), AdaGrad (Duchi et al.) 2011), RMSProp (Tijmen & Hinton 2012 and
AMSGrad [Rdddi et al.) 2018). Despite the tremendous success of SGD in optimizing neural network
parameters, a general convergence theory is still lacking. A broad stream of literature provides theoret
guarantees for SGD or variants thereof under fairly restrictive assumptions (Chen et al.] [020 Chizat et al.
2019
Du ct a 2019a b Li & Liang. 2018 Liang al.) [021 Zeyuan al., 2019 Zou & Gu 2019 Zou et al.
2020
Therein, the authors foremost assume some kind of over-parameetiizatoon i. e., the number of hidden
units N has to increase in linear (Liang et al.) 2021
polynomial (Du et al., 2019a by Li & Liang
2018
Zeyuan et al.] 2019 Zou & Gu 2019 Zou et al. 2020) or poly-logarithmic (Chen et al. 2020) order of the number of training samples m. For instance, in Du et al. (2019b), convergence is guaranteed if, among other assumptions, N = (m))) Other works make assumptions on the distribution of the input data or rely on diffcrentiability assumptions, i. c., smooth neural networks and smooth losses (Chizat et al. 2019). Of note, the analyses in Chen et al. (2020); Li & Liang (2018): Liang et al. (2021), and Zou et al. (2020) are restricted to classification tasks, while we are interested in a regression task. The aim of the aforementioned theoretical works is to answer the question of why neural networks are so successful in non-convex high-dimensional problems, rather than developing a unified convergence theory. Noteworthy, the analysis in Davis et al. (2020) establishes the subsequence convergence of SGD on tame functions. In contrast, our algorithm establishes the convergence of the whole sequence of parameters under certain assumptions. According to [Zeng et al.
(2019), this gap between the subsequence convergence and the convergence of the whole sequence comes from the fact that SGD can only achieve a descent. property (see Assumption F in Davis et al. (2220)) ) while we prove that our algorithm achieves a sufficient descent property.
Gradient-free free methods refrain from using first-order information and deal differently with the undesired characteristics of the objective function. One stream of research focuses on so-called extreme learning machines (Huang et al. 2006). Their idea is to merely sample the weights and intercepts associated with the input layer from a given probability distribution and then solve a linear least squares problem to derive the weights associated with the hidden layer. Extreme learning machines are used in various applications, yet. they do not solve (PNN) but instead only act a heuristic. Recently, Pilanci & Ergen (220)) showed that there exists convex problem with identical optimal values (PNN), from which optimal solutions to PNN can be derived. Consequently, this would give global optimum. However, this work should be seen
NNot that over-parametrization would require neural networks with a very large number of neurons, c. g., thousands of neurons for datasets with only a thousand training examples.
3

---

Published in Transactions on Machine Learning Research (01/2024)
purely theoretical contribution as the computational complexity of their algorithm scales exponentially in the number of inputs n.
Surrogate loss optimization: Another stream of research does not solve (PNN) directly, but uses a BCD or ADMM approach after replacing the objective with a surrogate loss. Both BCD and ADMM rely on a so-called two-splitting (e. g., Perreiaa-Perpinan & Wang 2014 Zhang & Brand 2017 or three- splitting formulation (e. g., Lau et al., [2018] [Taylor et al.] 2016): The underlying idea to introduce auxiliary coordinates for each datapoint and each hidden unit. These auxiliary coordinates appear equality constraints in the optimization problem of the neural network. However, these equality constraints lead to an intractable optimization problem, these approaches involve an alternative formulation of (PNN) in which an additional penalty term is required to enforce the equality constraints. The resulting formulation then allows one to optimize iteratively over different variable blocks, resulting in easier (and often convex)
subproblems (Askari et al. 2018 Lau et al.) 2018 Zhang & Brand 2017). As a result, is oftentimes possible to prove global convergence for these approaches (Zeng et al., 2019). However, such surrogate losses
for PNN lead to decreased performance in comparison to gradient- brasee solvers (Askari al. 2018 Lau
et al. 2018 or neural networks that cannot be evaluated at test time (Zhang & Brand 2017).
Other works derive efficient training algorithms for upper bounds of the loss function; see, c. g., Berrada et al. (2017). The latter also relies on a DC representation of the objective function. However, while the algorithm converges in value, a thorough convergence analysis of parameters missing. Only recently, [Miskkin et al. (2022) proposed a training algorithm for SLFNs with ReLU activation using convex optimization. However, their approach uses a convex reformulation (C-ReLU) of (PNN) that only equivalent to (PNN) under additional assumption (c. g., among others again sufficiently large number of hidden neurons), and then solves a surrogate problem (C-GReLU) involving different activation function, so-called gated ReLU, that is again only approximately solving (C-ReLU) and thus PPNN).
In sum, there is a large number of research papers that study the training of neural networks. However, to the best of our knowledge, we are the first that present an algorithm that (i) directly solves (PNN). (ii) is scalable to mid-sized datasets, and (iii) has general global convergence guarantees, i. e., does not rely on any kind of paramerrization.
3
Optimization Problem
In this section, formalize the optimization problem and discuss necessary optimality conditions.
3.1 Problem Statement
Given set of training samples consisting of covariate vectors Tj R and target variables yj R. j= I,..,, m, the objective is to optimize the parameters of a SLFN with N neurons in the hidden layer and ReL. activation 0, as given in (PNN). Tet w, E IR" and b, E l,..,. N, denote the weights and intercepts associated with the input layer, and let a; E R, i= 1,..., N, denote the weights associated with the hidden layer. All trainable parameters are given by f = (a, W,b) E R where N = 2n+ We denote the ovjective function in (PNN by RegLoss,, (0) = Loss(0) + 7 Reg(O), where Loss (0) is the mean squared error loss from (PNN) defined as
Loss(0) Σ
m
Vj
Σ
N
a ((w, +b1)
(1)
and Reg(f) is a weig-ted egregulaarizatin defined by
Σ N
Rog(O) = m
1
(w0,, + bx)2
1 + m |all
(2)
For convenience, we introduce a matrix M 1=+( which refers to the matrix with rows formed by the covariate vectors with an additional one for the bias, i.e. (... 1) for j {I,...,m] m). Using the
4

---

Published in Transactions on Machine Learning Research (01/2024)
above definition of M, Equation (2) can be written
M
Wi
||al| This form of regularization
has two main advantages in derivations later (i) it allows to derive convenient DC structure of the objective function, and (ii) it allows for a closed-form solution of the sub-gradients needed in our DCA
routine. Nevertheless, it merely corresponds to standard lz ry-reuularization with an additional weight matrix
M
3.2 Necessary Optimality Conditions
We first prove the existence of solution to PNNN
Proposition 1 (Existence of solution). Let M M > 0. That is, the smallest singular value of M denoted by miin (M) is greater than zero, i. e., mmin (M) > 0. Then, there ewists at least one solution to (PNN).
Proof. See Appendia: A
Next, we present a necessary optimality condition. Note that the loss function in neural network parameter optimization is, as in our case, usually not differentiable the classical sense. Hence, to state necessary optimality conditions for solutions to (PNN), we draw upon the concept of limiting subdifferentials. For a detailed introduction, we refer to Penot (2012).
Definition (Limiting subdifferential). Let f RV + R U foo), The Fréchet subdifferential of f at x dom(f), denoted by a= f(x), is given by the set of vectors RR
which satisfy
lim g
| vll (1() - ((x) (v,0 x)) 0.
(3)
If x & dom(ff, we set oF f(x) = 0. Then, the limiting subdifferential of at x E dom(f), denoted by oh f(x), is define as
04 f(z) = f RR 3z + x. f( + f( f(x*) ( θ v + te.
(4)
Definition [ provides generalized notion of critical point. Based on it, state the following necessary optimality condition.
Remark 1 (Necessary optimality condition). A necessory condition for 0* E RV to be solution to PNN is 0 E o RegLoss, For details, see Attouch et al. (2013) and the references therein.
Such point H* is called limiting-critiall, or simply critical. Besides the need for generalized notion of critical points, the lack of differentiability is also challenging when comes to analyzing the local behavior of functions. To derive an algorithm that converges towards critical points, we need a notion of how our objective function behaves near critical points. For this, we make use of the so-called Kurdyka- Kurdyka-Lojasievice Lojasiewicz (KL) property. The KE property is valuable tool in the context of optimization, as allows to reparameterize the function locally. The KE property defined follows (Attouhh al. 2013).
Definition 2 Seurdykaa-Fojaiiewee property). A proper lower semicontinuous function f RR. - R (oo) fulfills the Kurtyka-Lojasieus Lojasiewicz property at a point <oom(8 (aL f) if there exists an n E (0, oo], neighbor-
hood Un- of x", and continuous concave function 4p [0. R4 such that
NNot that the standard lerreuulrrizrr is given by term 12. while regularization term merely uses different energy- That is, regularizer can be seen ||0| B/2 for certain positive definite matrix given by
MT
D
0
MT M
0
B
0
0
M M
0
0
5

---

Published in Transactions on Machine Learning Research (01/2024)
1. ((0) =0,
v is C¹ on (0,7),
8. Vs E (0, ('(8) > 0,
4. Vo U. n (<(=)<><<+<>>)))>)
<5 <)< +1] ('([(z) - [(x)) d0 (0,00)))))) 2 1 (KE inequality).
A proper lower semicontinuous function f : Rn + R U (xo} which fulfills the Kurdyka- Lorjsika-Lojssewiicc properly at each point x² dom(@k f) is called KL function.
In the next section, we derive an algorithm for which we later prove that it converges to a cumiting-critical point of RegLoss,
4 DCON Algorithm
The idea behind our DCON algorithm is to show that the loss can be partly decomposed as a DC function. For this, we show that, for certain subsets the parameters 0, i.e., blocks, RegLoss, can be written as the difference of convex functions. Specifically, we use a BCD approach which we loop over different blocks Bt, - 1,,,..,, N. In each block, yield DC subproblem. The DC subproblem is then (approximately) solved via tailored DCA. The latter involves series of convex problems and is thus computationally efficient. After looping over all blocks B₁, the remaining variables in 0 form an additional block Ba, which is approached in the alpha subproblem. The alpha subproblem is already convex and can thus be solved efficiently. For better understanding, we visualized the subproblems in Appendix B.T
4.1 Derivation of Subproblems in BCD
In Proposition we show that RegLoss,, is DC function if we consider only weights wy mapping to the I-th hidden neuron and its intercept b,, and derive an explicit DC decomposition that later on allows for efficient subgradient computations.
Proposition 2. For fixed (ws) (be)s and (as) the loss can be written in the form
RegLoss, (a, b) RegLoss, (wi, bi) a + gr(u,, bi) he(wr, bt),
(5)
where Ct E RR is constant and the functions and tu are corver in (wi, bi). Both gi and hu are given by gi (w b1)
m7
m
at
8 o(wi, xz)) + bi)
(wn,, xÿ} + 6z)
(6)
m
7 (wwi, r.)) + bb)
+
m
j=1
hu bi)
Σ
B a ((w), + bi).
(8)
1=1
with non-negative weights 89th and shy. Furthermore, on implies 8 = =gah for all j E ,
m).
Proof. See Appendia B
With the DC decomposition from Proposition 2 we
DCA to address the corresponding subproblems. When looping over all B₁ (w,, bi), the only weights that are not updated are the weights ag == 1...., N of the hidden layer. Hence, in a last step, we hold all weights constant except for a, which results in a regularized linear least squares problem; see Proposition 3
Proposition 3. For fized (wi) and (b;) No the loss can be written in the form
RegLoss, (a, W,b) = RegLoss, (a) = ca + m
1ly Eall +
Y a Io.
(9)
m

---

Published in Transactions on Machine Learning Research (01/2024)
where Ca E IR is constant, I E BNNN is the identity matriz, y is the vector of target variables, is the vector of weights associaled with the hidden layer, and E E TRmxN is the matrix with entries Eji a o((w;, Rz) + bi) for j E {I,...,m, m) and E (1)
Proof. See Appendir B
Based on the above propositions, we can now optimize RegLoss, via a block coordinate descent approach where the blocks are given by Br (wr,br) for I E (I,...,N) with objective function Op (wi, bi) gr(wr, bı) - hu bt), and Ba = with objective function (a)a) m lly - Eall + a Ia. We thus define the following subproblems:
DC subproblems: The 1-th DC subproblem is defined
inf Op bi)-
(DC))
wy bz
alpha subproblem: The alpha subproblem is defined as
inf (*(a).
(A)
In the following section, we show how both DC and are (approximately) solved within the BCD approach.
4.2
Solution of Subproblems in BCD
We now derive efficient procedures to (approximately) solve the defined subproblems g
4.2.1
Approximate Solution of DC Subproblems.
The DC subproblems DC,
approached with tailored DCA. For introduction to DCA, refer to Le An & Tao (2005). First, we note that a = 0 implics that the corresponding DC subproblem reduces to
inf Σ 2 m ((wi, x + b2),, where solution is given by (wi, bt) 0. Hence, for the rest the section, we wi,bi
assume that as + 0. Following Le An & Tao (2005), the DCA routine for the I-th DC subproblem is
yk ahi((w), b()).
(10)
(w/+1 1 Ogi (vtt)
(11)
until the norm of successive iterates is sufficiently small (see Proposition 7 later on), and where (w,, 69) is given initial solution. Therein, the convex conjugate is defined as (" sup,, (y" f()) (see, e. g-: Borwein & Lewis (2006)) There are two steps that remain to be shown: (i) How to find an element in the subgradient of hy in Equation (1) (ii) How to find an element in the subgradient of the convex
conjugate of gi in Equation I Both are addressed in the following.
For (i), an element in dh; can derived analytically. This is stated in Proposition Proposition 4. For any (wi, bi), we have that
m
Z (1)))
H
Wi bi
ahy bt),
(12)
where H is the Heaviside function, i. e., H(x) for 2 0 and zero otherwise.
Proof. See Appendia B
Note that we use 8" to denote the subgradient h; to adhere to standard notation in the DCA literature. should not be confused with the target values demoted by y.

---

Published in Transactions on Machine Learning Research (01/2024)
Notably, Equation
12 gives the unique gradient of h4 if (ww,b))) (æy, 1)) + for all j {1,................ (1....,m).
For (ii), we first have to derive the convex conjugate of However, computing the convex conjugate involves an optimization problem itself, which makes it sometimes difficult to find a closed-form representation. In our case, it is possible to write of as the difference a characteristic function and the value function of positive semidefinite quadratic program. For notation, let xo denote the characteristic function of a set Q, e., Xn(x) oo for & Q and zero else. It will turn out that this difference is very convenient representation. All details are stated in Proposition 5]
Proposition 5. Let at + The convez conjugate gi of gi given by
gi (i')") xx =x(
(13)
where Ω = ker(M)* for M as defined in Section program
3.1 and E Ra+1 + IR is the value function of the quadratic
1 inf (gg 1) 3 Qi s.t. Av = 0 and v 2
(QP)
2
for qy- 12m+2(n+1), sparse block tridiagonal positive semidefinite matrir Qi with Q e depending solely on, and full rank matrix A B=x2m++(n41) independent of y" and ar Purthermore, we have dom(g;) Ω.
I
Proof. See Appendix B
In the finite case, the dependency of of on y² is only present in the lincar term (gy', u), and -E, can be seen as a supremum of convex functions over the general index set V= E B2m++2n+11) -A = and 2 0}. That is, a subgradient of gf can be obtained by standard subdifferential calculus techniques (see, e. e.g. Hiriart- Hiriart-Urruty Lemaréchal] 2004). For this, we need mild assumption.
Assumption 1. We assume that for all p E (1,...,n+11) there erists a solution Ap to MT = Ep, where Ep is the p-th cunonical basis vector. This is equivalent assuming that MT M as in Proposition
Assumption is usually fulfilled enough data are provided. Given that the above holds, we can now derive closcd-form solution of an element in Ögī (v*). This is detailed Proposition G
Proposition 6. Let on + O and yy E dom(gi). Purthermore, let By be a corresponding solution to QP with Uy- (uyr, ug-, u vgg)). then
AT
0
AT
0
0,
++1
eg. e "gg()""
(14)
AT a+1
o
0
m+1
where On+1 is the zero vector in Ra+1
Proof. See Appendir B.
In sum, the first DCA step from Equation (10) can be performed efficiently by evaluating Equation 12 The second DCA step from Equation [11p requires that one solves a positive semi-definite quadratic program, which can be done efficiently by out-of-the- box solvers for convex programming. Later, we also present an ADMM-basod approach that leverages the special form of the matrix Qi to derive a scalable solver for (QP).
In the following, we analyze the convergence behavior of the DCA routine for the DC subproblem; see Proposition 7
Proposition 7. The DCA routine (see 10 and 11 with vi given in 12 and (wo-11 _b/+1) as given in [4] converges in finitely many ileratoon to points (u',, (wi bf)) [gg[w? dhu(w b7)] x (0gī (v*) ah (y }). Purthermore, there cxists upper bound
the number of ilerations Kmna E EN depending solely on the number of training samples m, and (wi, bf) is local solution of (DC. if Ei(r") S Ei(y) for all
E Ohy The latter condition is equivalent to Ohi(wi. bt) S (w) Proof. See Appendia B.
8

---

Published in Transactions on Machine Learning Research (01/2024)
Note that the condition E,(r") < (1) for all E Öhr(ws bb) holds if Ohr(ws. bf) is singleton. That is, for instance, if (ww (m.. 1)) # for all j E (1,...,m) m), we have that (wi, Dj) is a local solution of (DC] For the rest of this paper, we make the following assumption.
Assumption 2. We ossume that our DCA routine always converges to point 0g((w, bi), i. e., local solution of (DC.).
with (hr(w] b7)
Note that this assumption is merely made for convenience, as we can always ensure that ah bbf S (gi("i w holds by simple restart procedure following Tao & An 1998). We provide such procedure in Appendix B.S
4.2.2 Solution of Alpha Subproblem.
To derive solution of A we introduce the matrix H = - Then, by ignoring constant terms, (A
is oquivalent to the quadratic program inf a H.a - y, a). Note that the objective is strictly convex.
Hence, the unique solution of (A) is given by the solution of the linear system H1, Σ.
4.3 Pseudocode
We now combine derivations into the DCON algorithm for optimizing single hidden layer neural network parameters (see Algorithm []. In the pseudocode, let DCA(3" 8h,, (w, b), refer to the DCA subroutine for the 1-th DC subproblem DC. with a given initial solution (w,, b). weights f and ghi and a maximum number of K. iterations. Further, let LS(E) refer to the solver of A with system matrix Σ.
The algorithm proceeds as follows. line I the neural network parameters are initialized via the Xavier initialization (Glorot Bengio 2010). The idca is then to approach all DC subproblems a randomizod order starting from the current weights (see lines 10 and, afterward, solve the alpha subproblem in each outer iteration (see lines 13 After each subproblem solution, the new weights are inserted into the parameter vector 0. This results in new parameter vector 0 after each outer iteration (line [4] Randomization is accomplished by sampling random permutations æ of the set [1....,N) from the set of all permutations denoted by Sv; see line 3
Algorithm 1: DCON
Input: Number of iterations M, maximum number of DCA iterations K. Output: Neural network parameters Initialize weights 0 via Xavier initialization 0....;M do Choose random permutation E Sy
for f =_..... do
/- Construst (-th DC subproblen Set 1- =(j)
5.
Get, initial weights and interoept for subprohlem from parameter vector (u) ; bf) GotWoights
Compute , gh1 + ComputeBetas(@.
/s DCA for DC subproblen
(u/tt1,// [++))+= e DCA(821, ,8 (wf b(),,
Update parameter end
Insgrr of +,)+)
/e Construct alpha subproblem
Get weights and intercepts for alpha subproblem from parameter vector (xe) ...., w 1,65 18-11_ 1....,,"" ...,)N)) GetWeights()) Compute system matrix BuildSigna(u, ..... w kt1 .u/41 ....... gli
/s alpha subproblen
18
k-1 + LS(E)
14
Update parameter vector + InsertWeights(a
18
end
4.4
Computational Complexity
The computational complexity of Algorithm i mainly driven by the cost for solving the quadratic program from Proposition The quadratic program is solved most K. times for each of the N hidden neurons in each outer iteration. While state-of-the-art. solvers for convex programming able to exploit the sparsity

---

Published in Transactions on Machine Learning Research (01/2024)
pattern in Qi, the worst complexity is still O(m²) assuming that > n. As remedy, we derive algorithm based an ADMM approach in Appendix C Our ADMM approach leverages the block form of Qi and reduces the computational complexity to O(Cm²), where & is the maximum number of ADMM iterations. In addition, relics only on basic linear algebra operations that can be implemented efficiently (e. g., using BLAS//LAPACK libraries for CPUs or cuBLAS for GPUs).
5 Convergence Analysis
In the following, we provide a convergence analysis for DCON. For this, we first list a set of convergence conditions (Soction 5.1 and show that these are fulfilled (Section 5.2) Afterward, we prove that our algorithm converges globally and give conditions under which it even yields global solution (Section 5.3 Finally, analyze the convergence rate of our algorithm (Section 5.4
5.1 Convergence Conditions
Our convergence analysis builds upon the framework in Attouch et al. (2013). Therein, the authors show that a sequence (x (eE) converges a limiting-critical point of a proper lower semicontinuous function f RM + RU }oo} if the following four conditions are fulfilled:
(HO) The function f is a KL function.
(H1) Sufficient decrease condition: There exists a > such that, for all & E N, f(x*+!)+ + ||a - x < f(x*) holds true.
(H2) Relative ervor condition: There exists a constant b > 0 such that, for all & E N, there exists a (00[((*+))) which satisfies ||u || < [1=
(H3) Continuity condition: There exists subsequence (x**) and t such that ths + 5 and f(a#))) + f(i) for + 00.
Condition (HO) can be relaxed. The function f only has to fulfill the Kurdyka- properly at z specified in (H3). We further note that, if all of the above conditions are met, the sequence (œ*)en has finite length, i.c Exsalla =01l < co. Later on, this will be used to guarantce fast convergence.
5.1.1 Preliminaries.
For convergence analysis, need notion of sufficient descent for DCA. The following lemma summarizes previous rescarch (Le An & Tao 1997). Therein, let p(f) denote the modulus of strong convexity for a convex function f, i. e., p( = sup(p 2 0: f() 111-112 is convex). In particular, f is strongly convex if p(f) > 0. Lemma (Sufficient descent of DCA). Let
h with convex functions and h. Furthermore, let. (o*))EN be the sequence generated by DCA. If one of the functions g or h is strongly convex, then f(*²) - -(xxh1) 2 (p(g) + p(h)) ||. - 11
Proof. See Le An & Tao 1997)).
In order to prove that all of the above convergence conditions are fulfilled, we make an additional assumption.
Assumption 3. Let K. be the marimum number of DC iterations in Algorithm 7 We assume that all DCA subroutines for solving DCG with E NI....,NN converge within no more than K. iterations.
Note that Proposition has already derived the finite convergence of DCA for our DC subproblems. As such, Assumption 3 merely guarantees a uniform upper bound of DC iterations across all DC subproblems. Note also that Assumption 3 is always fulfilled for Kmax Even the case that restarts are necessary to ensure Assumption [ Assumption 3 fulfilled if
K. = (Kmax)?2 These bounds are merely rough estimates and can get very large. However, they are by means tight and in practice setting K. to 50 is already sufficient as demonstrated in our numerical experiments later on.
10

---

Published in Transactions on Machine Learning Research (01/2024)
5.2 Proof of Convergence Conditions
In the following, prove first that the loss function fulfills (HO). We then prove that the sequence (0*)ne) generated by Algorithm fulfills each of the conditions (H1), (H2), and (H3).
5.2.1 (HO) Kt Property of the Loss Function.
The next proposition shows that RegLoss, belongs to the class of KE functions. Proposition 8 (KL property of the loss function). The loss function RegLoss, is KL function with (ss) = CKLS!-E for a constant CKL > and É [0,1). Proof. See Appendia
The KE property is widely used in optimization. The class of functions that satisfy the KL property is large. For instance, it includes all continuous subanalytic functions with closed domain (Bolte al. 2007).
5.2.2 (H1) Sufficient Decrease Condition.
We now prove that each subproblem solution achieves a sulficient local decrease, that is, fulfills (H1). After- ward, we combine the results to prove the sufficient. decrease condition for the sequence (f*))EN-
We begin with the DC subproblem. Lemma [ gives a sufficient descent for DCA if one of the involved functions is strongly convex. The following lemma shows that the modulus of strong convexity of gi is uniformly bounded from below.
Lemma 2 (Strong convexity of gt). Let gr,, bi) be the conver function defined in Proposition p(g:) 27 (m) holds true independently of I.
Then,
Proof. See Appendiz D
Due to Assumption minn (M) minn(M is positive and, thus, 9I is strongly convex. The latter now allows to derive the sufficient decrease condition for the DC subproblems.
Lemma 3 (Sufficient decrease condition for DC subproblems). Let 2 denote the j-th iterate of DCA for the 1-lh DC subproblem (DC,) in the k-th ouler ileration, i. i. 20 (wi, 1/) is the starling point and the endpoint after K iterations. Then,
KK_ = k+1 1,/+1) [
91(2)) - he(=²) (xx(=*) ho(=*1)) 2 270 || 21
(15)
Km
holds, which is equivalent to
[[ ,b/+1) (wt, 1/2 op bt) - 0p0 (wftt,, ( (M)
(16)
Km
Proof. See Appendia
Next, we prove the sufficient decrease condition for the alpha subproblem.
Lemma 4 (Sufficient decrease condition for alpha subproblem). Let E be given in Proposition k+1 be the solution of (A). Then,
and
-0 "11a* - 112
(17)
Proof. See Appendia D
Finally, we combine the results from above to ensure a sufficient decrease the loss function, as stated in Proposition g
11

---

Published in Transactions on Machine Learning Research (01/2024)
Proposition (Sufficient decrease condition). Let (4% YEE be the sequence generated by Algorithm Then, kEeN salisfies the sufficient decrease condition (H1). That is, there exists a. > O such that
RegLoss (00Loss,(00"1 (0" + 110 0²112 2 I RegLLoss,(00)
(18)
Proof. See Appendia D
5.2.3 (H2) Relative Error Condition.
We now prove that (0*) KEN satisfies (H2). For this, we present some additional intermediate results follows. First, Lemma proves that (0") )Ke stays uniformly bounded during optimization.
Lemma 5 (Boundedness of )EE)) The sequence (8*) kEN generated by Algorithm is uniformly bounded by a constant >> 0.
Proof. See Appendix D
Second, show that the terms Sgt and 13 are Lipschitz continuous functions in 0. Lemma 6. The functions
(0) 1 {(2y)ai) +
Σ 2(( + b,)
Σ 20(a)0)) bu)
(19)
m
imI+1
1 o(2y)or) +
(0)
(0) m
Σ ((a;ar))(((s;;4)) + b.) +
Σ 20 + bk)
(20)
=++1
where E(x) = max xx 0) are Lipschitz in Br(0) C VVV.
Proof. See Appendia D
Third, Proposition gives a closed-form representation of elements in the limiting subdifferential of the loss function.
Proposition 10 (Limiting subdifferential the loss function). Let 0 be given. Furthermore, let = (e E9N) and En = (e") e...,,eN)) with e e E [0, 11m for all E fl...., NY. and let {1}, if (u), + bi # 0,
Vje fl.....,m.) m): G. o E
(21)
[0.
else
and let the condition
< 0 2/ 1/ en S 3g 3 for j E {l, my with (wI,z)) + b, 0,
(22)
hold truc. Then, the vectors
v0, Eg. En) = (10,,(0, (* (er(O, ai " " No (0)):(0)))).....)))
(23)
tml. r.l...
12

---

Published in Transactions on Machine Learning Research (01/2024)
with entries
10, 0 m) =
3 H (()) + bt) 23
(24)
2 01
H (ww) + bi) Zge (1w1, + bi)
(25)
m
m
Σ
2 2
Tie
((wr, xz)) bi) - Σ
Sy ((w), + bi) xg
(26)
m
j=1
m
(0, a , (1)
Σ
3
H ((w), 1.)) + c
(27)
j=1
01
+
2
H (1)) + bi) (x) + bi)
(28)
m
1=1
+
2 ((w), rzy) + bi)
Σ
8/4 (101, + b,)
(29)
|=1
j=1
m
N
(0)
No.1
Σ
2 Vj Σ
(,o(( + bi) (-o((wn, + bi))
(30)
m j=1
+2 +2 aq, m
(31)
are elements of the limiting subdifferential of the loss function, i. e.,
v00 cos ( , hh E [0, 11Th fulfilling
21 and 22 for all l E {1, (1,...,,N7}
(32)
is subset of 0 RegLosss, (0). Here, (x) denotes again the Heaviside function, i. e., H(x) 1 if x 2 0 and
zero else.
Proof. See Aypendia D
From the proof of Proposition 10 it follows that, for E [l....,NN the elements
((VL,(0, e e )eEE (0 c (h)) yy(Wy, bj, c yh (wi, bi e²
(33)
where yo (wi, ( E (gr, by) and yn (wi, by, M E (hy by). Now, let apc.k denote the parameter vector
after the 1-th DC subproblem when starting with 8² From Proposition and Assumption 3 we know that for
all bi.k fulfilling (21) for 0/ D.C. there exists an eac. fulfilling (21h for 0, 0,0.h such that (y k+1 1/++1 .o.k) yn (w ++1 1/+1 che When solving additional DC subproblems and the alpha subproblem to reach gh+1, the terms 38t (opc,k) and 1hi (oPC,k) change to 87 (gh+1) and 1/t1 (gh+1). To prove condition (H2), need to make sure that (O eankk ,e eeeh.) )eE (0*--1 eat.k ( "ea.k,ehur ()) E 0t &n) RegLoss, (0*+1) and, hence, need cack ch to fulfill 22 at gh+1, Thus, make the following technical assumption.
Assumption (Differentiabilitty assumption). For each k E N and E [I,...,,N, we assume there exists an chick such that the corresponding eaik with
(en..OPCA m.k A M 07 (O.C. ench , =0
(34)
and dhcc fulfill 22
gh+1
Now, we can use the above to derive a useful technical property in Lemma 7 The lemma is later used to establish the relative error condition for )oE).
13

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma 7 (Technical lemma). Let l E N and Assumption there evists C'> O independent of E (I,..., N and vn 0 (wi,b)) RegLoss, (Ok+z) such that
and Assumption hold. For each I E [I....,NN]
| Cll0 opcckl + Claft1 - afl-
(35)
Proof. See Appendia
D
Finally, we combine the above results. This yields Proposition which establishes (H22) for (0E)).NN
Proposition 11 (Relative error condition). Let (0*) be the sequence generated by Algorithm and Assumption g and 4 hold. Then, (0*) satisfies the relative error condition (H2), c., there exists a such that, for all N, there erists rk+1 E RegToss, (0h+1), which satisfies
|| | s 11@h-1 -8% 11.
(36)
Proof. See Appendia D
5.2.4 (H3) Continuity Condition.
Finally, prove the continuity condition (H3). From Lemma have that ||0*|| is uniformly bounded for all l N. Hence, there exists convergent subsequence, and, therefore, (H3) follows by the contimuity of RegLoss,,
5.3 Global Convergence.
The derivations from the last section are now summarized in Theorem 1
Theorem (Global convergence of DCON). Let Assumption to hold. Furthermore, let (0*)ket be the sequence generated by Algorithm 1 Then, DCON converges to timiting-critied point of the loss function independent of the initial weights, i. e., lim 8 = = and 0 E RegTosss Furthermore, the sequence
k+000
(O*) has the finite length properly, i. e.,
Σ 21ott1 0%|| 00.
Proof. Follows from (HO), (H1), (H2) and (H3).
We note that Theorem yields the global convergence to maniting-criticas point, i. e., the convergence to limiting-critical point independent of the weight initialization. However, this does not necessarily ensure convergence to local minima. In other words, even if the conditions (H0), (H1), (H2) and (H3) are satisfied, the proximity of the starting point 8 to a local minimizer l" does, in general, not imply that the limit is near 0r This is owed to the fact that the sequence is not generated by a local model of the objective function [Atlouch 2013). However, we can show that DCON converges global minimum of RegLoss, when ( is sufficienlly near; see Proposition 12
Proposition 12 (Convergence to global minimum). Under the assumptions of Theorem 1 the following holds true. If 0* arg min RegLoss, (0), there exists neighborhood Ug. of 0" such that 0 Up-
lim 2 0r See Appendür D k0000
While Assumption to can be well justified, Assumption 4 is quite technical. Nevertheless, DCON converges globally value under much weaker assumptions.
Theorem (Global convergence of DCON in valuc). Let Assumption 1 hold. Furthermore, let keN) be Then, DCON converges value, i. e., (RegLoss, (0k)) converges
the sequence generated by Algorithm i
to the infomam inf RegLoss,,(""
KEN
Proof. Follows from monotone convergence.
14

---

Published in Transactions on Machine Learning Research (01/2024)
5.4 Convergence Rates
According to Theorem 1 the generated sequence has the finite length property. This is usually associated with fast convergence. In the following, we derive the convergence order of DCON, depending on the KL exponent & of the function & as specified Proposition g
Proposition 13 (Local convergence of the parameters). Under the assumptions of Theorem 1 let & be the KL exponent associaled with 0*. Then, the following holds true:
I = 0, DCON converges in finitely many iterations.
E (0, 2) DCON converges R-linearly.
e DCON converges R-sublinearly.
Proof. See Appendia
D
For machine learning practice, the convergence in value is also of interest. Here, one is also interested in how fast the value the loss decreases. For DCON, Proposition 14 gives conditions under which the loss sequence (RegLoss,, (0*)) KEN converges with order q-
Proposition 14 (Local convergence of the loss). Under the assumptions of Theorem let be the KL exponent associaled with 0" Then, the sollowing holds true:
f ([a+T)+ 2 the loss converges with order q N.
IJ 2; the loss converges Q-sublinearly.
Furthermore, if ( ) we even observe super- Super---cooveryencc. Proof. See Appendiz D
Proposition 14 shows that DCON can converge very fast in value given a small KL exponent & S 1/2. For example, il E (g. 4), the loss converges Qusuper--uadratieally, while, for & 1.- the loss converges Q-quadratically. In the following, give conditions under which the convergence rate in value can be transferred to the parameters.
Proposition 15 (Convergence of DCON under local convexity assumption). Under the assumptions of Theorem 1 let & be the KL exponent associaled with 0". If RegLoss, admils a neighborhood U of 0" in which RegLoss, strictly convex, the following holds true: 1f & S 2q for grrq- E N22, DCON converges with Q-convergence order of at least q- 2. Proof. See Appendiz
Proposition 13 can be seen a standard result in the KL. literature, whereas Proposition 14 and Proposi- tion 15 follow from stronger assumptions on the underlying objective function. For a discussion on how our results are linked to the general KF. literature, we refer to Appendix
In summary, the above results show that DCON can achieve fast convergence of parameters and loss values under mild assumptions. For comparison, given optimal assumptions (i. e., continuously differentiable and strongly convex objective function with Lipschitz continuous gradient), first-order methods converge only linearly (van Scoy et al. 2018), while DCON achieves the same if & 1/2 but without any additional assumptions. Evidently, the KL exponent is crucial in the above convergence analysis. Determining the Kurdyka-Lojasievinn exponent for general KE functions is still an open research problem. There are works that try to derive calculus rules to determine KL exponents under varions operations on KE functions (Li & Pong 2018), such as, for instance, the composition (see Theorem 3.2 in Li Pong 2018 or block separable sums (see Theorem 3.3 in Li & Pong 2018) of KL functions. Other works determine the KL exponent for certain classes of functions, often involving some kind of polynomial representation (Li et al. 2015; Bolte very strong assumptions the underlying function, convexily. To the best of our knowledge, there are results that can be directly used in our in general- non-differentiable and non-convex setting. Nevertheless, the following proposition gives conditions under which a KL exponent & = 1/2 can be achieved.
ct al. 2017). However, most of these results rely e. g-, differentiability
15

---

Published in Transactions on Machine Learning Research (01/2024)
Proposition 16 (KL exponent of the loss). Under the assumptions of Theorem 1 let (EE) be the sequence generated by DCON converging to some 0² = (a", W*, w',b'). If (W*, is such that (wt,az) 2z)) + by + 0 for all E [I,...,N] and j E {l....,m}, and ViRegLoss, is invertible, RegLoss, fulfills the KL property at 8* with Ç = 1/2. Proof. See Appendir D
6 Numerical Experiments
6.1 Experimental Setup
Our algorithm is evaluated based on nine datasets (named DS1 to DS9 in the following) that originated from a systematic search. Details can be found in Appendix F.2 In short, we draw upon the UCI machine learning repository and set the filter options to pure regression tasks with numerical attribute type and multivariate data with 100-1000 instances in the training set. Each of the datasets is preprocessed using standard techniques (e. g., scaling of covariates), while taking into account the specifics of each dataset. Details are provided in Appendix F.3
As a baseline, we consider a state-of-the-ar variant of stochastic gradient descent, namely Adam (Kingma & Ba 2014). On each dataset, we train DCON and the baseline on 30 random train-test splits for three different hidden layer sizes N E {10, 20, 30}. Besides that, the neural network architecture has one hyperparameter (regularization parameter 7), which we tune via grid search. We set the maximum number of DCA iterations to K. 50 and stop DCON after .M- = 1000 iterations. For Adam, we use early stopping with a patience of 10 epochs and standard ez-regularization. In addition, there are further hyperparameters related to the training algorithm for Adam (i. e., learning rate, first moment exponential decay rate, and batch size). These are also tuned via grid search for each of the 9-3 = 810 training instances. Details are listed in Appendix In contrast, comparable hyperparametors related to the training algorithm are absont for DCON.
The results of our main experiments are Section The section reports the prediction performance terms of mean squared error (MSE), which we average over all 30 runs, i. e., different train-test splits. We further provide a numerical analysis demonstrating our theoretical findings: global convergence guarantees and rale of convergence (Section 6.3 Finally, show the scalability of DCON by applying it to the MNIST
benchmark dataset [LeCun et al. 2010 in Section 6.4
6.2 Overall Numerical Performance
Table reports the relative improvements of DCON in the mean squared error for both the training and test set. On average, our approach outperforms Adam across all layer sizes.
Training loss. For the training loss, we find large improvements on almost all datasets and layer sizes. When averaging over all 27 combinations of dataset and layer size, we observe an improvement by a factor of 1.54. For out of 9 datasets, we consistently outperform the baseline by a factor of up to 12.02 (DS6). Only for one dataset (DS7), DCON and Adam are on par (here, Adam is slightly better for layer size of N 10, whereas the performance of both is comparable for all other layer sizes). Table 1 (bottom row) also lists the average performance improvement per layer size. Here, we see consistent and large improvements, ranging between a factor of 1.19 and factor of 1.90.
Test loss. For the test loss, we see an average improvement by a factor of 0.64 when averaging across all combinations of datasets and layer sizes. On 6 out of 9 datasets, DCON is on par with or even outperforms Adam, showing improvements by a factor of up to 11.81. One further observes a clear performance improve- ment of DCON for smaller layer sizes, i. e., for N 10 neurons in the hidden layer. For N 10, we obtain average improvement of factor 1.61 for the test loss. For N 20 and N = 30 neurons in the hidden layer, the improvements still amount to 18 % and 13 %, respectively.
In sum, we confirm numerically that DCON is superior in the training task. DCON yields lower mean squared errors than Adam, often by multiple orders magnitude. This may be attributed to the properties of DCA, namely that DCA often converges to global solutions
Le An & Tao 2003). Furthermore, our
httppe//arrchie.. wew.uci..ec......... uci. www.wwu/we/e/ee/ee////// odu/ml/index,.. php last accessed 03/20/20..
16

---

Published in Transactions on Machine Learning Research (01/2024)
results show that DCON can effectively generalize to unseen data. We think that reason is the superior training performance, as generalization bounds for regression problems show that lower training losses lead to tighter generalization bounds (e. g., Mohri et al. 2018). We offer a detailed discussion in Appendix F
Table 1: Relative performance improvement in mcan squared error of DCON over Adam.
Training
Test
N = 10
20
N = 30
N 10
20
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
DS1
3.69
(9.27)
1.79
(1.08)
1.76
(0.52)
0.80
(3.00)
0.21
(0.54)
0.12
(0.67)
DS2
0.26
(0.06)
0.43
(0.07)
0.60
(0.08)
-0.20
(0.15)
-0.29
(0.17)
00.6
(0.12)
DS3
0.10
(0.04)
0.13
(0.04)
0.14
(0.04)
-0.10
(0.12)
-0.13
(0.09)
-0.16
(0.10)
DS4
2.41
(2.86)
1.54
(0.95)
2.18
(0.86)
1.72
(2.25)
1.14
(1.01)
1.16
(0.85)
DS5
3.11
(15.04)
0.60
(2.67)
0,25
(0.71)
11.81
(50.77)
0.35
(2.00)
00.11
(0.62)
DS6
3.70
(0.91)
12.02
(3.20)
5.04
(0.93)
0.49
(0.82)
0.33
(0.61)
0.47
(0.80)
DS7
00.01
(0.09) 0.00
(0.06)
0.00
(0.05)
-..44
(0.09)
0.01
(0.11)
00.02
(0.08)
DS8
0.06
(0.07) 0.06
(0.04)
0.09
(0.05)
0.00
(0.08)
0.00
(0.07)
0.00
(0.07)
DS9
0.36
(0.11)
0.55
(0.11)
0.64
(0.11)
0.04
(0.14)
0.02
(0.13)
0.02
(0.15)
Average 1.52
(3.16)
1.90
(0.91)
1.19
(0.37)
1.61
(6.38)
0.18
(0.53)
0.13
(0.38)
Results are based on 30 rums with different train-test splits. Reported is the mean performance improvement (e.g-, 0.1 means 10%) the standard deviation (Std.) parentheses.
Theoretically, an extremely large number of hidden neurons can guarantee the convergence of SGD to a global minimum (Du et al.) 2019a]] Zeyuan et al., 2019 Zou Gu 2019). To see whether DCON is still beneficial in such an wver-parameterized setting, we perform additional experiments in Appendix [J.]] Evidently, DCON also benefits from large N and remains superior over SGD, This might be due to the fact that wer-parameterization allows to avoid unfavorable local minima in the landscape of the training objective [Zeyuan et al. 2019).
6.3 Numerical Analysis of Convergence Behavior
In this section, we perform further numerical experiments to study the convergence behavior of DCON. That is, in the following, we assunne that Assumption D to 4 hold. We demonstrate that DCON converges to limiting-critte critical point. Furthermore, we empirically assess the convergence rate in the training loss and compare it to our theoretical findings from Proposition 14 To do so, we draw upon the neural network architecture (i. e., the tuned regularization parameter) from the previous section and let DCON only termi- nate upon convergence (i.e., e., ||@k-1 g² 2| < 10-6). We then repeat. the experiments with this stopping criterion and report results from single run (i. e., train-test split). To facilitate comparability, the exact same initial weights 8 (a", Wo, b6) are used for both DCON and Adam. For the same reason, use full batch size for Adain to ensure accurale compulations of the gradients and mean squared errors.
Convergence to critical points. In Figure ! we demonstrate the convergence of DCON to limiting-crition critical points. The example shows the convergence for dataset DS1 with N = 30. Plots for all other datasets and layer sizes can be found in Appendix F.6 Figure Ta shows how the optimization lets the element in the limiting subdifferential (defined in Proposition 11 approach zero. Figure Tb reports the distance between the parameter vectors from two successive iterations, i. i.e., ||08+1 - 0*1/2. As expected, we find that the distance between two successive iterates decreases gradually.
17

---

Published in Transactions on Machine Learning Research (01/2024)
Nor of denere Initing subfffeertal |je*
18
Destnnee between Rtrates 1
Eyods
Exclle
100
(a) Norm element limting subdifferential
(b) Distance between iterates
Figure 1: Convergence to critical points for dataset DS1 (N = 30): Results are based on dataset DS1, = 30, and a single train-test split. The term epochs is used to refer to outer iterations. Results for all other datasets and layer sizes are in Appendix F.6 Plot (a) shows the norm v(0+11, , 1), where Eg is
determined by solving min EC (o1,(0PP Emh 1))² + (mi(0pC e 1))2 after each DC subproblem for each :=1
inner itcration. Note that C decodes the constraints in 21 The rationalc is to find the values for d that set the corresponding entries of v to zero for ch = 1, which exist due to Proposition 7 Note that we assume that 22 is fulfilled for (c") 1), i.e., we assume that Assumption holds for c = 1. Plot (b) shows the distance between two successive iterates.
Rate of convergence. We now analyze the convergence speed empirically, For this, we compare the mean squared error in the early training phase (here: the first 30 iterations) of DCON and Adam. This is shown in Figure 2a Evidently, DCON appcars to learn faster than Adam in epochs. Here, we adopt the term epoch to report the outer iterations of DCON, been updated once. Nevertheless, there is much more optimization involved in an epoch of DCON compared to an epoch Adam which morely consists of a gradient step. That is, the two curves might not be directly comparable.
this coincides with the point when each parameter has
We also estimate the convergence order of (RegLoss, (0*)) kEN empirically. The results are plotted in Fig- ure 26 The convergence order is estimated to 9 1.000, and, hence, observe linear convergence. In the early phase (first 30 iterations), observe faster decay. Similar conclusions can be drawn for most datasets and layer sizes (see Appendix F.6l.
Logurrons Lnn reg. (total)
Mar
in reg (early phase)
kg
(a) MSE early training phase
(b) Estimated convergence order
Figure 2: Rate of convergence for dataset DS1 (N = 30): Plot (a) shows the mean squared error (MSE) in the early training phase, i. e., the first 30 ilerations, of DCON and Adam. In plot (b) we estimate the convergence order of (RegLoss,(0*)) KEN" That is, we define e² = RegLoss, - RegLoss,,8") and plot In(e*+1) against In(e"). Afterward, we fit linear regression where the slope of the corresponding line gives the estimated order of convergence, We estimate it once in the early training phase and once for all epochs. The estimated convergence order is 1.000.
18

---

Published in Transactions on Machine Learning Research (01/2024)
6.4 Scalability
We now demonstrate the scalability of DCON. For this, we leverage the ADMM-based quadratic programing solver proposed in Appendix [ While a quadratic complexity hinders DCON to scale to applications with millions of samples (also due to memory restrictions), still scales to medium-sized datascts, i.c., with m < 10. 000. To demonstrate this, we apply DCON to the widely used benchmark dataset MNIST (LeCun) et al. 2010). MNIST provides multi-label classification task, where the inputs are images of handwritten digits (ranging from "0" to "9") based on which the corresponding digit should be predicted. Overall, MNIST comprises of 60, 000 images for training and m = 10, 000 images for testing.
As MNIST provides a multi-label classification task (while this paper considers regression task), we train one regression model for each digit, e.e., one-vs--al approach, where the correct digit is encoded with a one and the rest with minus one. Implementation details are provided in Appendix G We then mcasure the prediction performance on the training set via the mean squared error as we did above. During testing, we combine the predictions from the ten different digit-spocific neural networks via an ensemble. The ensemble returns the label corresponding discrete target label. Accordingly, we later report the mean squared error during training (where lower values are better) and the accuracy during testing (where larger values are better).
the neural network for which the prediction is closest to one, yielding
For our experiments, we use a subset. of m = 10, 000 samples from the MNIST dataset for training. DCON terminates on average within two hours for each digit (compared to 15 minutes for Adam). The runtime drops drastically for smaller datasets, where DCON can also outperform Adam in terms of computing time by several orders of magnitude. To further analyze the limits using current hardware, we also run DCON the complete MNIST benchmark dataset. Table 2
reports the prediction performances.
In sum, our results show that DCON scales well to medium-sized datasets with < 10.000 observations. For comparison, Lee et al. (2013) use datasets with m ~ 100, while datasets in Haugh & Kogan (2004) correspond to m Ri 4000.
Table 2: Performance of DCON and Adam for the MNIST benchmark dataset.
Training MSE
Test accuracy
Digit
Digit
Digit 2
Digit
Digit 4
Digit
Digit 6
Digit
Digit 8
Digit 9
Ensemble
3
MNIST subset
0.05
0.07
0.00
0.09
0.10
0.07
0.07
0.11
0.13
0.93
DCON
0.02
0.03
0.03
0.06
0.05
0.04
0.04
0.04
0.08
0.06
0.94
Improv. 1.50
0.33
1.33
0.50
0.80
1.50
0.75
0.75
0.38
1.17
0.01
Complete MNIST dataset
Adam
0.05
0.05
0.08
0.09
0.15
0.09
0.06
0.07
0.12
0.10
0.94
DCON
0.03
0.03
0.05
0.08
0.08
0.09
0.05
0.05
0.10
0.09
0.94
Improv.
0.67
0.67
0.60
0.12
1.50
0.00
0.20
0.40
0.20
0.11
0.00
Prediction performance measured via mean squared error (MSE) during training (lower is better) and via accurary during testing (higher is better). We also report the relative performance improve- ment of DCON over Adam (e. g., 0.1 means 10 % Improvement of DCON over Adam).
7 Conclusions and Future Work
We proposed an algorithm to optimize paramcters of single hidden layer feodforward neural networks. Our algorithm is based on a blockwise DC representation of the objective fonction. The resulting DC subproblems are approached with tailored difference-of-cone convex functions algorithm. We proved that DCON converges globally in value and to limiting-critical points under additional assumptions. Furthermore, we analyzed DCON in terms of convergence speed and convergence to global minima.
There are two directions for future work that we think are of particular value. First, Assumption is quite technical and not casy to verify. Here, might be possible to develop a proof that establishes (H2) 4 For this, one might use a more involved analysis using the properties of the limiting subdifferential in Proposition 10 to get rid of condition 22 by now we are directly working with Fréchet
without Assumption
19

---

Published in Transactions on Machine Learning Research (01/2024)
subdifferentials. Second, research could work on parallel version of our algorithm and make it scalable to much larger datasets. We provide first theoretical insights in how DCON can be parallelized in Appendix 2 can be decomposed into a sum of much smaller quadratic programs. parallel algorithm based on this docomposition can further help counteracting the theoretical computational complexity of (
K.I Our derivations show how the quadratic program from Proposition
References
Armin Askari, Geoffrey Negiar, Rajiv Sambharya, and Laurent El Ghaoui. Lifted neural networks. arXiv preprint arXiv:1805.013 01532,, 2018. URL /ttL/htt:///axxii wttp://.orrgp////////0/// 01532
Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Mathemalical Programming, 137(1):91-185)) 129, 2013. ISSN 1436-4646.
Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Trusting svm for piecewise linear cmns. In International Conference Learning Represenlations (ICLR), 2017. BRRphttp://aart htttp://axxi..org/paf///// wwtp/opf/////.111111/
02185v5
Jérôme Bolte, Aris Danillidis, and Adrian Lewis. The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4): 1205 1223, 2007.
Jéröme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165(2):471- 507, 2017.
Jonathan Borwein and Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Ezamples. CMS Books in Mathematics. Springer, New York, NY, 2nd edition, 2006. ISBN 9780387295701.
Miguel Parpeinan and Weiran Wang. Distributed optimization of deeply nested systems. Interna- tional Conference on Artificial Intelligence and Statistics CattisticssAASSAA (AISTATS), pp. 10 19, 2014. ISSN 1938-7228.
Hilmi Berk Celikoglu and Mchmet Ali Silgu. Extension of traffic flow pattern dynamic classification by macroscopic model using multivariate clustering. Transportation Science, 50(3):966-99) 2016. ISSN 0041-1655.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over paratttttmetiinnaioonn is sufficient learn deep relu networks? Tn International Conference on Learning Representations (TCLR), pp. 242-252 2020.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems (NeurIPS), pp. 2937-2947, 2019.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on lame functions. Foundations of Compulational Mathemalics, 20(1):119-11) 154, 2020.
Simon Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural norksrks International Conference on Machine Learning (ICMI.), pp. 1675-1685, 2019a.
Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. International Conference on Learning Representations (ICLR), 2019b.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011. ISSN 1532-4435.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 249-256, 2010.
20

---

Published in Transactions on Machine Learning Research (01/2024)
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. International Conference Artificial Intelligence and Stalistics (AISTATS), pp. 315-323, 2011.
Martin B. Haugh and Leonid Kogan. Pricing american options: A duality approach. Operalions Research, 52(2):258 270, 2004. ISSN 0030-364X.
Dean-Baptiste Hiriart- Urruty and Claude Lemaréchal. Fundamentals of Conver Analysis. Springer, Berlin, Heidelberg, 2004.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366) 1989. ISSN 08936080.
Guang-Bit Baing-Binnoe Huang, Qin-Yu Zhu, and Chee-Kheomg Siew. Extreme learning machine: Theory and applica- tions. Neurocomputingg 70(1-3)4489 501, 2006. ISSN 09252312.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint:1412.0o 6980. 2014.
Gert Lanckriet and Bharath K Sriperumbudur. On the convergence of the concave-convex procedure. Ad- vances in Neural Information Processing Systems (NeurIPS), 22, 2009.
Tim Tsz-Kit Lau, Jinshan Zeng, Baoyuan Wu, and Yuan Yao. A proximal block coordinate descent algorithm for deep neural network training. International Conference on Learning Representations (ICLR) Workshop Truck Proceedings, 2018.
Thi Hoai Le An and Pham Dinh Tao. Solving class of linearly constrained indefinite quadratic problems by d.c. algorithms. Journal of Global Optimization, 11(3):253 285, 1997. ISSN 1573-2916.
Thi Hoai Le An and Pham Dinh Tao. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Annals of Operations Research, 133(1): 2005. ISSN 1572-9338.
Yann LeCun, Corinna Cortes, and C. Burges. Mnist handwritten digit database. ATT Labs. Available: http://yaan.lecume hoom/edd///ae lend//mmist, 2, 2010.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521((553):436 444, 2015.
Kevin Lee, Zhihong Man, Dianhui Wang, and Zhenwei Cao. Classification of bioinformatics dataset using finite impulse response extreme learning machine for cancer diagnosis. Neural Computing and Applications, 22(3-4):457-466 4588 2013.
Guoyin Li and Ting Kei Pong. Calculus of the exponent of kurdyka-tojasioviez incquality and its applications to linear convergence of first-order methods. Foundations of Compulational Mathemalics, 18(5):1199 1232, 2018.
Guoyin Li, Boris S Mordukhovich, and TS Pham. New fractional error bounds for polynomial systems with applications to hölderian stability in optimization and spectral theory of tensors. Mathematical Programming, 153 2015.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems (NewrIPS), pp. 8168-8177, 2018.
Shiyu Liang, Ruoyu Sun, and R Srikant. Achieving small test error in mildly oxerparameterizee neural networks. arXiv preprint ar Xic:21104 11895, 2021.
Aaron Mishkin, Arda Sahiner, and Mert Pilanci. Fast convex optimization for two-layer relu networks: Equiv- alent model classes and cone decompositions. International Conference on Machine Learning (ICML), pp. 15770-15816; 2022.
Mehryar Mohri, Afshin Rostamizadeh, and Amect Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, Cambridge, MA, 2nd edition, 2018.
21

---

Published in Transactions on Machine Learning Research (01/2024)
Jean-Paul Penot. Calculus Without Derivatioes. Springer, New York, NY, 2012. ISBN 9781461445338
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. International Conference on Machine Learning (ICML), pp. 7695-7705 2020.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. International Conference on Learning Representations (ICLR), 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathematical Statistics. 22(3):400 407, 1951. ISSN 2168-8990.
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back- propagating errors. Nature, (23(688)):533355) 1986.
Justin Sirignano and Kay Giesecke. Risk analysis for large pools of loans. Management Science, 65(1):
107-121 2019. ISSN 0025-1909.
Pham Dinh Tao and Le Thi Hoai An. A DC optimization algorithm for solving the trust-region subproblem. STAM Journal on Oplimizalion, 8(2):476-5k) 1998.
Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, and Tom Goldstein. Training neural networks without gradients: A scalable admm approach. International Conference on Machine Learning (ICML), pp. 2722-2731, 2016.
Tieleman Tijmen and Geoffrey Hinton. Lecture 6.5: Rmsprop: Divide the gradient by a running average of its recent magnitude. Neural Networks for Machine Learning, (Lecture), 2012.
Bryan van Scoy, Randy A. Freeman, and Kevin M. Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Lellers, 2(1):49 54, 2018.
Jinshan Zeng, Tim Tiz-Kit Lau, Shaobo Lin, and Yuan Yao. Global convergence of block coordinate deseent in deep learning. International Conference on Machine Learning (ICML), pp. 7313-7323, 2019.
Allen-Zhu Zeyuan, Li Yuanzhi, and Song Zhao. A convergence theory for deep learning via over- parameterization. International Conference Machine Learning (ICML), pp. 242 252, 2019.
Jiawei Zhang, Yushun Zhang, Mingyi Hong, Ruoyu Sun, and Zhi-Quan Luo. When expressivity meets train- ability: Fewer than n neurons can work. Advances Neural Information Processing Systems (NeurIPS), pp. 9167 9180, 2021.
Ziming Zhang and Matthew Brand. Convergent block coordinate descent for training Tikhonov rogularized deep neural networks. Advances Neural Information Processing Systems (NeurIPS), pp. 1721 1730, 2017.
Difan Zon and Quanquan Gu. An improved analysis of training parameteriie deep neural networks. Advances in Neural Information Processing Systems (NewrIPS), pp. 2055-2005 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-parameterized deep relu networks. Machine Learning, 109(3):467 492, 2020.
22

---

Published in Transactions on Machine Learning Research (01/2024)
A Optimization Problem
A.1 Proof of Proposition
Proof. We prove the existence of a solution to PNN by showing that the loss function is cocrcive. Cocrcivity
follows by
1
m
RegLoss, (0)
((wi, x.)) bi)²
(37)
m
1
M
Wi
min (M)
( [w)
||
for all I {I,...,NN N), and
(38)
b1
m
m
1
RegLoss., (0) 2
||a|22
(39)
Using the contimuity of RegLoss, (0), the existence of solution follows.
23

---

Published in Transactions on Machine Learning Research (01/2024)
B Derivation of Algorithm
B.1 Visualization of Subproblems
For better understanding, we visualize the parameters involved in cach of the subproblems on simplified examples with N = 5 hidden neurons. Figure
3a shows the parameter notations. Note that the bias terms
are located on the hidden neurons. Figures 3b to 3i show the corresponding DC subproblems, while Figure 3g visualizes the alpha subproblem.
a
(a) Parameter
(b) DC Subproblem
(c) DC Subproblem
(d) DC Subproblem 3
(c) DC Subproblem
(f) DC Subproblem
(g) alpha Subproblem
Figure 3: Visualization of Subproblems.
24

---

Published in Transactions on Machine Learning Research (01/2024)
B.2 Proof of Proposition 2
Proof. To derive the stated decomposition, we proceed as follows:
N 0:0 ((11; + bi)
2
m. RegLoss, (101, bi) =
yj
(40)
==1
m
N
(fwr, Rz)) + bb)²² + +11a012
(41)
j=1
N
2yj
+ b;) +
Σ
a (wi, ( 25)
+ bii)
(42)
1=1
m
N
((wi, xz)) + bb)² + 7|aa1|
(43)
j=1
35
2yj
Σ
(oo((w; bi) + Σ a,o mr)) bi)
(44)
2
02 vooo( + b + bp)
(45)
N
(,,,, + b;)² + >laa|22
(46)
m
m
m Σ
2y,a;0((u,, + b,)
2y, ((1), + bt)
(47)
jml
(a 23) bb) + Σ
ai ((w), + bi)²
(48)
2 (t))
2z)) + bp)
(49)
m
201a ..2) + bi ((up + bp)
(50)
(1w,, + bb)) + Σ (w,, + bi)
(51)
+ ?
(52)
Rewriting the term
N 1-1
2a 20,0, 2z) + b.)o((up, + bp)
(53)
25

---

Published in Transactions on Machine Learning Research (01/2024)
m
20 ((0,, + (())p mz} + bp)
(54)
1=
20 b + bp)
(55)
pyl
20,0 b,)o(((1,, bi)
(56)
and defining the constant
17
m
2y (ww; 23) + b.)
(57)
j=1
m
000(Wu 23) + b.)
(58)
20,a (a mソ) + (1)) + bp)
(59)
Σ
20,a xz) + + bp)
(60)
j=1
m
N
((w,, + b,)² + >|aa|1
(61)
yields the form
m Σ j=1
m RegLoss,,(uy bi)
2yja ( + bt)
m
af 0 (w), σz) + b:)
j=1
20, (0w + bo)o((un, + bi)
(62)
j=1
20ra ((w1, (()p + bp)
(w11,2)) + +h)²
In Equation 66
we have isolated all terms with ii and by Note also that (wi, (y)) +by linear in (wn, by) and, hence, o ((w, T + by) is convex. Furthermore, the function o(w,, xz) + 6.)² is convex since is non-negative and convex and the function (-)2 is monotonically increasing. To ensure that the lincar combinations of those functions are also convex, we have to split the sums into linear combinations involving positive weights and linear combinations involving negative weights. Hence, we define the following index
2z) + by)
26

---

Published in Transactions on Machine Learning Research (01/2024)
sets
[ [j (L.....,m) mm. 2yjar 0},
(63)
4 = [L....,m m] \ 17;
(64)
21 ((13) E {1 ,...,,,; x {l....,mi m. (( + b,)) 2 0},
(65)
21 ( I,..,,..,N NN ......,,)]) 12.1
(66)
.,_,,111111111 3.1 = ((r.)) E (1...., - 1} (1,....,) 2000 + +bp) 2 0),
(67)
3.1 ((1, (11..../-11) x =1, (I....,ml) m]] T2.
(68)
By splitting the sums Equation 62 in the following manner
RegLoss, (1y, b1) à
Σ 2(),)) + b1)
Σ
(( 2.) + bi)
(69)
jEL
jETj.
af ((u,, + b,)
(70)
Σ 20,010 b.)o 2,) + bi)
(71)
(1)))
Σ [2 + b.)l mz} + bt)
(72)
(
Σ (p.))
20rapo + b bp)o bi)
(73)
Σ (20) 2z) + bb)))o((un, + bi)
(74)
(p.j)
7
((w,, + bi)
(75)
we yield the form
m RegLoss, (w), bt) = â + (u bi) he(we, bt).
(76)
27

---

Published in Transactions on Machine Learning Research (01/2024)
Here, the functions 9I and hy are defined
ge bi)
Σ
(3) + b))
(77)
1.
( - bi)
(78)
==1
Σ
20 + + b,)or((un;; bi)
(79)
(1,))22,,
Σ
20nap ((Up) 1z) + +b (p)o + bi)
(80)
(DJ))L
Σ (()), + bi)
(81)
hy(wi, b1)
Σ 2y ((wr, + bb)
(82)
sErf,
Σ Pa;aoo((1;, 2r)) ( (1))))()1 + bt)
(83)
(1,))222
Σ
12ja x3) + bo))o xzح + bt),
(84)
(p.i)E1
or, in short,
m
m afo((wr,3;) b1) +7 Σ 5=1
m
(w bi)
Σ
3 l (wn, (1), 1z) + +b) Σ
((w), bi)
(85)
1=1
j=1
m
hy(ur, bi)
Σ
3 (w1,, xz)) + b,)
(86)
1=1
with coefficients 3/ 2 0 and 8350 ž 0 for all j E (1.....m}. Dividing both sides of Equation
76 by m
finally yields the desired form with 83th B /m, 8 3/ /mm and a d/m.
B.3 Proof of Proposition Proof. By holding all parameters except for constant in RegLoss, (a, W,b), one yields
1 - 11y Eall 7 -aa.
RegLoss,, (w) = +
(87)
with
N ((w,, + b,)²
Ca = m
(88)
The linear least squares term with system matrix E, as defined in Proposition follows directly by the structure of the mean squared error loss.
B.4 Proof of Proposition 4
Proof. Recall that (wr, br) is given by
m
Wi (((m))
))
3
(89)
bz
1
j=1
28

---

Published in Transactions on Machine Learning Research (01/2024)
The proof follows by straightforward calculation. Let (mn bi) be arbitrary. We have to show that hu bi) 2 he(w,, bi)
H
Wy
23
24
(90)
bi
b1
by
The right-hand side of the above incquality can be rewritten as
Σ jml
8/ bt
(((
ku
i
Z
H
ui
1
(91)
1z
,
1
by
hu
Z
I
wi
(92)
bi
1
b
1
which equals
ghi
Wr
by
x3
1
H
wi
by
23
(93)
1=1
since
(((
wi bi
))
(((())
wi by
It 1
H
((oo))
Zj
(94)
bi
Hence, the incquality in Equation
190 is equivalent to
Σ 1-1
(
1i by
H
Wi
by
())) H
(((#))
1r
1
2 0.
(95)
Since 8/.1 2 0, this inequality holds if
(()).((
((
(+)
(1)
H
ii
by
(
(1)))= H
(((m))
I
2
0,
(96)
which can be easily verified by a case distinction.
B.5 Proof of Proposition
Proof. For a given y² = (y), the convex conjugate of gi is defined as
gi (vi. v5) sup
{
yf
W1
Σ
m
3
(ow(((()))) r.y) + bt)
(97)
y5
1=1
2
((Wr, 2.)) + b,)²
(98)
m
j=1
((w1, + bi)
(99)
Let the function F be defined as
F(wi, bi)
8/
3 o(wr, xz)) + bi)
(100)
1/
bz
m
((ww,, ..y) + bz)
(101)
m
((wi, 2z)) + by)
(102)
29

---

Published in Transactions on Machine Learning Research (01/2024)
Using the definition of M and extending the ReLu activation a for vectors R to
max( U1. 0)
( =
(103)
max max(Un+11 0)
one can rewrite F in the form
F(w,, bi) =
y/
by
89h
a
M
wi
bi
(104)
af
Wz
Wi
o
M
M
(105)
bi
by
M
MM
(106)
by
bi
For the rest of the proof, we proceed in two cases.
Case 1: 3 (il bi
<(0)
Vi
kcr(M):
#
bi
In this case, F' is unbounded. This can be seen by defining the sequence (wf, b(t) Ak(wr, bi), where
À = sgn
(((2)
vi
wi br
))
(107)
1/2
Since (wi, bi) E ker(M), we have that
y/
wi
K
F(ut. b/t) = Ah
= k
(108)
by
y2
,
bi
and, hence, Fww b/t + xo for k + oc.
That is, si (vi w5) ao.
Case 2: A
Wi b
kor(M):
Vi M2
W1
= 0
by
In this case, we have that y" E ker(M)+ Im(MT). Hence, there exists dy E IRm such that MT = y²" Leveraging the variable transformation
M
(109)
bi
the function can be rewritten as
F(w,, bi) (ddy,Vunry
(30r ( (unr,
(110)
(ar (Uwn,d)) (vw) m
(111)
7 m
(u Unoi
(112)
By splitting &wr in positive and negative component, e., Van dy vi x² with 0 od 1 2² 0 and using the fact that (Bum,,b) = o!,, Equation 110 is given in a quadratic form However, simply optimiz-
The notation 0 5 1 1 used as a compact expression complementary condition s and v? L.e.
0 Wi,
2 0, 0,
30

---

Published in Transactions on Machine Learning Research (01/2024)
ing Equation 110 is insufficient, since Equation 109 might not be satisfied. Hence, add additional constraints in the form
S 0 and 0² 2 s.t.; M (v-- -v²) = vwr.0r
(113)
Altogethor, this yiclds the following quadratic program
dy
3
(af
+ T)
Y
0
dy
2
2
-77
7 T
0
0
22
sup
0
3
2
0
0
0
0
v.3
0
0
0
0
0)
e²
(114)
2-2
s.t.
(-I
M
-M
2
0,
2.4
(v
2 0.
The above quadratic program naturally imposes the complementary conditions of v² and v². This can be
scen when observing the Karush?Kuhn?Tuun (KKT) conditions. That is, a solution (o!, v², v² u*) of the quadratic program Equation [114) fulfills
2 2
39h
dg
Mi
m m
m
dy
H2
+
M
(115)
-MTA
114
for some Lagrange multipliers 2 0, P2 2 0, pa 2 O, μr 2 0 and A. Furthermore, complementary slacknoss
holds between o² and μs- Solving for the first row and inserting it into the second row yields
at n² + f P11 112 m
(116)
Hence, whenever the i-th component of af is strictly greater than zero, we have
ot
(12),
5
0,
(117)
m
m
and, therefore, of = by complementary slackness.
The above-mentioned quadratic program equivalent to the one stated Proposition 5 with
9g- (3 dy. dy., 0),
(118)
(af T)T
7
2
7
Q
(119)
m
0
0
A (-I T M
-M
)
(120)
== (v
(121)
Hence; (5 v5) is given by the negative optimal objective function value of this quadratic program. The directly follows from the derivations in and
form of (f")) xx'))= - Ev("))
which says that either on or x? can be strictly positive.
31

---

Published in Transactions on Machine Learning Research (01/2024)
What remains to be shown is that dom(gf) = S2. To do so, we have to show that, for y E Q2 the quadratic program
(n u) + " Qru s.t. = and 0,
(122)
has finite solution. We prove the claim via contradiction. Suppose there exist up 2 0 with Avw = 0 and
(gy- Ui) + 1 2 Qree + oo for h + cc. As 2 Quek 2 0 for all &o E N, we yield (go-, vx) -> oc for h + co.
2 Now, we have that
(g Uk) = (3 - dy 2/t) + (dz- o = (89, wk) + (dy of u
(123)
(124)
11) 2 0. Then, this yields and, hence, that (dyr, ut - 11/) - -00 as (,m,
T Kdg' 12 -xtil= 2 ux
Qiuk
af m
|
7 11
7 m
11
(125)
m
for large k which means
||u - 0211 S , - S , I11|a
-
(126)
for large k. As (dy- v2 ut) + -o, we have that ||l] ri oc, which contradicts Equation (26)), as the left-hand side grows quadratically and the right-hand side only lincarly. Hence, the quadratic program has finite solution for all y" Ω.
B.6 Proof of Proposition 6
Proof- For y² E dom( =
Ω2 S2
have that 0g) = (o))),))), where E, the value function of (QP
To prove the claim, make use of Lemma 4.4.1 in Hiriart- Hiriart-Urruty & Lemaréchall (2004). Thus, following Hiriart- Urruty & Lemaréchal (2004), we have
(-Ei)(")) sup :VV)) < oo,
(127)
where (g()) = (gy,,, v) - Ju² Qru and = {u E 2m2++((+1)) Ae = and 2 0}. Note that O2 is Aqy- + (1 - X)q=- for all ,²,²" e lt and X [0,1] Hence, by Lemma 4.4.1 in Hiriart-Urruty & Lemaréchal (2044), have
convex y" as 41--+(1-11)) A)2
0 ((-E))(y") (LL8,,
(128)
where V(y*)= = (u E. = Now, we use that
y" tep dy + Xe, MT + +A
(129)
=:dg-
where A, is a solution of the linear system of equations M A, Ep: which exists due to Assumption We then have
ty- = (g9i dy +D2 dy tee, 0,0)
(130)
= (59t dy- AAp, dg- + AAp, 0,0)
(131)
= 9y' + A(- 0,0)
(132)
2g- + >A
(133)
where we define Ayp = (-Ap, Ap, 0). Hence, (==0 u)) pl. As Uy- is a solution to the quadratic program, 128 yiclds that vy- (v*) is a valid subgradient, which proves the claim.
32

---

Published in Transactions on Machine Learning Research (01/2024)
Furthermore, one has
AT
07
07
(Ai, mg- - v/g
0 h+1
0
(134)
=
(An+1 1g- - vgg)
1+1
0
0
(Ai, M (
2
(M A1, uy e
8"
(135)
=
(An+1, M(n. vyy
(M A n vyg - -
(e1, 1g- (/-)
3
(136)
(en+1, y - v/-))
B.7 Proof of Proposition 7
The analysis is based on the theory of polyhedral DC programming (see, e.g., Le An & Tao, 1997; 2005)- A DC program is called polyhedral if either 9 h is polyhedral convex. In the following, we summarize important results from polyhedral DC programming in earlier research.
Proof.
(a) For polyhedral DC programs, DCA converges in finitely many iterations. See (v) in the properties of the simplified DCA in Le An & Tao (2005) or Tao & An (1997).
(b) As we consider polyhedral DC program, the sequences (wt, by REN and y generated by DCA converge to ((w), b"),"") (v") n ohi (y")] [8n bt) (1y bj)]. See (iv) in Theorem 6
in Le An & Tao 11977
(c) If (wf, b7) is local minimizer of gi h4, then (wf bi) E Pi f(u, b)) E R ahy (wr, bt) Ógi(un, bi)}- The converse statement holds true if by a polyhedral convex function. See (ii) in Thcorem 1 in Le An & Tao (2005).
(d) (wi, b7) Pi if and only if there exists y E S(w) b7)
arg min {(uet ()),0) - ((() such yEBN, (w0 (w .6))
that (wi b7) E 0gt (v*). See (i) in Theorem in Le An & Tao 1997
Our proof is structured in two parts. In part 1, we first prove that by polyhedral convex. From point (a), it then follows that our DCA routine converges in finitely many iterations. In part 2, we then prove that (wwf (i), y²) from point (b) fulfills the assumption of point (d), given that Ery") Ey(y) Vy E (hy b7). By point (c), it then follows that DCA routine converges to local solution of (DC,).
Part 1: To show that hy is polyhedral convex, we have to show that its epigraph is polyhedral convex set, i.e., a finite intersection of closed half-spaces (see, e. g., Rockafellar 1997). To do so, we proceed as follows.
Let the sets A Aj for j E (I....,m) and G2g for J C [1,.... m) be defined as
A5
R
D2
wi
(137)
bi
1
bi
AJ
Wi)
R++1
x2
Wi
(138)
bi
by
(w])
R1+11
W1
A
Vj
J and
E
Vi Vie vol
(139)
bi
bi
11
33

---

Published in Transactions on Machine Learning Research (01/2024)
Furthermore, denote with My the matrix M where all rows corresponding indices not in J are set to zero, with My the matrix
MJ -
My
(140)
0
and with She the vector 3hu = (8h,1 1)a Now, we have, for (wi, bi) E 9t5
(w b1) = Σ 8 ((w), + bi) = (Bri, M
wi
gh My bi )
Wi
(141)
by
where we used again the vectorized version of a as defined Equation
103
Thus, for t E R, it holds
bu (um bt) SL
3/,Mo
MJ
0
(142)
b1
Wi
gru
M
by
S 0
(143)
(w
MF 8h
bt
S 0.
(144)
By defining the vector ag -Mf33" and using that
R=+1_
By and 2g
n JET ie.70
n
A7 nA,
(145)
where mm denotes the power set of m., we now have
{
epi(h:) =
bi
R
be)
St
(146)
{
ui (1
E CR,
bi
$ 0
(1477
Jeafl
U
1 b
E
ag.
[mj
(148)
seath...m) sea teg0
U
E extt1
.ER:
bi
S 0.
(149)
scaflimm) JEJ t0g0
O.
(150)
b
(151)
= U
by
=
.ER: :
as.
0
(152)
i
3eaflomm)) JEl segi
10 bz
EER:
3
bi
(153)
[w)) {
R
IER:
S 0
(154)
bi
34

---

Published in Transactions on Machine Learning Research (01/2024)
Hence, epi(hi) is union of convex polyhedra. From Lemma 1 in Bemporad et al. (2001 it follows that union of convex polyhedra is convex if and only if it is convex polyhedron. Since epi(hu) is the epigraph of a convex function and thus convex, it follows that epi(hr) is a convex polyhedron. This proves the first part.
Note that due to the above derivations one can also see that, independently of and (wy, there are only at most 2 different elements @hy(wr, b)) in the form of Equation (12). Hence, the number of DCA iterations is bounded by K 2mm. See also Theorem 5 in Tao & An 1997 and the arguments therein for fixed respectively natural choices of subgradients.
Part 2: For the second part, we first observe that
{(m)
Σ
( (
3 (7))
[0. it
(12 by)
(155)
(1),
else
Now, let ((wf. b,).3/"
E (gg (y ) rhh (y" )} [agi(ut. of ()) (f be given as in point (b). By Theorem (i) in Le An & Tao (1997) and p(gi) p(hi) O, we know that
bf
y =
gh
Ij
H
101
17 ()))
(156)
bi
==1
as DCA converges in finitely many iterations and (wf+2, have
bbtt) auutt,,/ttt
(wt, For E Ohi(wi, bt), we thus
V/
wi
3
H
67
xj
Ij
1
h
(157)
Σ
H
w
wf
xz
(158)
65
1
wi
y.
(159)
bj
where the second equality follows by the definition of e in Equation (155). By assumption, we have that Erly") < Ev) Vy E Ohr bf), which implies that y" S(wif, b7), needed in point (d).
In summary, we have that (wf, bf) E Ogf (v²) and y" E S(wf, b7). By point (d), it follows that (of,)))) E Pi and, hence, by point (c), that (w b7) is a local minimizer of (C.).
B.8 Restart Procedure for our DCA Routine
The point (wf, bt) returned by the DCA routine developed Section 4.2
a local solution of DC if
Ohg(wf. bt) S 0gl (wi; bT) holds true. If the latter condition is violated, we provide procedure that allows further reduce the objective function value by restarting the DCA routine from new initial point following 2 always holds true.
Tao & An 1998). In that manner, can ensure that Assumption
The main idea is the following. Suppose that there exists y hu(wf b7) such that y" & g((w] b)). Then, Tao& & An 1998) show that restarting the DCA routine from the point ((w), bf), v²) yields a strict decrease in the objective function value in the first iterations, i. e., for (wi, (T)) E dgi (v²) it holds g(w bz) h(wt D/)
g(wf, bt) - h(w,, 6f). Thus, we merely need to provide a procedure to compute yd for restarting the DCA routinc or ensuring that (hi b7) S (w] bt) holds true. We do in the following.
First, note that.
35

---

Published in Transactions on Machine Learning Research (01/2024)
oi
[0, 1],
if
(vc )=
Σ
80
H
2
: ef
b9
:
(160)
1
69
{1},
else
where
i 2
m Σ
9
H (1w7,
;z) + bf)
(Lw) m3))
b7)
7
(fo7,
+ bf)
(161)
m
m
j=1
and
[0,1]
wr
2;
Slu(wī =))=
Σ
8
H
E
(162)
bt
(1);
else
Now, @hr(wt. bft dgi (wf, bt) always holds true if Ōh (wf 6f) is singleton, i.e., if ((wf,z) + bf) / 0 for all E f1..... m}. Hence, we assume that there exists a non-empty subset J S f1,..., m) with (wf z3) +b; = 0 for all j E I and xw)) + bi # 0 for all j $ I and yield
0gi(u (wt b7)
Σ NET
B
Tjj
91 j
=
10, 10
9g 9.
(163)
with
4g
Σ
8
Iz
H
(((8))
w
bi
(164)
and
0hr(wi, bi) =
Σ
ghy
Izj
j
E
10,
11
+ gh.
(165)
JEJ
JEJ
with
9h
ghu
H
(166)
NEJ
Next, define the following matrices
M₁
E
[1(++)x171
(167)
1
iEJ
M₁
ghe
[((+1))117
(168)
GET
36

---

Published in Transactions on Machine Learning Research (01/2024)
Now, to find yd hy(wf, b7) such that v & giww, bf), we need to find ch [0, such that, for all e [0, 1]13, we have
Mae" + qn Maeh + 90 q.
(169)
To check whether or not such an h exists, we consider the following max-min problem
max min e (lE( 51 M hy + 9n Mae"
49 - all1
(170)
If 170 admits solution (c"t,e cht) with objective function value strictly larger than zero, then yº MA + yn E hy(wi, bi) and vd $ (w( b(). If the optimal objective function value of 170) is zero, conclude that
(he(wt bf) S Og((w] bt) holds true. What remains to be shown is how to solve the max-min problem in 170).
Note that 170 is equivalent to
max min eht e 10
(w), 1) + (w2, 1)
MA M + +hh M - 9g 9 W1 - W2
s.t.
Mn tu + Myr 9g + S w1 02
(171)
の < 1,
hi 1
e hh w1 W2 2
and, thus, can be solved with the branch and bound algorithu developed in Falk 1973). We further note that [J] usually small and sctting th 1 yiclds an initial solution with objective function value zero. That is, if (ly bj) (gi(w, b7) holds true, already start with optimal solution, and if Oly(w, bf) g (w bf), we terminate the algorithm whenever it yields feasible solution with objective function value larger than zero. Thus, our restarting procodure can be implemented very efficiently.
37

---

Published in Transactions on Machine Learning Research (01/2024)
C Efficient Implementation of QP Solver
In this section, we show how the solution of the quadratic programs in the DCON algorithm can be solved efficiently. turns out that a single singular value docomposition (SVD) of the matrix M can be used in order solve all quadratic programs by a sequence of basic linear algebra operalions. To do so, we note that quadratic program like QPP) can be solved via the alternating direction method of multipliers (ADMM);
soc, for instance, Boley 2013
We summarize ADMM for (QP) in Algorithm 2
Algorithm 2: ADMM for QQP)
Input: ADMM parameter maximum number of iterations E
Output: Solution
Set & 4-
Sot z",u² 6-0
while not converged and < C do
Solve (Qi+al pl A²)
(0 -
(
90- for +t
Set 2ft1 4- max(0, aht + + elementwise
Set #+1 +- vt + ott
k+1
end
return k+1
In the following, we show how the lincar system of equations in line of Algorithm 2 can be solved efficiently. By drawing upon the so-called Schur-complement Nocedal & Wright (see, e. g.. 2006), know that the above KKT matrix can be inverted via the formula
G 17
C E
with
(172)
A
F
G G-! AT AT) AG
(173)
= G- (AG-IA7)
(174)
== -AG
(175)
Now, let = p (2* u²) - -y. As the right- right-hand side of our linear equality constraints in QPP is zero, the above can be used to simplify line $ to
++1 Cw - (AG- AG-1w.
(176)
Let w be split into four components according to the dimensions of the submatrices in the definition of Q: in the proof of Proposition i.e., w (w*, w² w3 wt). In the following, we show how Equation (176) can
be computed efficiently.
First, note that G = Qi + pl. The simple structure of Qi now allows to directly compute the inverse of G, e.,
gil
g2l
0
0
g2l
I3l
0
0
G-1
0
0
11
0
:
(177)
1
where
2(a7+7)
91
9
Q1
P:
q3
27 m
92
and
Q2
01 03
27 + p.
93
01
o
38

---

Published in Transactions on Machine Learning Research (01/2024)
Furthermore, Cholesky decompasition of the inverse, i. e., G L, is given by defining L as
1 I
2
0
0
1
0
0
L
(178)
0
34
0
11
where
{
=
V91,
91
92
&2
E1
V
Now, AG-
-T ALTLAT = (LAT) = BTB with
(E2 E1)
Eal
L
(179)
&MTT
-
Suppose we have a singular value decomposition M Le., M UEVT. Then,
(E2 - (
V
0
0
(E2 E
==
&AM
EST
0
0
V
0
0
0
0
&E
E
VT.
(180)
0
0
0
U
-6,-
That is,
(E2 (1)-
E1
E
AG- AT BdB = V ((52 ET)T EN GET
-GE UTD
VT
(181)
{1
-4
V ((& E1 +8T 22/-" VT
(182)
VDVT.
(183)
with D= (E2 - G TE E, and, hence,
AAG--A")~-
(184)
By defining h = (h 1/, 124 = 1 w. we thus have that A (AG--AT) -1 "Ah equals
(g2
(h2 - hh)) + (gz DDD LONDD--VM((M" M(h3 ht)
(ga 92) VD- (1.2 h²²) + (ga (ga- V M(h3 124)
V - 12') +
- -MVVD--V" M(h -14)
(185)
MMV -2h)--)---- -
hht)
The evaluation of Equation 176 is now stated in Algorithm
Note that the computations in Algorithm 3 are most of the time only scalar-vector products vector-vector additions, and the matrix-vector products in lines g can be implemented efficiently. Furthermore, the only terms that change between quadratic programs are the scalars 92, 93, and Eι, E2, εa- That is, in A in the beginning. All
the implementation of DCON, we only need one singular value decomposition subsequent stops involve only basic linear algebra subroutines that can be implemented efficiently. Note, however, that the memory requirements still may limit the above algorithm, as singular value decomposition of M involves in general dense m matrix V.
39

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 3: Evaluation of Equation 176
Input: Right hand side vector Output: Next iterate = (1",, ,0 2.00 @0 + gaw"
A 92te + Sasw
h + 1
h fu
e' VD='VT(R 1
f < c
E + VD-IVTMO -19)
fa M
V² h²
(g2 91 +
2² t²
(ga (e)(e' +
8 ha ( 14)
12 5¹ + (f" +
13 return
D Convergence Analysis
D.1 Preliminaries
For some of the proofs, we need additional concepts and results summarized in the following.
Definition 3 (Semialgebraic set (Bochnak et al. 1998)) ). A set D C R is called semialgebraic if it can be represented as the finite union of sets of the form
{x EE Pi(x) = _..._ (m)( = 0, Q,Q)(z) ,0...,, Qma (x) > 0},
(186)
where mp, mQ E No and Pi..... Pmr: Qi...., Qma are real polynomial functions.
Definition 4 (Semialgebraic function [Bochnak et al. 1998 ) A function f RR" R is called semialgebraic if its graph
= ( E R"+1 : = -
(187)
is semialgebraic.
Lemma 8 summarizes some results used in Zeng al. (2019) that also need in our convergence analysis. Thereby, we indirectly use the concept of so-called subanalytic functions. Since we are not directly working with subanalytic functions, we refrain from a rigorous definition of subanalyticity and refer to Bolte et al. (2007) for further details.
Lemma 8, The following holds true:
The composilion of semiaagebraic functions is semvialgebraic (see Proposilion 2.2.6 in Bochnak et al. (1993))
The sum of semialgebraic, functions is semialgebraic (see proof of Proposition 2.2.6 in Bochnak al. (1998)..
3. Semialgebraic functions are subanalytic (see Shiota 1997)).
I R [00) is sulonalytic function with closed domain, which is continuous on its domain, then is a KL function (see Theorem 3.1 in Bolte et al. (2007)
D.2 Proof Proposition
B
Proof. The main idea of the proof to show that RegLoss,, semialgebraic. Then, by point in Lemma it follows that RegLoss., is subanalytic and, hence, by continuity and point 4 that it KE function.
40

---

Published in Transactions on Machine Learning Research (01/2024)
To do so, proceed as follows. First, we rewrite RegLoss,
m
N (0)
RegLoss, osss, (0) =
Σ
+ +
(188)
/=1
i=1
j=
where we use the following definitions
1 (g) - w) v (w) =
(189)
fi,(0) 0,77 (wwi, xz)) + b:),
(190)
fi (0) Y (wwr, mÿ) + 6:)² and
(191)
m
(0()) m ||a|?
(192)
If all the above functions semialgebraic, point 1 and 2 of Lemma yield that Equation 188 is semial- gebraic. That is, we only have to check each of the above functions individually.
The functions ,,, for j E (1,..., m), are one-dimensional polynomial functions and thus trivially semial- gebraic. The graph of fua can be written as
G(Sc)) = =(0,)): == f()
(193)
=( z= (1w,, rz) + bb) 0} U =() as ((w,, 1z) + b,)
(194)
0, ((wi xz)) be) > 0)
(195)
U ((0,z): = 0, (wwi, mr)) + b.) = 0}.
(196)
The involved functions are all multi-dimension polynomial functions (at most quadratic) in 0, where coeffi- cients of unused variables are set to zero. Hence, fij is semialgebraic. The function fij is a multi-dimensional polynomial function and therefore semialgebraic. By writing as
(0)
Σ
0
(197)
m
the structure of & is again polynomial, and, hence, it is a semialgebraie function.
Applying point and of Lemma S yields that RegLoss, is semialgebraic. By point 3 of Lemma also subanalytic. Furthermore, the loss function continuous and, hence, by point of Lemma g KL function. The form of yp follows directly from Theorem 3.1 in Bolte et al. (2007).
D.3 Proof of Lemma 2
Proof. First, observe that the first two summands of gi are not strictly convex. Hence, we only consider the last summand, i. e., we have show that
m
(ww), x,) + bi)²
(198)
is strongly convex. We set == (wi,b) and proceed as follows:
m
7 (w1) 2z)) bi)² - 11101/
(199)
m
2 |M - p
- 111111
(200)
2
= (v. (2M² M 21) v)
M
(201)
m
41

---

Published in Transactions on Machine Learning Research (01/2024)
The above function is convex if the eigenvalues of the matrix in Equation 201 are positive. The spectrum of this matrix is given by
10
2 a is a singular value of M
(202)
By setting the above terms to zero, the claim follows.
D.4 Proof of Lemma 3
Proof. Rewriting the left-hand side of Equation 15 as telescope sum yields
(x hx(=²) (9((=)) 1x(=*))
(203)
(91(2)) - h1(2²))
(204)
Σ (p(g)) + p(hi)) -2--2--111
(205)
where Equation 205
follows by Lemma
Furthermore, we bound the sum of squared norms from below
by Σ || - 2
x5-1 & 1| - =011,, which yields
K
p(gi) + p(h))
(1 he(=²) (sc(=*h) - -ho(=*]]
=001
(206)
K
p(g))
|| =0112
(207)
2 min (M) - 112K-200 2012
(208)
Km
270 min mM) 1|2 2013 Km
(209)
where the last inequality follows from Assumption
D.5 Proof of Lemma
Proof. First, we observe that (a) is strongly convex with modulus y. Hence, the inequality (*(a*) (a 2 (a a a *+1) + Illa* 2 holds truc. Second, the solution of A fulfills (a 0, which proves the claim.
D.6 Proof of Proposition g
Proof. We proceed as follows. When starting the inner iterations of Algorithm 1 with 0², we denote the parameter vector after the (-th DC subproblem with &.c,k and get
RegLoss, (0)) ) RegLoss, ( (0R+1)
(210)
RRegLoss, (8t) Σ
RegLoss, (0DC,
(211)
RegLoss, (0Dc.t) (00 - RegLoss, (0*+))
(212)
42

---

Published in Transactions on Machine Learning Research (01/2024)
After reordering the summands, this yields
RegLoss, (0*) RegLoss, (B
(213)
(ut b(t) (wt b(tt)) + -0a0))))0)00))))
(214)
N
min (M)
1 (/+t1 (wf b1) + 1 Illat - 11
(215)
Km
1=1
20
(ww (w/tt1 ,6 (bttt (ut b12 11a - / 112 112)
(216)
=0
||ght1 8/112,
(217)
where a min mm (M)
3.
Km
D.7 Proof of Lemma
5
Note that, due to (H1), Algorithm yields a monotonically decreasing sequence of loss function values, e., RegLoss, R < RegLoss, (0t) for all k E N. This ensures the boundedness the sequence (0h) kEN, since
Proof.
RegLoss, (0)) 2 RegLoss, (0k) 2 Σ j=1
(lUF x0g) + bb))
(218)
mmin (M)
(u 11
M
(219)
RegLoss, (0%) 2 RegLoss,, (0k)
la 112.
(220)
m
Hence, all trainable parameters are uniformly bounded.
D.8 Proof of Lemma 6
Proof. First, Lemma
ensures that 0² E Br(() for all N. Second, we note that the functions
N
(0) E(2y)or) + Σ
20(0,00)(((3;2))) + b.) +
20(0)a)))(((u)z))) 24)) + bb))
(221)
i=1+1
(0) m
(2g)or)) +
2((az0))0((u,, + bi) +
((( 2z)) bk)
(222)
are sums and products Lipschitz functions. The claim then follows as sums of Lipschitz functions are Lipschitz and products bounded Lipschitz functions are Lipschitz.
D.9 Proof of Proposition 10
Proof. In the following, we make use of the so-called smooth variational description of Fréchet subgradients detailed in Proposition 17
Proposition 17 (Proposition 2.1 in Mordukhovich et. al. (2006)). Let f R" + R U (20) be finite at T. Then, x' OF f(x) if and only if there is a neighborhood U of x and a function s + R which is Fréchet differentiable &o with derivative ( such that
s(7) = f(T), Vs(T)= = xx, and s(x) < f(x) for all a E U.
(223)
43

---

Published in Transactions on Machine Learning Research (01/2024)
To prove claim, we show that v08, Eg. 6h) is an element of the Fréchet subdifferential of the loss function. First, we observe that, due to Proposition 2
we have that
RegLoss, (wi, bi) ct + gu bi) hu(wi, br).
(224)
Second, we have that for all eh th fulfilling
(21
m
(1))) 1
Vg (u bi, 09
Σ
gg
Fij
H
Øjj
+ (gi(ur, bt),
(225)
bi
where
m q
Σ j=1
oi m
H ((u), 22)) +b) (7)
(1u), 23)) + +b)
m Σ
2
[23]
(w) + bi),
(226)
(1)
m
j=1
and
m
)1)
yn(wr, bi, )))
8he j=1
Zj
H
Wi bi
E alx(wr,
(227)
We now show that yo (wt, bi, e - (wr, ei,) E O RegLoss, (wr, bi), where the differential operator corresponds to the partial Fréchct subdiffercntial with respect to (wi, whenever e and ch fulfill (22
Note that
Vg (wi, b,, e - (wr, b,, c") = ((vr, by, ett, (e vi ei e"
(228)
That is, with a slight abuse of notation exactly as given in 26 and (9 Note also that RegLoss, is differentiable with respect to a. Hence, the element Vo,r in (31 18 exactly the partial derivative with respect to a.
To prove claim, we first note that a RegLoss,, (wf. (uf.00 B9) (VRegLoss, (wff b9)) for all (uf bf) with (wf, 2z) + bf + 0 for all j E mb]. Furthermore, this case yields (n by e Vyr (ow./,0g b9) and In (w b8. cht) = Vhi(wf, b)). Thus, the claim directly follows in this case.
Now, assume that we have a (wf, bf) such that there exists a non-empty subset J S f1...., m} with (wf, (,,x,,))+ Df 00 for all j E I and (uf,,,)) + + for all j & J. By continuity, there exists a neighborhood U of wff.bf such that (un, mz))
o O and sign((wr, my)) + bi) = sign( (wgg((ff 2z)) + B)) for all (w), bi) E and $ J. Let e eh E [0, 1Jmh fulfill (11) and (22). and let the function
R be defined as
s(w,, bi) =q + Σ B a ((u), + bi) + Σ
89 (1m),,z)) bi)e
(229)
14J
JEJ
m
m
afo((u), + bb)) + ? Σ (w,,, + +b))
(230)
Σ
8h a (ww), xz)) + bb) - Σ
8 (ww,, xz)) + bi)e Ar
(231)
3E3
hEJ
Then, s is differentiable in U and Vs(uf (0) = yg (w) b9 enh - yn yn (wf e)) as
44

---

Published in Transactions on Machine Learning Research (01/2024)
0
Σ
89f0 ((11, + + + Σ
8 (wn, + bi)e (w0
(232)
awi, bi)
iEJJ
JEJ
8 H (ww + ui)
(4)
[ij
+ Σ
g
Ij
of
(233)
(1)
(1)
JEJ
Σ
13 H (wwf mz) + bf)
+
Σ
$3 H (kwf Rz}} + +b)
3ij
(234)
1
1
j4J
jEJ
8 H (ww) xz) +,)
24
(235)
==1
and analogously
① A(w,, bi)
(-
Σ
th o((w), bi) - - 2hth ((w1, 2z) + bi)c"')
(236)
(w)66))(10P.09)
j4J
SET
m
Σ
2 H (ww9, + b9)
(237)
To prove that Vs(wf, bf) e of RegLoss, (w. b9), we make use of Proposition 17 that
That is, we have to show
(a) stof, bP) RegLoss, (wf, 89) holds true, and
(b) s(w,, bt) < RegLoss, (wi, bi) for all (wi, bn) E U.
For point (a), we arrive at
s(wi,b9) -q + Σ B x1) +/) + Σ
39 ((u) ((wf, xzz) + +10) be)e
(238)
343
JET
a10((10 m3) + b1) + 7
(Ww f m.y) + bg)
(239)
Σ s 24)) + 69) Σ
B/ (wof 2.) + bl)ct
(240)
JEJ
JET
=q +
3 (ww) x
(241)
afo((1) ) + b0) +
(wwf æz) + b9)
(242)
j=1
Σ
8/ o ((w] xz,) + b,)
(243)
j=1
=q + g6 (w] (8) he(w, (00) = RegT.oss (ws b9)
(244)
45

---

Published in Transactions on Machine Learning Research (01/2024)
For point (b), we proceed as follows. Let (wi, bi) E U. Then,
s(w,, bi) =q +
Σ 8 o(ur, Rz)) + bi) + Σ
89 ((111 + b
(245)
345
jEJ
Σ ((u1, + +bi) + 7
Σ (())) + b1)²
(246)
==1
j=1
Σ
8g o ( xz)) + bi) - Σ
B ((ur, xz)) + bb)ee he
(247)
jEJJ
jEJ
Sa +
Σ ff ((ur, }3)) + bi) + Σ
8 a (a0, 03)) + bi)
(248)
34J
jEJ
aio 2(0( + b1) + +
(()), + bn)
(249)
==1
j=1
Σ
8/ o ((w,, kz) + bi) - Σ
By ((wi, xz)) + bi)
(250)
JEJ
jEJ
RegLoss,,
(251)
holds true if and only if
E ef - ((wn))))))) + +b)) = >. - (0)))
23) + b1).
(252)
JEJ
jEJ
For (ww1, + bi) s 0 we have that
(8 e 8 e ((ws, 23)) + b1) - 0 = =03 - 1311) (o(ur, xz)) + bi),
(253)
as (8 - 2 2 by 22 For (ww), .zy) + bi) > we have that
(39 8 c ki ) (wi, mz) + bi) s (6 - 3/50 )o())o 2z) b1) +
(254)
(8 0t - 3/ ) S (3 - 1,
(255)
which again holds by 22 Thus, the incquality in 252 holds true and the claim follows by Proposition 17
D.10
Proof of Lemma 7
Proof. Let le E N and e [1. be arbitrary. We denote with (uf+1, bl++2) the element (wi, b,) in g
By Assumption and Proposition 10 we know that
m
) eg
k+1
3 10h+1)
H
(256)
1
18+1
1=1
+
m
(a)
12
H
(
w
bl+1
Dzj
(7) ((
w b+1
b
1
(257)
m
J=1
7
w
k+1
+
(258)
b
m
1=1
k+1
ghu
(Oh+1)
H
w bi+1
cj bii E (o D. RegLoss, (0*+1),
(259)
1=1
where & and Bosk are given in Assumption
Furthermore, Assumption 3 yields
46

---

Published in Transactions on Machine Learning Research (01/2024)
((
x+1
89 (opc
zij
1
H
bltt1
zjj
1
(260)
m
(at)² H
(
(<
(((#ft)
zj
1
1
(261)
77
(
Ij
(262)
bltt1
m
m
8 (0/(0) (0) ())C.))
Zij
H
(((0/
++1
(4)
(1))
zzj
(263)
i
b
Then,
27
6++
1/
k+11 00
(264)
110
(89t (0h++1) (0g
(1:) H
(
(265)
bet1
m
(a) 1)2 2 - (a/)2 11 ((
112
(
(((641)
x
((+t1)
(1(1)
(266)
m
1=1
w k+1
Σ (ottt)) - -1h (0/ (opc.))
H
beck
(267)
b/
and, by writing (a (att)² as (a (at k- + at) and using Lemma and Lemma C independent of such that
we yield
| s Clight1 - opcc||1 + Claf+ ++ afl.
(268)
D.11 Proof of Proposition 11
Proof.
First, we observe that va (0k++) ( = (O*(a)+1)
0. Then, the proof is
direct application of Lemma Let
h+1
(uf
k+1
: 2222
6+1
o k+t .0) E 8² RegLoss, (ak+1),
(269)
where oft1 for E (I....,NN N} is given as Lemma Then,
N
N C
|
o
||| S
C
Σ
k+1
of
(270)
1=1
1=1
$ C
|0++1 8 + Clla -I a²112
(271)
< (N + 1)C100110+ - -011
(272)
Since all norms are equivalent in finite dimensions, this proves the claim.
47

---

Published in Transactions on Machine Learning Research (01/2024)
D.12 Proof of Proposition 12
Proof. The following is based on the theory in Attouch et al. 2013 First, note that Assumption
1
implies min (M) > O, and, hence, there exists at least one solution to [PNN] by Proposition [
Now, let 8" E mig RegLoss, (6). The claim follows by Theorem 2.10 and condition (H4) in Attouch et al. 2013). For the sake of clarity, we shortly restate the two statements in our setting.
(H4): For any 8 > 0, there exist O p 6 and 0 such that
x E B(x", ,), f(x) f(x)) + = [(x) y $ p)
=5(x) < f(y) + ally x||?,
where a the parameter of the sufficient decrease condition. With the above condition, it possible prove the convergence local minima.
Theorem 3 (Theorem 2.10 in Attouch et al. (013)) Let f: R" BR(Oo} be a proper lower semicontinuous Sunction which salisfies the Kh. properly at some local minimizer x² Assume that (H4) holds al x². Then, for any r >> 0, there crist u E (0,r) and O such that the inequalities
||x0 x x01
and f(x') f(x <(xx)+
(273)
imply the following: any sequence )ee that starts from x² and that satisfies (HI) and (H2) has (i) the finite length property, (ii) remains in B(x"r), and (tit) converges to some I E B(x",r) critical point of f with f(z) = f(x).
From Remark 2.11 in Attouch al. (2013). we know that (H4) satisfied for local minimum x" the function satisfies
f(w) 2 f(x²) a -lu x²1 for all y E TR..
(274)
Now, it is easy to see that, for all 0 e RW,, we have
- a 11 0 10
RegLoss, > RegLoss, (0*) 2 RegLoss,,(""
(275)
4
and, hence, the claim follows by Theorem 3
D.13 Proof of Proposition 13
Proof. The proof essentially follows the one in Attouch & Bolte (2009) where it is tailored to the proximal algorithm for nonsmooth functions. Hence, restale the proof and adapt it to our setting and notation.
As in Attouch & Bolte (2099), we assume w.l.o.g that RegLoss,((0)) = O. Now, let S₁ denote the tail of the scries of distances between iterates, i.
2 S₁
Σ
1 8'11
(276)
Then, we first observe that
|10h - 00 S |10h - gh+1|| 1| + -0'l <
(277)
100t1 0'll + |
0+1 K+*00
St-
(278)
Hence, it sufficient bound St. To do so, we prove the intormediate result
C₁
Sk < 0 g
r(1 r) RegLoss, (85)
(279)
48

---

Published in Transactions on Machine Learning Research (01/2024)
for constant 0 0, (0, 1): specified in the KL property, and for & sufficiently large.
Let p(s) = CK be the function specified in the KL property. Then, we have
p(RegLoss, (0") - vo(RegLsss (0*+1))
(280)
2Φ' (RegLoss, (0') (RegLoss, (0') RegLoss,(0**))
(281)
2/y (RegLoss, (0" )a 1'1
(282)
where Equation (281) follows by the concavity of o and Equation (822 follows by (H1). Now, for i 2 Ko: we can use the KL inequality and yield
alleit1 - 10 = *(RegToog (0¹) - sp RRegLoss, (0' (0'+))
(283)
4 P'ReLLsss, (6+))
s (RegLosss ( - 40 (Regl Loss, (0(+))) ||0²||
(284)
s (R (0')) - (RegLLsss, (o++)))) bll0* - 11.
(285)
where the last inequality follows by (H2). Hence, we have
||0+1 0¹1/2
b
1 (v(RogLoss, (0*) y ((RegLoss, (0(+1))) a
(286)
||0| - 11
C ((RegLoss, (00) (RegLoss, (0+ 2-)).
(287)
Now, let E 10 be arbitrary. If |10 0' 1110i -0i 0i--11, the above inequality yields
1100t1 - 0'11 S Ci (RegLoss,, (0))) 1-5 (RegLoss, (0 (0i+1)) 1-5).
(288)
Hence, we have that
||0011 11 S r - 10 C1
--ReLLosSSSS (RegLoss, (0(+1))=
(289)
By summing up the above inequality from Ko to some K 2 Ko, we yield
K
10t+1
0'1l
(290)
Ko
K
100 -00--111 001111 11+ + Ci K
Σ (R)) 1-5 (RegLoss, (0 (0++1)) 1=5 r =
Sr
(291)
i= Kg
K-1
Σ
110 0'1l +
Ci
(ReggLoss, (0Ko)) 1-E (RegLoss, (0 (0K 1-5) 1-5)
(292)
K=
K
|0/+1 - 0'11 + Ci
(RegTosss, (otKo)) 2-5 (RegLoss, (RegT.oss(0oKt))) (0k++)) 1-5)
(293)
k=
+ 0k
0k 1| - r110k+1- 0K11
(294)
K
Ci (R8 2-5 (RegLoss, (RegLo8s,(0KK+1)) (0K+11)
Sr | - 04l +
(295)
k=
+ +r 0Ko-111 -
(296)
Hence, by rearranging terms, we arrive at
11+t11 - 0'll <
110k0 - -kk0-11
(297)
Ko
Ci
(RegILoss, (0Ko)) 1-8 (RegLoss, (RegI.os,((KKt1)) (0*+
(298)
r(1 - r)
49

---

Published in Transactions on Machine Learning Research (01/2024)
For K oc, this yields Equation 279
To prove our claim, we again make use of the KL inequality, From Corollary 16 in Bolte et al. 2007b and the resulting definition of ,,, we know that
RegLoss, (RegLoss,, (0h) RegLoss,,;00))
S <11-))Ckl
(299)
||u*1|
1
for & large enough and || 0.
Now, are ready to prove each of the three cases.
Case 1: =0
Let [k E N: 0h + 0 and let k E I large enough. We assume w.L.o.g. that || + O. Otherwise, we would have that vt for all I and, by (H2), for all e N I, and, thus, the algorithm would have been already initialized with a critical point. Now, from Equation (299), we have ||=*]| 2 Ckt. From (H2), get b²1l0* - 1|2 2 || 2 CKL and, hence,
Cki. 110k - 11- 2 6
> 0.
(300)
By (H1), this yields
RegLoss, (0%) < RegLoss, (o0gLoss,((011)) -0²-212 5 RegLoss (aogLooss(0011 (0h-2)- aCki.
(301)
and, hence,
aCxi, 6
RegLoss, (8h) RegLoss (0k-1) 1
(302)
Since the left-hand-side of the above incquality converges zero, this implics that I is finite and, hence proves the first claim.
Case 2: & E []
Let k 2 Ko. We assume w.l.o.g. that Sy > 0 for all k 2 Ko and ||o*|| + 0. Now, Equation 279 yields
C₁
S₁ S --r (Sa-1 - Sp) r(1 - r) RegLoss, (05)
(303)
From Equation (299,, we have
RegLoss, (Bh)E) 1=
$ (11 CKKL)) +
(304)
||
RegLoss., (04))
< ((1 CKT. 3/5 ||
(305)
+ - 0/
< ((1 ()..
(306)
C2|10* 0h-11| 1=1
(307)
RegLoss, Reg) < C2 (Sa-1 Sh)) 1=
(308)
and, hence,
(S Sx) + C₁C₂ (Sk-1 -St) 1-6 r(1 - r)
Sy <
(309)
1
50

---

Published in Transactions on Machine Learning Research (01/2024)
Let K1 2 Ku be such that Sk-1 Sy= < 1 for k 2 K1. Since & E (0, 21, have that 1-1 1, and, thus, Equation (309) yields Sp S C3 (Sk-1 Sk) for a constant C3 > O. With TH05 this yields
0 E Sk S qSk-1 S gt SiSK, Ok |0
(310)
for k 2 K1. The sequence ag converges Q- Q-linearly to zero with rate 0 1, i.e.
ax+1 q. 10000
lim
(311)
Thus, by definition, the sequence (0t) converges R-linearly NNcedal & Wright 2006).
Case 3: E ()
Analogously case 2, we yield Equation 309
Since (2,1) 1) and Se 0, we have that 1-3 and
that there exists K2 2 Ko and constant
0 such that
k
CS Sk)
(312)
for all k 2 K2. By proceeding analogously to Attouch & Bolte 20099 (see derivations after Equation (13)
therein), there exists a constant C₁ > such that
Sy Cgk: x-
(313)
for all k 2 K2. This yields
110b - 100-0011 S Sb s Oak 2 =: ab.
(314)
The sequence dg converges Q-sublinearly, i.e.,
1-c
lim
0k+1
lim
k
1,
(315)
100
ag
k0000
(I: + 1) 25-
1-c
and, hence, the claim follows.
D.14 Proof of Proposition 14
Proof. Let a RegLoss, (0+) and a" RegLoss, (0*). By Equation 299
from Proposition
13 we know
that
(a=-a" (a)=
|| S (11- CK]
(316)
for large enough and ||o*|| o O. Hence, we yield
a al10++1 0h112 2 ab *1 2 ab (a++1 - a*) 2²)2
C (att1 - -at) -a))
(317)
((1 C)..))
for large h, where the first incquality is due (H2). By (H1), we then have
a² a 6+1 +alloht1 1²112 2 a x-1 CC =a²)²²
(318)
and, thus,
a k- a" k+1 aa" C Catt1l
(319)
||u*|| * since, otherwise, the algorithm would have converged in for large enough k. Note that we assume finite number of iterations.
51

---

Published in Transactions on Machine Learning Research (01/2024)
We start with assuming that & > 2 and yield
la - a*1 lim
ak+1 a²
a a*
lim R=000 lat - a+1
S lim
(320)
10000 at - a
k-000 a ah+1 a + C C(att1 - -
lim 1-000 1 + C (alt1 a+) 2 =1
(321)
and, hence, sub-linear convergence. Furthermore, for { = 2,2 the above limit is bounded by 1/(1+ which results in linear convergence.
Now, we assumne that & E (Z(+TT): T for y E and proceed as follows. First,
- aa)=a))² ( aa' a' CC - -aa 22)
(322)
holds for k large enough. Second, we yield
la k++ a²)
a a²
a k+1 a
lim k+0
lim
S lim
(323)
aa
a=10
10000
(a* a²)
k-
a - a + C (alt1 - 22))
a k+1 a*
lim
(324)
+00
(ak+1 at) Ca (ak+1 at) 281
lim
(325)
10000
9 (t) (akt1 (-)
1
< lim
(326)
10000 Ca (ak - -=0 122--11--1---111
Now, for & 24 it follows that 9 (25 1)9 - 1 < 0 and, hence, that the above limit is zero. For & have that the above limit is bounded by 1/C9, which proves the claim. Note that the special case & = 1/2 has been analyzed separately above.
1 we 24
D.15 Proof of Proposition 15
Proof. Let S 24 for q E N22. Furthermore, let U be a neighborhood of in which RegLoss, is strictly convex. Now, let r (0, 1) be such that (f*) S U* i.c., the closed ball with radius around 0 lies inside ext via
U". We define the function RegLoss.
RegLoss, (0) RegLoss,,00 (0*) i E B,))),, elsc.
RegLoss ext (0)
(327)
c0,
Note that RegLoss, is a proper, convex, lower-semicontinoous function with min RegLoss ext (0*) arg min RegLoss ext From Theorem 5 in Bolte et. al. (2017) we thus get.
and
||0 0* s CKL. RegLoss ext (0))
(328)
for 0 E (0')") with 2 >>> 0 sufficiently small. Furthermore, from Theorem 3.1.8 in Nesterov 2003 know that there exists a constant L such that RegLoss, is L-Lipschitz in (0*),, and from Proposition 14
we know that there cxists constant Cg 0 such that |RegLoss,, - (e*) S Cg RegLoss (8*) RegLoss, 19, for large enough k.
52

---

Published in Transactions on Machine Learning Research (01/2024)
Now, for & large enough, yield
| - l*l Cka. RegLoss (eg RegLoss, (00) (0-)
(329)
s CKI. - RogLass (0+) RegLoss, (0*) (00))((1-3)
(330)
C 10 0= (010((=-3)
(331)
C 110 0 110-1
(332)
and, thus, |10kt1 - 0-1| 2 - 11100-00100- for C = CKI. C2
D.16 Proof of Proposition 16
Assune that 0" = (ax", W" b*) fulfills
(w) x,) + + #0 ViE (I.....NN and Vj (L...., m..
(333)
If 333 holds true, there exists neighborhood U of 0 such that (w;, mz)) b + for all i E (1..... N)
E ....., m), and 0 U That is, RegLoss, is twice continuously differentiable function in U*
Furthermore, by assumption, (e") is invertible. From Proposition 1 in Huang et al. (0019 it then follows that RegLoss,, fulfills the KT. property at l" with & = 1/2, i. i.e., there exists a C>> and r 0 such that
RegLoss, (0) RegLoss, ( & ClIVRegLLss, (0)
(334)
for all 0 E B, U
53

---

Published in Transactions on Machine Learning Research (01/2024)
E
Discussion of our Findings in Context of the Kt Literature
Proposition 13 can be seen as standard result in the KE literature (see, g.g Attouch & Bolte 2009
However, Proposition 14 and Proposition 15 follow from stronger assumptions on the underlying objective function. The main difference that the standard assumptions on the objective function f in the KT. literature (see, e. g.: Attouch et al. 2013 are usually the following:
The function f is assumed to be proper but is allowed to take infinite values, i. i. f : - RU(x). This allows to incorporate convex constraints in the objective function via a characteristic function. In our case, RegLoss, is always finite.
The function f is assumed to be lover-semioontinnoss This allows for much larger class of optimization problems, but renders the analysis of the convergence in value obsolete, as x² + x² does not imply f(**) - f(x*). In our case, RegLoss, is continuous.
As such, our results in Proposition 14 and Proposition 15 come from the fact that is finite and continuous in our case. In fact, we can extend the results in Allouch et al. (2013) under these additional assumplions as follows.
Proposition 18 (Extension of Theorem 2.9 in Attouch et al. 2013 Let all assumptions of Theorem 2.9 in Attouch et al. (0015) hold. Furthermore, let f - I be (fintee, continuous, and a KL function with &p as given in Proposilion
8. Let & be the KE exponent associaled with ã. Then, the following holds true:
I 2(++1)+ 2 f(x*) converges to f()) with order q E N.
IJ > 3, f(**)) converges Q-sublinearly to [(T).
Furthermore, if 11 ) we even observe Snner-Q-coovergencc
Note that the proof of Proposition 14 merely uses the continuity of f, the KE property, (H2), and (HI). Hence, the proof of the above proposition follows the exact same structure. Furthermore, the following holds true:
Proposition 19 (Extension of Theorem 2.9 in Attouch et al. (2013) ). Under the assumptions of Proposi- tion 18. let admit a neighborhood Ü of क in which is strictly conver. Then, the following holds true: If
2q for q E N22, the sequence (a*) (eE) converges with order at least q 1
merely uses the continuity of f and the finiteness of inside the ball BY(T), thus the proof of the above proposition follows the one of Proposition 15
Again, Proposition 15
We illustrate these results based on an example. We consider the proximal algorithm given by
x+l E arg min { ((w) + - 11 x112 : yy ER
(335)
where À is positive parameter that can vary for each k but remains bounded, i.e., X [A, (0, oo). We demonstrate that, under the above assumptions on the objective function f. the proximal algorithm achieves a much faster convergence than the one derived in Attouch & Bolte (2009). However, at this point., we want to emphasize that their analysis holds under much weaker assumptions, which allows to consider more general optimization problems.
Attouch al. (2013) derived (H1) and (H2) for the proximal algorithm (see Equations (33)-(33) therein) given that is a proper, lover-semicontimuou function that is bounded from below. Furthermore, if the function f is contimuus, (H3) directly follows. Now, let E N22 and f be defined as follows f(x) = --
Then, fulfills the KL property at the global minimizer 0 with & = 1/24. To show this, we define
54

---

Published in Transactions on Machine Learning Research (01/2024)
(s)) =s'== z0 2 and yield ('())
2g-1 24 8 क. Now,
('((xx) 29
1
||>||| 2
(336)
2q
29
[V](2)]] = 29 ||=||| 24-1
(337)
for all x + 0. That is, v = for all + O. Furthermore, fulfills all assumptions of Proposition 18 and Proposition 19. That is, we expect the itcrates of the proximal algorithm in this sctting to converge with order of at least z. In the following, we will prove analytically that the iterates converge even faster with order 2(g - }) In addition, we demonstrate our results numerically. Note that the analysis in Attouch & Bolte (2009) guarantees only R-linear convergence in this sctting.
As g is convex and differentiable for * have that Vg(x*++1 0 x x 0. The latter results in finite convergence. Hence, we assuine x k+1 f 0 in our analysis. The gradient of is given by
To compute the next iterate w²*11 given xt, we consider the function g(x) f(x) * -
Vg(z)
= 2q
||0|||
201-o1 T
+ i (x - -xx),)),
(338)
29
and, hence, the following equality holds
kt x²
29p
||,.411|
211-91 24-1 x.
(339)
29
which gives (1+
2qd I
|
|| || = || Thus,
|
|oo
(340)
x 12q
20 1 +
|
2(1-a1 24 1
24-1
| 1
24-1
(341)
12-11)
(
2411
||
201-911 2--
||
1|2011
24--1
(342)
24-1 Σ
(29-1)
24A
||
192
201-)2
2
1=0
1
(343)
-4-11
2q
1
24-1 1
(344)
29-1
2q 2--1
To confirm our results numerically, we set A 0.1 and vary g E 3,,3,4,5, 6). We use the above proximal algorithm to solve min ((x with 100 random starting points for each q. Furthermore, we estimate the convergence order via
log
-
(345)
1x il
log
for large h. The results are reported in Table
Evidently, the thcoretical convergence orders are also observed the numerical experiments. Our example shows that faster, e., super-linee linear, convergence orders can be achieved under additional assumptions on the objective function and, thereby, links our analysis to the general KF. literature.
55

---

Published in Transactions on Machine Learning Research (01/2024)
Table 3: Estimated convergence order (mean and std.) across different values for g E (2,3,4,5,6)
3
6
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
2.9931 (0.0325)
4.9834
(0.0702)
6.9582
(0. 1480)
8.9711 (0.1479)
10.9398 (0.2334)
F Numerical Analysis
F.1 Implementation of DCON
General implementation details. For our experiments, DCON is implemented as a Python package using C++ code to accelerate computations. is built using cmake. For building the Python interface, we For solving the quadratic programs, DCON requires Gurobi To accelerate lincar algebra the Intel Math Kernel Library We use Python class called DCON through which we can easily access the DCON algorithm via .itt routine. This class also implements function get teraeera to return the trained model as a keras model. An implementation of DCON using only Python code can be downloaded from GitHut
use pybind11 [ operations, our package
DC subproblem. In our implementation, the DC subproblem is approached as follows. DCA is stopped if either the norm of the difference two successive iterates smaller than 10-12 or maximum number of DCA iterations reached. The latter can be passed as parameter.
Alpha subproblem. The solution of the alpha subproblem given in Scction 4.2 is computed via singular value decomposition (SVD). For this, we make use of the Eigen library particularly the divide-and-conquer SVD algorithm bdcsvd.
Convergence critcrion. A parameter n_epochs is used to set the number of outer iterations M. an integer passed n_epochs in the . fit routine, DCON stops after the specified number of iterations. If n_ epochs is to "auto", DCON stops when the distance between two successive iterations smaller than 10-6.
F.2 Datasets
We searched the UCI machine learning repository using a systematic procedure. For this, we set the filter options follows:
Default Task: Regression
Attribute Type: Numerical
Data Type: Multivariate
Instances: 100 to 1000
Afterward, we filtered for datasets where Regression the unique task the column Default Task. Alto- gether, this lod to ten datasots. In addition, we filtered datascts that have least 100 training instances after the train-validation-less split, yielding nine benchmark datasets listed in Table 4 We note that the range of instances Datasets with fewer than 100 training instances might not provide enough data to meaningfully train and test a neural network, while those with more than 1000 instances could introduce prohibitive computational demands for 30 train-test splits as performed this work. summary, these criteria were chosen to provide fair and rigorous evaluation of the model performance.
chosen to strike balance between computational feasibility and rigorous evaluation.
htttes///gchho..co//pppia/aaaatt commppbbind/yybindii.
last accessed 02/ 02/12/21.
https://swk.gun http://wwwgg.ob..ooo// com httmm//roducss///ooem
last accessed 02/12/21.
https://softwant intel wtt.c//ootet////////aaaaaao//eae
kowpa//lnnntt-keeellllalaa-aa--- html last accessed 02/12/21.
bttps://github... httpa//////o///ooceeetttt//////
http:://eiggn..uufaally.../ accessed 02/12/21.
56

---

Published in Transactions on Machine Learning Research (01/2024)
Table 4: Datasets
Dataset
Description
Num. of covariates
DS1
Computer Hardware Data Set!
9
DS2
Forest Fires Data Set²
13
DS3
Stock Portfolio Performance Data Set
12
DS4
Yacht Hydrodynamies Data Set
DS5
Facehook Metrics Data Set.
DS6
Residential Building Data Set
105
DS7
Real Estate Valuation Data Set?
DS8
QSAR Fish Toxicity Data Set
DS9
QSAR Aquatic Toxicity Data Set
9
bstpa://arcatve.. sca uct. wdw. /tt.///tttttt////////aa /oep 1in dwaze last accussed 03/20/20.
bttpa://arcatve.... Sen uct wwt.////////// htt////ttttttt//////// wow.sttee/arrrrrrrr Juue aecosund 03/ 13/20/20.
bilya wwwea//eee.... uni wau
las accessed 08/20/20.
bilya /wreiarr.....c. uni whu da wfy.ttttttsssaaaa.
lust accossed 18/20/20.
httpe://nodstw..ccc act ads /atanatta Pawnboosseetttr
accousee 03/22/220
hstpes//ndciioe.ccc wds hagpst////eeeeeeettseeeettttaaae
luet aecessed 00/30/330
0S/20//20.
sttpes//arcstve.cc aggaaaaaetttt...aaaaaaaaaeottee
03/20/20.
F.3 Preprocessing
Each of the datasets are preprocessed using standard approaches, while taking into account dataset- dependent restrictions and recommendations. The following describes the steps taken preprocess the datasets.
Dataset DS1. We drop the columns VENDOR, MODEL, and ERP. Furthermore, we use RobustScaler and MinMaxScaler for features and target variable We split the data into 80 % for training, 10 % for validation, and 10% for testing. This split is repeated 30 times to obtain 30 different splits of the
data.
Dataset DS2. We encode month and day into numbers 1 1-12 and 1 7, respectively. As recommended, we log-transform area. Finally, we scale the features and the target variable with the RobustScaler and the MinMaxScaler, respectively. We split the data into 80 % for training, 10% % for validation, and 10 % for testing. This split is repeated 30 times to obtain 30 different splits of the data.
Dataset DS3. We concatenate the sheets 1st period to 4th period and keep the columns Large B/P, Large ROE, Large S/P, Large Return Rate the last quarter, Large Market Value, and Small systematic Risk training features. The column Annual Return. represents our tar- get variable. Finally, scale the features and the target variable with the RobustScaler and the MinMaxScaler, respectively. We split the data into 80 % for training, 10 % for validation, and 10 % for testing. This split is repeated 30 times to obtain 30 different splits of the data.
Dataset DS4. We drop the column prismatic_coeffccieee coefficient due to missing values. Finally, we scale the features and the target variable with the RobustScaler and the MinMaxScaler, respectively. We split the data into 80 % for training, 10% for validation, and 10 % for testing. This split is repeated 30 times to obtain 30 different splits of the data.
Dataset DS5. We drop the columns comment, like, and share. We use one-hot encoding for the column Type and drop all samples with missing values. Finally, scale the features and the target variable with the RobustScaler and the MinMaxScaler, respectively. We split the data into 80 % for training, 10 % for validation, and 10 % for testing. This split is repeated 30 times to obtain 30 different splits of the data.
We use the scalers of sklearn.pre preprocessing
57

---

Published in Transactions on Machine Learning Research (01/2024)
Dataset DS6. We drop the columns START YEAR, START QUARTER, COMPLETION YEAR, and COMPLETION QUARTER. We use a time lag of 4 as this was found to be effective in earlier research (Rafiei & Adeli 2018). We use CONSTRUCTION COSTS as the target variable. Finally, we scale the features and the target variable with the RobustScaler and the MiMMaxScaler, respectively. We split the data into 80 for training, 10% for validation, and 10% for lesting. This split repeated 30 times to obtain 30 different splits of the data.
Dataset DST. We drop the column No. We scale the features and the target variable with the RobustScaler and the MinMaxScalor, respectively. We split the data into 80 % for training, 10 % for validation, and 10 % for lesting. This split repeated 30 times to obtain 30 different splits of the data.
Dataset DS8. We scale the features and the target variable with the RobustScaler and the MinMaxScaler, respectively. We split the data into 80 % for training, 10 % for validation, and 10 % for testing. This split is repeated 30 times to obtain 30 different splits of the data.
Dataset DS9. We scale the features and the target variable with the RobustSealer and the MinMaxScaler, respectively. We split the data into 80 % for training, 10% for validation, and 10 % for testing. This split is repeated 30 times to obtain 30 different splits of the data.
F.4 Hyperparameter
All hyperparameters and their tuning ranges reported in Table 5 Of note, DCON has no hyperparameter related to training, only one related to the neural network architecture. In contrast to that, Adam has hyperparameters related to both the neural network architecture and the training process.
Table 5: Hyperparameter tuning ranges.
Hyperparameters
Tuning range
Adam (Hyperparameters related to training) Learning rate
100-,5-10-3,55 0.99)
First moment exponential decay rate 81
Batch size
{64, 128, m}
Adam (Hyperparameters related neural network structure) Regularization parameter
[10 210-2,10 3)
DCON [Hyperparaneters related to neural network structure)
Regularization parameter 7
{10-2 10 10 53
Note: The patience for early stopping was set 10 epochs for Adam.
F.5 Discussion of Generalization to Unseen Data
For the following analysis, we follow Mohri et al. (2018) and denote with X' C R" the input space and with the measurable set y C R. the larget space. Furthermore, let. D be distribution over Xx y' and the training set S = ((x1,1)) (I2, ......., (Im, Vm)) be i.i.d. samples drawn from D. The class of single hidden layer neural networks is denoted by H. and the elements depending on the actual paramcters O by hg. Then, from Theorem 11.3 in Mohri et al. (018)) it follows that, for å > 0 and ha E H.
log( 2m
(x ((ho(x) - )) < Σ (ho( vi + 4MRs(H)) + 3M2 ==1
(346)
holds true with probability 1 1- where M is such that [ha(z) S M for all (z,z) E X x and he H, and Rs(H) denotes the empirical Rademacher complexity of the class H. A broad stream of literature provides bounds for the empirical Rademacher complexity of neural networks. For instance, Theorem 2 in Golowich et al. (2018) gives bound in O (())) under suitable norm constraints on the neural network parameters and
x R
|||||| s B). That is, given > 0, boundod input and target space, and defining
58

---

Published in Transactions on Machine Learning Research (01/2024)
Hr (ho E H. |0|| r) for 0, one yields generalization bound of the form
E Elyyy/D ((ba(x)) - y)²² S (ha(s;)) y;)² + O
(347)
which holds true with probability 1 1- 8 for all he E H,,
Thus, one reason that DCON achieves a better generalization to unseen data compared to Adam in our numorical experiments (Section may be attributed to the superior training performance of DCON.
F.6 Convergence Plots
In the following, we show the convergence plots for cach combination of dataset and layer size for the At this point, we note again that
experiments in Section 6.3 The plots are in Appendices F.6
Lo
.6
" Eg is determined by solving min Σ (v1,((0CC.. ,, 1))2 + (vr c 1))² after each DC subproblem for 1=1 cach inner itcration. Here, the set C decodes the constraints in 21 As mentioned in the main paper, the rationale is to find the values for e that set the corresponding entries of v to zero for Λ = 1, which exist due to Proposition 7 Sometimes, numerical issues lead to poor estimates of the correct values of cg- The main problem arises in identifying the correct j E [I.....m] for which e, E [0, 1] and building the corresponding objective function. In our implementation, we decided vary the corresponding ef [0, if (w1, + bel with = 10-0. Afterward, the objective function built by sctting
m7
m
of H ((1) 23) bi) 2z ((w1, 2z)) + bi)
01,
3 Hd (1 + bi) 23 91
(348)
m
+
(uu) 22) + b() - Σ
8) (ww,, x3) + b1) x5,1.
(349)
m
/=1
j=1
172
e0 = >
3 Hd (m1), 25) + bi) + Σ
ai H (ww, Hz} + bi) ((wr, xz)) + b))
(350)
1=1
1=1
+
Σ
2 (wW11z)) + bi)
Σ
8 H (ww), x.)) + bi).
(351)
1=
3=1
where Hx)x) = 1 if x > - and zero else.
59

---

Published in Transactions on Machine Learning Research (01/2024)
N 10
20
N 30
"cor el shrne bikinn abcPeneril 11'
Noen ciennt briing ubdieortta (1 "),
Norn clenar friting culd trrerta I-"
(a) | 112
(b) |
||2
(c) || ||2
Detance betwee Iereees 1 g%
Detsect belvees fenees 1 #/.
Dituece inteen keides
8%
(d) 110 00112
(e) 110kt1 gl 112
(I) 10
0 11a
(g) MSE early training phase
(h) MSE early training phase
MSE early training phase
(oea)) reg. (ealy plos
(btt) (raly plose)
(bex) mg (exty prov))
Iolecad 1501
1001
1000
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 4: Convergence plots for dataset DS1.
60

---

Published in Transactions on Machine Learning Research (01/2024)
N
10
20
N 30
'con ver Enking abcPeneril 11
Noen cieaet briing Pudeeonttal (+ ")
Norn clever Fesiing culd frrerta J."
(a) ||e ||+++111
112
(b) 1|00 1|2
(c)
||
Detinee bewees Ierees 1 9.
Delsect belveen fenees 15 21.
Ditueee ieteen keidee
1%
(d) 110 1/112
(e) 110kt1
0² 112
(f) 10
0 1|2
y
(g) MSE early training phase
(h) MSE early training phase
MSE early training phase
Laperoos og [Mex] Ln. my (eadl prowe)
rg (seaf) in rg (poty plowe)
mg (Mtta) Do ig (ealy plowe!
1901
1060
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 5: Convergence plots for dataset DS2.
61

---

Published in Transactions on Machine Learning Research (01/2024)
N 10
20
N 30
Ycon ele Lrbing abcPeotria 11
Noe cieae traing Pudeeott I+ "
Norn clener Friting culd frrerta J."
(a) ||e
112
(b) | 112
(c) + ||2
17
Desance bntwen Ierees 1 4%
Detiece belven fenwes 1 1%.
Ditueee inteen kestes
21.
(d) 110kt1 1
(e) 110kt1 g² 112
(1) 10h-1
0 1|2
y
(g) MSE early training phase
(h) MSE early training phase
MSE early training phase
rg (seaa) rg (poty plowe
reg (Mtta) Di ig (ealy plow!
(bex) mg (exly prow)
1000
1000
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 6: Convergence plots for dataset DS3.
62

---

Published in Transactions on Machine Learning Research (01/2024)
N
10
20
N 30
"con el tiking abcPeneria [1
Noe cieant traing undPeortta (+ "),
Nom cieentt feeerts
(a) ||e |
112
(b) | 1|2
(c) || ||2
Desance between Ieneee 1 %1
Diturce seteen keidee l
1%.
(d) 110k+1 0*112 1/2
(e) 110kt1 8²
(1) 110
0 11a
(g) MSE early training phase
(h) MSE early training phase
MSE early training phase
(Meaf) in mg (pety plow)
mg (Mtta) Db. mg (ealy plow
(bex) mg (exlyrou) grow)
1901
1000
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 7: Convergence plots for dataset DS4.
63

---

Published in Transactions on Machine Learning Research (01/2024)
N
10
20
N 30
Ycon el Likinn abcPenrria 11
Nom cieaet traing Puderrt [+ "I
Norn clenez Fritin culd freerta J."
170
(a) ||e 112
(b) 1|00 ||2
(c) |+
Desanee betwen Ierees 1 9%.
Detsect beteee trree 1 2%.
Ditueee ieteen keites 1- -%.
(d) 110tt1 04/12
(6) 110tt1 112
(I) 10
0 1|2
131
13-
19
(g) MSE early training phase
(h) MSE early training phase
(i) MSE early training phase
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 8: Convergence plots for dataset DS5.
64

---

Published in Transactions on Machine Learning Research (01/2024)
N 10
20
N 30
vere brking abcPeneril 11
Noe cieant traing audeeerrta [1 "1
Non federti
(a)
||e 1|2
(b) 2 1|2
(c) || ||2
14
Desarce betwee Ioreee 1 %%
Detsece belveen frre 1 2%.
Ditunce inteen keides
5%
(d) |10 1/
(e) 110kt1 0²
(I) 1
0 11a
15
(g) MSE early training phase
(h) MSE early training phase
(i) MSE early training phase
(seaf) mg (poty plow)
reg Db. ig (eady plase
(bex) mg (exly prowe)
1000
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 9: Convergence plots for dataset DS6.
65

---

Published in Transactions on Machine Learning Research (01/2024)
N
10
20
N 30
"con el Lrking abcPeortil [1
Noen cieae braing audeeontta [1 "I
Norn clenez Friting culd frrerta I."
(a) ||e |
112
(b) 2| ||
(c)
||
Desance bntwees Iereee
1
Detsect beleees fonzes 1 8%.
Ditunee inteen keidee
8%.
(d) ||0k+1 1/112
(e) 110 0² 112
(I) 10
0 1|2
8
171
(g) MSE early training phase
(h) MSE early training phase
MSE early training phase
Logerias
(seaf) Ln mg (poty plowe)
ln mg (rea)) Lis rg (ealy plore
(bex) mg (exty growe)
1900
1001
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 10: Convergence plots for dataset DS7.
66

---

Published in Transactions on Machine Learning Research (01/2024)
N 10
20
N 30
"cor mere biking abcPenrtil 11
Nown beaing uudeeosrta ")
Norn clenes Frstin culd ftreeta J."
(a) || 112
(b) 2| ||
(c) || ||2
Desance betwen Iereee 1/
Detsect beleees fennes 1 FI.
Dituree setem keides
8%.
(d) 110 1/2
(e) 110 0² 112
(I) 1
0 1|2
8
(g) MSE early training phase
(h) MSE early training phase
MSE early training phase
rg (seaf) Ln reg (poly plowe]
reg Di. ig (eady plowe
(bex) mg (exty pro))
1000
1000
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 11: Convergence plots for dataset DS8.
67

---

Published in Transactions on Machine Learning Research (01/2024)
N 10
20
N 30
fcon el Erking atcPenrril [=
Noe cieaet briing Pudieorrtal ( [1,
Nom clerer Friling culd frrerta I."
(a) || 112
(b) 1| 1|2
(c) ++
Detanee beteen Serees 1 1
Deliees beteee teane 1 f%.
Ditueee seteen keites
(d) 110 0
(e) 110kt1 g² 12
(I) 10
0 1|
5
(g) MSE early training phase
(h) MSE early training phase
MSE early training phase
Legeraas reg (staa)
me (Mtta] Li. ng (ealy plowe
(bex) mg (exly prow))
Lis res (carty chooe]
1901
1900
Estimated convergence order
(k) Estimated convergence order
(1) Estimated convergence order
Figure 12: Convergence plots for dataset DS9.
Figures (a) to (c) show how the norm of the element the limiting subdifferential approaches zero as the number of iterations increase for different hidden layer sizes. Figures (d) to (f) report the distance between the parameter vectors of successive iterations, e., ||@ 6 ll,, and should empirically analyze convergence. We find that the difference between two successive iterates decreases gradually in all experiments. Figures (g) to (i) report the MSE for training with Adam and DCON, while Figures (j) to (1) estimate the convergence rale of DCON. We observe linear convergence in all experiments except for dalaset 5, where DCON terminates after finitely many iterations for all three hidden layer sizes.
68

---

Published in Transactions on Machine Learning Research (01/2024)
G Experiments using the MNIST benchmark dataset
Preprocessing. First, the image data (color codes of cach pixel) are scaled to lie within zero and onc. Second, the images, originally of size 28 x 28, are down-sized using interpolation to images of size 10 x 10 using sklearn. The reason is to fulfill Assumption [ for M. Otherwise, due to the large number of pixels that show white background, the matrix M singular. Afterward, we scale the data again with a MinMaxScaler. The target variables are encoded as explained the main paper. We split the data into 70 % for training and 30 % for validation. For the experiment the MNIST subset, we only the first. 10,000 samples of the training set. The test. data are already provided in the MNIST benchmark dataset.
Implementation of scalable version. For the scalable version of DCON, we implemented the ADMM approach described in Appendix C That is, we refrain from using Gurobi to solve (QP), and, instead, we
use cuBLAs and Thrust 13 to compute the basic lincar algebra subroutines in Algorithms 2 and 3
addition, we use an acceleration approach via over-relaxation; see Boley (2013) for details. We set the ADMM parameter p p= Orelax 1.4 for over-relaxation, and the maximum number of ADMM iterations C = 500. The choice determined via trial and error for the MNIST benchmark dataset and then hard- coded. We stop Algorithm 2 when both the primal and dual residuals are smaller than 10-3, see Boley (013) for details. The scalable version of DCON runs on GPU using CUDA.
Hardware. We performed the MNIST experiment on a server with an Nvidia Tesla V100 with 32 GB of RAM. After the train-validation split, we yield m = 42000, which results in a memory requirement of ~14 GB for the matrix (in double-precision floating-point arithmetic). For comparison, mediun-sized datasets as defined in the main paper require merely 800 MB. Furthermore, state-of-the-art training algorithms usually work in singlo-precision
noating-point arithmetic, while, recently, even half precision floating-poin arithmetic is used to speedup computations.
http:////acs.wtttt...cc///uuua/s accessed 02/12/21. http:://acss.ataa.a...//////bbbs accessed 02/12/21.
69

---

Published in Transactions on Machine Learning Research (01/2024)
H Runtime Experiments
In the following, we compare DCON and Adam in terms of runtime. The experimental sctup is as follows. We consider between 50 and 1000 training examples of the MNIST dataset and construct 5 to 50 random Fourier features following Rahimi & Recht (2007). Then, we use the same parameter settings as in the main paper for DCON and fix the number of hidden neurons N = 10 and the regularization parameter to ? = 0.01. First, we let DCON train for 30 iterations and mcasure the runtime in seconds. Second, we train again with Adam for each hyperparameter combination in Table and stop the training when it reaches the mean squared error DCON.
70

---

Published in Transactions on Machine Learning Research (01/202))
8
1.
13
14.14
61.4
40
08
9114
9733
177M8
122
172TH
201
200
20
2974
-40
40
12:0
12:30
17.00
54.00
65.53
77.0
12044
10L17
1STA0
17662
10.03
20405
20364
20775
Number of features
35
30
30
34T
3.22
16:11
14.16
20:00
27:20
41:0
02.45
0:00
72433
05.47
00.22
19070
1800
13415
14.04
15
07231
19334
21040
25
-0
20
13.30
12.32
22:22
+1:21
47.01
53.58
04.25
6778
10-22
15301
19365
19070
15
11:42
15:30
20:09
10
10
11.0
9034
18
54.11
053M
16000
111
12548
100
155
19306
19249
10
10
5
1.17
11/08
14:00
1::34
29:00
3329
30:3
84.10
12000
09.00
6538
19379
130
100
150
200
250
360
400
450
500
650
800
650
700
750
850
900
950
1000
Number data points
(a) Total runtime of DCON
50
45
11:11
13.43
10:27
1200
11:05
12:04
13:57
13:40
SC.48
18:43
17:23
16.15
10.13
0::04
22:4
22.4
24144
24.00
2.41
-40
40
11:54
13:29
17:37
13:44
12:00
13:22
14:07
15:43
18:17
10.70
20.17
20.00
22.79
24-08
24.77
Number of features
36
30
30
11.33
13:30
3.00
10--1
10:40
12:45
13:35
14:01
15,2
15.22
17:37
10.
20.00
10.00
21.07
22:35
23.05
37.07
20.03
25
20
20
12:35
52.13
15:14
A6.22
22.44
22.17
23.39
28.20
32.44
6411
15
10:24
12:00
14:97
201m
14.0
14:24
X314
27.1
-10
10
5
2.10
11.00
11.09
12:00
14.77
25.05
23.20
25.27
2017
14:14
29.99
35.00
30.00
2:54
42.22
42
4002
4614
48.13
100
150
200
250
350
400
450
500
550
600
650
700
750
850
900
950
1000
Number data points
(b) Average runtime of Adam over all hyperparameter combinations
8
1ear
13
122
0.40
1::0
1441
1:42
2:30
1144
13.4
0.4
0:30
0.37
1:34
1:07
44
80
10:4
16:0
13:30
1:2
0.77
0:45
0.02
0:55
0.64
1:12
Number of features
36
30
30
R:22
18:22
3.52
0.44
4:4
0.52
3.4
0.54
0:5
0:01
0.12
0.02
0.2
8:77
0.00
1.04
1:2
C2T
2:00
25
20
201
0.55
0.54
2:05
15
5:1
2.46
1:24
1:50
5.00
1.13
1:29
4.4
1.44
0.65
2:20
5:32
10
10
5
3.00
1/0
087
6.0
6m
2.42
610
41
1.34
15.0
8:0
3114
100
150
200
250
300
350
400
450
500
550
600
850
700
750
850
900
950
1000
Number data points
(c) Best runtime of Adam over all hyperparameter combinations
Figure 13: Runtime for DCON and Adam.
71

---

Published in Transactions on Machine Learning Research (01/2024)
Figure 13 shows the total runtime of DCON, the average runtime per hyperparameter combination of Adam, and the best runtime over all hyperparameter combinations of Adam. Evidently, Adam has difficulties reaching the same mean squared error as DCON in the "small number of features" and "large number of training examples" (lower right) region. Furthermore, DCON is consistently faster than Adam in the "small number of training examplee"" (left) region. At this point, we also want. to emphasize that the numbers reported in Figure 13e strongly favor Adam, as they report the runtime the fastest run among all hyperparameter combinations to reach the same mean squared error as DCON. These combinations are of course priori unknown, and we thus merely report the runtime for transparency reasons.
DCON requires no hyperparameter optimization and the above comparisons are made with respect to the average or best runtime of Adam per hyperparameter combination. Thus, for a more realistic comparison, we would need to compare the runtime of DCON to the total runtime Adam, i.e., the total runtime needed for hyperparameter combinations in Table Figure 14 shows the percentage improvements of DCON over Adam with respect total runtime. We can see large improvements by a factor of up 5.2 in the "small number of training examples" (left) region but still consistent improvements of around 2% in the "large number of training examples" and "large number of features" (upper right) region.
20.0
8
7.1%
6.%
38%
4.%
32%
305
215
18%
1.%
17.5
15.35
36.%
18.1%
7.1%
13%
56%
48%%
33%
3.5
345
27%
30%
27%
40
15.0
Number of features
35
181%
36.%%
30.5%
221
131%%
6.%
7.5
27%
51%
52%
5.1%
4.%
435
304
3..%
48%
34%
41%
31%
32%
12.5
30
10.0
33
20.0%
38%
43%
535
435
59%
34%
40%
20
29.4%%
17.8%
17
17.4%
11.
18.4%
12.3%
40%
7.4%
7.%%
7.1%
0.7
16.6
7.4
84%
4.%
7AB
63%
7.5
15
412%
M44
2774
2.5%
2.4%
15%
142%
12.%%
100%
122%
128%%
124%
137%
1025
105%
1335
03%
05%
-2.
215%
366%
22.%
222%
14.%
16.%
0.0
100
150
200
300
350
400
450
550
600
650
700
750
800
850
900
950
1000
Number of data points
Figure 14: Percentage runtime improvements of DCON over Adam.
72

---

Published in Transactions on Machine Learning Research (01/2024)
Experiments with Additional Baselines
Here, we also compared DCON against other, non-ncural basclines. In particular, we consider (i) linear regression, (ii) lasso, (iii) ridge regression, and (iv) kernel ridge regression. The hyperparameter grids can be found Table
Table 6: Hyperparameter tuning ranges for additional baselines.
Hyperparameters
Tuning range
Lasso
Regularization parameter
(10-5,10-1, 10 10
Ridge
Regularization parameter
(10 (10-8,10-1 10
10
Kernel ridge
Regularization parameter
{10-3, 10-2, 10,1,1,,,,,,, 10 (linear, roly,rbff.
Kernel
Hyperparamcceers tuned the validation
Evidently, DCON achieves large performance improvements on average against linear models. Furthermore, we observe improvements the training loss, on average, up 31% for kernel ridge regression.
Results are reported in Tables to 10
Table 7: Relative performance improvement mcan squared error DCON over linear regression.
Training
Test
N
10
20
N
30
10
N 20
N 30
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
DS
3.11
(1.09)
2.71
(0.68)
2.95
(0.79)
0.47
(0.75)
0.51
(0.60)
0.45
(0.75)
DS 2
0.34
(0.06)
0.54
(0.08)
0.67
(0.09)
-0.13
(0.22)
-0.24
(0.16)
-0.20
(0.15)
DS 3
0.18
(0.06)
0.23
(0.06)
0.26
(0.06)
-0.07
(0.14)
-0.10
(0.13)
-0.13
(0.13)
DS 4
3.88
(2.84)
3.73
(1.67)
5.09
(1.53)
2.72
(2.01)
2.87
(1.85)
3.27
(1.82)
DS 5
0.94
(0.02)
0.89
(0.03)
0.84
(0.04)
-0.55
(0.11)
-0.4
(0.09)
-0.81
(0.10)
DS 6
1.73
(0.58)
6.53
(2.03)
3.40
(0.86)
0.02
(0.47)
0.03
(0.52)
0.14
(0.55)
DS 7
0.51
(0.14)
0.67
(0.13)
0.72
(0.13)
0.27
(0.14)
0.35
(0.15)
0.39
(0.16)
DS 8
0.26
(0.06)
0.36
(0.05)
0.42
(0.05)
0.07
(0.08)
0.09
(0.10)
0.09
(0.09)
DS 9
0.48
(0.12)
0.73
(0.11)
0.86
(0.11)
0.06
(0.13)
0.04
(0.10)
0.06
(0.18)
Average 1.06
(0.55)
1.62
(0.54)
1.50
(0.41)
0.28
(0.45)
0.30
(0.41)
0.36 (0.44)
Results based runs with different train-test splits. Reported mean performance improvvmeent (c. 0.1 moans 10 %) and the standard deviation (Std.) in parentheses.
73

---

Published in Transactions on Machine Learning Research (01/2024)
Table 8: Relative performance improvement in mean squared error of DCON over Lasso.
Training
Test
N
10
N
20
N = 30
N
10
N
20
N
30
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
DS 1
3.73
(2.32)
3.31
(2.10)
3.66
(2.77)
0.47
(0.83)
0.54
(0.82)
0.49
(1.03)
DS 2
0.36
(0.08)
0.57
(0.08)
0.70
(0.09)
-0.16
(0.20)
-0.28
(0.15)
-0.23
(0.14)
DS 3
0.21
(0.13)
0.29
(0.13)
0.32
(0.14)
-0.05
(0.16)
-0.08
(0.13)
-0.11
(0.14)
DS 4
3.93
(2.83)
3.78
(1.67)
5.15
(1.49)
2.73
(2.01)
2.88
(1.84)
3.28
(1.82)
DS 5
-0.87
(0.33)
-0.77
(0.60)
-0.57
(1.35)
-0.81
(0.27)
-0.81
(0.22)
-0.68
(0.81)
DS 6
2.23
(1.26)
7.55
(2.20)
4.10
(1.40)
0.09
(0.63)
0.07
(0.52)
0.21
(0.61)
DS 7
0,55
(0.17)
0.71
(0.16)
0.76
(0.16)
0.30
(0.19)
0.38
(0.20)
0.42
(0.20)
DS 8
0.28
(0.07)
0.39
(0.09)
0.45
(0.09)
0.09
(0.09)
0.11
(0.10)
0.11
(0.09)
DS 9
0.51
(0.15)
0.77
(0.14)
0.90
(0.17)
0.08
(0.13)
0.06
(0.12)
0.08
(0.20)
Average
1.22
(0.82)
1.84
(0.80)
1.72
(0.85)
0.30
(0.50)
0.32
(0.46)
0.40
(0.56)
Results are based on 30 runs with different train-test splits. Reported is the mean performance improvement (e.g., means 10 1)) and standard deviation (Std.) in parentheses.
Table 9: Relative performance improvement in mean squared error of DCON over Ridge
Training
Test
NV
10
20
N
30
N
10
N 20
N
30
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
DS 1
3.13
(1.10)
2.73
(0.69)
2.97
(0.80)
0.43
(0.76)
0.48
(0.62)
0.42
(0.77)
DS 2
0.34
(0.06)
0.54
(0.08)
0.67
(0.09)
-0.17
(0.17)
-0.27
(0.16)
-0.23
(0.12)
DS 3
0.18
(0.05)
0.24
(0.06)
0.26
(0.06)
-0.08
(0.14)
-0.11
(0.12)
-0.14
(0.13)
DS 4
3.91
(2.83)
3.76
(1.67)
5.13
(1.51)
2.72
(2.01)
2.87
(1.85)
3.26
(1.82)
DS 5
-0.93
(0.03)
-0.88
(0.04)
-082
(0.09)
-0.85
(0.11)
-0.84
(0.09)
-0.81
(0.11)
DS 6
1.82
(0.57)
6.78
(2.00)
3.55
(0.83)
0.02
(0.47)
0.04
(0.54)
0.15
(0.58)
DS 7
0.51
(0.14)
0.67
(0.13)
0.72
(0.13)
0.27
(0.15)
0.35
(0.15)
0.39
(0.16)
DS 8
0.26
(0.06)
0.36
(0.05)
0.42
(0.05)
0.07
(0.08)
0.09
(0.10)
0.09
(0.09)
DS 9
0.48
(0.12)
0.74
(0.11)
0.87
(0.11)
0.07
(0.13)
0.05
(0.10)
0.07
(0.18)
Average 1.08
(0.55)
1.66
(0.54)
1.53
(0.11)
0.28
(0.15)
0.30
(0.41)
0.36 (0.44)
Results based 30 runs with different train-test splits. Reported mean performance improvement
(e. R. 0.1 means 10 %) and the standard deviation (Std.) in parentheses.
Table 10: Relative performance improvement in mean squared error of DCON over Kernel Ridge.
Training
Test
N 20
N
30
N 10
N 20
N 30
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean
(Std.)
Mean (Std.)
Mean (Std.)
DS 1
1.22
(2.82)
1.16
(2.75)
1.21
(2.80)
15.98
(71.11)
48.60
(246.09)
26.70
(126.44)
DS
0.32
(0.20)
0.52
(0.25)
0.65
(0.24)
-0.06
(0.41)
-0.16
(0.41)
-0.14
(0.35)
DS 3
0.18
(0.29)
0.23
(0.29)
0.25
(0.30)
-0.03
(0.19)
-0.06
(0.19)
-0.08
(0.20)
DS
0.89
(0.08)
0.89
(0.04)
-0.86
(0.05)
-0.84
(0.11)
-0.84
(0.08)
-0.82
(0.07)
DS 5
-0.89
(0.10)
-0.83
(0.15)
-0.74
(0.23)
92.91
(471.78)
149.62
(774.18)
117.87
(584.89)
DS 6
0.29
(2.67)
2.70
(8.06)
1.25
(4.91)
3.04
(7.68)
2.60
(6.80)
2.77
(7.73)
DS 7
-0.15
(0.16)
-0.06
(0.17)
-0.03
(0.19)
-0.03
(0.25)
0.04
(0.31)
0.06
(0.29)
DS 8
0.08
(0.29)
0.00
(0.30)
0.04
(0.32)
0.07
(0.23)
0.10
(0.26)
0.10
(0.26)
DS 9
0.20
(0.25)
0.05
(0.33)
0.02
(0.35)
0.61
(2.03)
0.58
(1.93)
0.59
(1.84)
Average 0.02
(0.76)
0.31
(1.37)
0.20
(1.04)
12.41
(61.53)
22.28
(114.47)
16.34
(80.23)
Results are based 30 runs with different train-test splita, Reported is the mean performance improvement (e.g..
0.1 means 10 %) and the staudard deviation (Std.) in parentheses.
74

---

Published in Transactions on Machine Learning Research (01/2024)
J Sensitivity Analysis
J.1 Experiments for Over- Paeamearmeteri Neural Networks
In the following, we compare DCON to SGD in an wer-paaamettriied setting as discussed in the related work section of the main paper. That is, the number of hidden neurons is set to a very large number compared to the number training samples m. Previous research proved for this setting that gradient descent converges to globally optimal solution (Du al. 2019a bj Zeyuan al. 2019 Zou & Gul 2019). To do so, we choose dataset DS7 (m = 297) on which DCON performed worst in main experiments in Section 6.2 and vary the number of hidden units N in (29, 210 211 212, 218.. We choose the hyperparameters according to the best-performing ones for N 30. For Adam,
early stopping with patience of 50 monitoring the training loss to eventually observe convergence of SGD. Our experiments are shown in
Figure 15
OC0N
OCON
OCON
Acer
Mr
8
8
101
171
(a) MSE on training set for N 29
(b) MSE on training set for 200
(c) MSE on training set for
LCON
8'
(d) MSE on training for 222
(e) MSE on training for 2
MSEs on for varying
Figure 15: Performance on training and test set for DS7 with varying number of hidden neurons.
As expected, Figure 15 indicates the convergence of Adam in the over-parameterized setting, yielding a constant performance on the test set for N E (29,20 210 241 22,,213,, 213). Furthermore, we observe that DCON also benefits from over-parameteriiationn, yielding similar results as Adam. However, DCON converges much faster.
J.2 Fast Convergence in Over-Regularized Settings
Our experiments also indicate a relationship between the magnitude of the regularization parameter y and convergence speed. We analyze this numerically in the following. To do so, we use the datasets DS1 and DS7 and vary the regularization parameter 7 E {10", : (-5, 3,, DCON when ||0*+1 0+|| < 10-1, Afterward, we plot the resulting number of epochs and the resulting test
We set N 30 and stop
performance in Figure
16
75

---

Published in Transactions on Machine Learning Research (01/2024)
17
12"
10
30
12"
1810
10
3P1 10"0
10
12
10
37
16
(a) Results for DS1
(b) Results for DS7
Figure 16: Number of epochs and test performance for DS1 and DS7 with varying regularization param- eter: Results are based datasets DS1 and DS7 with N 30. We vary the regularization parameter E {10",, : {-5,- .., 3, 4]} visualized in the upper plot, while the lower plot shows the corresponding test performance.
and stop DCON when ||@ - 6h1 < 10-4. The mumber of epochs is
As we can see, DCON converges faster larger values of the same time, the test performance increases due over-regularization. Further theoretical analyses of this behavior are beyond the scope of this paper and left for future research. Nevertheless, a theoretical relationship between the regularization parameter y and convergence speed might help to determine value of that balances both metrics.
76

---

Published in Transactions on Machine Learning Research (01/2024)
K Future Work
K.1 A Parallel Approach for Solving (QP
As mentioned in Appendix [ our algorithm may be limited by memory requirements. The reason is that the singular value decomposition M involves a - in general dense m x m matrix V. As a remedy, we propose a decomposition into batches in the following. This eventually allows one to solve (QP) very efficiently in the case of larger m. To do so, we consider again QP), which given by
B
d
(a 2
+
7)I
d
22
7
22
inf
0
2
m
0
0
0
2
0
2
0
0
0
2/
(352)
s.t. (-I
I
M
-M
0.
(v* 2²
04)
2 O.
For simpler notation, dropped the superscript gi from 3 and the subscripts y" from d, and from a. Now, assume we split the dataset of size m into B batches of sizes my > 0 for b E fl..... B} with
m = = + m2 + ... + mg. For the rest of this section, we use the following notation:
v (o) v2 ................................ 2/) with of Rm for all b (1..... B).
(353)
2 (o vg vi with og Rm for all E (1....,B), B).
(354)
8 (81, 32. ................................ BB) with Bg E Rm for all b (1..... B),
(355)
d (di,d2,..., dR) with do R for all b E (1..... B}.
(356)
I, mm xma the identity matrix of size m, m..
(357)
I+11 E [(x+1)((++1) the identity matrix of size (n + 1) (n + 1),
(358)
Mj pmax((+1) the matrix formed by the rows of M corresponding to batch 6,
(359)
A (-1o Io Mr -Mp
(360)
At this point, we emphasize that we use the term "batch" in this setting to denote the partition of the training set into smaller subsets. This follows the terminology from batch processing in parallel computing where data is processed in chunks to reduce peak memory consumption. It should not be mistaken with batches from traditional gradient-based neural learning, which used to compute only inexact approximations of the gradient to speed up computations. Conversely, our approach still solves the underlying problem exactly as demonstrated in the following.
For the above splitting, we yield
B di
B2 d2
11
BB dg
BB
de
22
d1
B
dp
(361)
2y3
d2
:
d
0
0
0
77

---

Published in Transactions on Machine Learning Research (01/2024)
for the linear term and
(a² +
+7)1
-Y
2²
-
7
(362)
2x3
v.3
2r4
T
(a2 + 7
-711
S S
(a? + +1
0
12
(a
+
+B
0
1
T
7I
770
122
712
7
00
0
0
2/4
0
0
(363)
(a²
1)
-746
B
IIb
0
(364)
0
0
0
0
for the quadratic term. By defining
Bn do
dp
96 6
(365)
(a²
7)
-7
2
746
Ib
0
Q1,
(366)
0
0
0
0
0
0
0b (og Dg 2g 26)
(367)
we yield the equivalence of QP with
inf
Σ (g bi Ub) + 2"h Q1,6%
6=1
s.t.
An = 0 for all b be {1...., B),
%b 2 for all be E {1...., B),
(368)
3 2 0.
1 2 0.
of v² for all b be {l...., B),
of od for all b (l...., B}.
78

---

Published in Transactions on Machine Learning Research (01/2024)
Note that the B quadratic programs from above merely coupled by the common variables 6 and vt. As last step, we introduce quadratic penalty term for the last two equality constraints. We then yield
inf
Σ (g do ub) + Q1,b%
1un
0²112
12 2
bbb
0 |
2 6=1
b=1
s.t.
Abb, 0 for all b E (1,..., ,B)
(QPP)
0 2 0 for all b E (1...., B),
3 2 0,
2 0,
where μl > and μ22 > 0 are penalty parameters. To solve (QPP). we make again use of a block coordinate descent approach outlined in the following.
Updating v To update v² solve the following quadratic program
B14 (63)² 100
B
inf
p1
b
3
2
2
(369)
bm
s.t. 3 0.
Updating 04: To update vi we solve the quadratic program
B14 (o*)"Innzrh
inf
Inti0*
1/2 b=
b
(370)
s.t. 01 20
Updating us: Finally, to update vs, we solve the quadratic program
1
inf (Tr- b, Ub)
11.4%
2
(371)
8.6. Apub = 0,
Ub 2
where
Bb do
db
Ty-.b b
(372)
1110
H220
(a² + Tb
-T
0
0
2
7
7/6
0
0
21.6
(373)
miji
I +1+
2
map
I
2
Note that the updates of v3 and of can be computed by solving quadratic programs with system matrices of size (n+1) x (n + 1). Afterward, all quadratic programs given in (371) are decoupled from one another and, therefore, can be solved in parallel. Furthermore, all of the above subproblems are strictly convex. The ADMM approach derived in the last section can still be used to solve these quadratic programs by adjusting accordingly.
the coefficients in Equation 177
79

---

Published in Transactions on Machine Learning Research (01/2024)
In summary, our parallel algorithm for solving QPP is outlined in Algorithm 4
Algorithm 4: Parallel (QP)-Solver
Input:
Batch sizes "s" m... Parameter w for increasing the penalty parameter
Output:
Solution (e', "0.0". ..") of (QP)
Initialize v², v" and uy for all E .m....m)
while convergence criterion
do
while convergence criterion not met do E (l,..., B) do
Compute dy and Q1.b Update us by solving
inf
(i
2¹ 20.n
s.t.
Ab%b
0,
end
Update x² by solving
2
Bp1 (13)² Inti0
inf
6-1
o²
Update of by solving
8
Inf
Byg (1")²
Inti0*
6m1
0² 2
end
11
Update Ri <- m11
Update M2 wp2
end
(s)...., v
We refrain from an in-depth convergence analysis at this point. Nevertheless, establish the conver- gence up to a subsequence of the inner while-loop to solution of (QPP) for fixed penalty parameters via Proposition 2.7.1 in Bertsekas (016)). Moreover, the outer while-loop converges to a subsequence to a solution of (QP) due to Theorem 17.1 in Nocedal & Wright (2006).
Algorithum allows one to solve QP) very efficiently. The inner for-loop consists of decoupled quadratic programs, which can all be solved in parallel. With the above, algorithm DCON can thus be scaled much larger problem instances. For future research, more sophisticated approaches for handing the equality constraints og 1² for all b E (I..... B} and of ot for all b E {1..... B} in (368) could be of interest. One example is, for instance, the augmented Lagrangian method.
K.2 An inexact DCA Approach for the DC Subproblem
To further counteract the computational complexity of DCON, it might be worth considering inexact versions of DCA, see Zhang & Yamada (2023) and the references therein. In this way, it might be possible to iterative solver (as the one presented in the last section) to solve (QP) and stop the computations prematurely if a certain threshold of optimality is reached. Note that more involved convergence analysis taking into account these incxact DC steps might be necessary in this case.
K.3 Extension for Deep Neural Networks
To extent DCON to deeper neural networks a greedy layer-wise approach might be considered (compare to Bengio et al. 2006 ). That is, one first trains a shallow neural network and then uses the features decoded in the hidden layer of that network as an input to train another shallow neural network. that way, new
layers are stacked on top of the previous ones, while each of them is trained individually using DCON. As the
80

---

Published in Transactions on Machine Learning Research (01/2024)
performance should increase with each layer, one can also consider stopping the training process prematurely after a fixed number of epochs for each layer. Even single epoch so that every neuron is considered only once for each layer and a "full" training for the last layer is thinkable.
81

---

Published in Transactions on Machine Learning Research (01/2024)
References in Appendix
Hedy Attouch and Jéröme Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1):5-16, 2009. ISSN 1436-4646.
Hedy Attouch, Jéröme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Mathematical Programming, 137(1):911 129, 2013. ISSN 1436-4646.
Alberto Bemporad, Komei Fukuda, and Fabio Torrisi. Convexily recognition of the union of polyhedra. Computational Geometry, 18(3):141 154, 2001.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. Advances in Neural Information Processing Systems (NewrIPS), 19, 2006.
Dimitri P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, MA, 3rd edition, 2016.
Jacek Bochnak; Michel Coste, and Marie-Françoin Roy. Real Algebraic Geometry. Springer, Berlin, Heidel- berg, 1998. ISBN 978-3-642-08429-44
Daniel Boley. Local linear convergence of the alternating direction method of multipliers on quadratic or lincar programs. SIAM Journal on Optimization, 23(4):2183-22M) 2207, 2013.
Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The lojasiewicz incquality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Oplimizalion, 17(4): 1205-1223, 2007a.
Jérôme Bolte, Aris Daniilidis, Adrian Lewis, and Masahiro Shiola. Clarke subgradients of stratifiable func- tions. STAM Journal Optimization, 18(2):556-51) 572, 2007b.
Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165(2):471- 507, 2017.
Simon Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima deep neural networks. International Conference on Machine Learning (ICML), pp. 1675-1685, 2019a.
Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. International Conference on Learning Representations (ICLR), 2019b.
James E Falk. A linear max-min min problem. Mathematical Progromming, 5(1):169-188 1973.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural net- works. In Conference On Learning Theory (COLT), pp. 297-299, 2018.
Jean-Baptiste Hiriart- Hiriart-Urruty and Claude Lemaréchal. Fundamentals of Conver Analysis. Springer, Berlin, Heidelberg, 2004.
Meng Huang, Ming-Jun Lai, Abraham Varghese, and Zhiqiang Xu. On de based methods for phase retrieval. In International Conference Approrimation Theory, pp. 87-121, 2019.
Thi Hoai Le An and Pham Dinh Tao. Solving a class of linearly constrained indefinite quadratic problems by d.c. algorithms. Journal of Global Optimization, 11(3):253 285, 1997. ISSN 1573-2916.
Thi Hoai Le An and Pham Dinh Tao. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Annals of Operations Research, 133(1):23-465 02662344446666 2005. ISSN 1572-9338.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, Cambridge, MA, 2nd edition, 2018.
82

---

Published in Transactions on Machine Learning Research (01/2024)
Boris S Mordukhovich, Nguyen Mau Nam, and ND Yen. Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming. Oplimization, 55(5-6)):857700 708, 2006.
Yurii Nesterov. Introductory Lectures on Convez Optimization: Basic Course, volume 87. Springer, New York, NY, 2003.
Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer, New York, NY, 2006.
Mohammad Hossein Rafiei and Hojjat Adeli. Novel machine-learning model for estimating construction costs considering economic variables and indexes. Journal of Construction Engineering and Management, 144 (12), 2018.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems (NeurIPS), 2007.
Ralph Tyrrell Rockafellar. Convex Analysis, volume 36. Princeton University Press, Princeton, NJ, 1997.
Masahiro Shiota. Geometry of Subanalytic and Semialgebraic Sets, volume 150 of Progress in Mathematics. Birkhäuser, Boston, MA, 1997. ISBN 9781461273783.
Pham Dinh Tao and Le Thi Hoai An. A DC optimization algorithm for solving the trust-region subproblem. SIAM Journal Optimization, 8(2):476-500 1998.
Pham Dinh Tao and LT Hoai An. Convex analysis approach to DC programming: theory, algorithms and applications. Acta mathemalica vielnamica,, 22(1):288 355, 1997.
Jinshan Zeng, Tim Tiz-Kit Lau, Shaobo Lin, and Yuan Yao. Global convergence of block coordinate descent in deep learning. International Conference on Machine Learning (ICML), pp. 7313 7323, 2019.
Allen-Zhu Zeyuan, Li Yuanzhi, and Song Zhao. A convergence theory for deep learning via parameterization. International Conference Machine Learning (ICML), pp. 242 252, 2019.
Yi Zhang and Isao Yamada. An inexact proximal linearized de algorithm with provably terminating inner loop. ai preprint Xrxv::2005. 206:000000050 2023.
Difan You and Quanquan Gu. An improved analysis of training wer-parameterized deep neural networks. Advances in Neural Information Processing Systems (NewrIPS), pp. 2055-2064, 2019.
83


Reviews:
[{"review_id": "iRMh07RLEa", "reviewer": "Reviewer_bQDE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**  The writing is mostly clear and logical. The analysis seems reasonable and believable.  I apologize that I did not have time to go through the whole proof.\n\n\n**Drawbacks:** See below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposed a method called DCON, tailored for training 1-hidden-layer neural networks. Convergence analysis is provided. This is a purely theoretical paper.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The motivation of the proposed method is to find the global optimal solution, in lieu of local ones. However, the theoretical guarantee of finding a global solution is rather weak: the global convergence only holds if the initial solution is close enough to the global min. This is not consistent with the motivation of the paper. In this sense, the advantage over the gradient-based method is unclear.  Please discuss.\n\n\n\n2. For me, this is a purely theoretical paper that helps us understand the training of the most simple neural nets, i.e.,  1-hidden-layer networks. I would not expect the proposed method could be easily scaled up to more complicated network structures and large real datasets. However, it is still reasonable to ask the practical computational complexity of the proposed method. DCON needs to solve certain QP sub-problems, which could be expensive.    Please provide the wall-clock running time comparison with Sgd or Adam on your current experiments. Larger-scaled experiments with deep networks will also be appreciated.\n\n\n3. To prove the convergence of DCON, What is the minimum number of hidden units required in theory? \n\n\n4. Missing reference： the problem considered in the script is related to that in [1]. In [1], they consider finding a near-global solution of one-hidden-layer networks via projected gradient-based methods. Since the projected gradient-based method is cheap to implement, the proposed method in [1] seems more practical than DCON. Please discuss.\n\n[1] when expressivity meets trainability: fewer than n neurons can work, Zhang et al, NeurIPS 2021.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "a699x6Gp9A", "reviewer": "Reviewer_JRQp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\n- The proposed approach is original. The algorithm can have the benefit of having no hyperparameter to tune a priori since it amounts to a block coordinate descent.\n- The proofs are thorough. The authors present convergence results through multiple angles and derive convergence rates.\n- The experiments show some promising results on small datasets.\n\n**Weaknesses**:\n\n\n- The proposed algorithm is tailored for a very particular structure of objective. Deep learning and machine learning strive by the flexibility to choose any model. I list here the current limitations:\n  - *Single* hidden layer networks: while applications exist for those, neural networks are generally deeper.\n  - Specific regularization: the authors consider a data-weighted $\\ell_2$ regularization, that is non-standard. The algorithm could probably be run with a standard $\\ell_2$ regularization on the weights though, but it should be discussed.\n  - Deterministic regime: the algorithm and proofs are tailored for full-batch operations. They scale poorly with the number of samples m. Stochastic variants of the algorithm could be more relevant.\n  - Regression problem with least-squared losses: numerous applications consider classification tasks with a logistic, a.k.a. cross-entropy, loss.\n  - ReLU activation function: It is unclear how other activation functions such as a SiLU or a GeLU could be used.\n- The complete computational complexity of each iteration of the algorithm is not fully discussed and compared to the complexity of a simple stochastic gradient descent and variants thereof. To compare fairly with the baselines, the experiments should be run for an equal amount of computational ressource, such as plotting the performance of the algorithms in time. \n- Assumptions appear limiting: in the Appendix, the authors consider subsampling MNIST images to 10x10 for the problem to satisfy assumption 1. Note by the way, that the algorithm should adapt to the problem not the reverse.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a new optimization algorithm for single layer deep network for regression tasks in a deterministic regime for small to medium datasets with an appropriate regularization term and a ReLU activation function. The algorithm is based on using the specific structure of the problem use the design difference of convex functions framework. Each iteration solves several subproblems, one per coordinate of the intermediate layer and one for the outer layer, not counting additional decompositions to solve the subproblem associated to each coordinate.\n\nThe authors present several proofs of convergence: convergence towards limiting critical point, local convergence and convergence in values. The proofs follow a template of previous work (Attouch et al 2013) but each step required a careful analysis of the problem. Rates of convergence are provided.\n\nSeveral experiments illustrate the performance of the algorithm on small (up to 1 000 samples) to medium datasets (10 000 samples). The algorithm outperforms a standard stochastic baseline (Adam) in terms of training and testing loss on UCI datasets (up to 1 000 samples) and is on par with Adam on the MNIST dataset. Some experiments confirm the theoretical findings. No comparisons on time are provided, while it appears that the proposed method can be computationally very expensive.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Required changes**:\n\n- The paper could really benefit from being able to justify the relevance of the proposed objective. One possibility would be to compare the given model to some much simpler models like classical linear regression for example with least squares or non-parametric regression with kernels. This would strengthen the case for needing a new optimizer for the current objective. \n- It is unclear whether the baseline and the proposed algorithm were run on the same objective given the specific choice of regularization chosen by the authors for their algorithms. The authors need to clarify that. Moreover the authors need to justify clearly their choice of regularization. If the authors could also explain how the algorithm could tackle standard $\\ell_2$ regularization it would be great.\n- The authors need to detail fully the computational complexity of the given algorithm and compare to the computational complexity of SGD. Experiments in time in the appendix would also help understand the relevance of the proposed algorithm in practice. Poor results in time would not make the paper rejected but they cannot be missing for the paper to be accepted. \n\n**Suggestions/Questions**:\n- Given that the algorithm is not yet practical enough to tackle usual tasks in deep learning, the authors may consider changing the tone of a paper from \"we have an algorithm outperforming baselines\" to \"we explore alternatives to baselines and their advantages\". For example, on page 2, the authors say \"DCON offers a key benefit for machine learning practice\". It is unclear how \"practical\" the DCON algorithm truly is especially in terms of overall computational complexity. If DCON takes 10 times more time to run, a simple Adam could have been launched with just 10 hyper-parameters for example. In the numerical examples, the authors often affirm that DCON is superior. Adding a pinch of salt and explaining something like \"in epochs, DCON appear superior\" would help emphasize the exploratory perspective taken by the authors. Otherwise if the authors consider that DCON should be used as is, and that the work is mature enough for real applications, more experiments are needed. Right now, having to subsample MNIST images and consider only a fifth of the whole training data suggests that the algorithm is not mature enough for applications. To be clear, the paper proposes a thorough and original proof of convergence that would appeal to the audience. It may just be worth balancing better the cost of such theoretical contributions in terms of practical considerations.\n- The authors may consider changing the title to \"... algorithm for single layer neural network parameter optimization\". \n- For this paper to have larger audience and potential follow-ups, it would be great if the authors could suggest ways to extend the algorithm beyond single layer neural networks even if a proof of convergence would be lost.\n- How close or far is the current objective from some simple hierarchical Bayes model? Rather than focusing on neural networks which are generally deeper in practice, the authors may consider applications in Bayesian statistics that may often deal with composition similar to the ones used here.\n- Could the proofs be extended in a stochastic setting?\n- Can the proofs take into account approximate solutions of the subproblems?\n- Why did the authors consider a one vs all approach for the MNIST dataset while they could have considered a simple squared loss on one-hot labels?\n\n*Other details*:\n\n- Eq. 10, 11: unfortunate notation $y_k$ given that $y$ was already used as the targeted values for regression.\n- Page 17, test loss paragraph: a factor of 0.64 reads as if the algorithm was performing worse, maybe write \n- Page 19, paragraph before conclusion: \"many datasets in practice and theory are of similar size\": first what are datasets in theory? second, I would disagree that many datasets are of such size (MNIST, CIFAR10, or even numerous UCI datasets have much larger sizes).", "broader_impact_concerns": "This is a technical paper presenting a new optimization algorithm. No concern of ethical implications are foreseen.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TOALrzN4jW", "reviewer": "Reviewer_QEZY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - the overall idea is novel and interesting\n - experiments show that on certain small scale problems (the largest problem considered is a 10k subset of MNIST), the proposed approach empirically finds a global optimum\n- experiments show that the proposed method can sometimes outperform Adam on a per-iteration basis (where iteration means _outer iteration_ for the proposed approach, which involves much more computation than an iteration of Adam).\n\nWeaknesses: \n- as with standard approaches to training, the approach proposed here is ultimately heuristic, in the sense that there are no guarantees of global convergence to a global optimum that are provable under realistic assumptions\n- the approach is much less scalable than standard approaches to training", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new approach for optimizing neural networks that have one hidden layer and ReLU activations.   The main insight is that if one considers this objective with respect to the incoming weights to a single arbitrary hidden neuron, this objective is a difference of two convex functions -- which is a type of objective for which specialized solvers exist.  So the idea is to repeatedly sweep through all the neurons and optimize the objective w.r.t the incoming weights to each one.  After each outer iteration, the objective is optimized w.r.t the weights of the second-layer weights, which is just a least squares problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.  Since one of the main concerns here is scalability, could the authors include an experiment where they show how wall clock runtime (say, to time to reach a fixed objective value) varies as a function of (1) number of training data points, and (2) data dimension?  (To construct problems of varying data dimension, you could take the dataset to be random feature encodings of MNIST or CIFAR of varying data dimension).  https://gregorygundersen.com/blog/2019/12/23/random-fourier-features/.\n\n2. In the introduction, the authors write,\n> Foremost, stochastic gradient descent (SGD) and variants thereof (e. g., using momentum) are applied to optimize neural networks. However, gradient-based methods can get stuck in local minima, do not have general convergence guarantees, and require expert knowledge during training due to many hyperparameters (e. g., initial learning rate, momentum)\n\nThe context makes it seem like the authors are implying that their proposed method does not suffer from these three limitations.  I do agree that the proposed method involves less hyperparameter tuning, but I do not necessarily agree that the proposed method is more prone to avoiding local minima, or that it enjoys stronger guarantees than gradient descent does under analogous assumptions.  Could the authors clarify?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1RwLG9o85I", "reviewer": "Reviewer_eoLq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper proposes a novel method for optimizing the parameters of single hidden layer neural networks.\n\n2.The writing of the whole article is relatively smooth, first deducing the subproblems in BCD, then providing methods for solving different subproblems, and finally presenting the proof of convergence and convergence conditions.\n\n3.This paper provides sufficient theoretical proof and proves both the proposition and assumption given.\n\n4.This paper gives a relatively detailed introduction to the experimental settings and details.\nWeaknesses：\n1.This paper mentions alpha subproblem in Proposition 3, but does not give a good explanation of the occurrence of alpha subproblem, making it difficult to understand during the reading process.\n\n2.Also in section 4.2.2 Solution of Alpha Subproblem, the solution to the alpha subproblem is relatively brief.\n\n3.The author introduces the filter options for the data set in the appendix F.2, but does not give a basis for filtering the data set in this way.\n\n4.Appendix F.6 does not provide a text analysis of Figures 3 to 11. It only provides an experimental effect diagram, which cannot explain the experimental effect well.\n\n5.The location of Preliminaries in subsection 5.1.1 is strange. I think it can be presented in section 3.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an algorithm named DCON for optimizing the parameters of single hidden layer neural networks. DCON directly solve PNN, and partly decompose the loss as a DC function. They use a BCD approach to loop over different blocks and derive efficient procedures to (approximately) solve the defined subproblems. They prove DCON converges in value and give the conditions under which the training loss converges.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I suggest that the author add a detailed explanation of the alpha subproblem in Proposition 3 and introduce how to generate the alpha subproblem.\n2. It is recommended that the author supplement the basis for the filter options introduced in appendix F.2 and give a reasonable explanation.\n3. I suggest that the author add experimental analysis of Figures 3 to 11 in appendix F.6. For example, (g) to (i) in Figure 10 respectively represent the changes in MSE values of Adam and DCON with the increase of epoch under the conditions of N=10, N=20, and N=30. It can be seen that DCON increases with the training epoch. The model stabilizes faster as the increase in\n4. I suggest that the author adjust the order of writing and write all the preparation work in the third section, so that the article will be more organized.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a block-wise algorithm together with theoretical analysis to optimize a one-hidden-layer ReLU network. The algorithm runs as follows: (1) Randomly choose one neuron and then optimize only the incoming weights to that layer. (2) Repeat step 1. (3) Optimize the readout weight, which is a quadratic problem. Reviewers believe that the idea is novel and original, the analysis is thorough, and the small-scale empirical results show some promising results. Several issues have been raised by reviewers (e.g., confusion about "global convergence," fair comparison to Adam, the potential shortcomings of the method, etc.), most of which have been addressed properly during the rebuttal. Finally, all reviewers recommend acceptance of the paper, which I agree with.


Two minor points. 
(1.) The paper's 20-page length might be daunting for a general audience. Consider significantly shortening it by moving some technical details to an appendix. This would enhance its accessibility and clarity for a wider readership.


(2.) The definition of "global convergence" in the paper is non-conventional (pointed out by several reviewers.) Please consider alternative terminology, or at least **highlight** how it differs from the standard definition.
Decision: Accept (poster)