Quasiconvex Shallow Neural Network
Authors: CHENHAN XIAO
Yang Weng
Venue: Submitted to ICLR 2023 (2023)

Abstract: Deep neural networks generally have highly non-convex structures, resulting in multiple local optima of network weights. The non-convex network is likely to fail, i.e., being trapped in bad local optima with large errors, especially when the task involves convexity (e.g., linearly separable classification). While convexity is essential in training neural networks, designing a convex network structure without strong assumptions (e.g., linearity) of activation or loss function is challenging. To extract and utilize convexity, this paper presents the QuasiConvex shallow Neural Network (QCNN) architecture with mild assumptions. We first decompose the network into building blocks where quasiconvexity is thoroughly studied. Then, we design additional layers to preserve quasiconvexity where such building blocks are integrated into general networks. The proposed QCNN, interpreted as a quasiconvex optimization problem, allows for efficient training with theoretical guarantees. Specifically, we construct equivalent convex feasibility problems to solve the quasiconvex optimization problem. Our theoretical results are verified via extensive experiments on common machine learning tasks. The quasiconvex structure in QCNN demonstrates even better learning ability than non-convex deep networks in some tasks.

Under review as a conference paper at ICLR 2023
QUASICONVEX SHALLOW NEURAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Deep neural networks generally have highly non-convex structures, resulting in multiple local optima of network weights. The non-convex network is likely to fail, i.e., being trapped bad local optima with large errors, especially when the task involves convexity (e.g., linearly separable classification). While convexity is essential in training neural networks, designing a convex network structure with- out strong assumptions (e.g.. linearity) of activation or loss function is challeng- ing. To extract and utilize convexity, this paper presents the QuasiConvex shallow Neural Network (QCNN) architecture with mild assumptions. We first decom- pose the network into building blocks where quasiconvexity is thoroughly studied. Then, we design additional layers to preserve quasiconvexity where such building blocks are integrated into general networks. The proposed QCNN, interpreted as quasiconvex optimization problem, allows for efficient training with theoretical guarantees. Specifically, we construct equivalent convex feasibility problems to solve the quasiconvex optimization problem. Our theoretical results are verified via extensive experiments on common machine learning tasks. The quasiconvex structure in QCNN demonstrates even better learning ability than non-convex deep networks in some tasks.
INTRODUCTION
Neural networks have been at the heart of machine learning algorithms, covering a variety of ap- plications. In neural networks, the optimal network weights are generally found by minimizing supervised loss function using some form of stochastic gradient descent (SGD) (Saad (1998)). in which the gradient is evaluated using the backpropagation procedure (LeCun et a (1998). How- ever, the loss function generally highly non-convex, especially in deep neural networks, since the multiplication of weights between hidden layers and non-linear activation functions tend to break the convexity of the loss function. Therefore, there are many local optima solutions of network weights (Choromanska equivalent and yield similar learning performance, the network is likely to be trapped in bad local optima with large loss.
al. (2015)). While some experiments show that certain local optima are
Issue 1: Is non-convex deep neural networks always better?
Deep neural networks have shown success in many machine learning applications. such as im- age classification, speech recognition, and natural language processing (Hinton & Salakhutdinov (2006):[Crrgan Ciregan et al. (2012), Hinton et al. (2012), and Kingma et al. (0144). Many people believe that the multiple layers in deep neural networks allow models to learn more complex features and perform more intensive computational tasks. However, deep neural networks are generally highly non-convex in the loss function, which makes the training burdensome. Since the loss function has many critical points, which include spurious local optima and saddle points (Choromanska et al. 2215)), it hinders the network from finding the global optima and makes the training sensitive to the initial guess. In fact, (Sun et al. (2016)) pointed out that increasing depth in neural networks is not always good since there is trade-off between non-convex structure and representation power. In some engineering tasks requiring additional physical modeling, simply applying deep neural net- works is likely to fail. Even worse, we usually don't know how to improve the deep neural networks during failure since it is a black box procedure without many theoretical guarantees.

---

Under review as a conference paper at ICLR 2023
Motivation
Space
Problem: ExtractUsiize convexity general
Quasiconcaavity product ReLU
Nonconvasiy
Challenge: Mulliplication of weights and non- ineer sctivtioos
Minpoool preserve quesiconcenity
Data:
vector input
scalar label
Solve quasiconvex as corveex problem
Quassiooveextt
Figure Proposed Method. (Left) The motivation and challenge of this study. (Middle) We design quasiconvex neural network structure to efficiently train for optimal network weights in quasiconvex optimization problem. The quasiconvexity studied and preserved via special pooling layers. (Right) Unlike non-convex loss function, the quasiconvex loss function of our design allows for finding the global optima.
Issue Solution non-convexity is not practical.
To overcome non-convexity in neural networks, new designs of network structure were proposed. The first line of research focused on specific activation functions (e.g., linear or quadratic) and specific target functions (e.g.. polynomials) (Andoni et al. (2014)) where the network structure can be convexity, However, such methods were limited in practical applications (Janzamin et al. (2015). Another line of research aimed at deriving the dual problem of the optimization problem formulated by neural network training. Unlike the non-convex neural network, its dual problem is usually convex. Then, conditions ensuring strong duality (zero duality gap and dual problem solvable) were discussed to find the optimal solution to the neural network. For example, Ergenn & Pilanci (2020)
derived the dual problem for neural networks with ReL.U activation, and Wang al. (2021) showed that parallel deep neural networks have zero duality gap. However, the derivation of strong duality in the literature requires the planted model assumption, which is impractical in many real-world datasets. Aside from studying the convexity in network weights, some work explored the convexity in data input and label. For instance, an input convex structure with given weights Amos et al. (2017) altered the neural network output to be a convex function of (some of) the inputs. Nevertheless, such a function only an inference procedure with given network weights.
In this work, we introduce QCNN, the first QuasiConvex shallow Neural Network structure that learns the optimal weights neural network (shown in the middle of Figure D into building blocks (denoted by distinct colors). In each building block, the multiplication of two weights, as well as the non-linear activation func- tion in the forward propagation, makes the building block non-convex. Nevertheless, inspired by Boyd et al. (2004), we notice that the multiplication itself is quasiconcave if the activation function ReLU. The quasiconvexity (quasiconcavity) is generalization of convexity (concavity), which shares similar properties, and hence, is a desired property in the neural network. To preserve quasi- concavity in the network structure when each building block is integrated, we design special layers (e.g., minimization pooling layer), as shown in the middle of Figure [ In doing so, we arrive at quasiconvex optimization problem of training the network, which can be equivalently solved by tackling convex feasibility problems. Unlike non-convex deep neural networks, the quasi-convexity QCNN enables to learn the optimal network weights efficiently with guaranteed performance.
quasiconvex optimization problem. We first decompose a general
2 RELATED WORK
Failure of training non-convex neural networks. In training a non-convex neural network, the commonly used method, such as gradient descent in the backpropagation procedure, can get stuck in bad local optima and experience arbitrarily slow convergence (Janzamin et al. (2015)). Explicit examples of the failure of network training and the presence of bad local optima have been discussed in (Brady et al. (1989); Frasconi et al. 1993)). For instance, Brady et al. (1989) constructed simple cases of linearly ly separable classes that backpropagation fails. Under non- non-linee non-linear separability setting, Gori & Tesi (1922 also showed failure of backpropagation. These studies indicate that deep neural
2

---

Under review as a conference paper at ICLR 2023
networks are not suitable for all tasks. Therefore, it motivates to think: can simple networks with convex structure beat deep networks with non-convex structure in some tasks?
Convexity in neural network. The lack of convexity has been seen as one of the major issues of deep neural networks (Bengio et al. (2005), drawing much research in the machine learning community. Many people studied convex structures and convex problems in neural networks. For instance, (Bengio et al.] (2005); AAndoii et al.] (2014); Choromanska et al. (2013); Milne (2019); Rister & Rubin (2017) showed that training neural network under some strong conditions can be viewed as a convex optimization problem. (Farnia & Tse Tse] (2018); Ergen & Pilanci (202)); Wang et al.)
(202T] Pilanci & Ergen (2020)) studied convex dual problems of the neural network optimization
and derived strong duality under specific assumptions.
Aside from directly studying convexity in neural networks, people also discussed conditions where the local optima become global. For example, Haeffele & Vidal (2015) presented that if the network over-parameterized (i.e., has sufficient neurons) such that there exist local optima where some of the neurons have zero contribution, then such local optima is global optima (Janzamin et al. (2015). Similarly, Haeffele & Vidal (2017) also showed that all critical points are either global minimizers or saddle points if the network size is large enough. However, such studies only provide theoretical possibilities while efficient algorithms to solve (infinitely) large networks are missing. Based on the existing literature, restrict our research to finding simple but practical neural network with some convexity to provide performance guarantees.
Quasiconvex optimization problem. The study of quasiconvex functions, well quasicon- vex optimization problems, started from (Fenchel & Blackett (1953); Luenberger (1968) and has become popular nowadays since the real-world function is not always convex. For instance, quasi- convex functions have been of particular interest in economics (Agrawal & Boyd (2020)) modeling the utility functions in an equilibrium study (Arrow & Debreu 1954); Guerraggio & Molho (2004).
The quasiconvex optimization has been applied to many applications recently, including engineering (Bullo & Liberzon (2006)). model order reduction (Sou). computer vision (Ke & Kanade (2007) and machine learning (Hazan et al.) (2015)). Among many solutions to quasiconvex optimization problems, a simple algorithm is bisection (Boyd al. (2004)), which solves equivalent convex fea- sibility problems iteratively until converging.
3 PRELIMINARY
To model for the general case, we consider a L-layer network with layer weights W, E 1 VI E [4]. where mno d and my = 1 are the input and output dimensions, respectively. As the dimensions suggest, the input data is a vector, and the output is a scalar. Given a labeled dataset D = [(x,, y:) with n samples, consider neural network with the following architecture.
fx(X)= = h1, h = g(h,-1Wt). AI [Z]
(1)
where h denotes the layer activation and ho X Radd is the data matrix. Here, 0 {Wi) are the network weights which need to be optimized via training, and g(-) is the non-linear activation
function. The network is trained with I.2 loss as follows:
arg min b 11 - v12
where y E R" is the data label vector. The loss function in Equation 2 is generally non-convex because of the multiplication of weights as well as non-linear activation functions. As discussed previously, non-convexity will likely cause the network to be trapped in bad local optima with large errors. Therefore, we still want to extract some convexity in this loss function to help with the training process. In this paper, we will show that quasiconvexity and quasiconcavity are hidden in the network. These properties can be utilized to construct a convex optimization problem to train the optimal network weights. Here, we introduce the definition of quasiconvexity and quasiconcavity. Definition 1. A function f Rd + R is quasiconvex if its domain and all its sublevel sets {z e dom flf(z) S a.. Va are convex. Similarly, a function is quasiconcave if ff quasiconvex, i.e., every superlevel set {x]f(x) 2 a} is convex.
We also note, since convex functions always have convex sublevel sets, they are naturally quasicon- vex, while the converse is not true. Therefore, the quasiconvexity can be regarded as a generalization of convexity, which is exactly what seek in the non-convex deep neural networks.
3

---

Under review as a conference paper at ICLR 2023
4 QUASI-CONCAVE STRUCTURE
For designing a quasiconvex structure of neural networks, we start by considering the simplest and most representative building block in network and analyze its characteristics. Specifically, we consider the network
f (W11 9 (00(xxxw]]) w1)w2),
where E Id is the input data, W1 E Rd and W2 We analyze such a two-layer structure because it is the simplest case in neural networks yet can be generalized deep neural networks. In Equation 3 the network because (1) the network function contains the multipiicttion of the weights and (2) the activation function g(-) is usually non-linear.
are the weights for hidden layers.
convex weights (W1: W2)
Nevertheless, we still want to explore the potential possibilities of the network becoming convex or being related to convex. Inspired by Boyd et al. (2004), we notice that although the multiplication of two weights in the forward propagation makes the network non-convex, the multiplication itself is quasiconcave in specific circumstances. For example, the product of two variables forms the shape of saddle, which is not convex in those variables. However, if we restrict these two variables to be positive, the saddle shape will reduce to a quasiconcave surface, as shown Figure
Lemma 1. The function f(W1, w2) W1w2 with dom f = R is quasiconcave.
Shape
Quasiconcavity
constrained
Figure 2: (Left) The function f(w1, W2) Wi W2 has saddle shape. (Middle) Constrained on positive domain, i.e., dom f f IR3, the function becomes quasiconcave. (Right) The quasiconcave function always has convex superlevel sets.
Motivated by Lemma ! and Figure 2 to preserve the property of quasiconcavity of the network in Equation 3 straightforward approach is to assume the network weights (W1; w2) to be non- negative, like in (Amos et al. (2017)). However, this assumption will significantly reduce the neural network's representation power In fact, suppose there are m weights, constraining all the weights to be non-negative will result in only 1/2" representation power. To bypass this impractical as- sumption, we notice that some activation functions naturally restrict the output to non-negative. For example, the ReLU activation function g(x) = max (0. x} forces the negative input to be zero. Therefore, we can demonstrate that the network in Equation with ReLU activation function is quasiconcave in the network weights, shown in Theorem
Theorem 1. The neural network in Equation with ReLU activation functionn 9(-) is quasiconcave in the network weights (W1: W2).
Proof. To prove quasiconcavity, we need show that all superlevel sets
S. ((Wi:w))]S(w) wa) 2 a),
Va E IR
are convex sets. When a S 0, the superlevel set the complete set, i.e, Sa = dom f due to the ReLU activation function. Hence, Sa, is evidently convex. When the empty set nor the complete set. For any two elements (W,; W2), (W,; W2) E S,, we aim to show that (Aw1 (1 A)wi; Awa
0, the superlevel set is neither
A)wa) Sa for X (0, 1). From the condition
O,
4

---

Under review as a conference paper at ICLR 2023
know that x W1 0 and W2 as well as x W1 0 and W2 O. Therefore, we would have
f(Awi (1 A) + (1 A)w2) [Xx W1 (1 A)x wi] [Am2 + (1 A)Wal
12x
W, W2 + A(1 - X) |x Wi + x w1
2 2 (1-A)a A(1 A)
x
W1W2 xx W1W2]
2 + + X(1 - A)
a
W2
a
W2
W2
W2
2 21aa+ 1(1 A) x 2a
a(>² + (1 A)2 22(11 - A)]
In Theorem we show that the simple two-layer network in Equation quasiconcave in network weights, given that the activation function is ReLU. Then, a natural question arises; does this prop- erty of quasiconeavity remain in deeper networks? Unfortunately, the quasiconcavity does not hold in more complex neural networks due to one fact: the summation of quasiconvex (quasiconcave) functions not necessarily quasiconvex (quasiconeave). The deeper networks can be regarded as weighted summations of many networks in Equation 3 hence, not quasiconcave anymore. There- fore, we aim to design new network structures preserve the property of quasiconcavity more general neural networks.
To achieve this goal, we focus on the operations that preserve quasiconcavity, including (1) the com- position of a non-decreasing convex function, (2) the non-negative weighted minimization, and (3) the supremum over some variables. Among these operations, we choose the minimization proce- dure because it is easy to apply and has simple gradient. Specifically, pooling layer to integrate the simple networks in Equation 3 as shown in Figure 3 In doing so, manage extend the network in the simplest building block quasiconcavity ensured by semma@and visually explained in Figure[4] Meanwhile, we note that the proposed network still a shallow network. Although infinitely stacking layers with appropri- ate minimization pooling layers can also keep the entire network convex, too many minimization pooling layers will damage the representation power of the neural network.
apply minimization
general structures, where
minimization pooling Φ
Simple
Quasiconcavity
General NN
data
output
f(w): sla(x w:)wu))
/(W;: w2) Molsix W()w)))
J(W Wa ws) = ofolatatx W. W.)Wai)ws)
Figure 3: The structure of quasiconvex shallow neural network (QCNN).
Lemma 2. Provided that fi.... fn are quasiconcave functions defined on the same domain, the non-negative weighted minimum
f min 02,2, "nnff)
is quasiconcave given a,,.." On E R...
Proof. The superlevel set S. = {x E dom f15(x) 2 a} of / can be regarded as:
S. (x dom minn(a (nff 2 a} n (x dom flß ") a
which is the intersection of (convex) superlevel sets of fa(i =1....m)
5

---

Under review as a conference paper at ICLR 2023
[W,, Wg) wy
Wo Wa) wy
fln, my)
10Wy, wa) - my
minmization
Figure 4: The minimization of quasiconcave functions on the same domain is still quasiconcave.
QUASICONVEX OPTIMIZATION OF NEURAL NETWORK
In Section 4 design neural network structure where output f(0) is quasiconcave function over the network weights 0. To further utilize the property of quasiconcavity, this section, we propose to train the neural network (() is quasiconcave, the optimization problem in Equation is not quasiconvex, since the L loss monotonie. However, if we restrict the network output be smaller than the network labels, i.e, [(0) < y, the 1,2 loss is non-increasing in this range. Therefore, the resulting loss function in non-increasing function a quasiconcave function, is quasiconvex. That is, the training of QCNN is an unconstrained quasiconvex optimization problem
quasiconvex optimization problem. Even though function
Equation 2 composition of
P min ((0) min [1((()) - yy1
0
To solve the quasiconvex optimization problem in Equation 4 we can transform it into an equivalent convex feasibility problem. Let (0) := y t - f(), f E IR be a family of convex functions satisfying ((0) S t = (0) s 0. Then, the quasiconvex optimization problem in Equation 4 can be equivalently considered as min ((0)
min 0.2
find
(5)
s.t. 1(0) St
s.t. (p) <
The problem in Equation 5 is convex feasibility problem since the inequality constraint function convex. For every given value t, we can solve the convex feasibility problem. If the convex feasibility problem is feasible, i.e., 30, (0) S 0, this point 0 is also feasible for the quasiconvex problem by satisfying I(0) S t. It indicates that the optimal value P is smaller than f, i.e., P < t. In this circumstance, we can reduce the value and conduct the above procedure again approach the optimal value p* On the other hand, if the convex feasibility problem is infeasible, we know that P* 2 t. this case, we should increase the value of t. Through this procedure, the quasiconvex optimization problem in Equation 4 can be solved using bisection, i.e., solving a convex feasibility problem at each step (Boyd et al. (204)) The procedure summarized as Algorithm
Algorithm QCNN Training Process
1: given < P* u 2 pa, tolerance e > 0 while u- do
lower/upper bounds of optimal value i convergence criterion
2:
3: t:= u)/2
4: Solve the convex feasibility problem in Equation 5
5: if problem Equation 5 feasible then
6:
n==l
record the feasible point
7:
else
8:
1==t
9:
end if
10:
end while
D return the current feasible point
Remark 1. The quasiconvex optimization problem in Equation 4 has zero duality gap. The proof can be derived by verifying that unconstrained quasiconvex optimization problem in Equation satisfies the condition in Fang et al. (2014). Therefore, the quasiconvex optimization problem could also be solved via exploring its dual problem.

---

Under review as a conference paper at ICLR 2023
EXPERIMENTS
We use the proposed framework in Section 5 conduct several machine learning tasks, comparing QCNN to deep neural networks. Our experiments aim to validate the core benefits of QCNN: (1) the convexity, even in shallow networks, makes learning more accurate than non-convex deep networks in some tasks, and (2) the convexity enables the network to be more robust and converge faster.
6.1 FUNCTION APPROXIMATION
Since the purpose of neural networks can be generally seen as learning mapping from input x to label y, in this section, evaluate the performance of using QCNN approximate some function.
Synthetic dataset. For synthetic scenario, the dataset is generated by randomly sampling x from a uniform distribution Unif(- and calculating the corresponding label y fxx given function f. We generate 1,000 samples for training and 200 samples for testing, where the mean square error (MSE) of the testing is used to evaluate the model performance.
The results of approximating various functions are summarized in Figure 5 As we see, the perfor- mance of deep neural networks depends the choice of initial guess network weights. In the first two experiments (first two rows in Figure 5). the deep network seems to be trapped in a bad local optima, which corresponds to relatively large MSE. In the third experiment, the deep network arrives at good local optima. However, it still exhibits certain flaws at the non non- non-differrentiblle points (turning points) in the function f. matches the finding of Brady et al. (1989) where deep neural net- works fail in simple cases of linearly separable classifying tasks. On the contrary, although QCNN uses a shallow structure, its quasiconvexity nature enables it to learn piecewise linear functions to approximate function f. In many replications of experiments, we find that learning procedure of QCNN more robust to initial guess network weights since it is quasiconvex. Moreover, QCNN demonstrates quicker convergence when learning the function f.
Function
Deep network
QCNN
MM
MSE: 0.03
M
MSE: 0.00
Converge:
Converge: 1.9s
MA
M
Converge:
Converge: 2.2s
Plecowis-linerrrnnnineer
W
MSE: 0.007
M
MSE: 0.005
Converge:
Converge: 2.3s
Piecewise-nonlinear
4.1s
The performance of approximating functions using deep neural networks and QCNN: QCNN tends behave better because the quasiconvex structure enables learn piecewise linear mappings more efficiently.
Figure 5:
Contour detection dataset. For the real-world application of function approximation, we consider the task of detecting the contour of an object, which is usually the first step for many applications in computer vision, such as forge-oor extraction (Banerjee et al. (2016)), simple-image segmentation (Saini Arora (2014), detection, and recognition (Kulkarni et al. (2013)). The ex- periment is conducted the Berkeley Segmentation Dataset (Arbeláez et al. (2013) composed of 200 training, 200 testing, and 100 validation images. Each image has between five and six manually annotated labels representing the ground truth (Yang et al. (2019). These labels also used to calculate two metrics: optimal dataset scale (ODS) and optimal image scale (OIS) to evaluate the model performance. The comparison performed against DeepNet (Kivinen al. (014))).

---

Under review as a conference paper at ICLR 2023
In the experiment, find that the performance of QCNN and DeepNet depend the objects in the image. For some objects with clear and angular contours, e.g., phone in Figure (a), detecting such a contour can be seen learning closed polygon with piecewise linear functions defining its edges. For such a class of images, the ODS of QCNN achieves 0.824 compared to 0.784 of DeepNet, while the OIS of QCNN achieves 0.831 compared 0.798 of DeepNet. On the contrary, DeepNet has better accuracy in recognizing complex (e.g.. highly non-linear) contours. In this class of images, the ODS of QCNN is 0.717 compared 0.743 of DeepNet, while and the OIS of QCNN is 0.729 compared to 0.760 of DeepNet. To conclude, QCNN with the quasiconvex structure still outperforms the deep networks when the task involves some characteristics related to convexity.
Mass-damper system dataset. Aside from synthetic functions and irregular functions, we also learn functions that have physical meanings. Specifically, we consider the mass-damper system, which can be depicted as: incidence matrix of the system, R is the diagonal matrix of the damping coefficients for each line of the system, and M is the diagonal matrix of each node mass of the system. Thus, we can set y and x = q with the goal to learn the parameter matrix DDRD M We simulate the dataset for 10-node system and obtain 6,000 samples for 1 1-min simulations with step size be 0.01s (Li ett al. (2022)). Figure 6 (b) shows the prediction error (MSE) during training epochs, where QCNN converges faster smaller error, compared deep neural networks. This is perhaps because that the target parameter matrix in the system constructs a linear bridge between input x and label y.
DRD M In the system, 9 is vector of momenta, D is the
objects with angular contours
objects with complex contours
QUNN
Deep NN
QCNN has smaller error
MSE
QCNN conveyers
faster
QCNN
Deep neural network
68
50
100
Epoch
(a) contour detection
(b) training of mass-damper system
Figure 6: (a) QCNN works better in detecting angular contours while deep networks are better for detecting complex contours. (b) MSE against training epochs in learning the mass-damper function.
6.2 CLASSIFICATION TASK
The experiments in Section 6.1 represent the regression tasks. In this section, we further consider the classification task, covering two major categories of machine learning applications.
Change point detection of distributions. Finding the transition of the underlying distribution of sequence has various applications in engineering fields, such as video surveillance (Sultani et al. (2018) ) sensor networks Xie & Sicgmund (2013) and infrastructure health monitoring Liao et al.
2019 Aside from engineering tasks, it also important in many machine learning tasks, including speech recognition Chowdhury et al. (2022). sequence classification Ahad & Davenpori (2020). and dataset shift diagnosis Lu al. (0166). To simulate a sequence of measurements, we randomly generate the pre-change sequence from normal distribution N (0, 0.2) and generate the post-change sequence from (1, 0.1) where the change time the left part of Figure
50. The time-series sequence shown in
Using the neural network to detect the change point À can be seen as classifying pre-change data and post-change data using five samples in shifted window. The classifying threshold is chosen as a, i.e., the maximum false alarm rate (Liao al.) (2016)). The results are shown in Figure using 1,000 Monte Carlo experiments. As we see, QCNN shows a smaller average detection delay than deep neural networks. Meanwhile, it seems that QCNN less likely to falsely report a fake change, since the empirical false alarm rate of QCNN is below that of deep networks, and is mostly below the theoretical upper bound a (especially when a - 0). QCNN outperforms the deep neural network in this task because the transition of the distribution is abrupt, shown in Figure (Left). The abrupt change results a con-dificreniiall/non-ss -moothh point in the mapping to be learned, which is more efficiently represented by QCNN via piecewise linear functions.
8

---

Under review as a conference paper at ICLR 2023
Sequence
Average detection delay
False alarm rate
=
"TR NO,00.)
Tieesticll
QUNN
(10,0.2)
cupiéball
QCNN smaller delay
QCNN smaller false rate
1.
100
pre-change
post-change
20
[ap
Figure 7: (Left) The change of underlying distribution of the sequence. (Middle) The average detection delay of detecting the distribution change using QCNN and deep neural networks. (Right) The false alarm rate of detecting the distribution change using QCNN and deep neural networks.
Solar meters classification. The UMass Smart dataset (Laboratory for Advanced System Software (Accessed Sep. 2022.)) contains approximately 600,000 meters from U.S. city with a one-hour interval between each meter reading (Cook et al. (02TT). Among these meters, around 1,973 have installed solar panels, and are labeled solar in the classification task. The remainder of the meters are labeled as non-solar. The average smart meter readings, including the household electricity consumption and the PV generation, as well as the household's address, are considered input data to classify whether a meter has solar panels. We randomly select 20,000 samples from this dataset to train and select 1,000 samples to test the performance. Figure shows the location of all the meters and solar meters. As we see, the meters that have solar installed are concentrated in roughly convex area instead of being spread over the entire area. Therefore, learning the classifier for solar meters using the feature of address is equivalent to learning a convex domain. It could explain that the classification accuracy of QCNN (94.2%) outperforms that of deep networks (92.7%).
Locations of solar meters
zoom in
Solar meters locate together in convex area
Classification accuracy
Locations of all the meters
QCNN (94.2%) > Deep NN (92.7%)
Figure 8: The locations (solar) meters and the classification accuracy of using QCNN and deep neural network to classify the solar meters.
CONCLUSION
In this work, we analyze the problem of convex neural networks. First, we observe that deep neu- ral networks not suitable for all tasks since the network is highly non-convex. The non-convex network could fail, i.e., being trapped in bad local optima with large errors, especially when the task involves convexity (e.g.. linearly separable classification). Therefore, motivates to design convex structure of neural networks to ensure efficient training with performance guarantees. While convexity is damaged due the multiplication of weights well as non-linear activation functions, we manage to decompose the neural network into building blocks, where the quasiconvexity is thor- oughly studied. the building block, we find that the multiplication of ReLU output quasiconcave over network weights. To preserve the property of quasiconcavity when such building blocks are integrated into a general network, we design minimization pooling layers. The proposed Quasi- Convex shallow Neural Network (QCNN), can be equivalently trained via solving convex feasibility problems iteratively. With the quasiconvex structure, QCNN allows for efficient training with the- oretical guarantees. We verify the proposed QCNN using several common machine learning tasks. The quasiconvex structure in QCNN demonstrates even better learning ability than non-convex deep networks in some tasks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Akshay Agrawal and Stephen Boyd. Disciplined quasiconvex programming. Optimization Letters, 14(7):1643-1657, 2020.
Nauman Ahad and Mark A Davenport. Semi-supervised sequence classification through change point detection. arXiv preprint arXiv:2009. /829, 2020.
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Confer- ence on Machine Learning, pp. 146-155. PMLR, 2017.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning polynomials with neural networks. In International conference on machine learning, pp. 1908-1916. PMLR, 2014.
Arbeláez, M Maire, C Fowlkes, and J Malik. Contour detection and image segmentation resources.
Berkeley Segmentation Data Set and Benchmarks, 500, 2013.
Kenneth J Arrow and Gerard Debreu. Existence of an equilibrium for a competitive economy. Econometrica: Journal of the Econometric Society, pp. 265-290, 1954.
Biplab Banerjee, Sudipan Saha, and Shabbir Merchant. Image foreground extraction a su- pervised framework based region transfer. In 2016 International Conference Signal and Information Processing (IConSIP), pp. 1-5. IEFE, 2016.
Yoshua Bengio, Nicolas Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. Advances in neural information processing systems, 18, 2005.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Martin L Brady, Raghu Raghavan, and Joseph Slawny. Back propagation fails to separate where perceptrons succeed. IEEE Transactions on Circuits and Systems, 36(5):665-674, 1989.
Francesco Bullo and Daniel Liberzon. Quantized control via locational optimization. IEEE Trans- actions on Automatic Control, (1):2211 2006.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pp. 192-204. PMLR, 2015.
Md Foezur Rahman Chowdhury, S-A Selouani, and O' Shaughnessy. Bayesian on-line spectral change point detection: a soft computing approach for on-line asr. International Journal of Speech Technology, 15(1):5-23, 2012.
Dan Ciregan, Ueli Meier, and Jürgen Schmidhuber. Multi Multi-column deep neural networks for image classification. In 2012 IEEE conference on computer vision and pattern recognition, pp. 3642- 3649. IEEE, 2012.
Elizabeth Cook, Shuman Luo, and Yang Weng. Solar panel identification via deep semi semi-supervised learning and deep one-class classification. IEEE Transactions on Power Systems, 37(4):2516 2526, 2021.
Tolga Ergen and Mert Pilanci. arXiv:2002.09773. 097700 22, 2020.
Convex duality of deep neural networks.
arXiv preprint
Donghui Fang, XianFa Luo, and Xianyun Wang. Strong and total lagrange dualities for quasiconvex programming. Journal of Applied Mathematics, 2014, 2014.
Farzan Farnia and David Tse. A convex duality framework for gans. Advances in neural information processing systems, 31, 2018.
Werner Fenchel and Donald W Blackett. Convex cones. sets, and functions. Princeton University, Department of Mathematics, Logistics Research Project, 1953.
10

---

Under review as a conference paper at ICLR 2023
Paolo Frasconi, Marco Gori, Alberto Tesi, al. Successes and failures of backpropagation: A theoretical investigation. Progress in Neural Networks, 5(0), 1993.
Marco Gori and Alberto Tesi. On the problem of local minima in backpropagation. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 14(1):76-86, 1992.
Angelo Guerraggio and Elena Molho. The origins of quasi-concavity: a development between mathematics and economics. Historia Mathematica, 31(1):62-75, 2004.
Benjamin D Haeffele and René Vidal. Global optimality in tensor factorization, deep learning, and beyond. arXiv preprint 100iv 2015.
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7331-7339, 2017.
Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex opti- mization. Advances in neural information processing systems, 28, 2015.
Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal processing magazine, 29(6):22-97, 2012.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-577, 2006.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity: Guar- anteed training of neural networks using tensor methods. arXiv preprint
2015.
Qifa Ke and Takeo Kanade. Quasiconvex optimization for robust geometric reconstruction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18341888,, 2007.
Durk P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. Semi-supervised learning with deep generative models. Advances in neurul information processing systems, 27, 2014.
Jyri Kivinen, Chris Williams, and Nicolas Heess. Visual boundary prediction: A deep neural predic- tion network and quality dissection. In Artificial Intelligence and Statistics, pp. 512-521. PMLR, 2014.
Girish Kulkarni, Visruth Premraj, Vicente Ordonez, Sagnik Dhar, Siming Li, Yejin Choi, Alexan- der C Berg, and Tamara I. Berg. Babytalk: Understanding and generating simple image descrip- tions. IEEE transactions on pattern analysis and machine intelligence, 35(12):8811-200, 2013.
Laboratory for Advanced System Software. Umass dataset. addu/nndx..o php/ Smart/ Smart Accessed Sep. 2022.
lattp:/ umass.
Yann LeCun, Leon Bottou, Genevieve B Orr, Klaus-Robert Müller, et al. Neural networks: Tricks of the trade. Springer Lecture Notes in Computer Sciences, 1524(5-50):6, 1998.
Haoran Li, Yang Weng, and Hanghang Tong. Console: Convex neural symbolic learning. arXiv preprint arXiv:2206.00255 2022.
Yizheng Liao, Yang Weng, Chin-Woo Tan, and Ram Rajagopal. Urban distribution grid line out- age identification. In 2016 International Conference on Probabilistic Methods Applied to Power Systems (PMAPS), 1-8. IEEE, 2016.
Yizheng Liao, Anne S Kiremidjian, Ram Rajagopal, and Chin- Loh. Structural damage detection and localization with unknown postdamage feature distribution using sequential change- point detection method. Journal of Aerospace Engineering, 32(2):0401 8149, 2019.
Kang- Kang-Ping Lu, Shao-Turme Tung Chang. and Minn-Sen Yang. Stange--oiin detection for shifts in control charts using fuzzy shift thange-poine algorithms. Computers & Industrial Engineering, 93:12-27, 2016.
11

---

Under review as a conference paper at ICLR 2023
David G Luenberger. Quasi-convex programming. SIAM Journal Applied Mathematics, 16(5): 1090-1095, 1968.
Tristan Milne. Piecewise strong convexity of neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time con- vex optimization formulations for two-layer networks. In International Conference on Machine Learning. pp. 7695-7705. PMLR, 2020.
Blaine Rister and Daniel Rubin. Piecewise convexity of artificial neural networks. Neural Net- works, 94:34 45, 2017.
David Saad. Online algorithms and stochastic approximations. Online Learning, 5(3):6, 1998.
Sujata Saini and Komal Arora. A study analysis on the different image segmentation techniques. International Journal of Information & Computation Technology. 4(14):1445 -4522, 2014.
Kin Cheong Sou. Parameterized model order reduction via quasi-convex optimization.
Waqas Sultani, Chen Chen, and Mubarak Shah. Real-world anomaly detection in surveillance videos. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 6479-6488, 2018.
Shizhao Sun, Wei Chen, Liwei Wang, Xiaoguang Liu, and Tie- Yan Liu. On the depth of deep neural networks: A theoretical view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap- arXiv preprint arXhv:2110.06443 2021.
Yao Xie and David Siegmund. Sequential multi-sensor change-point detection. In 2013 Information Theory and Applications Workshop (ITA), pp. 1-20. IEEE, 2013.
Hongju Yang, Yao Li, Xuefeng Yan, and Fuyuan Cao. Contourgan: Image contour detection with generative adversarial network. Knowledge-Bond Based Systems, 164:21 1-2, 2019.
12


Reviews:
[{"review_id": "xvkTBDUwym6", "reviewer": "Reviewer_xAee", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new neural network architecture, i.e., QuasiConvex Neural Network (QCNN), which could make the training process quasiconvex with proper loss functions. QCNN is a stack of its basic building block, which is a linear layer with ReLU activations and min-pooling. The training process of QCNN was formalized as a convex feasibility problem and can be solved using existing algorithms, e.g., bisection. The authors also provide small-scale experimental results of shallow QCNN versus regular neural networks on synthetic data and several other datasets and show that QCNN is better in accuracies or convergence speed for some tasks.", "summary_of_the_review": "I tend to vote for rejecting this paper. Although the idea of constructing a quasiconvex neural network in this particular way is interesting, many important details about the network and especially the experiments are missing, making the claims less convincing. On the theoretical side, this paper doesn't provide enough theoretical guarantees about the representation power and training efficiency of the proposed network.", "strength_and_weaknesses": "-Strengths:\n\n1. The idea of combining ReLU outputs and min-pooling to construct quasiconvex functions is interesting and novel. It provides a tradeoff between the strict convexity of some previous models and the high degree of non-convexity in commonly-used deep neural networks.\n\n2. The authors include many figures in their paper, which helps with the understanding of their arguments, network design, and tasks in the experiments.\n\n-Major Weaknesses:\n\n1. Many essential details about the network training process and the experimental setting are missing in this paper, which makes the results and claims in this paper much less convincing. I will explain this in detail below:\n\n1.1 For minimization pooling, how do the authors select the weights $a_1,\\cdots,a_n$ in the weighted minimization pooling $\\phi$?\n\n1.2 When transferring the quasiconvex optimization problem into a feasibility problem, how do the authors choose the function $\\varphi_t(\\theta)$? Besides, how to make sure that the network output is always no larger than the labels?\n\n1.3 In the experiment section, what are the network structures used for QCNN and \"deep neural networks\"? Is the same structure used for every task? What optimizer and hyperparameters are used for training the deep neural networks? It is difficult to draw conclusions about the performance of deep neural networks without knowing any such detail.\n\n2. It is unclear how much advantage in representation power QCNN has over convex neural networks because the structure of QCNN appears to be quite restricted. Specifically, QCNN only contains linear layer, ReLU, and min-pooling and cannot do addition operations on intermediate representations of the networks, deeper QCNNs might not have better representation power than shallower ones. This paper doesn't provide a theoretical analysis of the representation power of QCNN, and the experiments section doesn't provide the performances of convex neural networks.\n\n3. The scale of the experiments is somewhat small, and it seems the authors did not run the experiments multiple times. These makes the experimental results less convincing.\n\n4. This paper doesn't provide theoretical guarantee for the convergence speed of the proposed network with the training algorithm, making it unclear whether QCNN is more efficient than previous methods.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pDmM4Aw48v", "reviewer": "Reviewer_kN6h", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "1. This paper proposed the QuasiConvex shallow neural networks (QCNN) whose optimization is equivalent to a convex feasibility problem, which can be solved efficiently with theoretical guarantees. As the building block, they first proved that the multiplication of ReLU output is quasiconvex. These building blocks can then be integrated by minimization pooling layers while preserving the quasi-convexity. \n2. In the experiments, this paper showed that QCNN outperformed deep neural networks in some tasks, in particular when the tasks involve some characteristics related to convexity. ", "summary_of_the_review": "I think it's certainly an important direction to either prove training guarantees for deep neural networks or propose alternative architecture with theoretical guarantees. Although the proposed QCNN enjoys training guarantees, its representation power seems to be very limited. So I am not sure to what extent QCNN can replace the modern deep networks. All the experiments showing the advantage of QCNN are restricted to synthetic datasets or easy tasks.", "strength_and_weaknesses": "Strengths:\n1. I think it's important to either prove theoretical guarantees for the widely used deep neural networks or propose new architectures that admit simpler theoretical analysis. This paper made progress along the second direction by proposing QCNN that can be optimized efficiently with theoretical guarantees. \n2. It's also interesting that QCNN outperforms deep neural networks on some tasks when the tasks involve some convexity characteristics. This might guide the design of neural networks for these types of tasks in the future. \n\nWeaknesses:\n1. This paper claimed that deep neural networks are likely to be trapped in bad local optimal with a large loss, which I doubt. Although bad local minima do exist, stochastic gradient descent can usually find good solutions on standard tasks with modern architectures. There has been much recent progress in explaining this surprising phenomenon for over-parameterized neural networks (notably the NTK theory and the mean-field theory). \n2. Although over-parameterized deep networks may not be difficult to train empirically, I do agree that it's important to either prove training guarantees for these deep networks or propose other architectures that admit easier analysis. However, the proposed architecture in this paper (QCNN) is very limited in its representation power and may not be able to replace modern deep networks. Although QCNN can be stacked infinitely, as the authors mentioned in the paper, too many minimization pooling layers can damage the representation power. All the experiments showing the advantage of QCNN are restricted to synthetic datasets or easy tasks, which further reinforces my impression of the limitation of QCNN. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Xn0ICUkcnc0", "reviewer": "Reviewer_B2PF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This submission develops neural network architectures for which the squared-error training objective is quasi-c.\nThe proposed models are based on the observation that composition of single ReLU neurons preserves quasi-concavity, as does\nthe minimum-pooling operation.\nBy combining these operators, the authors obtain quasi-concave neural networks capable of representing \nnon-negative piece-wise linear functions.\nThey propose a training algorithm based on bisection search that solves convex feasibility problems as a sub-routine. \nThe submission concludes with empirical evaluations on both synthetic and real datasets.", "summary_of_the_review": "This is an interesting attempt to develop a model class somewhere between the representation power of non-convex neural networks\nand the polynomial-time optimization guarantees of convex models. While the quasi-concave neural networks\nare elegant and mathematically appealing, their utility is not effectively demonstrated by the experimental evaluation and a more rigorous presentation of the training algorithm is necessary. \nI think this could be a strong submission if sufficient baseline experiments are added and I encourage the authors to continue the work.\nHowever, I feel that it is not ready for publication at this time.", "strength_and_weaknesses": "The main strength of this submission is the simplicity and elegance of the construction for quasi-concave neural networks. \nEndowing neural networks with additional structure that makes them possible to globally optimize while preserving some of their\nrepresentation power is a great approach to principled deep learning and valuable for the ICLR community. \nThe manuscript text is also polished and contains many nice figures which contribute to an intuitive understanding of the quasi-concave architecture.\n\nHowever, I feel the strengths of this submission are outweighed by its weakness, which are summarized in the following points:\n\n- Important limitations of the quasi-convex architecture are not addressed in the main text. The proposed architecture can only represent non-negative functions, which is a significant weakness for regression problems. However, this is completed elided and could be missed by the casual reader. \n\n- The submission is not always rigorous and some of the mathematical developments are unclear. For example, see the development of the feasibility algorithm in Eq. 4 and Eq. 5. Firstly, $t \\in \\mathbb{R}$ while $y, f(\\theta) \\in \\mathbb{R}^n$, where $n$ is the size of the training set, so that the operation $y - t - f(\\theta)$ is not well-defined. Moreover, even if $y, f(\\theta) \\in \\mathbb{R}$, the inequality $\\psi_t(\\theta) \\leq 0$ implies $l(\\theta) \\leq t^2 / 2$, rather than $\\(\\theta) \\leq t$. Since, in general, the training problem will be defined for $y \\in \\mathbb{R}^n$, the derivations in the text should handle this general case.\n \n- The experiments are fairly weak and do not convince me that the proposed models have sufficient representation power to merit use over kernel methods and other easy-to-train models. The main issue here is the experimental evaluation does not contain a single standard benchmark problem nor does it compare against standard baseline methods. For example, I would really have liked to see regression experiments on several UCI datsets with comparisons against kernel regression, two-layer ReLU networks, etc. Although boring, such experiments establish a baseline capacity for the quasi-concave networks; this is necessary to show they are \"reasonable\". The experiments as given have several notable flaws:\n    \n    - Synthetic dataset: This is a cute synthetic problem, but obviously plays to the strength of the quasi-concave models. I would have preferred to see a synthetic problem for which was noisy with non piece-wise linear relationship.\n    - Contour Detection Dataset: It is standard to report the overall test ODS, instead of reporting it on different subgroups. This allows the reader to make a fair _overall_ comparison between the two methods.\n    - Mass-Damper System Datasets: This is a noiseless linear regression problem in disguise, so it's not surprising that quasi-concave networks perform well. \n    - Change-point Detection: Again, I would really have rather seen some basic benchmarks like MNIST before moving on to novel applications like detecting changes in data distribution.\n\n#### Minor Comments\n\n**Introduction**: \n    - The correct reference for SGD is the seminal paper by Robbins and Monro [1]. \n    - The correct reference for backpropagation is Rumelhart et al. [2]  \n    - \"Issue 1: Is non-convex deep neural networks always better?\": \"is\" should be \"are\".\n    - \"While some experiments show that certain local optima are equivalent and yield similar learning performance\" -- this should be supported by a reference.\n    - \"However, the derivation of strong duality in the literature requires the planted model assumption\" --- what do you mean by \"planted model assumption\"? The only necessary assumption for these works is that the shallow network is sufficiently wide.\n\n**Section 4**:\n    - \"In fact, suppose there are m weights, constraining all the weights to be non-negative will result in only $1/2^m$ representation power.\" -- A statement like this only makes sense under some definition of \"representation power\". For example, it is not obvious how non-negativity constraints affect the underlying hypothesis class (aside from forcing it to contain only non-negative functions), which is the natural notion of representation power. \n    - Equation 3: There are several important aspects of this model which should be mentioned explicitly in the text. Firstly, it consists of only one neuron; this is obvious from the notation, but should be stated as well. Secondly, it can only model non-negative functions. This is a strong restriction and should be discussed somewhere. \n    - \"Among these operations, we choose the minimization procedure because it is easy to apply and has a simple gradient.\" --- the minimization operator may produce a non-smooth function, which does not admit a gradient everywhere. Nor is it guaranteed to have a subgradient since the negative function only quasi-convex, rather than convex.\n    - \"... too many minimization pooling layers will damage the representation power of the neural network\" --- why? Can the authors expand on this observation? \n\n**Section 5**:\n    - \"... if we restrict the network output to be smaller than the network labels, i.e., $f(\\theta) ≤ y$\" --- note that this observation requires $y \\geq 0$, which does not appear to be explicitly mentioned. \n    - What method is being used to solve the convex feasibility problem in Eq. (5)? I cannot find this stated anywhere. \n\n**Figure 6**:\n    - Panel (b): \"conveyers\" -> \"converges\".\n\n**Figure 7**:\n    - The text inside the figure and the labels are too small to read without zooming. This text should be roughly the same size as the manuscript text.\n    - \"It could explain that the classification accuracy of QCNN (94.2%) outperforms that of deep networks (92.7%)\" --- Is this test accuracy, or training accuracy? I assume this is the test metric on the hold-out set, but the text should state this clearly. \n### References\n\n[1] Robbins, Herbert, and Sutton Monro. \"A stochastic approximation method.\" The annals of mathematical statistics (1951): 400-407.\n\n[2] Rumelhart, David E., Geoffrey E. Hinton, and Ronald J. Williams. \"Learning representations by back-propagating errors.\" nature 323.6088 (1986): 533-536.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "URtsdCcBwS", "reviewer": "Reviewer_QKhx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This work suggests a novel shallow neural network architecture that is quasi-concave. Consequently, the network can be trained in regression settings with convex optimization tools that have optimization guarantees. The efficacy of the network is demonstrated in several practical tasks.", "summary_of_the_review": "Interesting architecture and idea of introducing quasiconvexity. However, the claims in the paper are not well supported and the experimental settings should be clarified. Furthermore, there is currently an unclear step in the optimization algorithm.", "strength_and_weaknesses": "Strengths:\n1. Novel neural architecture with formal optimization guarantees.\n2. Introducing quasi-convex/concave structures to neural networks is interesting.\n\nWeaknesses:\n1. The paper only focuses on the regression setting, while it is written as if the results hold more generally (i.e., in both classification and regression settings). Furthermore, the quasi-convex network is shallow.\n2. In the paper there are several claims which are not well established:\n(a) It is claimed that neural networks can fail to optimize. The main example given to support this, is the theoretical work of Brady et al. (1989). They show that backprop fails in a regression setting with logistic activation functions. In contrast, there are many theory papers which show that for modern-day networks with ReLU activations, optimization is tractable for overparameterized neural networks (e.g., see papers on NTK). Thus, the claim that optimization is an issue for neural networks is not well established.\n(b) It is claimed that “The non-convex network could fail, i.e., being trapped in bad local optima with large errors, especially when the task involves convexity (e.g., linearly separable classification)”. The claim that networks fail in tasks that involve convexity is not well established and seems to be only based on the example of Brady et al. (1989). As mentioned, the latter example is in a regression setting and networks with logistic activations (which, to my knowledge, are not widely used in practice). I am not aware of papers which show that networks with ReLU activations fail when classifying linearly separable datasets.\n\n3. The training procedure is unclear. How is the network output restricted to be smaller than the network labels? There are no details on this.\n\n4. Some of the experimental settings are unclear. (a) In the synthetic dataset, which neural network was used? It seems odd that a neural network cannot fit the curves exactly. What were the training points in these experiments? (b) The experimental setting of the change-point detection and contour detection are unclear. What exactly are the data and labels and what is the regression/ classification task?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject