Stochastic Proximal Point Algorithm for Large-scale Nonconvex Optimization: Convergence, Implementation, and Application to Neural Networks
Authors: Aysegul Bumin
Kejun Huang
Venue:  (2021)

Abstract: We revisit the stochastic proximal point algorithm (SPPA) for large-scale nonconvex optimization problems. SPPA has been shown to converge faster and more stable than the celebrated stochastic gradient descent (SGD) algorithm, and its many variations, for convex problems. However, the per-iteration update of SPPA is defined abstractly and has long been considered expensive. In this paper, we show that efficient implementation of SPPA can be achieved. If the problem is a nonlinear least squares, each iteration of SPPA can be efficiently implemented by Gauss-Newton; with some linear algebra trick the resulting complexity is in the same order of SGD. For more generic problems, SPPA can still be implemented with L-BFGS or accelerated gradient with high efficiency. Another contribution of this work is the convergence of SPPA to a stationary point in expectation for nonconvex problems. The result is encouraging that it admits more flexible choices of the step sizes under similar assumptions. The proposed algorithm is elaborated for both regression and classification problems using different neural network structures. Real data experiments showcase its effectiveness in terms of convergence and accuracy compared to SGD and its variants.

Under review as a conference paper at ICLR 2021
STOCHASTIC PROXIMAL POINT ALGORITHM FOR LARGE-SCALE NONCONVEX OPTIMIZATION: CONVERGENCE, IMPLEMENTATION, AND APPLICA- TION TO NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We revisit the stochastic proximal point algorithm (SPPA) for large-scale nonconvex optimization problems. SPPA has been shown to converge faster and more stable than the celebrated stochastic gradient descent (SGD) algorithm, and its many variations, for convex problems. However, the per-iteration update of SPPA is defined abstractly and has long been considered expensive. In this paper, we show that efficient implementation of SPPA can be achieved. If the problem is nonlinear least squares, each iteration of SPPA can be efficiently implemented by Gauss- Newton: with some linear algebra trick the resulting complexity in the same order of SGD. For more generic problems, SPPA can still be implemented with L-BFGS or accelerated gradient with high efficiency. Another contribution of this work is the convergence of SPPA to stationary point in expectation for nonconvex problems. The result is encouraging that it admits more flexible choices of the step sizes under similar assumptions. The proposed algorithm is elaborated for both regression and classification problems using different neural network structures. Real data experiments showcase its effectiveness in terms of convergence and accuracy compared to SGD and its variants.
INTRODUCTION
Algorithm design for large-scale machine learning problems have been dominated by the stochastic (sub)gradient descent (SGD) and its variants (Bottou al. 2018). The main reasons are two-fold: on the one hand, the size of the data set may be so large that obtaining the full gradient information too costly; on the other hand, solving the formulated problem to very high accuracy is typically unnecessary in machine learning, since the ultimate goal of most tasks is not to fit the training data but to generalize well on unseen data. As a result, stochastic algorithms such as SGD has gained tremendous popularity recently.
There has been many variations and extensions of the plain vanilla SGD algorithm to accelerate its convergence rate. One line of research focuses reducing the variance of the stochastic gradient, resulting in famous algorithms such as SVRG (Johnson and Zhang 2013) and SAGA DDfazio et al. 2014), which results in extra time/memory complexities of the dlgorithm (significantly). More recently, adaptive learning schemes such as AdaGrad (Duchi et al. 2011) and Adam (Diederik) Kingma, 2014) have shown be more effective in keeping the algorithm fully stochastic and light- In terms of theory, there has also been surging amount of work quantifying the best [
possible rate using first-order information (Lei al., [017]] Allen [007 [01 b), well as its
ability to obtain not only stationary points but also local optima (Ge et al. 2015 Jin et al. 2017 Xu
al. 2018 Allen-Zhu 2018).
1.1 STOCHASTIC PROXIMAL POINT ALGORITHM (SPPA)
In this work, consider different type of stochastic algorithm called the stochastic proximal point algorithm (SPPA), also known as incremental proximal point method (Bertsekas) 201 b) or stochastic proximal iterations (Ryu and Boyd 2014). Consider the following optimization problem

---

Under review as a conference paper at ICLR 2021
with the objective function in the form of a finite of component functions
minimize Oete
Σ 4(0)= = L(O).
(I)
SPPA takes the following simple form:
1: repeat
2: randomly draw i from f1, (I.....n)
3: 0,11 arg ming ( (1/2)l1e 0,11 Proxi, (0,)
4: until convergence
The update rule in line 3 is called the proximal operator of the function 2, evaluated at 0,. This is the stochastic version of the proximal point algorithm, which dates back to RRockaflllar (1976).
Admittedly, SPPA not as universally applicable as SGD, due to the abstraction of the per-iteration update rule. It is also asking for more information from the problem than merely the first-order derivatives. However, with the help of more information inquired, there is also hope that provides faster and more robust convergence guarantees.
As we will see in numerical experiments, SPPA is able to achieve good optimization performance by taking fewer number of passes through the data set, although it takes little more computations for each batch. We believe in many cases it is worth trading off more computations for fewer memory accesses.
To the best of our knowledge, convergence analyses of SPPA has only been studied for convex problems (Bertsekas) [011a]] Ryu and Boyd 2014 Bianchi 2016). Their study shows that SPPA converges somewhat similar to SGD for convex problems, but the updates are much more robust to instabilities in the problem. Most authors also accept the premise that the proximal operator sometimes difficull to evaluate, and thus proposed variations to the plain vanilla version to handle
more complicated problem structures (Wang and Bertsekas) 2013: Duchi and Ruan 2018 Asi and
Duchi 2019b Davis and Drusvyatskiy 2019).
In terms of nonconvex optimization problems, there is very little work until very recently (Davis and Drusvyatskiy 2019 Asi and Duchi 2019a). However, their convergence analysis is somewhat
unconventional. Typically for a nonconvex problem, we would expect a theoretical claim that the iterates generated by SPPA converges (in expectation)
stationary point. This is not easy, and the result given by (Davis and Drusvyatskiy 2019) and (Asi and Duchi 2019a) defined an imaginary sequence (that is not computed in practice) (0,} as 0, arg ming a, (() + (1/2) 0, 1l i.e., the proximal operator of the full loss function from the algorithm sequence {0,). Their results show that this imaginary sequence (0,) converges to a stationary point in expectation.
1.2 CONTRIBUTIONS
There are main contributions we present in this paper; efficient implementations of proximal operator update for SPPA with application on regression and classification problems, and convergence stationary point for SPPA algorithm for general non-convex problems. The cost of this abstract per-iteration update rule has been the burden for SPPA algorithm, even though it has been shown to converge faster and more stable than the celebrated SGD algorithm. In this paper, we show that is actually not a burden when the per-iteration update is efficiently implemented.
In the implementation section we will discuss the implementation of abstract per-iteration update rule for non-linear least squares (NLS) problem and other non-linear problems. We present two different implementations for these two different categories of problems. SPPA-Gauss Newton (SPPA-GN) and SPPA-Accelerateer respectively for regression with nonlinear least squares and classification problems. We apply SPPA to large family of nonconvex optimization problems and show that the seemingly complicated proximal operator update still be efficiently obtained. Both implementations give results that are comparable with the state of the art stochastic algorithms.
On the other hand, there is large group of nonlinear problems that are not necessarily expressed as a NLS problem (non-NLa noS.. Many of the classification problems in deep learning applications as of today, use different type of loss functions than mean least squared error. Hence, we suggest
2

---

Under review as a conference paper at ICLR 2021
Convolutional Neural Network
Convolutional Neural Network
60
Cross Entropy Loss
1.75
140
Accuracy
1.50
40
1.25
30-
5PH (Aouptill)
1.00
3PA% (L.)
20
Adom
0.75
Adagrad
SCD with Nomentum
5CD
20
40
60
80
100
120
20
40
60
80
100
120
500 Stochastic Update (Batch Size
500 Stochastic Update (Batch Size 4)
Figure 1: CIFARIO: cross entropy loss
Figure 2: CIFARIO: prediction accuracy
alternative to SPPA-GN where we implement the per-iteration update rule based on well-known stochastic optimization algorithmss, preferably with the ones that take less number iterations to converge like L-BFGS (Liu and Nocedal 1989).
As second contribution, we show that SPPA, when applied to a nonconvex problem, converges to a stationary point in expectation, informally stated follows
Theorem 1. (informal.) For SPPA with fixed A, A, the expected gradient converges to region where the norm bounded with radius proportional to d. For diminishing step sizes such that
T
ΣJ A7
the expected gradient converges to zero.
Finally, we apply SPPA with the novel efficient updates to some classical regression and classification using 4 different data sets for neural network training. Detailed algorithmic descriptions are provided, and we show the outstanding performance of SPPA when effectively executed.
As sneak peek of the numerical performance of the proposed SPPA implementation. Figures 1 and shows the cross entropy loss and prediction error on the test set over the progression of SPPA verses various baseline algorithms. SPPA indeed converges much faster than all SGID-based methods, achieving peak prediction accuracy after only going through the data set approximately 10 times. We should stress that the per-iteration complexity of SPPA is higher than other methods, since it tries to solve small optimization problem rather than a simple gradient update. However, as we have argued before, in many cases it is worth trading off more computations for fewer memory accesses.
EFFICIENT IMPLEMENTATION
In this section we introduce several efficient methods to calculate the proximal operator update given in pseudo-code of SPPA section I.I line 3. The two methods emerge from the question of 'How can implement the proximal operator update efficiently?". The answer to this question depends the type of the objective function. We considered the problems two different categories, nonlinear least squares (NLS) and other generic nonlinear problems.
2.1 SPPA-GN FOR NONLINEAR LEAST SQUARES
A nonlinear least squares (NLS) problem takes the following form
1 Σ 1=1
minimize BeRd
(0))
where each 9 is a general nonlinear function with respect to It is a classical nonlinear programming problem (Bertsekas) 1999) Boyd and Vandenberghe 2018) with many useful applications, including

---

Under review as a conference paper at ICLR 2021
least squares neural networks (Van Der Smagt of fitting for the ith data sample for regression. We will show that problems of this form can be efficiently executed by SPPA-GN, despite its seemingly complication.
1994). where each yi corresponds to the residual
To apply SPPA to NLS, the main challenge is to efficiently evaluate the proximal operator
A (0)) + + 0,11?. 0 arg min
1
(3)
2
Notice that this function itself is nonlinear least squares objective, although with only component function together with the proximal term.
The traditional wisdom solve NLS problem is to apply the Gauss-Newton (GN) algorithm: at each iteration, we first take a first-order approximation of the vector-valued function inside the Euclidean norm, and set the update the solution of the approximated linear least squares problem. It is well-known algorithm that can be found in many standard textbooks, e.g.. (Bertsekas 1999 Nocedal and Wright 2006 Boyd and Vandenberghe 2018).
To apply GN to first take linear approximation of y the current update 0 as
()) = (0) + (O) 0),
and set the solution of the following problem 0* as the next update
1 } 0,11 minimize 2 vv 0))
(4)
Obviously, has closed form solution
0 = 0,
1 8:88 1r
(0) 87 0,)).
(5)
where we denote g; ( (0) to simplify notation. Notice that the matrix to be inverted in (5) has simple "identity plus rank-one" structure, implying that it can be efficiently computed in linear time. Using the "kernel trick" (Boyd and Vandenberghe, [2018] pp.332)
(A'A+al)-'A"= (AAA++a))"
(6)
update (5) simplifies to
0+ 0, (0) (0) 01)
(0).
27' + (0]12
As we can see, each GN update only takes O(d) flops, which is cheap that of a SGD step. To fully obtain the proximal operator 33, one has to run GN for several iterations. However, thanks to the superlin- convergence of GN near its optimal (Nocedal and Wright 2006), which in- deed the case if we initiate at O, because of the proximal term, it typically takes no more than 5-10 GN updates.
Algorithm 1 SPPA-GN
1:
initialize Gp. / < 0
repeat 3: randomly draw from {1....,
0* O.
5:
repeat
6:
0 - 0"
7:
0+
- 00.00 Vo
Vip
8:
until convergence
The detailed description of the proposed algorithm, which we term SPPA-GN, for solving general NLS problems is shown in Algorithm
9:
0,+1 + , +++++1
10:
until convergence
2.2 SPPA-LBEGS AND SPPA-AGD FOR GENERIC LOSSES
Even for generic nonlinear programming problems, it is still possible to efficiently evaluate the proximal update beyond merely a simple gradient step. The idea is to apply the limited limited-memory memory BFGS algorithm (Nocedal and Wright 2006), or I.-BFGS for short. L-BFGS is memory-efficient
4

---

Under review as a conference paper at ICLR 2021
implementation of the famous quasi- algorithm BFGS. In nut shell, L-BFGS is iterative algorithm that makes use of the second-order information from the optimization loss function, but does not require solving matrix inverses and only requires explicitly evaluating first-order gradients. For a prescribed number of iterations, it requires one matrix-vector multiplication and multiple vector multiplications, As a result, the overall complexity is again ((d) if the initial guess of the Hessian matrix is diagonal.
While there are certain limitations for applying L-BFGS general nonlinear programming problems, we reckon that it fits perfectly in the context of SPPA implementations.
L-BFGS has to specify a good initial guess of the Hessian approximation matrix. While in many cases people simply use the identity matrix to start, it may result in very poor approximation. Fortunately, thanks the proximal term, the identity matrix is in fact very good initial guess for the Hessian matrix for SPPA updates.
In order to save memory consumption, L-BFGS has to prescribe the number of iterations before running the algorithm. Obviouly. if the prescribed number of iteration is too large, we incur unnecessary computations, while if it is too small we need invoke another round with a new estimated Hessian matrix. However, again in the context of SPPA, the proximal term ||0 1. naturally provides a good initialization 0,- Our experience show that prescribing 10 iterations of L-BFGS updates is more than enough to obtain extremely accurate solutions.
On the other hand, it perhaps makes more sense to simply use some more advanced first-order methods such as Nesterov's accelerated gradient descent (1983) 2013) to calculate the proximal update. Both L-BFGS and accelerated gradient descent evaluates the gradient of the loss function with (d) complexity, and the question is how to leverage convergence rate versus sophistication.
CONVERGENCE ANALYSIS
In this section we provide convergence analysis of SPPA for general nonconvex loss functions | to a stationary point, as informally stated in Theorem I To the best of our knowledge, convergence of SPPA for nonconvex problems is still missing of this writing.
There is a well-known resemblance between proximal methods and gradient descent: while a full gradient descent step takes the form 0,+1 0, A, (O,),,, the definition of full proximal step guarantees that A, V ())(++)) = 0,+1 0,, meaning that 0,+1 = 0, A, (. Therefore, one might expect that well-established convergence analysis of SGD for nonconvex problems, for example (Bottou et al.) 2018 $4.3), can be seamlessly applied to SPPA. This is unfortunately not the case.
Consider V[ where the expectation is taken over the sampling procedure conditioned on 0,, for SGD we typically require ((, to be an unbiased estimator of VL())), which is easy to satisfy. For SPPA then one needs to consider [[ again over the sampling procedure conditioned on 0,. This is in fact difficult to quantify because the update 0,+1 depends on the sample that is drawn from the data set. requires a somewhat different approach to establish its convergence.
The convergence analysis is developed under the following three assumptions, and we explain their implications when applied SPPA. The detailed proofs are presented in supplementary document. Assumption 1. The loss function | has bounded deviation:
([)(()) - (())) s o.
Assumption 2. Each component function (())) is differentiable and Lipschitz continuous with parameter (0) ((;(0)] s иI|Ø Ø11. V 0. 0 e dom 6,
Assumption 3. The SPPA updates lie in compact set, i.e., there exists constant that ||0 0|| s for all 0 and 0.
Under these rather standard assumptions, we have the following proposition, which serves as the stepping stone for our main convergence results. The proof of Proposition relegated to the appendix.
Proposition Under Assumptions 7 and at iteration we have
[VV( < 4p (L(6,) - E[L(O,,)] + o)) + 2cC,
(8)
where C = 2 1) and the expectation is taken over the sampling of conditioned on O,
5

---

Under review as a conference paper at ICLR 2021
With the help of Proposition! | the rest of the results follows similarly to those presented in (Bottou et al. 2018 $4.3) for constant step sizes and diminishing step sizes. However, we point out two significant advantages compared to the standard SGD results:
For constant step sizes, there is no limit on how small A should be. Obviously larger rapidly converges to bigger vicinity around stationary point, while smaller a slowly converges smaller vicinity. However, unlike SGD, the constant step size d can be arbitrarily large, and the expected gradient can still be bounded.
For diminishing step sizes, we only need 2, - 0 and Σ,, - co, but not the square summable assumption Σ 27 < co. This gives the option of picking slower diminishing step size such as 1/vi for faster convergence rate.
3.1 CONVERGENCE WITH CONSTANT STEP SIZES
Theorem 2. Under Assumptions and &
suppose SPPA is run with constant step size d, A for all I, then the expected averuged squared gradients satisfy
and
E
T
VL(0,)
x 4pp
(.((0)
Linf
+ +o + + 1C T-20 1(4p2o
(9)
T
T
1=1
Proof.
Taking the total expectation of (8) and summing over 1 I...., ,,, we get
E
|VL0))1
s (L(o) +o) TACC
Replace E[L(Or)) with the infimum Lint E[L(Or)) and divide both sides by T shows
Theorem 2 shows that 7 increases, SPPA spends increasingly more time in regions where the updates have relatively small gradients. The size of the region is proportional to d. The interesting observation is that can be arbitrarily large, unlike the SGD case, albeit the bound on the expected gradient would also be thereupon large as well.
3.2 CONVERGENCE WITH DIMINISHING STEP SIZES
To further drive the expected gradients closer to zero, we can use diminishing step sizes as shown below. Notice that we only require that the sum of the step size reciprocals grow faster than T, without the more stringent condition that the diminishing step sizes are square summable. This allows us use step sizes that decrease lot slower, such as A, 1/vi, for faster convergence rate, while ensuring that the expected gradient goes to zero asymptotically. An analogous result has not been achieved SGD when applied to nonconvex problems.
Theorem 3. Under Assumptions and suppose SPPA run with a diminishing step size, then the expected averaged squared gradients satisfy
Σ
4p² (L(Oo) - Linf +To) +TC T-20 0.
E
<
(10)
AT
AT
where a, = 1/2, and Ar = En Un if the step sizes satisfy that
lim 0. --00 Ar
(11)
Proof. We rearrange 8 into
1, IV s 4u² - -[[(()))))) +o)
Then apply similar strategy as in the proof of Theorem 2 to obtain the first line of 10 Furthermore, if (TT holds, (10) goes to zero T co.

---

Under review as a conference paper at ICLR 2021
MNIST Dataset
MNIST
Convolucional Neural Network
Convolutional Neural Network
100
SPRneN (2r)
2.0
Adagrad
80-
Cross Entropy Loss
1.5
Accuracy
60
1.0
40
STT--GD DeenKi
0.5
SP% LiF-N
(34)
20
Haart
0.0
10
15
20
25
30
35
5
10
15
20
25
30
35
25 Stochastic Update (Batch Size 64)
25 Stochastic Update (Batch Size
64)
Figure 3: MNIST: cross entropy loss
Figure 4: MNIST: prediction accuracy
4 EXPERIMENTS
We show some real data experiments to demonstrate effectiveness of the proposed SPPA implementa- tions in classification and regression problems respectively. We compare our proposed algorithms with three variants of SGD; the original version with various step strategies. SGD with momentum (Sutskever et al. 2013), Adagrad (Duchi et al. 201T). and Adam (Diederik Kingma 2014), with the default settings suggested in their original papers. We used the PyTorch (Paszke et al. 2019) implementation of the algorithms and used the same platform for implementing our customized optimization algorithm.
4.1 CLASSIFICATION WITH SPPA-AGD AND SPPA-LBEGS
We present the results of the classification problem with two data sets (MNIST (LeCun et al. 2010). CIFARIO 10 (Krizhevsky et al. 2010) using SPPA-AGD algorithm. In all the results presented, the settings are the default settings provided by PyTorch library. We experimented with different settings with all the algorithms and the best results are obtained when the settings were the default settings.
MNIST MNIST Handwritten Digits Dataset (LeCun et al. 2010) is a common dataset used for showing the effectiveness of many state of art the algorithms. It consists of 60,000 training, 10,000 test images of size 28 x 28 in 10 classes. The network we used for this experiment is based on convolutional deep neural network. It consists of 4 layers, the first of which being convolutional and last 2 being fully connected. The loss function is cross entropy loss, and the activation function is RELU. Batch size is 64. To show the behaviour of the algorithms more in detail we recorded the loss values at every 25 stochastic update, the experiment is run for epoch and in total 38 updates are presented (25 x 38 x 64 giving the number of training samples). The accuracy is calculated on the test data at every 500 stochastic update, using the accuracy calculation in PyTorch tutoria[]] As observed in Figures 3 [ oppA-based methods outperforms all SGD-based algorithms in terms of both the cross entropy loss and prediction accuracy on the test set.
CIFAR10 CIFAR1O (Krizhevsky et al., 2010) is relatively extensive dataset compared to MNIST. consists 50,000 training, 10,000 test images of size 32 x 32 in 10 classes. The network we used for this experiment is based convolutional deep neural network. It consists of 5 layers, the first 2 of which being convolutional and last being fully connected. The loss function is cross entropy loss, and the activation function is RELU. Batch size is 4. To show the behaviour of the algorithms more in detail we recorded the loss values at every 500 stochastic update, the experiment is run for epochs and in total 125 updates are presented (25 500 x giving the number of training samples). The accuracy is calculated on the test data at every 500 stochastic update overall for 5 epochs, using the accuracy calculation in Py Torch tutorial. Convergence plots are shown in Figures and the beginning of the paper.

---

Under review as a conference paper at ICLR 2021
Housing Dataset Regression
Regression
200
175
12
MSE Loss
MSF Locs
125
8
100
75
25
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
5
Epoch (Batch Size 1)
Epoch (Batch Size 1)
Figure 5: Boston housing prices
Figure 6: Ames housing prices
4.2 REGRESSION WITH SPPA-GN
In this subsection, we compare the performance of SPPA in two regression problems. Using the least squares loss, the problem becomes an instance of nonlinear least squares, thus our proposed SPPA-GN algorithm could be applied. The inner loop in SPPA-GN algorithm is run at most 10 times for the results presented below.
Boston House Prices Boston House Prices data set (Harrison Jr and Rubinfeld 1978) is relatively small data set but one of the most commonly used one for regression. It consists of 506 samples (404 training, 102 test) with 13 features each predict housing prices. The neural network used for this experiment is multi-layer feed-forwan network. It consists of input layer, 2 hidden layers, and I output layer (13-(10-10)-1) 1). All layers are fully connected. The batch size is We present the loss value that we observed in every epoch. Figure 5 shows the test error obtained after each pass of the entire training set. Similar to the previous experiments, SPPA converges faster than all of the baseline SGD-based algorithms, although the improvement is not as great as the previous experiments due to the small-size this data set.
Ames Housing Prices Ames Housing Dataset (De Cock 2011 is extended version of Boston House Prices data set (Harrison Jr and Rubinfeld 1978). It consists of 1460 samples (1 training, 292 test) with 80 features. The neural network used for this experiment is again multi-layer feed- forward network. It consists of I input layer, 2 hidden layers, and I output layer (288-(72-18)-1), All layers are fully connected. The batch size is 1. Figure [ shows the test error obtained after each pass of the entire training set. Again SPPA performs better than all other methods on this slightly bigger data set for regression. A somewhat remarkable observation is that the testing loss manages to achieve the minimum in only one pass of the entire data set (of course with a little more computations when handling each data point). If the computing node prefers more computations than data loading, SPPA is much more preferable in this case.
5 CONCLUSION
In this paper presented efficient implementations of the stochastic proximal point algorithm (SPPA) for large-scale nonconvex learning problems. The specific approach to efficiently evaluate the proximal operators is based on the somewhat forgotten quasi-Newton methods with superlinear convergence rate such as Gauss-Nee Newss-Newton and L-BFGS. We also proved that SPPA converges, in expectation, to stationary point of nonconvex problem with more flexible choices of the step sizes. Detailed proof can be found in the appendix. The resulting algorithm has cheap per-iteration complexity, while enjoying faster and more robust convergence under milder conditions. We demon- strate the performance of SPPA with our proposed efficient implementation on some well-known classification and regression data sets for neural network training, and showed that they outperform many existing methods.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The First Direct Acceleration of Stochastic Gradient Methods. In STOC, 2017.
Zeyuan Allen-Zhu. Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Op- timization. In Proceedings of the 35th International Conference on Machine Learning, ICML 118, 2018a.
Zeyuan Allen-Zhu. How To Make the Gradients Small Stochastically. In Proceedings of the 32nd Conference on Neural Information Processing Systems, NeurlPS '1, 2018b.
Zeyuan Aluen-Zhu. Natasha 2:
Faster non-convex optimization than SGD. In Advances in Neural Information Processing Systems, pages 2675-2686, 2018.
Hilal Asi and John C Duchi. The importance of better models in stochastic optimization. Proceedings of the National Academy of Sciences, 16(46):22224-222900 2019a.
Hilal Asi and John C Duchi. Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity. SIAM Journal on Optimization, 29(3):225--2900, 2019b.
Dimitri P. Bertsekas. Nonlinear Programming. Athena Scientific, 1999.
Dimitri P Bertsekas. Incremental proximal methods for large scale convex optimization. Mathematical programming, 129(2):163, 201
Dimitri Bertsekas. Incremental gradient, subgradient, and proximal methods for convex optimiza- tion: A survey. Optimization for Machine Learning, 2010(1-38):3, 201 1b.
Pascal Bianchi. Ergodic convergence of stochastic proximal point algorithm. SIAM Journal Optimization, 26(4): 2260, 2016.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Stephen Boyd and Lieven Vandenberghe. Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares. Cambridge University Press, 2018.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-239) 2019.
Dean De Cock. Ames, iowa: Alternative to the boston housing data end of semester regression project. Journal of Statistics Education, 19(3), 2011.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pages 1646-1654, 2014.
Jimmy Ba Diederik P. Kingma. Adam: method for stochastic optimization. In Proceedings of the 3rd International Conference Learning Representations, 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(ull)2121-2155) 201
John Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimization problems. SIAM Journal on Optimization, 28(4):3229-3255) 2018.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-onling stochastic gradient for tensor decomposition. Conference on Learning Theory, pages 797-842, 2015.
David Harrison Jr and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. 1978.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1724-1732. JMLR. org, 2017.

---

Under review as a conference paper at ICLR 2021
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315-323 2013.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). URL http://ww.. cs. toronto, edu/kriz/cifar. html, 5, 2010.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. 2010. URL http://yann. lecun. com/exdb/mmist, 7:23, 2010.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via
scsg methods. In Advances in Neural Information Processing Systems, pages 2348-2358, 2017.
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming. 55(1-3):503-528 1989.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Yurii E Nesterov. A method for solving the convex programming problem with convergence rate (1/k2). Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances neural information processing systems, pages
2019.
R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal control and optimization, 14(5).877-893 1976.
Ernest K Ryu and Stephen Boyd. Stochastic proximal iteration: a non-asymptotic improvement upon stochastic gradient descent. Preprint, 2014.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1 1139- 1147, 2013.
Patrick Van Der Smagt. Minimisation methods for training feedforward neural networks. Neural networks, 7(1):1-11, 1994.
Mengdi Wang and Dimitri Bertsekas. Incremental constraint cnojection-proxinee methods for nonsmooth convex optimization. SIAM J. Optim. appear), 2013.
Yi Xu, Rong Jin, and Tianbao Yang. First-orde stochastic algorithms for escaping from saddle points in almost linear time. Advances Neural Information Processing Systems, pages 5530-5540, 2018
10

---

Under review as a conference paper at ICLR 2021
A
APPENDIX: PROOF OF PROPOSITION 1
First, we introduce a new notation
@ r+1
1 arg min (0) + -110- 0 -
=2100)++10000
(12)
0
to denote the update at iteration had we sampled the ith data point. Since 4 is nonconvex, there is typically no guarantee that the exact minimum (I2) is obtained. However, as we will see soon, the convergence analysis stays valid as long as the following two conditions hold:
decrease:
110 r+1 - =0,12=&((00) - (1(0 22,
(13)
stationarity:
2 (VC r+1 0, (00)
(14)
1+1'
Lemma 1. Under Assumption 7 we have at iteration
E[Il0,,1 0, s 22, (L(0,) E[L(O o0)
(15)
where expectation is taken over the sampling of conditioned on O,.
Proof. Taking expectation of 13 over conditioned on 0, gets
B[] 0, 11
11 ++
0,112 s 24, L(O,)
Σ
(( [+1
Invoking Assumption I shows
15
Lemma 2. Under Assumption and
we have at iteration 1
(V 24² E[]l0,+1 0,11²) + 2C
(16)
where expectation is taken over the sampling i conditioned on O,.
Proof. Apply Assumption to 0 f and 0,, and take expectation over conditioned on 0,, get
R
VE VE
#
110 12 0,11- r+1
(17)
n
The feft-hand-side of can be lowerbounded by the triangle inequality
V0 (+1 - vL((.)
IV -
(18)
where
n VL(0,)
(,)
by definition. Then we apply triangle inequality again to obtain
[[V 1 (0
v -V
(19)
Invoking Assumption stationary condition 14). and combining them with gives
and
19
|V < 4 1 0,1l + vd.c
(20)

---

Under review as a conference paper at ICLR 2021
The right-hand hid---innddddddd----------eeee of (20
be upperbounded by the norm inequality || ll
Vill 1l2 as
Vdten
Σ
110 (1) r+1
0,1l +
f
d
(n+ 1)
10000
0,11
11
i=1
2, (n 1) n(n + 1) E[10,,,, 0,11-]
(21)
1
Combining 20 and 21
and squaring both sides shows (16)
Simply putting Lemma 1 and Lemma together, we obtain in Proposition !
12


Reviews:
[{"review_id": "ygqk6REafp", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the stochastic proximal point algorithm (SPPA) for large-scale nonconvex optimization problems. The authors propose to use Gauss-Newton to perform the proximal update in nonlinear least squares and L-BFGS or accelerated gradient for generic problems. The authors derive the convergence of SPPA to a stationary point in expectation for nonconvex problems, and perform numerical experiments to showcase the effectiveness of the proposed method compared to SGD and its variants. \n\nThe paper is generally clear, yet the convergence analysis is mainly based on adapting Bottou et al. (2018). While the proposed methods could be significant additions to stochastic optimizers in deep learning, I found the study of the current paper is insufficient; see the cons below. \n\nPros: \n- It is well-known that the proximal point algorithm (PPA) converges faster than gradient descent (GD), and the same holds for their stochastic counterparts. One advantage is that the step sizes in PPA and SPPA can be larger than those in GD and SGD, which can speed up convergence. The proximal steps in PPA and SPPA are however hard to perform for generic (nonconvex) problems since the proximity operator of the objective functions usually do not have closed forms. The proposal of the authors to perform efficient inner-loop optimization schemes like Gauss-Newton and L-BFGS allows approximation of such proximal steps, without much computational burden added. \n\nCons: \n- Theory:\n    * I found that Assumption 3 is too strong and do not think it is a standard assumption. Otherwise the constant $ c $ can be very large. This also leads to a question of why using the upper bound $ c $ is the second part of the RHS of (20) but not the first part?\n    * Also why $ \\sqrt{\\lambda_t} $ instead of $ \\lambda_t $ in (20)? If I did not misunderstand, it is derived from (14).\n    * As $ c $ and hence $ C $ can be very large, the bounds (9) and (10) in Theorems 2 and 3 can well be vacuous.\n    * Also the quantifier in Assumption is missing (for all $ i\\in \\lbrace 1, \\ldots, n \\rbrace $?) \n    * Another pitfall of the theoretical results of this work is that the convergence analyses of the proposed SPPA-LBFGS, SPPA-AGD and SPPA-GN are all missing, especially since this work considers nonconvex problems. \n\n- Experiments:\n    * To showcase the proposed methods are really comparable to or outperform methods like SGD or Adam, numerical experiments should be performed on data sets of larger scales and much deeper networks. In particular, the regression data sets in the paper are so small that the gain of the proposed method over other baselines are so marginal. \n\nTypos: \n- Theorem 1: do you mean the limit is equal to 0 or is finite? I guess something is missing. \n- Proof of Theorem 2: $ L(\\theta_1) - \\mathbb{E}[L(\\theta_{T+1})] $ instead of $ L(\\theta_0) - \\mathbb{E}[L(\\theta_{T})] $\n- (10): the LHS of the inequality should be $ \\alpha_t $ instead of $ \\alpha $", "extra_scores": {}, "extra_text": {}}, {"review_id": "xYX4ikYSEuM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors study stochastic proximal point algorithm for nonconvex optimization, where the model is iteratively updated by solving a proximal optimization problem based on a randomly selected loss function. The authors develop efficient implementation for solving the proximal optimization problem: first for nonlinear least squares and then for general losses. Then the authors study the convergence rates for the developed algorithm. Upper bounds on the expected average squared gradients are developed for both constant step sizes and diminishing step sizes. Experimental results are also reported to support the algorithm in practical implementations.\n\nComments.\n\n1. The authors show that the proximal optimization problem can be efficiently solved. This is nice. However, the idea in the development of the algorithm seems standard. It seems a bit surprising that this algorithm has not been developed before.\n\n2. The convergence rates are a bit surprising. For example if we set $\\lambda=0$ in Thm 2, then eq (9) shows that the averaged gradient converges to zero, which should not happen since in this case the algorithm makes no progress.\n\n3. In Appendix A, the authors make two assumptions in (13) and (14). However, it remains unclear whether these two assumptions can be satisfied simultaneously. In particular, does the stationary point in (14) satisfies the sufficient decrease in (13)?\n\n4. I think eq (20) is not correct. The term $\\sqrt{\\lambda_t}c$ should be $c/\\lambda_t$. As the theoretical results depend on this inequality, the results are not correct.\n\n5. In Assumption 3, the authors assume the updates lie in a compact set. This can be only guaranteed if you impose a constraint on the space. However, the constraint would make the stationarity in (14) no longer hold. \n\n6. In Theorem 1, the equation is not complete.\n\n7. In eq (10), $\\alpha$ should be $\\alpha_t$", "extra_scores": {}, "extra_text": {}}, {"review_id": "buj5oICT9QC", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the stochastic proximal point algorithm for solving nonconvex nonlinear least squares optimization problems. A linearization strategy is used to accelerate the procedure and in each iteration the algorithm works by solving a linear system. Some convergence analysis for the proposed is present. Some experiments have been conducted.\n\nI have the following comments.\n1. In the proposed algorithm, the authors only take one example instead of a batch of training examples to construct the gradient. This strategy often results in much large variance and slow convergence in practice.\n\n2. The results in Proposition 1 does not imply the convergence of the algorithm. The theoretical analysis is incremental. \n\n3. The numerical comparisons are not sufficient.  The authors should include the comparisons with state-of-the-art second-order optimization solver such as K-FAC.\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "1VbaktTPQzJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper revisits the stochastic proximal point algorithm (SPPA) and apply SPPA to solve nonconvex optimization problems with efficient subproblem solvers.\n\nFirstly, there is a work [Chen et. al 2020] which also provides the convergence result of SPPA on manifold problem and it is not the weakly convex setting.\n\nSecondly, the convergence rate of SPPA is 1/epsilon^2, which is the same as SGD. Regarding the convergence result, there is no advantage of SPPA against SGD and the author should have a discussion about this. The convergence rate is asymptotic and this paper does not point out which iteration we should use as the final output.\n\nThirdly, the convergence analysis is rather standard and lack of novelty. Moreover, the convergence result of Gauss-Newton and L-BFGS to solve the proximal subproblem should also be provided. Since the main concern for PPA-type method lies on the convergence behavior and efficiency to solve the proximal subproblem. Furthermore, in the experiment part, the comparison of running time between SPPA and SGD, ADAM, Adagrad should also be provided. \n\nLastly, I wonder whether the assumption 1 is reasonable, since I have not seen this assumption in other nonconvex stochastic programming papers. Authors should remark on this assumption and it would be better to put some references on this.\n\n\nConfidence level: 5, abusolutely certain.\n\nRating: reject\n\nreferences:\n[1] Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning.\nShixiang Chen, Zengde Deng, Shiqian Ma, Anthony Man-Cho So.  arXiv preprint arXiv:2005.02356, 2020.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommend rejection: concerns were raised in terms of technical correctness, quality of presentation and the quality of experiments. There was no rebuttal. The AC agrees with the reviewers and recommends rejection.
Decision: Reject