SOREL: A Stochastic Algorithm for Spectral Risks Minimization

4. Definition of $\boldsymbol{w}^\star$

We apologize for not formally defining $\boldsymbol{w}^\star$. $\boldsymbol{w}^\star$ should be defined as the optimal solution to Eq. (1). Since the objective function in Eq. (1) is strongly convex under Assumption 1, $\boldsymbol{w}^\star$ is unique. We have added this definition to Theorem 1 in the revised manuscript.

5. Training small neural nets

We train a two-layer neural network with ReLU activation function. We conduct experiments on the same regression task as in Section 5.1, on the energy and concrete real-world datasets. Detailed experimental results are presented in Appendix F of our revised manuscript. Here, we report the mean losses and standard deviations (in parentheses) over the last ten passes. We observe that our method outperforms other baselines, especially on the energy dataset, where our method achieves significantly lower losses, even though none of the four algorithms have theoretical guarantees.

Energy

Concrete

References

[1] Nesterov, Yu. "Smooth minimization of non-smooth functions." Mathematical programming 103 (2005): 127-152.

[2] Mehta, Ronak, et al. "Stochastic optimization for spectral risk measures." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

We thank reviewer TvDg for the constructive feedback.

1. Not deal with the original spectral risk

In Eq. (1), $g(\boldsymbol{w})$ represents the regularizer on the model parameters. In Eq. (2), we present the equivalent form of the original spectral risk as $R_{\boldsymbol{\sigma}}(\boldsymbol{w})=\max_{\boldsymbol{\lambda} \in \Pi_{\boldsymbol{\sigma}}} \sum_{i=1}^n \lambda_i \ell_i(\boldsymbol{w})$. In lines 340-342 and 127-130, we point out that other methods smooth the original spectral risk by adding a strongly concave term with respect to $\boldsymbol{\lambda}$. Specifically, the smoothed spectral risk can be expressed as: $\tilde{R}\_{\boldsymbol{\sigma}}(\boldsymbol{w})=\max_{\boldsymbol{\lambda} \in \Pi_{\boldsymbol{\sigma}}} \sum_{i=1}^{n} \lambda_i \ell_i(\boldsymbol{w})-\nu\Omega(\boldsymbol{\lambda})$, where $-\nu\Omega(\boldsymbol{\lambda})$ is a strongly concave function with respect to $\boldsymbol{\lambda}$, and $\nu>0$. $\tilde{R}_{\boldsymbol{\sigma}}(\boldsymbol{w})$ is differentiable with respect to $\boldsymbol{w}$ [1], and by setting $\nu=O(\epsilon)$, the gap between the original spectral risk and the smoothed spectral risk does not exceed $\epsilon$.

Therefore, in Eq. (1), we consider the original spectral risk. Eq. (1) can be viewed as minimizing the spectral risk with a regularization term on the model parameters, such as the L2 regularization. If we set $\sigma_i=1/n$, Eq. (1) simplifies to minimizing the empirical risk plus a regularization term on the model parameters.

In Section 3.1, we explain that our algorithm can be viewed as iteratively solving Eq. (4) and Eq. (5). Therefore, Eq. (4) is merely a subproblem that needs to be solved during the execution of Algorithm 1. Algorithm 1 is still aimed at solving Eq. (1).

We apologize for the confusion that may arise between the regularizer on the model parameter and the strong concave term with respect to $\boldsymbol{\lambda}$. We will include the formulation of the smoothed spectral risk in our paper to eliminate ambiguity.

2. Total time complexity

As mentioned in Section 3.1, our algorithm can be seen as alternately solving Eq. (4) and Eq. (5). Solving Eq. (4) involves computing the projection onto the permutahedron $\Pi_{\boldsymbol{\sigma}}$, which can be done in $O(n\log n)$ time. Line 5 of Algorithm 1 is inside the outer loop in Line 3, so the total time complexity requires an additional $O(Kn\log n)$, where $K$ is given in Corollary 1 as $K=O\left(\frac{\sqrt{n} G}{\mu \sqrt{\epsilon}}\right)$. Therefore, the total complexity of our algorithm with respect to $n$ and $\epsilon$ is $\tilde{O}(n^{3/2}/\sqrt{\epsilon})$.

Next, we compare this complexity with baselines in Section 5. SGD has been shown to fail to converge to the optimal solution of the spectral risk minimization problem, and LSVRG only guarantees convergence for $\nu \geq \Omega\left(n G^2 / \mu\right)$ [2]. For Prospect, for any $\epsilon > 0$, the sample complexity to achieve an $O(\epsilon)$ optimal solution is $\tilde{O}(n/\epsilon^3)$ or $\tilde{O}(n^2/\epsilon^2)$ (depending on the size of $\epsilon$). However, Prospect requires solving a projection problem similar to Eq. (4) at each step, so the total time complexity is $\tilde{O}(n^2/\epsilon^3)$ or $\tilde{O}(n^3/\epsilon^2)$.

We thank the reviewer for highlighting the importance of the total time complexity and the complexity with respect to $n$. We will include this discussion in our paper.

3. Understanding Lemma 1

We apologize for the confusion caused here. A key idea of our proof is that $L\left(\boldsymbol{w}, \boldsymbol{\lambda}^{\star}\right) \geq L\left(\boldsymbol{w}^{\star}, \boldsymbol{\lambda}\right)$ for any $\boldsymbol{w} \in \mathbb{R}^d$ and $\boldsymbol{\lambda} \in \Pi_{\boldsymbol{\sigma}}$, where $\boldsymbol{w}^\star$ and $\boldsymbol{\lambda}^\star$ are an optimal solution to Eq. (3). Indeed, we know that $L\left(\boldsymbol{w}^{\star}, \boldsymbol{\lambda}^{\star}\right)=\max_{\boldsymbol{\lambda} \in \Pi_\sigma} L\left(\boldsymbol{w}^{\star}, \boldsymbol{\lambda}\right) \geq L\left(\boldsymbol{w}^{\star}, \boldsymbol{\lambda}\right)$ and $L\left(\boldsymbol{w}, \boldsymbol{\lambda}^{\star}\right) \geq L\left(\boldsymbol{w}^{\star}, \boldsymbol{\lambda}^{\star}\right)=\min _{\boldsymbol{w}} L\left(\boldsymbol{w}, \boldsymbol{\lambda}^{\star}\right)$. Thus, as mentioned before Theorem 1 in Section 4, we can choose appropriate parameters of Algorithm 1 such that the adjacent terms indexed by $k$ on the right-hand side of Eq. (6) can be canceled out during summation, and the left-hand side of Eq. (6) is always greater than or equal to 0.

Due to space limits, we did not include this idea in the main text. We will adjust the content of Section 4 in future revisions to make the theoretical analysis more readable.

3. Similarity to referenced work

We appreciate the reviewer's recognition of our paper's presentation in the Strengths section, and we thank the reviewer for pointing out the similarity in writing between our work and some referenced work.

Here we would like to clarify some portions that may be similar to referenced work. Since spectral risk measures are not yet widely known in the machine learning field, introducing them from the perspective of the empirical risk is natural and intuitive. This perspective of introduction is similar across works related to the spectral risk research. Additionally, we have elaborated on our research motivation in detail in Section 1.

In Section 2, we review the existing work from the perspective of the spectral risk measure, particularly focusing on deterministic and stochastic methods for solving the spectral risk minimization problem. We also specifically highlight and analyze the shortcomings of existing stochastic algorithms: their lack of convergence guarantees for the original spectral risk minimization problem. Our introduction to the applications of spectral risks may be similar to some references. But we interpret these applications from a unified perspective of spectral risks.

We elaborate on the experimental details in Appendix B. Since we follow the same experimental setup as [1] in Section 5.1, we describe the experimental setup of [1] in Appendix B. We have revised Appendix B to reduce redundancy with the experimental setup in [1].

References

[1] Mehta, Ronak, et al. "Distributionally robust optimization with bias and variance reduction." The Twelfth International Conference on Learning Representations, abs/2310.13863, 2024.

We thank reviewer YNq6 for the thoughtful feedback, especially for pointing out that the complexity in Corollary 1 includes units.

1. Complexity not unitless

We acknowledge that the complexity in Corollary 1 is not unitless.

We point out that the unit in the complexity arises from the use of the inequality $2\left(\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)^{\frac{1}{2}} \leq \left(1+\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)$ in the proof of Lemma 2 at line 803. While this inequality is mathematically correct, it results in inconsistent units on both sides of the inequality. To ensure consistent units, we simply need to modify the inequality to $2\left(\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)^{\frac{1}{2}} \leq \left(D+D^{-1}\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)$, where $D=G/\mu$. Next, we only need to adjust the coefficients of the affected terms in our analysis and set $\tilde{\delta}_k=D^2\delta_k$ in Theorem 1, where $\delta_k=\min \left(\frac{\mu}{8(k+5)}, \mu(k+1)^{-6}\right)$ is the parameter used in Theorem 1 when we obtained the complexity with units. This allows us to obtain the unitless complexity $O\left(\frac{n^{\frac{3}{2}} G}{\mu \sqrt{\epsilon}} \log \frac{\sqrt{n}}{G \sqrt{\epsilon}}+\frac{L}{\mu} \log \frac{\sqrt{n}}{G \sqrt{\epsilon}} \log \frac{\sqrt{n} G}{\mu \sqrt{\epsilon}}\right)$. Note that the numerator in $\log \frac{\sqrt{n}}{G \sqrt{\epsilon}}$ implicitly includes units of loss. Indeed, the modified precision parameter $\tilde{\delta}_k$ in the inner loop is in units of loss.

We have uploaded a revised version of the manuscript and corrected our analysis, including Theorem 1 and Corollary 1 in the main text, as well as the proof in Appendix 1. The changes are highlighted in blue. We emphasize that our proof before modification is mathematically correct. To obtain a unitless complexity, we only need to adjust the coefficients of certain terms, and our analysis remains valid.

2. No large practical improvements in experimental results

We state that our main contribution is the proposal of the first stochastic algorithm for solving the original spectral risk minimization problem, achieving a near-optimal complexity with respect to $\epsilon$. The convergence of SGD and LSVRG lacks theoretical guarantees. In our experiments, we primarily focus on the performance of the algorithm during the training process, rather than pursuing state-of-the-art test metrics. In the experiments, SOREL successfully converges to the true optimal solution under various spectral risk settings, with optimal or near-optimal runtime. This aligns with the discussions with reviewer TvDg and reviewer fKff, where we point out that SOREL also has advantages in complexity with respect to the sample size $n$.

Additionally, following the suggestions of reviewer fKff and reviewer TvDg, we train a two-layer neural network under the experimental setup of Section 5.1. Detailed experimental results are presented in Appendix F of our revised manuscript. Here, we report the mean losses and standard deviations (in parentheses) over the last ten passes. We observe that our method outperforms other baselines, especially on the energy dataset, where our method achieves significantly lower losses, even though none of the four algorithms have theoretical guarantees.

Energy

Concrete

Thank you for your hard work and revision in the rebuttal period. I have raised my score to recommend acceptance.

We appreciate the comments provided by reviewer CGGB, especially for pointing out that the complexity in Corollary 1 includes units.

1. Complexity not unitless

We acknowledge that the complexity in Corollary 1 is not unitless.

We point out that the unit in the complexity arises from the use of the inequality $2\left(\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)^{\frac{1}{2}} \leq \left(1+\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)$ in the proof of Lemma 2 at line 803. While this inequality is mathematically correct, it results in inconsistent units on both sides of the inequality. To ensure consistent units, we simply need to modify the inequality to $2\left(\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)^{\frac{1}{2}} \leq \left(D+D^{-1}\mathbb{E}\|\boldsymbol{x}-\overline{\boldsymbol{x}}\|^2\right)$, where $D=G/\mu$. Next, we only need to adjust the coefficients of the affected terms in our analysis and set $\tilde{\delta}_k=D^2\delta_k$ in Theorem 1, where $\delta_k=\min \left(\frac{\mu}{8(k+5)}, \mu(k+1)^{-6}\right)$ is the parameter used in Theorem 1 when we obtained the complexity with units. This allows us to obtain the unitless complexity $O\left(\frac{n^{\frac{3}{2}} G}{\mu \sqrt{\epsilon}} \log \frac{\sqrt{n}}{G \sqrt{\epsilon}}+\frac{L}{\mu} \log \frac{\sqrt{n}}{G \sqrt{\epsilon}} \log \frac{\sqrt{n} G}{\mu \sqrt{\epsilon}}\right)$. Note that the numerator in $\log \frac{\sqrt{n}}{G \sqrt{\epsilon}}$ implicitly includes units of loss. To verify its correctness, as pointed out by reviewer YNq6, $\delta_k$ should be in units of loss (based on Lemma 3). Indeed, $\tilde{\delta}_k$ is in units of loss.

We have uploaded a revised version of the manuscript and corrected our analysis, including Theorem 1 and Corollary 1 in the main text, as well as the proof in Appendix 1. The changes are highlighted in blue. We emphasize that our proof before modification is mathematically correct. To obtain a unitless complexity, we only need to adjust the coefficients of certain terms, and our analysis remains valid.

2. Reporting error bars

In Appendix E of the revised manuscript, we provide the error bars for the experiments in Section 5.

Specifically, Figure 7 shows the mean training curves and standard deviations of algorithms with minibatching in the linear regression experiments. Since our plots are in log scale, we only keep the upper error bar to make the plots easier to read. Table 4 presents the fairness metrics and their standard deviations from the experiments in Section 5.2. Figure 8 shows the mean training curves, mean worst classification error, and error bars from the experiments in Section 5.3.

We observe that the standard deviations of the fairness metrics in the experiments in Section 5.2 is relatively large. This is because we adopted 5-fold cross-validation, as suggested by [1]. Tables 5-7 and Tables 8-10 present the fairness metrics and suboptimality for each fold of the data. The standard deviations of fairness metrics and suboptimality within each fold is very small, indicating that the standard deviations of results in Section 5.2 mainly stems from differences between folds, rather than the randomness of the algorithms.

We thank the reviewer for highlighting the importance of reporting error bars, and we will integrate these results into the experiments in Section 5.

3. Definition of $\boldsymbol{w}^\star$

We apologize for not formally defining $\boldsymbol{w}^\star$. $\boldsymbol{w}^\star$ should be defined as the optimal solution to Eq. (1). Since the objective function in Eq. (1) is strongly convex under Assumption 1, $\boldsymbol{w}^\star$ is unique. We have added this definition to Theorem 1 in the revised manuscript.

References

[1] Ding, Frances, et al. "Retiring adult: New datasets for fair machine learning." Advances in neural information processing systems 34 (2021): 6478-6490.

3. Experiments restricted to linear models

As mentioned earlier, our method does not require adding a regularization term with respect to $\boldsymbol{\lambda}$ to the objective function. We dropped the strongly concave term $-\nu\Omega(\boldsymbol{\lambda})$ required by the LSVRG and Prospect, as they have been observed to exhibit linear convergence for the original spectral risk minimization problem in practice even without it [3]. Please let us know if we have misunderstood anything.

For nonlinear models, we train a two-layer neural network with ReLU activation function. We perform experiments on the same regression task as in Section 5.1, on the energy and concrete real-world datasets. Detailed experimental results are presented in Appendix F of our revised manuscript. Here, we present the mean losses and standard deviations (in parentheses) over the last ten passes of the training process. We find that SOREL outperforms other baselines, particularly on the energy dataset, where our method achieves significantly lower losses, even though none of the four algorithms have theoretical guarantees.

Energy

Concrete

4. Definition of `total sample complexity'

Total sample complexity refers to the total number of samples used in Algorithm 1. The complexity of the gradient evaluation is the same as the complexity presented in Corollary 1. Indeed, in lines 8-15 of Algorithm 1, for every $m_k$ updates of $\boldsymbol{w}$, $(n + m_k)$ samples are required, as well as $(n + m_k)$ gradient evaluations (if $\nabla\ell_1(\bar{\boldsymbol{w}}), \ldots, \nabla\ell_n(\bar{\boldsymbol{w}})$ are stored) or $(n + 2m_k)$ gradient evaluations (if $\nabla\ell_1(\bar{\boldsymbol{w}}), \ldots, \nabla\ell_n(\bar{\boldsymbol{w}})$ are not stored).

References

[1] Nesterov, Yu. "Smooth minimization of non-smooth functions." Mathematical programming 103 (2005): 127-152.

[2] Mehta, Ronak, et al. "Stochastic optimization for spectral risk measures." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[3] Mehta, Ronak, et al. "Distributionally robust optimization with bias and variance reduction." The Twelfth International Conference on Learning Representations, abs/2310.13863, 2024.

We are grateful for the diligent efforts of reviewer fKff in evaluating our paper and for the constructive feedback provided.

1. Discussion of the strongly convex regularizer

In Lines 340-342 and 127-130, we claim that other methods smooth the original spectral risk by adding a strongly concave term with a coefficient $\nu$ with respect to $\boldsymbol{\lambda}$. Specifically, the original spectral risk can be expressed as Eq. (2): $R_{\boldsymbol{\sigma}}(\boldsymbol{w})=\max_{\boldsymbol{\lambda} \in \Pi_{\boldsymbol{\sigma}}} \sum_{i=1}^n \lambda_i \ell_i(\boldsymbol{w})$.

The smoothed spectral risk can be expressed as: $\tilde{R}\_{\boldsymbol{\sigma}}(\boldsymbol{w})=\max_{\boldsymbol{\lambda} \in \Pi_{\boldsymbol{\sigma}}} \sum_{i=1}^{n} \lambda_i \ell_i(\boldsymbol{w})-\nu\Omega(\boldsymbol{\lambda})$ , where $-\nu\Omega(\boldsymbol{\lambda})$ is a strongly concave function with respect to $\boldsymbol{\lambda}$ and $\nu>0$. $\tilde{R}_{\boldsymbol{\sigma}}(\boldsymbol{w})$ is differentiable with respect to $\boldsymbol{w}$ [1], and by setting $\nu=O(\epsilon)$, the gap between the original spectral risk and the smoothed spectral risk does not exceed $\epsilon$. However, our method does not smooth the original spectral risk, and therefore, $\nu$ does not appear in our iteration complexity.

$\mu$ is the strong convexity coefficient of the regularizer $g$ on the model parameters. In this paper, we consider minimizing the spectral risk with a regularizer (Eq. (1)), similar to minimizing the empirical risk with a regularizer.

We apologize for the confusion that may arise between the regularizer on the model parameter and the strong concave term with respect to $\boldsymbol{\lambda}$. We will include the formulation of the smoothed spectral risk in our paper to eliminate ambiguity.

2. Discussion of the computational complexity of SOREL

In Eq.(3), we adopt a minimax reformulation and solve Eq. (1) by alternately solving Eq. (4) and Eq. (5). In line 2 of Algorithm 1, we update $\boldsymbol{\lambda}$, which requires $O(n\log n)$ time. In lines 7 and 11 of Algorithm 1, we use variance reduction techniques to accelerate the solution of Eq. (5). As a result, the subproblem Eq. (5) converges linearly. However, this makes the complexity linearly dependent on $n$. In other words, we trade off complexity with respect to $\epsilon$ for complexity with respect to $n$. The $\sqrt{n}$ term originates from Assumption 1, where we assume $\ell_i$ is $G$ Lipschitz continuous. Therefore, $\boldsymbol{\ell}$ is $\sqrt{n}G$ Lipschitz continuous.

Here, we discuss the complexity of baselines in Section 5 with respect to $n$ and $\epsilon$. SGD has been shown to fail to converge to the optimal solution of the spectral risk minimization problem, while LSVRG only guarantees convergence for $\nu \geq \Omega\left(n G^2 / \mu\right)$ [2]. For Prospect, by setting $\nu = O(\epsilon)$, we obtain its sample complexity with respect to $n$ and $\epsilon$ as $\tilde{O}(n^2/\epsilon^2)$ or $\tilde{O}(n/\epsilon^3)$ (depending on the size of $\epsilon$). This is similar to our case, where there is a tradeoff between complexity in $n$ and $\epsilon$.

Moreover, as mentioned in Section 5.1 and in the response to reviewer TvDg, Prospect requires solving a projection problem similar to Eq. (4) at each step, which takes $O(n\log n)$ time. Therefore, its total time complexity is $\tilde{O}(n^2/\epsilon^3)$ or $\tilde{O}(n^3/\epsilon^2)$. Note that SOREL solves Eq. (4) only once in each outer loop. Therefore, the total time complexity of SOREL requires an additional $O(Kn\log n)$, where $K=O\left(\frac{\sqrt{n} G}{\mu \sqrt{\epsilon}}\right)$ as stated in Corollary 1. Thus, the total time complexity of SOREL is $\tilde{O}(n^{3/2}/\sqrt{\epsilon})$.

We thank the reviewer for pointing out the importance of $n$ in the complexity analysis, and we will include this discussion in our paper.