SOREL: A Stochastic Algorithm for Spectral Risks Minimization

Authors: Yuze Ge, Rujun Jiang
Primary area: optimization
Keywords: spectral risk, conditional Value-at-Risk, stochastic optimization, convex optimization, fair machine learning

Abstract:
The spectral risk has wide applications in machine learning, especially in real-world decision-making, where people are concerned with more than just average model performance. By assigning different weights to the losses of different sample points, rather than the same weights as in the empirical risk, it allows the model's performance to lie between the average performance and the worst-case performance. In this paper, we propose SOREL, the first stochastic gradient-based algorithm with convergence guarantees for spectral risks minimization. Previous approaches often rely on smoothing the spectral risk by adding a strongly concave function, thereby lacking convergence guarantees for the original spectral risk.  We theoretically prove that our algorithm achieves a near-optimal rate of $\widetilde{O}(1/\sqrt{\epsilon})$ to obtain an $\epsilon$-optimal solution in terms $\epsilon$. Experiments on real datasets show that our algorithm outperforms existing ones in most cases, both in terms of runtime and sample complexity.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730373113734

thread_type:
official_review

<thread_object>
creator: reviewer_tvdg

<content>
summary:
This paper introduces SOREL, a stochastic gradient-based algorithm for spectral risk minimisation. After an introduction and an overview of this work, the authors carefully present the current drawbacks of current approaches of spectral risk minimisation alongside their new algorithm in Section 3. Section 4 provide convergence guarantees, and Section 5 gathers various experiments showing competitive performance and computational time with respect to existing methods.

strengths:
- Sections 1, 2 and 3.1 are truly well-written, it has been a pleasure to read it
- The idea of using a primal dual method based on Lemma 1 of (Blondel et al. 2020) is clever and elegant
- Algorithmic performances are convincing and are accompanied by sound theory
- It is great to propose a mini batching version of SOREL

weaknesses:
See Questions part

questions:
- You wrote in your abstract that there is a lack of guarantees for the original spectral risk. You said later in l.78 that SOREL is the first stochastic algorithm with convergence guarantees for the spectral risk minimisation problem. However, in Section 3.1 you directly consider a regularised version of the spectral risk with a strongly convex function (Eq. 1). Later, in Eq. (4) you added another regulariser in $\mathbf{\lambda}$ to avoid huge variations of $\lambda$ during the learning process. All of these reason suggests that you actually do NOT deal with the original spectral risk. Do I miss something?
- l. 268-269 : Those lines are unclear, I do not under whether there is a need to compute $\mathcal{O}(n\log(n))$ operations at line 5, within the loop of line 3 in Algorithm 1 or if this is the total number of computations. Can you explicitly write the time complexity of your algorithm and compare it with those proposed in literature? This would draw a useful theoretical link to understand why your algorithm is faster than others in Section 5.
- I am not sure to understand why Lemma 1 is stated here, as there is no proof sketch in the main document. What do I miss?
- In Theorem 1, can you please define $w^*$? I do not understand what it is.
- In Section 5, it seems that you focused exclusively on linear regression, would SOREL work with small neural nets with 1-2 hidden layers? Even if theoretical guarantees may not hold anymore, I am curious to know whether the methods remain tractable and efficient.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730622355243

thread_type:
official_review

<thread_object>
creator: reviewer_ynq6

<content>
summary:
The paper presents SOREL, an optimization algorithm designed for spectral risk measure objectives, which can also be understood as  primal-dual min-max objectives for learning problems. In comparison to previous stochastic methods, the algorithm adds a proximal term to the dual update and claims a near-optimal convergence guarantee for the strongly convex-(nonstrongly) concave variant of this objective. The method employs an SVRG-style variance reduction similar to [Mehta et al. (2023)](https://proceedings.mlr.press/v206/mehta23b.html). While SOREL generally performs favorably in experiments, the theoretical convergence analysis is incorrect, making this work unpublishable in its current state.

strengths:
- The paper points out an important fact about the analysis of algorithms for "smoothed" spectral risk measures, which is that when the smoothing parameter $\nu = O(\epsilon)$, it should be included in the complexity guarantee, making "linearly convergent" methods sublinear for the original non-smooth problem.
- By using the experimental benchmark of [Mehta et al. (2024)](https://arxiv.org/pdf/2310.13863), the authors are able to perform head-to-head comparisons to  recent algorithms designed for spectral risk measures (Figure 3).  The empirical performance is competitive with, and often outperforms, other methods.
- The exposition is clear and well-written, although some sections are nearly identical to sections in the referenced work on spectral risk measure optimization with stochastic algorithms (Section 1, Section 2, Appx B).

weaknesses:
Upon viewing Corollary 1, we see that the complexity contains the term $\log(\frac{\sqrt{n}G}{\mu^2\sqrt{\epsilon}})$, i.e. a logarithm is taken for a quantity that is *not* unitless. This does not pass a basic sanity check for convergence analyses in optimization theory: that the complexity does not depend on the units of the input. The error comes from the fact that the precision parameter $\delta_k$ in the inner loop is dependent on the strong convexity parameter $\mu$ (units of loss/inputs$^2$) when it should be in units of loss (based on Lemma 3). To see why this is invalid, recall that an optimization algorithm should not change its exact complexity when the inputs are reparametrized in different units. Consider the objective as a function of $\boldsymbol{w}/10$ instead of $\boldsymbol{w}$. Then, we have the Lipschitz and strong convexity constants change as $G \mapsto 10G$ and $\mu \mapsto 100\mu$. Then,
$$
\frac{\sqrt{n}(10G)}{(100\mu)^2\sqrt{\epsilon}} = \frac{1}{1000}\frac{\sqrt{n}G}{\mu^2\sqrt{\epsilon}}.
$$
This indicates that the number of iterations in the inner loop would change based on the scale, which is not a valid analysis. Please check the units before presenting the result.

Matters such as significance, novelty, and impact come second to the analysis, especially as the experimental results do not show a large practical improvement over the methods of [Mehta et al. (2023)](https://proceedings.mlr.press/v206/mehta23b.html) and [Mehta et al. (2024)](https://arxiv.org/pdf/2310.13863). Please correct the analysis.

questions:
n/a
</content>
</thread_object>

</thread>
<thread>
creation date:
1730664349216

thread_type:
official_review

<thread_object>
creator: reviewer_fkff

<content>
summary:
This paper considers the problem of optimization in *spectral risk minimization*, which aims to produce more risk-sensitive models than standard ERM.  More precisely, spectral risk is defined as a weighted empirical risk minimization problem, where the weights depend on the order statistics of a given empirical sample, thereby subsuming both empirical risk (with all weights being the same) and such risk-sensitive measures as CVaR and Extremiles.  While minimizing spectral risk can be attractive due to the risk-sensitivity, it can be challenging to scale as the evaluation of the spectral risk of a given parameter depends on the entire dataset through the order statistics and is thus not amenable to naive applications of existing SGD approaches.  In particular, in order to obtain an unbiased estimate of the subgradient of the loss, all samples must have losses evaluated.  The authors circumvent this problem by applying the rearrangement inequality to reduce the problem to finding the value of a min-max game and then propose applying what amounts to a regularized form of projected gradient ascent-descent with momentum.  The authors present rates on their algorithm that are close to earlier lower bounds and conclude the paper with a number of experiments with ridge regression on a variety of instantiations of spectral risks and datasets, demonstrating that their approach is generally superior to alternatives.

strengths:
This paper sets out an interesting problem that has some (at least distant) applications to relevant areas in ML including risk sensitivity, fairness, and generalization OOD.  The proposed solution of reducing to a minimax game and then running a primal-dual algorithm is interesting and the empirical validation uses a reasonable diversity of datasets and loss functions that suffices to convince me that the proposed algorithm is superior to alternatives, at least when considering ridge regression.

weaknesses:
There are several main weaknesses with the paper:

1. With respect to the theory, I think more discussion of the strongly convex regularizer is necessary.  I understand that it is necessary in order to ensure identifiability, but I find the discussion under Corollary 1 confusing.  For example, in the comparison to related work, the authors cite several works that set the regularization term to be $O(\epsilon)$ in order to be $\epsilon$-suboptimal with respect to the unregularized solution and note that this leads to a worse sample complexity of $O(1/\epsilon)$; I am confused as to why the current proposal does not suffer the same drawback.  Indeed, in order to be $\epsilon$-suboptimal with respect to the unperturbed spectral risk, it seeems as if the bound in Corollary 1 would scale with $\epsilon^{-3/2}$ which is obviously worse than the alternative.

2. I think a more thorough discussion of the computational complexity of SOREL is in order.  While I understand that for most steps, the gradient updates are cheap and independent of $n$, lines 2, 7, and 11 of Algorithm 1 require linear in the number of samples time.  The authors claim that these steps are for variance reduction, but do not investigate the necessity thereof.  Another way of saying this is that the authors claim almost optimality of their algorithm in how the iteration complexity scales with $\epsilon$ but it seems like the dependence on $n$ is also fairly important (and is what motivates the study itself) and the extent to which the authors' algorithm is optimal in this respect is left largely undiscussed.

3. The experiments are all restricted to linear models.  While I understand that the authors wish to ensure that their key Assumption 1 is satisfied, it would be nice if they considered something nonlinear as well.  This is especially true because they remove the regularization in their experiments anyhow and thus are at least somewhat happy to depart from their theory.

questions:
1. Can you define `total sample complexity' in Corollary 1 please?  Is this the sum of calls to a stochastic gradient oracle?  It would be helpful if this were made rigorous as my understanding of the key contribution of the present work is that the dependence in complexity on the number of samples is reduced substantially.

2. See weaknesses 1 and 2.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730680995436

thread_type:
official_review

<thread_object>
creator: reviewer_cggb

<content>
summary:
This paper proposes a stochastic algorithm for spectral risk minimization with trajectory stabilization for the primal variable. It is claimed that their approach enjoys a near-optimal rate of convergence that matches the known lower bound. They also demonstrate that this method outperforms existing baselines in various experimental settings.

strengths:
This paper is well-written and easy to follow. The claimed contribution is interesting to the community. However, I have a major concern regarding its correctness which I elaborate on in the next section.

weaknesses:
I didn't read the proofs closely but the main theorem seems to be incorrect by a sanity check. To be more specific, $\mu$ is in unit loss/par^2 and $\delta_k$ is in unit loss, but $\delta_k \sim \mu$ in Theorem 1. Moreover, $G$ is in unit loss/par and $\epsilon$ is in unit par^2, so $G/(\mu \sqrt{\epsilon})$ is unitless. However, there is $\log{(G/(\mu^2 \sqrt{\epsilon}))}$ in the sample complexity given in Cor. 1 which makes it not unitless.

Other comments:
1. I do not see error bars (standard errors) reported in all the experiments. Are these results based on a single run or multiple independent runs? Can you report error bars so that we can tell how significant the improvements are?
2. $w^*$ is not defined in Theorem 1.

questions:
See the section above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732458023328

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We thank all the reviewers for their constructive and insightful comments and appreciate the time spent on our manuscript. As the discussion stage is nearing its end, we kindly request the reviewers to take some time to review and respond to our rebuttal. We summarize the modifications in our revised manuscript as follows.

- We have corrected Theorem 1 and Corollary 1 to ensure that the complexity in Corollary 1 is unitless. We also revised the corresponding proofs in Appendix A.
- We presented the error bars for the experiments in Section 5 in Appendix E, as suggested by reviewer CGGB.
- In response to reviewers fKff and TvDg's concerns about SOREL's performance in optimizing nonlinear models, we presented the experimental results for training two-layer neural networks in Appendix F.
- We further discussed the dependence of the complexity in Corollary 1 on $n$ in Appendix G, as suggested by reviewers fKff and TvDg.
- We added the definition of $\boldsymbol{w}^\star$ in Theorem 1.
- We revised Appendix B to reduce redundancy with [1], as our experimental setup mainly follows the setup in [1].

A major concern raised by multiple reviewers is that the complexity in Corollary 1 is not unitless. We have corrected this issue in our revised manuscript. 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. 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. 

We thank all the reviewers again for their insightful feedback. If the reviewers have any further questions or concerns about our work, we are more than happy to provide any clarification.

**Reference**

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

</thread>
<thread>
creation date:
1733076250429

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thank you for your feedback

comment:
We would like to express our deepest gratitude to all the reviewers for their acknowledgment of our paper and constructive comments. In particular, we appreciate reviewers CGGB and YNq6 for pointing out that the complexity in Corollary 1 of our initial manuscript was not unitless, and reviewers fKff and TvDg for highlighting the importance of discussing the overall time complexity and the complexity with respect to the sample size $n$.  This has greatly helped us improve our manuscript. Below, we summarize the main concerns raised by the reviewers and how we addressed them.

- Reviewers  CGGB and YNq6 pointed out that the complexity in Corollary 1 of our initial manuscript was not unitless. We clarified that this error was due to an improper use of the inequality at line 803, and that our initial proof was mathematically correct. We have corrected the result and the reviewers have confirmed our result.
- Reviewers fKff and TvDg raised concerns regarding the strongly convex regularizer and whether we are solving the original spectral risk minimization problem. We clarified that the strongly convex regularizer is a regularization term on the model parameters, and that our approach does not involve smoothing the original spectral risk by adding a strongly concave term with respect to $\boldsymbol{\lambda}$, as in some other methods. We have clarified the potential confusion that may arise between the regularizer on the model parameters and the strongly concave term with respect to $\boldsymbol{\lambda}$.
- Reviewers fKff and TvDg raised concerns about the overall time complexity of our method and the complexity with respect to $n$. We further discussed this in Appendix G of our revised manuscript. Our method also has advantages in complexity with respect to the sample size $n$.
- Reviewers fKff and TvDg asked about the performance of our algorithm in the case of nonlinear models or non-convex situations. We presented the experimental results for training two-layer neural networks in Appendix F. Our method achieves significantly lower losses compared to other baselines, even though none of the algorithms have theoretical guarantees.
- Reviewer CGGB pointed out that our experiments in Section 5 lack error bars. We presented the error bars in Appendix E.

We are confident that we have addressed all the reviewers' concerns. The reviewers also acknowledged the presentation of our paper and its contribution to the community. Again, we greatly thank all the reviewers for their constructive comments and the discussions with us.  We hope that the rebuttal phase can be informative for all reviewers.
</content>
</thread_object>

</thread>


Metareview:
metareview:
An algorithm called SOREL is proposed for spectral risk minimization, with convergence analysis for convex losses together with a strongly convex regularization. Experiments was limited to linear models in the original submission, but additional ones with nonlinear models are conducted during the discussion. Revision should include the corrected proof and additional experiments.