Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions

We thank the reviewer for the positive comments and feedback on our paper.

Q1: Clarification of theoretical contribution within a novel setting.

A. We proposed a unified framework of analysis for non-smooth DWC and WCSC min-max problems, which leads to single-loop methods that achieves the best convergence rate. Our main contribution is the novel analysis that applies to problems with complex structures (difference of max-structured weakly convex functions) and potential non-smoothness. In particular, in our technical analysis, the Lemma 4.4 is novel, which does not exist in any existing work. This make its possible for us to prove the convergence of a special error function $\|x_\phi^t - prox_{\gamma\phi}(x_{t-1})\|^2 + \|x_\psi^t - prox_{\gamma\psi}(x_{t-1})\|^2 + \|\nabla F_{\gamma}(x_t)\|^2$.

Q2: Confusion about the complexity as a contribution (Line 59) for WCSC problems.

A: We are sorry for the confusion. For WCSC problem, we did not intend to claim a better complexity, but rather emphasize that it is the first single-loop method with the same complexity as existing double-loop methods. The improved complexity of our algorithm lies at its application to difference-of-weakly convex functions, which can be seen from Table 1.

Q3: Does the proof and algorithmic technique employed in this study resemble SBCD?

Response. NO. The main difference between the analysis of SMAG and SBCD is in the error bounds $E\|x_\phi^{t+1} - prox_{\gamma \Phi}(x_t)\|^2$ and $E\|x_\psi^{t+1} - prox_{\gamma \Psi}(x_t)\|^2$. For SBCD, they use inner loops to solve for $prox_{\gamma \Phi}(x_t)$ and $prox_{\gamma \Psi}(x_t)$. In order to reach error bounds $E\|x_\phi^{t+1} - prox_{\gamma \Phi}(x_t)\|^2 \leq O(\frac{1}{t+1})$ and $E\|x_\psi^{t+1} - prox_{\gamma \Psi}(x_t)\|^2 \leq O(\frac{1}{t+1})$ at iteration $t$, they need to use $O(t^2)$ inner loop iterations because of the involved maximization. With $O(\epsilon^{-2})$ outer iterations guarantees a nearly $\epsilon$-critical point, it leads to a total sample complexity of $O(\epsilon^{-6})$. In contrast, our analysis directly builds the recursion for $\|x_\phi^{t+1} - prox_{\gamma \Phi}(x_t)\|^2 + \|y_{t+1} - y^*(prox_{\gamma\phi}(x_{t}))\|^2$ in Lemma 4.4. In addition, we introduce a special potential function $P_t$ as in Eq. (23). We are able to build a decreasing recursion in terms of $P_t$, i.e., $P_{t+1}$ in the left, and $(1-\beta)P_t$ in the right of the bound (cf line 541), where $\beta<1$. These make it possible for us to prove a better convergence rate of a special error function $E[\|x_\phi^t - prox_{\gamma\phi}(x_{t-1})\|^2 + \|x_\psi^t - prox_{\gamma\psi}(x_{t-1})\|^2 + \|\nabla F_{\gamma}(x_t)\|^2]$ for a randomly chosen $t$.

Q4. Misunderstanding about the hinge loss (Line 271) as a smooth function. About the large variance in training curves observed, such as in FER 2013 (Figure 1).

A. The hinge loss is in the form of $\ell(x,y) = \max(0, 1- y * f(x))$ where $x,y$ are the data sample and its label, and $f(x)$ is the prediction score of the sample $x$. This clearly is a non-smooth loss due to the presence of the function $\max(0, \cdot)$. Regarding the variance in the training curves: (i) the large variance of our method for FER2013 is due to a bug in the code, which loads a wrong file of one trial result for plotting. A corrected training curve of our method is included in the attached PDF file of the global rebuttal. It has much smaller variances. (ii) We have also incldued the means and standard deviations of our method on all datasets for references in the attached PDF file. It can be seen that the standard deviations are indeed one order smaller than the loss values. Please also note that the scale of the y-axis is very small, which makes the std more obvious. (iii) We have conducted hyperparameter tuning as stated in lines 283-289. Thank you!

We thank the reviewer for the positive comments and feedback on our paper.

Q: The special structure of the difference of convex functions is not used.

A: Thank you for your good question. (1) In this paper the problem considered is the Difference of Max-Structured Weakly Convex Functions (DMax) Optimization, which is more general than the difference of convex functions due to the maximization structure in the two component functions. Hence, we cannot use some technique like linearization of the second component as in previous work on solving difference-of-convex functions. (2) We do utilize the difference structure to some degree. In particular, we apply Moreau envelope smoothing to each component separately instead of jointly. It is notable that even each component is weakly convex, their difference is not necessarily weakly convex. Hence, applying Moreau envelope smoothing to the joint function would not make sense. (3) For the difference of weakly-convex functions problem (DWC), we have summarized its existing works in Table 1. To the best of our knowledge, our proposed method is the first single-loop stochastic methods and it achieves the best convergence rate $O(\epsilon^{-4})$.

We thank the reviewer for the positive comments and feedback on our paper.

Q1. The authors should distinguish if the difference/improvement from previous work are "double loop vs single loop", and/or faster rates and/or weaker assumptions. For the DWC setting, it seems it is "double loop vs single loop", and/or faster rates and weaker assumptions, where as for WCSC, it is "double loop vs single loop".

A: The improvement over baselines can be seen from the difference in terms of assumptions, complexity and number of loops in Table 1 and Table 2. For the DWC setting, our improvement over SDCA [25] lies at weaker assumption and single loop, over SSDC-X lies at weaker assumption, faster rate and single loop, over SBCD lies at faster rate and single loop. In the WCSC setting, our improvement over PG-SMD/Epoch-GDA lies at single loop, over SAPD+ lies at weaker assumption and single loop, and over StocAGDA lies at weaker assumption.

Q2. The authors should mention the notion of optimalities in various settings (nearly critical and near stationarity) eraly on, and remark that they are standard.

A: Thank you the suggestion. We will revise our draft accordingly.

Q3. Are the proof ideas useful to give single loop algorithms for non-smooth convex minimization via Moreau smoothing, with optimal rates?

A: Thanks for the good question! We have not explored the non-smooth convex minimization via Moreau smoothing. It might be useful in the sense that our technique can be used to argue that with one step update of $x_t'$ for solving $\min_{x'}f(x') + \frac{1}{2\gamma}\|x_t - x'\|^2$, we can establish recursion of $|x'_t -$

$prox_{\gamma f}(x_t)\|^2$, where $prox_{\gamma f}(x_t)$ is the optimal solution to $\min_{x}f(x') + \frac{1}{2\gamma}\|x_t - x'\|^2$. This is the error of gradient estimator of the function $F_{\gamma}(x_t) = \min_{x}f(x') + \frac{1}{2\gamma}\|x_t - x'\|^2$. For deep analysis, we will leave it as a future work.

Q4. Is the $O(\epsilon^{-4})$ rate achieved optimal in these settings?

Response. We believe so. $O(\epsilon^{-4})$ rate has been proved to the optimal even in the smooth setting for non-convex optimization [r1].

Reference.

[r1]: Arjevani et al. Lower bounds for non-convex stochastic optimization. 2019.

We thank the reviewer for the positive comments and feedback on our paper.

Q1. There are some typos that may affect readability

A: Thank you for pointing out these typos. We will fix them in our revision.

Q2. Are there examples that DMax gives more applications beyond DWC and min-max optimization?

A: One example can be found in [43] for optimizing partial AUC in a range of false positive rates for binary classification. The objective can be written as $\sum_{i=1}^{N^+}\phi_{n}(s_{i}) - \phi_m(s_{i})$, where $s_i=(s_{i1},\ldots, s_{iN^-})$ denotes the pairwise loss between a positive data $x_i$ and all $N^-$ negative samples, and $\phi_n$ is the an operator that outputs the sum of the top-$n$ items in the input vector. Since $\phi_{n}(s_{i}) =\max_{p_j\geq 0, \sum p_j = n}p_j s_{ij}$, as a result, $\phi_{n}(s_{i}) - \phi_m(s_{i})$ is a structure of DMax.

Q3: About the technical novelty.

A: It is true that single-loop updates can give the same rate for strongly-concave problems compared to double-loop algorithms that first solve the inner-problems to a required accuracy. However, existing single-loop algorithms for min-max problems all require smoothness of the objective function. In our work, we did not use the smoothness assumption in terms of $x$ and hence the analysis is completely different. In terms of technical analysis, the Lemma 4.4 is novel, which does not exist in any existing work. In addition, we introduce a special potential function $P_t$ as in Eq. (23). These make it possible for us to prove the convergence of a special error function $E[\|x_\phi^t - prox_{\gamma\phi}(x_{t-1})\|^2 + \|x_\psi^t - prox_{\gamma\psi}(x_{t-1})\|^2+ \|\nabla F_{\gamma}(x_t)\|^2]\leq \epsilon$ for a randomly chosen $t$.