SOREL: A Stochastic Algorithm for Spectral Risks Minimization
Authors: Yuze Ge
Rujun Jiang
Venue: ICLR 2025 Poster (2025)
Keywords: spectral risk
conditional Value-at-Risk
stochastic optimization
convex optimization
fair machine learning
Primary area: optimization

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.

Published as a conference paper at ICLR 2025
SOREL: A STOCHASTIC ALGORITHM FOR SPECTRAL RISKS MINIMIZATION
Yuze Ge & Rujun Jiang
School of Data Science, Fudan University yzge23em. fudan. edu. on rj rijiange fudan. edu.cn
ABSTRACT
The spectral risk has wide applications in machine learning, especially in real- world making, where people are concemed with more than just average model performance. By assigning different weights to the losses of different sam- ple points, rather than the same weights as in the empirical risk, it allows the model's performance
between the average performance and the worst-case performance. In this paper, we propose SOREL, the first stochastic gradient- algorithm with convergence guarantees for spectral risks minimization. Previous approaches often rely on smoothing the spectral risk by adding strongly concave function, thereby lacking convergence guarantees for the original spectral risk. We theoretically prove that our algorithm achieves near-optimal rate of ((1/VE) to obtain an e-optimal solution in terms e. Experiments on real datasets show that our algorithm outperforms existing ones in most cases, both in terms of runtime and sample complexity.
INTRODUCTION
In modern machine learning, model training heavily relies minimizing the empirical risk. This ensures that the model have high average performance. Given training set of n sample points D = [ X, the goal of the empirical risk minimization is to solve
min R(w) = - Σ (ww) 1=1
Here, E Rd is the parameter vector of the model, (=(w) l(w, æ;,) is the loss of the i-th sample, and l Idd x X' + R is the loss function. However, as machine learning models are deployed in real-world scenarios, the evaluation metrics for these models become more diverse, including factors such as fairness or risk aversion.
In this paper, we consider generalized aggregation loss function: the spectral risk, which is of the form
R (www)= = Σ (w))).
Here E(p()) S ... 5. (mn(()) denotes the order statistics of the empirical loss distribution, and 0 S 1. In form, the spectral risk penalizes the occurrence of extreme
σi .... on, Ei= losses by assigning greater weights to extreme losses. When o, = 1/n,, the spectral risk reduces and
to the empirical risk. When on the maximum loss. Therefore, the spectral risk measures the model's performance between the average case and the worst case. By assigning different values a, the spectral risk encompasses a wide range of aggregated loss functions that have broad applications in fields such as machine learning and finance. Common spectral risks include Conditional Value Risk (CVaR) or the average of top-k loss (Artzner) 1997;; Rockafellar & Uryasev 2000), Exponential Spectral Risk Measure (ESRM) (Cotter & Dowd] (006),, and Extremal Spectral Risk (Extremile) (Daouia et al. 2019). Their specific forms are shown in Table [ MeMhta et al. 2022).
0 for 1,...
1, the spectral risk becomes
RRjun Jiang the corresponding author.

---

Published as a conference paper at ICLR 2025
Table 1:
Different spectral risks and the corresponding weights.
Spectral Risks
Parameter
i [n(1 - aa]
no
a-CVaR
0<a<l
no
nn(1 a)] < i [m(1 - a)]
otherwise
p-ESRM
p>
e
a
-1--
r-Extremile
r
(4)
Despite the broad applications of spectral risks, optimization methods for spectral risks are still limited. In particular, for large-scale optimization problems, there is currently a lack of stochastic algorithms with convergence guarantees for the spectral risk minimization. Indeed, the weight of each sample point depends the entire training set, introducing complex dependencies and thus making the optimization process challenging. Existing algorithms either abandon the convergence guarantee the minimum of the spectral risk problem due to the difficulty of obtaining unbiased subgradient estimates (Levy et al.) 2020: Kawaguchi & Lu 2020), or turn to optimize the smooth regularized spectral risk (Mehta al., 2024b 2022), which lacks convergence guarantees for the original spectral risk. Given the widespread application of the spectral risk in machine learning and the lack of stochastic algorithms for the spectral risk minimization, we are committed to developing stochastic algorithms with convergence guarantees for the spectral risk minimization.
Our Contributions. this paper, we propose the Stochastic Optimizer for Spectral Risks mini- mization with trajectory Stabilization (SOREL). i) We propose SOREL, the first stochastic algorithm with convergence guarantees for the spectral risk minimization problem. In particular, SOREL sta- bilizes the trajectory of the primal variable the optimal point. ii) Theoretically,
prove that obtain an e-optimal solution in terms of the squared distance to the optimal point for spectral risks with a strongly convex regularizer. This matches the known lower bound of 12 in the deterministic setting (Ouyang & Xu (022). iii) Experimentally, SOREL outperforms existing baselines in most cases, both in terms of runtime and sample complexity.
SOREL achieves near-optimal rate of ((I/Ve)
RELATED WORK
Statistical Properties of the Spectral Risk. As a type of risk measures, the spectral risk assigns higher weights the tail distribution and has been profoundly studied in the financial field (Artzner
ct al. 1999 Rockafellar & Uryasev 2013 He et al. 2022). Recently, statistical properties of the spectral risk have been investigated by many works in the field of learning theory. Specifically, Mehta al. (2022); y; A. & Bhat (2022) demonstrate that the discrete form of spectral risks converges to the spectral risk of the overall distribution, controlled by the Wasserstein distance. [Hollnd & Haress (2022): Khim et al. (2020); Holland & Haress (202]) also consider the learning bounds of spectral risks.
Applications. The spectral risk is widely applied in various fields of finance and machine learn- ing. In some real-world tasks, the worst-case loss is as important as the average-case loss, such as medical imaging (Xu et al., (022) or roboties (Sharma al., 20200. The spectral risk minimization can be viewed as risk-averse learning strategy. In the domain of fair machine learning, different subgroups are classified by sensitive features (c.g., gender and race). Subgroups with higher losses may be treated unfairly in decision-making By penalizing samples with higher losses, the model's performance across different subgroups can meet certain fairness criteria (Williamson & Menon 2019), such demographic parity (Dwork et al.) 2012) and equalized odds (Hardt et al.) (006)). In the field of distributionally robust optimization (DRO), the sample distribution may deviate from uniform distribution, which can be modeled by reweighting the samples (Chen & Paschalidis
2

---

Published as a conference paper at ICLR 2025
2020). Mehta et al. (2024) adopts the spectral risk measures the uncertainty set of the shifted distribution, which is similar to the form of the spectral risk minimization.
In practical applications, people can choose different types of spectral risks based on actual needs. For example, CVaR is popular in the context of portfolio optimization (Rockafellar Uryasev
2000), as well reinforcement learning (Zhang al. 2024 Chow et al. 2017). Levy et al. (2020) uses the CVaR measure as the uncertainty set in DRO, resulting in the same loss function as the spectral risk. Other applications of spectral risks include reducing test errors and mitigating the impact of outliers (Maurer et al. 2021
Kawaguchi & Lu
2020
Fan et al. 2017 to name a few.
Existing Optimization Methods. There have been many algorithms to optimize CVaR, a special case of spectral risks, including both deterministic (Rockafellar & Uryasev] (2000) and stochastic algorithms (Fan al. 2017; Curi et al., 2020). For the spectral risk, deterministic methods such as subgradient methods have convergence guarantees, although they are considered algorithms with slow convergence rate. Xiao et al. (2023) propose an Alternating Direction Method of Multipliers (ADMM) type method for the minimization of the rank-based loss, inspired by Cui et al. (2024). Other deterministic methods reformulate this problem into a minimax problem (Thekumparampil et al. 2019; Hamedani & Aybat, 20211; Khalafi & Boob] 2023). However, these methods require calculating (n) function values and gradients at each iteration, posing significant limitations when solving scage-scale problems.
Stochastic algorithms for solving the spectral risk minimization problems are still limited. Some al- gorithms forgo convergence the true minimum of the spectral risk (Levy et al. 2020: Kawaguchi
& Lu 2020). Other methods modify the objective to minimize a smooth approximation of the spec- tral risk by adding strongly concave term with coefficient (Mehta et al.) 2022] 2024b). The
smaller v is, the closer the approximation is to the original spectral risk. Mehta et al. (2024b) propose the Prospect algorithm and prove that it achieves linear convergence for any v >> O. Furthermore, if the loss of each sample is different at the optimal point, then the optimal value of the smooth approx- imation of the spectral risk the same as the optimal value of the original spectral risk as long as is below certain positive threshold. However, in practice, these conditions are difficult to verify. The convergence of these algorithms still lacks guarantees for original spectral risks minimization. Other stochastic algorithms, including /Hamedani & Jalilzadeh] (2023); Yan et al. (2019), designed for solving general minimax problems, have a slower convergence rate O(1/e) terms of to obtain an e-optimal solution.
After our original submission of this work we have also recently become aware that Mehta et al. (2024a) proposed primal-dual stochastic algorithm to solve the DRO problem. Moreover, their algorithm can also be improved to minimize the original spectral risk, even though their convergence analysis focuses the smoothed spectral risk. We discuss this in Appendix Fin detail.
3 ALGORITHM
We consider stochastic optimization of the spectral risk combined with a strongly convex regularizer:
min
o, (.ga +g(w).
(1)
Ra (w=)
Firstly, we make the basic assumption about the individual loss function E, and the regularizer g.
Assumption
The individual loss function l, Rd R. is convex, G- G-Lipschitz continuous and L-
smooth for all i E nt).. The regularizer RRd + R U {oo} is proper, lower semicontinuous and p-strongly convex.
Assumption i is a standard assumption the literature on stochastic optimization (Nemirovski et al. 2009; Davis & Drusvyatskiy 2019). especially in the field of the spectral risk minimiza- tion (Kawauuchi & Lu| 2020; Holland & Haress 2022 Levy et al. 2020 Mehta et al.) 2022 2024b). The logistic loss satisfies this assumption. The least-square loss satisfies this assumption as long as the iterative sequence lies in a bounded sublevel set. The assumption of strong convexity of g is very common, for example, the la regularization is widely used in machine learning.
3

---

Published as a conference paper at ICLR 2025
3.1 CHALLENGES OF STOCHASTIC OPTIMIZATION FOR SPECTRAL RISKS
In this section, we describe the challenges of the spectral risk minimization problem and the tech- niques to solve them.
Biases of Stochastic Subgradient Estimators. From convex analysis 10), we know that the subgradient of Ro is
WWang et al. 2023 Lemma
(w) = Conv { No, (. (x(n(()) S.... .... La(n)
where Conv denotes the convex hull of set, and π is permutation that arranges f en in ascending order. Note that R. (w) non-smooth, Indeed, when there exist i + j such that e (,()) e (w), 0R (w) contains multiple elements.
The subgradient dient estimator of OR, if we use only mini-batch with m (m < n) sample points. For example, when m = 1, we randomly sample uniformly from .1.....7). The subgradient estimator V& unbiased only if o; 1/n. For general σ, unfortunately, to obtain timator of 2R,, we have to compute n loss function values and then determine the ranking of l, among the losses (or the weight corresponding (nn) losses at each step is computationally heavy. To remedy this, we next design an algorithm that first uses minimax reformulation of Problem (I) and then alternately updates the weights of each sample point and w using primal-dual method.
Rs is related to the ordering of f,,... We cannot obtain an unbiased subgra-
unbiased subgradient
the i-th sample point). However, computing
Equivalently, we can rewrite Ro (w) in the following form
(w) = -mxx Σ (,)( XETI ==1
where 11, = (llo 111 1, 1.11 [0, 1| is the permutahedron associated with or, ie., the convex hull of all permutations of a, and 1 the all-one vector (Blondel et al. 2020). Then Problem { can be rewritten
min max L(w, A) = Σ (w)) + g(w).
(3)
w XEll,
Next, primal-dual method to solve Problem A:
Specifically, we iteratively update and
A++1 arg max XEIL,
Xcl((wk))
a| Atel?
(4)
277
Wh++1 arg minPa
Ax.411 (e + g(w)
1/0
wxll?
(5)
2Tk
Steps (4 and 5 be seen alternatingyy solving the min problem and the max problem in with proximal terms.
Stabilizing the Optimization Trajectory. To update A one may naturally think of solving
Problem (2): As++1 = arg maxxeнi, Σt= (wx), similar to methods in Mehta et al. (2022 2024b) with smoothing coefficient v/ 0. However, since Problem (2) merely convex. the solution
A lacks continuity with respect to w, that is, a small change in could lead to large change in
A. Indeed, it is often the case that there are multiple optimal solutions for (2) when there exists
i * j such that (w)) = (w)), and in this case, an arbitrary small perturbation of ur will lead to different value of X; As shown in Figure [ this can cause w to oscillate near points where some losses are the same and prevents the convergence of the algorithm. We also provide a toy example in Appendix further illustrate this difficulty, Therefore, the proximal term 2m ||> As [2 is added
I
in (4) to prevent excessive changes in À and stabilize the trajectory the primal variable, where
m 0 controls the extent of its variation.
4

---

Published as a conference paper at ICLR 2025
Trajectoyy atailizttion
Trajctoory bibiiaaaion
Figure I: The level set plot of 2D least-square regression with primal-dual optimization trajectories described in Section 3.1] The max subproblem does not have a proximal term (left) or has proximal term (right). The min subproblem does not have proximal term. The black star represents the optimal point. The sample points are obtained by projecting the yacht dataset onto IR² using PCA.
Stochastic Optimization for the Primal Variable. We use a stochastic algorithm to approxi- mately solve (5) Through the minimax reformulation in (5), we avoid directly calculating the stochastic subgradient of Ro (w), which requires computing all loss function values to obtain the corresponding sample weight X;- Additionally, since X is fixed, the finite sum part of the ob- jective function in ( smooth, allowing us to use variance reduction (VR), commonly used technique in stochastic optimization (Shalev-Shwartz & Zhang 2013] Roux et al. [012 Johnson & contrast, since Ro ()) non-smooth, previously mentioned, VR cannot be used to directly solve Problem (I) For smooth convex functions in the form of the finite sum, many methods such as SVRG (Johnson &
Zhang 2013 Defazio al. 2014), accelerate our stochastic algorithm.
Zhang 2013), SAGA (Defazio al. 2014), and SARAH (Nguyen et al. (0017) enable stochastic methods to achieve the convergence rate of deterministic methods. We apply the proximal stochas-
tic gradient descent with generalized VR method inspired by SVRG approximately solve (5), which will be presented in Section 3.2 in detail. Thanks to its strong convexity, Problem (5) can be solved efficiently.
Similar to 4 we add proximal term 27c 11w 2 where TH >> O is the proximal parameter. The proximal parameter ты is crucial for the convergence proof of our algorithm. By carefully choosing Th (l/k)), the updates of become more stringent the algorithm progresses, and SOREL can achieve a near optimal rate Ö(1/VE) in terms of
3.2 THE SOREL ALGORITHM
Our proposed algorithm SOREL summarized in Algorithm T The specific values for the param- eters lk. MJs, тą and m& in Algorithm 1 will be given in Section In Line 2 algorithm initializes An by solving Problem (2) In Lines 8 15 the algorithm computes the stochastic gradient and update Additionally, we compute the full gradient of every my updates to reduce the variance. In Lines 45 we update A. Note that we replace (xwx)) with (s(w))) + 0% (L,)w))= (wx-1)) to accelerate the algorithm. This can be seen as a momentum term, a widely used technique in smooth optimization (Tseng) 1998] Liu et al. (2020) Gitman et al.) 2019 Sutskever et al. (013),, where 0₂
w for fixed X, described in Section 3.1
the momentum parameter.
Define the proximal operator prox, (#) == arg min h(x)) + 2 || - æ|| for function h. In Line 15 we apply the proximal stochastic gradient descent step. We assume that p b (-) easy to compute, which the case for many commonly used regularizers g, such as the 4 norm and the elastic net regularization (Zou & Hastie, (005). If is differentiable, we can replace the proximal stochastic gradient with stochastic gradient: Wk,t+1 = Wk.t
(de, (Wxk we) + Vg(wk.)) This will not affect the convergence or convergence rate
of the algorithm long Vg is Lipschitz continuous and the step size is small enough. In Line [5] we need to compute the projection onto II,- For an ordered vector, projecting onto the permuta- hedron takes (nn) operations using the Pool Adjacent Violators Algorithm (PAVA)(Lin) & Wright
5

---

Published as a conference paper at ICLR 2025
2016). In SOREL, need first sort elements of the projected vector and then compute the projection onto IIg. which takes a total of On log n) operations.
In practice, set 73 and my to in Lines 8 and meaning the algorithm updates À once it traverses the training set. We also set the reference point w and the output wk-1 in Lines [T0 and 17 to be the last vector of the previous epoch rather than the average vector, with most practical algorithms (Johnson & Zhang, 2013 Zhu & Hazan 2016 CCukkosky & Orabonal 2019] (Babanezhad aaaal,2011 2015 Gower al. | 2020). In this way, SOREL only requires computing the full batch gradient once for each update of X, and becomes single-loop in Lines 8 [6 This makes the algorithm more concise and parameters easier to tune. Additionally, in the Appendix D
we provide the SOREL
algorithm with mini- mini-batching.
Algorithm SOREL
1: Input: initial wp: w-1
wo. o, and learning rate a, (0x) (m)) {T
(m²) K-1 K-1 and [Tx] km
K-1
2: An = arg minxen. -L(wo) TA
3: for k = O..... K do
4:
2k = (1 (x)((())) - 0nL (1)
5:
A&+1 arg minxell, U2 X + 2nk || 1+112.
6:
Wk.0 wk. v = Wk.
7:
g Σ うー 1 (w)
8:
for / = 1, 1,... T3 do
9:
if l moo m 0 then
10:
10
m Wkj"
11:
9 EE A (l(
12:
end
Sample i, uniformly from {1, [1,...,9. nn),
14:
du,t = n4 Vl,, (Wk,e) - k+1 Vl, (w) + Wk.1+1 Prox (1+ (1 12) (wk. ad ).
16:
end for
Wk+11 m. Th
-i=li-ma+] Wket
end for
19: Output: WK.
4 THEORETICAL ANALYSIS
For convenience, consider that Tik (will be determined in Theorem D is large enough so that wP is a 6y-optimal solution of P& (w), that is, E& Px(W))+1) min (x(w) I &g- Here, E, represents the conditional expectation with respect the random sample points used to compute Wx-1 given Wh .... Wo. Then, we can provide a one-step analysis of the outer loop of SOREL. We use L(w, A) X ((w) + g(w) in the analysis for simplicity. The envergence analysis for SOREL with mini- bani-batchhng is presented in Appendix D
Lemma Suppose Assumption holds. Let {ark) and {Ax) be the sequences generated by Algo- Then for any w Rd AE 1l and D G/p, the following inequality holds,
rithm 1
Es (L(wk+1, 2) - L(w, At+1)}
<E () Abt1, ((wb+1)) + 2m7.
||| - ARll - || A 112 - || - Ao
1
[1| w//ll 12 -- -1/w- Wk+all 11 | w 11 [|w w6+1112 (6)
+
2Tk
(T + +1)8x
+ (Ux, A - A) Sx +
(D -1 ||u wh+1 D)
2

---

Published as a conference paper at ICLR 2025
Next, try to telescope the terms the right hand side of O by multiplying each term by Y By choosing appropriate parameters in Algorithm to satisfy some conditions (will be discussed in Appendix A). we can ensure that the adjacent terms indexed by l o..... K 1 can be canceled out during summation. Then we can achieve the desired convergence result.
Theorem Suppose Assumption
1 holds.
Ser 7/k k +
=
m(k+1) SnG
0%
k41
k
M[++I) 5x D min and Tę Omm log 86
B(K+5]- lu(k + 1)- D G/u,, the step-size a 12L. my
381L
[K+5)
in Algorithm / Let un be the optimal solution of Problem nCa N2R2
1 Then we
have EI|WK w0 =0
Corollary Under the same conditions in Theorem 7 we obtain an output wx of Algorithm 7 such
that B| wk w' 112 in a total sample complexity of O nna uyl
log 1 (log 2)²
Our algorithm achieves near-optimal convergence rate of ((1/Vo) in terms of 6, which matches the lower bound of S2(1/ /c) in the deterministic setting up to logarithmic term (Ouyang & Xu 2021]. This the first near-optimal stochastic method for solving the spectral risk minimization problem. Previously, Mehta et al.) (2022) 2024b) add a strongly concave term with respect to X in L(w, A) and achieve a linear convergence rate for the perturbed problem. One may set the coefficient of the strongly concave term v to O(e), obtaining an e-optimal solution for the original spectral risk minimization problem. However, this approach has drawbacks: it leads to a worse sample complexity of Ö(1/e) (Palaniappan & Bach, 2016) or even ((1/E") (Mehta et al. 2024b); additionally, achieve an c-optimal solution, the step size would need to be set to O(c), resulting in very small steps that perform poorly in practice. In contrast, SOREL's ' step size is independent of e. We also discuss the dependence of complexity on n in Appendix
5 EXPERIMENTS
In this section, we compare our proposed algorithm SOREL with existing baselines for solving the spectral risk minimization problem. In addition to the precision of the optimizers during training, also explore fairness and distribution shift metrics on the test set. We focus more on the performance of an optimizer during the training process; therefore, do not pursue state-of-the-art test metrics due to potential overfitting issues.
We train linear models with l2 regularization in all experiments. We adopt a wide variety of spectral risks, including ESRM, Extremile, and CVaR. Baseline methods include SGD (Mehta et al. 2022) with a minibatch size of 64, LSVRG [Mehta et al. 2022), and Prospect (Mehta al. (024b). Note that although both LSVRG and Prospect add strongly concave term with coefficient to smooth the original spectral risk, they have been observed to exhibit linear convergence for the original spectral risk minimization problem in practice without the strongly concave term (Mehta et al. 2022 2024b). Consequently, we set / = 0 our experiments. Detailed experimental settings are provided in Appendix B The source code is available at https:://gi t/ubbbb...ttttu.. com SXtp///XXXXXXII
5.1
LEAST-SQUARES REGRESSION
Five tabular regression benchmarks are used for the least squares loss: yacht Tsanas & Xi-
fara 2012), energy (Baressi Segota et al. 2019), concrete (Yeh) 2006), k kin&m (Akujuobi & Zhang (017)) , power (Tüfekei|20144 We compare the suboptimality versus passes (the number
of samples divided by n) and runtime. The suboptimality is defined as
Ror (wxx + g g(wx) - Ro (w=) - g(ww))
Suboptimality(mn)))
Rs (wo) g(w)) Ro (w=) )(w))*
where wn is calculated by L-BFGS (Nocedal & Wright 1999)
7

---

Published as conference paper at ICLR 2025
10
32
yacht
10-3
33-14
10.
10-1
16-7
22
22
10-1
334
00"1
3311
10-1-
22
10.1
50
100
160
10-1
33.1
enerey
22-1
10t1
10-0
12:11
32-1
10
10
12
10
33-1
32-1
30
22.4
100
107
concrete
10-11
23"1
10.1
10-1
10-7
33-1
10'5
Mywwm
20.1
33.1
100
16.0
104
10"
32-1
10- 9--
Win8mm
22-1
10-4
10-1
33-1
22
10.
35m
40
166
26
66
161
20
1.67
16'
10
32
Dower
10me
10-h
32
10-1
12-4
40
11a
46
1.2 Time
20
16"
10
Passes
Passes
Passes
Time
SGD
LSVRG
Prospect
SOREL
Figure 2: Suboptimality of spectral risks for different algorithms without mini-batching. The x- axis represents the effective number of samples used by the algorithm divided by (odd columns) or CPU time (even columns), Each row corresponds to the same dataset, and each column corresponds the same type of the spectral risk.
Results. Figure Souure@compe compares the training curves of our method with other baselines across various datasets and the spectral risk settings. In terms of sample complexity and runtime, SOREL outper- forms other baselines most cases; SOREL also achieve comparable results in the kin8nm dataset. In the power dataset, the sample complexity of Prospect is better than that of SOREL. However, the runtime of SOREL is significantly shorter than that Prospect due to the fact that Prospect needs the calculation of projections onto the permutahedron with (n) operations each step. As expected, SGD fails to converge due to its inherent bias (Mehta et al.) 2022 Although Mehta et al.) (2024b) discusses the equivalence of minimizing the smoothed spectral risk and the original spectral risk when losses at the optimal point are different from each other, we find that LSVRG and Prospect of- In contrast, SOREL converges to the true optimal point in all settings (suboptimality less than 0 means the solution's 's accuracy higher than L.BFGS).
fail reach the true optimal point, indicating limitations of these methods.
5.2 FAIR MACHINE LEARNING
In this experiment, we explore the role of the spectral risks in enhancing fairness machine learning, as studied in Williamson & Menon (2019). We use the 1 law and acs datasets. 1aw refers to the Law School Admissions Council's National Longitudinal Bar Passage Study, which is used for the regression task of predicting student's GPA (Wightman 1998). acs is derived from US Census surveys, which is used for the classification task of predicting whether an adult is employed (Ding et al. 202T All algorithm implemented using mini-batching in this experiment.
8

---

Published as a conference paper at ICLR 2025
Assume source distribution (Y, where Y is the true label, X represents the available fea- tures, and A E (0. 1) is the binary sensitive attribute. Let Ý f(X, A) be the model's prediction. For binary classification problems, we consider the fairness metric of Equal Opportunity (EO) de- fined by
EO P( 1 = 1 - P( = -
For regression tasks, we consider the absolute mean difference (SMD) as the fairness metric defined by
SMD E
A- - -
A A-
+ E
y
A
-E
Intuitively, if the EO and SMD are close the model does not discriminate with respect A. In both datasets, we set race as the sensitive attribute.
Results. Tables 2 shows the results of using different spectral risks on the acs and law datasets, respectively. ERM represents the empirical risk. We find that using spectral risks instead of the em- pirical risk does improve the fairness metries of the model, and in most cases, a lower suboptimality indicates better fairness of the model. In the acs classification task, SOREL significantly outper- forms other algorithms in terms of both fairness metrics and suboptimality. For ESRM, SOREL's suboptimality surpasses that of L-BFGS, while the fairness metric of SGD is worse than the baseline under the ERM setting, possibly due to poor performance of SGD when optimizing the objective function. Additionally, CVaR and Extremile are more effective at reducing EO, compared to Ex- tremile. In the 1 aw regression task, there is no significant difference in SMD improvement among LSVRG, Prospect, and SOREL,, but all perform better than SGD. However, SOREL achieves the lowest suboptimality, and its suboptimality is lower than that of L-BFGS under both the ESRM and Extremile settings. Furthermore, training curves in Appendix B show that SOREL can reach low suboptimality in the shortest amount of time.
Table 2: Results of different algorithms on acs and law. The values in the ERM row represent the mean fairnes metries (values closer to 0 indicate better fairness) the test set. The first to third rows for each spectral risk (except ERM) represent, respectively: the mean fairness metrics on the test set, relative fairness metric improvements (%) from ERM, and training suboptimality.
Datasets
acs
law
ERM
0.02092
0.05188
SGD
LSVRG
Prospect
SOREL
SGD
LSVRG
Prospect
SOREL
0.00645
0.00816 16
0.00634
0,00551
0.04019
0.03896
0.03893
0.03890
CVaR
69.17
60.99
69 69
73.66
22.53
24.90
24.96
25.02
4.29c-4
7.23c-4
2.12c-4
2.31e-6
3.80c-3
5.88c-3
6.71c-4
2.95e-5
0.02469
0.01842
0.01840
0.01770
0.04184
0.04122
0.04123
0.04123
ESRM
11.95
12.05
15,39
19.35
20.55
20.53
20.53
1.47e-3
3.33e-4
4.38e-6
-2.38e-8
7.60e-4
1.13e.4
1.52e-7
-1.13e-7
0.00424
0.00377
0.00237
0.00130
0.04416
0.04377
0,04380
0.04381
Extremile
79.73
81.98
88.67
93.97
15.63
15.57
15.56
5.11e-3
7.90e-3
6.69e-4
1.14e-4
1.63e-4
6.14e-4
8.14e-6
-2.12e-7
5.3
GENERALIZATION
In this subsection, we explore the role of the spectral risk in enhancing model robustness under distribution shift. We use CVaR and Extremile as the spectral risks. Levy al. (2020) uses the CVaR measure as the uncertainty set, and their optimization problem is the same as the spectral risk minimization problem (T) that uses CVaR as the spectral risk. We use the amazon dataset preprocessed by Mehta et al. (2024b) for the multi-class classification task, which consists of feature representations generated by BERT (Devlin et al.) 2019) from the original dataset. amazon refers to the Amazon Reviews dataset (Ni et al.) 2019), which includes textual reviews of products along with their corresponding ratings from one to five, with different reviewers for the training and test sets. We evaluate the worst group classification error (Sagawa et al. 2020) the test set. Each group is classified based on the true labels. All algorithm are implemented using mini-batching in this experiment.
We also explore the impact of distribution shift on fairness metrics in Section 5.2 In Ding et al. 2021), it is observed that training and testing on different states lead to unpredictable results. We use

---

Published as a conference paper at ICLR 2025
data from California the training data and train models using ERM and CVaR loss functions, respectively. We then test the models on four other states.
Results. Figure 3 shows the results of using CV&R and Extremile spectral risks ama SOREL achieves the best worst group classification error in both settings. For CVaR, under similar suboptimality, SOREL reaches the minimum worst group classification error, indicating better gen- eralization performance. Moreover, SOREL the only algorithm that can converge to the true op- timal solution under the CVaR setting. Additionally, SOREL demonstrates optimal near-optimal convergence rates in both spectral risk settings.
Figure shows the results of models tested on four other states. The circles represent model's per- formance in California (in-distribution). Models' performance in other states cottoo-ddsstrbutiin is indeed hard to predict. Notably, models trained with ERM often fail meet the expected fairness metrics in other states. However, models trained with CVaR often achieves higher test accuracy and better fairness metrics. Moreover, the models trained with SOREL achieve the best or nearly the best EO and test accuracy.
CVWR
CVWR
Extremile
Extremile
5,770
10'
Worse Groupp Emuur
0.530
10:1
Group Emor
2,785
Suteptmmaity
Sckeptimallty
20-2
20
0,700
20-1
20-4
10-4
10-1
10-1
22"
104
10
963
Prctect
SORT!
10-1
10)
30
500
(5V66 Proszeet
SOKEI
Time (5)
Time
Prospect
Figure 3: Training curves and worst group classification errors of different algorithms on the ama zon dataset. The suboptimality at the 500 pass (where we evaluate the worst group er- ror) is marked on the training curves. The training curves are extended to illustrate convergence.
0.10
of of oporniiks
0.26
0.20
4
Accursoy
Figure 4: Model performance under geographic distribution shift. The models are trained on the state CA and tested on other states. Dots of different colors (except black) represent the results of using different optimization algorithms to solve the CVaR minimization problem. Baseline refers to the results using ERM as the loss function.
CONCLUSION
We have proposed SOREL, the first stochastic algorithm with convergence guarantees for the spec- tral risk minimization problems. We have proved that SOREL achieves a near-optimal rate of Ó(I/VC). In experiments, SOREL outperforms existing baselines in terms of sample complexity and runtime in most cases.
Future work includes exploring convergence of SOREL for nonconvex problems, and investigating broader applications of the spectral risk in areas such as faimess and distributionally robust opti- mization.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGEMENTS
This work was partly supported by the National Key R&D Program of China under grant 2023YFA 1009300, National Natural Science Foundation of China under grants 12171100 and the Major Program of NESC (72394360,723393344))
REFERENCES
Prashanth L. A. and Sanjay Bhat. A Wasserstein Distance Approach for Concentration of Empir- ical Risk Estimates. Journal of Machine Learning Research (JMLR), 23:238:1-238.0 2022.
Uchenna Akujuobi and Xiangliang Zhang. Delve: A Dataset-Driven Scholarly Search and Analysis System. SIGKDD Explorations, 19(2)36-46, 2017.
Philippe Artzner. Thinking coherently. Risk, 10:68-71, 1997.
Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, and David Heath. Coherent measures of risk. Mathematical finance, 933):233-228 1999.
Reza Babanezhad, Mohamed Osama Ahmed, Alim Virani, Mark Schmidt, Jakub Konecný, and Scott Sallinen. Stopwasting My Gradients: Practical SVRG. In Conference on Neural Information Processing Systems (NeurIPS), pp. 2251-2259, 2015.
Sandi Baressi Segota, Nikola Andelić, Jan Kudláček, and Robert Čep. Artificial neural network for predicting values of residuary resistance per unit weight of displacement. Pomorski zbornik, 57 (1):9-22, 2019.
Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast Differentiable Sorting and Ranking. In International Conference on Machine Learning (ICML), pp. 950-959, 2020.
Digvijay Boob, Qi Deng, and Guanghui Lan. Level constrained first order methods for function
constrained optimization. Mathematical Programming, 2024.
Ruidi Chen and loannis Ch Paschalidis. Distributionally robust learning. Foundations and Trends
in Optimization, 4(1-2):1-243, 2020.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-Constrained Reinforcement Learning with Percentile Risk Criteria. Journal of Machine Learning Research (JMLR), 18: 16::1-66775 2017.
John Cotter and Kevin Dowd. Extreme spectral risk measures: An application to futures clearing- house margin requirements. Journal of Banking Finance, 30(12)33499-3485 2006.
Xiangyu Cui, Rujun Jiang, Yun Shi, Rufeng Xiao, and Yifan Yan. Decision making under cumu- lative prospect theory: An alternating direction method of multipliers. INFORMS Journal on Computing, 2024.
Sebastian Curi, Kfir Y. Levy, Stefanie Jegelka, and Andreas Krause. Adaptive Sampling for Stochas- tic Risk-Averse Learning. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-Baun Variance Reduction in Non-Convex SGD. In Conference on Neural Information Processing Systems (NeurIPS), pp. 15210-15219, 2019.
Abdelaati Daouia, Irêne Gijbels, and Gilles Stupfler. Extremiles: A New Perspective Asymmetric Least Squares. Journal of the American Statistical Association, 1146527))1336-13381 2019.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic Model-Based Minimization of Weakly Convex Functions. SIAM Journal Optimization, 29 2019.
Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien. Saga: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. In Conference on Neural Information Processing Systems (NeurIPS), pp. 1646-1654, 2014.

---

Published as a conference paper at ICLR 2025
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of Deep Bidirectional Transformers for Language Understanding. Proceedings of the 2019 Conference of the North, pp. 1171-4186. Association for Computational Linguisties, 2019.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring Adult: New Datasets for Fair Machine Learning. In Conference Neural Information Processing Systems (NeurIPS), pp- 6478-6490, 2021.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science (ITCS), pp. 214-226, 2012.
Yanbo Fan, Siwei Lyu, Yiming Ying, and Bao-Gang Hu. Learning with Average Top-k Loss. In Conference on Neural Information Processing Systems (NeurlPS), pp. 497-505, 2017.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the Role of Momen- tum in Stochastic Gradient Methods. In Conference on Neural Information Processing Systems (NeurIPS), pp. 9030-66396699 (6009964,,22 2019.
Robert M. Gower, Mark Schmidt, Francis R. Bach, and Peter Richtárik. Variance-Reduced Methods for Machine Learning. Proceedings of the IEEE, 108(1)):1988-198, 2020.
Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A Primal-Dual Algorithm with Line Search for General 1299-1329, 2021.
Saddle Point Problems. SIAM Journal on Optimization, 31(2):
Erfan Yazdandoost Hamedani and Afrooz Jalilzadeh. A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems. Computational Optimization and Ap- plications, 85(2):653-679, 2023.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of Opportunity in Supervised Learning. In Conference on Neural Information Processing Systems (NeurIPS), pp. 3315-3323, 2016.
Xue Dong He, Steven Kou, and Xianhua Peng. Risk measures: robustness, elicitability, and back- testing. Annual Review of Statistics and Its Application, 9(1):141-166, 2022.
Matthew J. Holland and El Mehdi Haress. Learning with risk-averse feedback under potentially heavy tails. International Conference on Artificial Intelligence and Statisties (AISTATS), pp- 892-900- 2021.
Matthew J. Holland and El Mehdi Haress. Spectral risk-based learning using unbounded losses. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1871-1886, 2022.
Rie Johnson and Tong Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. In Conference on Neural Information Processing Systems (NeurIPS), pp. 315-323, 2013.
Kenji Kawaguchi and Haihao Lu. Ordered SGD: New Stochastic Optimization Framework for Empirical Risk Minimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 669-679, 2020.
Mohammad Khalafi and Digvijay Boob. Accelerated Primal-Dual Methods for Convex-Strongly- Concave Saddle Point Problems. International Conference on Machine Learning (ICML), pp- 16250-16270. 2023.
Justin Khim, Liu Leqi, Adarsh Prasad, and Pradeep Ravikumar. Uniform Convergence of Rank- weighted Learning. In International Conference Machine Learning (ICML), pp. 5254-52666 2020.
Daniel Levy, Yair Carmon, John C. Duchi, and Aaron Sidford. Large-Scale Methods for Dis- tributionally Robust Optimization. In Conference on Neural Information Processing Systems (NeurIPS). 2020.
12

---

Published as a conference paper at ICLR 2025
Cong Han Lim and Stephen J. Wright. Efficient Bregman Projections onto the Permutahedron and Related Polytopes. In International Conference on Artificial Intelligence and Statistics (AIS- TATS), pp. 1205-1213, 2016.
Yanli Liu, Yuan Gao, and Wotao Yin. An Improved Analysis of Stochastic Gradient Descent with Momentum. In Conference on Neural Information Processing Systems (NeurIPS). 2020.
Andreas Maurer, Daniela Angela Parletta, Andrea Paudice, and Massimiliano Pontil. Robust Unsu- pervised Learning via L-statistic Minimization. In International Conference on Machine Learning (ICML), pp. 7524-7533, 2021.
Ronak Mchta, Jelena Diakonikolas, and Zaid Harchaoui. Drago: Primal-Dual Coupled Variance Re- duction for Faster Distributionally Robust Optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, volume abs/2403. 10766, 2024a.
Ronak Mehta, Vincent Roulet, Krishna Pillutla, and Zaid Harchaoui. Distributionally Robust Opti- mization with Bias and Variance Reduction. The Twelfth International Conference on Learning Representations, abs/2310. 10. 13863, 2024b.
Ronak R. Mehta, Vincent Roulet, Krishna Pillutla, Lang Liu, and Zaïd Harchaoui. Stochastic Opti- mization for Spectral Risk Measures. In International Conference Artificial Intelligence and Statistics, pp. 101 10112-10159 2022.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):5574- 1609, 2009.
Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáe. Sarah: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient. International Conference on Machine Learning (ICML), pp. 2613-2621, 2017.
Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying Recommendations using Distantly-Laben Labelld Reviews and Fine-Grained Aspects. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), Association for Computational Linguistics, 2019.
Jorge Nocedal and Stephen J Wright. Numerical optimizution. Springer, 1999.
Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex- concave bilinear saddle-point problems. Mathematical Programming, 185(1-2):1-35, 2021.
Balamurugan Palaniappan and Francis R. Bach. Stochastic Variance Reduction Methods for Saddle- Point Problems. In Conference on Neural Information Processing Systems (NeurIPS), pp. 1408- 1416, 2016.
Tyrrell Rockafellar and Stan Uryasev. The fundamental risk quadrangle in risk management, optimization and statistical estimation. Surveys Operations Research and Management Science, 18(1-2):33-53, 2013.
R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. The Journal of Risk, 2(3):21-41, 2000.
Nicolas Le Roux, Mark Schmidt, and Francis R. Bach. A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets. In Conference on Neural Information Processing Systems (NeurIPS), pp. 2672-2680, 2012.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally Robust Neural Networks. In International Conference on Learning Representations (ICLR), 2020.
Shai Shalev-Shwartz Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(1), 2013.
13

---

Published as a conference paper at ICLR 2025
Vishnu D. Sharma, Maymoonah Toubeh, Lifeng Zhou, and Pratap Tokekar. Risk-Aware Plan- ning and Assignment for Ground Vehicles using Uncertain Perception from Aerial Vehicles. In IEEE/RJS International Conference on Intelligent RObots and Systems (IROS), pp. 11763-11769, 2020.
Ilya Sutskever, James Martens, George E. Dahl, and Geoffrey E. Hinton. On the importance of initialization and momentum in deep learning. In International Conference on Machine Learning (ICML). pp. 1139-1147, 2013.
Kiran Koshy Thekumparampil. Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient Al- gorithms for Smooth Minimax Optimization. Conference on Neural Information Processing Systems (NeurIPS), pp. 12659-12670, 2019.
Athamasios Tsanas and Angeliki Xifara. Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools. Energy and Buildings, 49:560-567, 2012.
Paul Tseng. An incremental gradient (-projection) method with momentum term and adaptive step- size rule. SIAM Journal on Optimization, 8(2):506-553 531, 1998.
Pinar Tüfekei. Prediction of full load electrical power output of a base load operated combined cycle power plant using machine learning methods. International Journal of Electrical Power & Energy Systems, 60:126-140, 2014.
Peng Wang, Rujun Jiang, Qingyuan Kong, and L. Balzano. Proximal DC Algorithm for Sample Av- crage Approximation of Chance Constrained Programming: Convergence and Numerical Results. arXiv, 2023.
Linda F Wightman. Lsac national longitudinal bar passage study. Isac research report series. 1998.
Robert C. Williamson and Aditya Krishna Menon. Fairness risk measures. International Confer- ence on Machine Learning (ICML), pp. 6786-6797 01666677,420 2019.
Lin Xiao and Tong Zhang. A Proximal Stochastic Gradient Method with Progressive Variance Reduction. SIAM Journal on Optimization, 24(4):2057- 2014.
Rufeng Xiao, Yuze Ge, Rujun Jiang, and Yifan Yan. A Unified Framework for Rank based Loss Minimization. Thirty-sevents Conference on Neural Information Processing Systems, 2023.
Ziyue Xu, Andriy Myronenko, Dong Yang. Holger R. Roth, Can Zhao, Xiaosong Wang, and Daguang Xu. ClinicalReealsstee Annotation for Histopathology Images with Probabilistic Semi- supervision: Worst-Case Study. Springer Nature Switzerland, 2022.
Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. Stochastic Primal-Dual Algo- rithms with Faster Convergence than O(1//T) for Problems without Bilinear Structure. ArXiv, abs/1904.10012. 2019.
1-Cheng Yeh. Analysis of Strength of Concrete Using Design of Experiments and Neural Networks. Journal of Materials in Civil Engineering, 184))5977604, 2006.
Qiyuan Zhang, Shu Leng, Xiaoteng Ma, Qihan Liu, Xueqian Wang, Bin Liang, Yu Liu, and Jun Yang. Coar-Constrained Policy Optimization for Safe Reinforcement Learning. IEEE Transac- tions on Neural Networks and Learning Systems, 2024.
Zeyuan Allen Zhu and Elad Hazan. Variance Reduction for Faster Non-Conver Optimization. In International Conference on Machine Learning (ICML), pp. 699-707, 2016.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B: Statistical Methodology, (((2):3113200) 2005.
14

---

Published as a conference paper at ICLR 2025
A PROOFS
First, we provide an auxiliary lemma. This is an extension of Boob ct al. (0024 Lemma 8).
Lemma Let a be an c-approximate solution min (g())
2 211a
in expectation, where =]1²)
g: Rd + R is p-sttrongy convex, i 2 Then for any D>0
X 2
E (((()) g(x)) S
||
a=1² -
1|::
||
11 m01
(A + DDE
(A+ +
wee
D --Bli
x=1² +
D t
2
2
Proof: = arg (
201 l1.... By (μ + X) -sstong convexity of g(-) + -
we have
X || 103l) =b| 2g(x*)
A
- -01 2 1 X
g(x) + 2
| x²11
X ||l: 101 ||=- l0
g(x²) g(x) v
||a, xe 2=12]]
10 x=1
By the definition of we have
A
A
((((z) + 1 2 - =b13} S g(xx)) ) + 11 2212
(8)
Combining and gives
X
E (1( ( g(x)}
|| æ|
||0 x 2/|2 2== 18| a1|3
x
x²1
x
(9)
2
\ [||a 21|2
|
12
|| +
1:2]
|| x
2
A + P
[||a
||0
x x=1
2
S
X
[||a: 2112
||a
x
||0
+ [1]
11 || - x:11
2
2
+(A + 1)]l=
æ |||
@
x=1
+ej,
(10)
where the last inequality is due to the fact that ||a|2 - |16|2 < -2(a, b-/j,b-a - a) s 2|aa|l|bb all.
Let Ø in
9 and take the expectation with respect to t. Then we have
À + M
E -
a Se
By Hölder's inequality we have
E
x
[||
x0
[E| x 2012) (EE| 2))
E
x
=1
D + D-'Ell x=)²)
2e
<
V A+ μ
(D+ D- æ T
Combining the above results and 10) we get the desired result.
Consider solving the problem from Line 8 to Line i6 Algorithm I while updating ws
min (w) := g(w) + AL ((w) + 2nk ||w wx 1
The following lemma provides the error between wi++1 and arg min, Pa(ww.
15

---

Published as a conference paper at ICLR 2025
Lemma 3 Let Pk(w) := X [(() + g(w) + 2 || wxl12 Set 4. my 27a.
O Lok
pra +1 and
Tr Om, log :) in Algorithm ! The overall sample complexity of obtaining an c-approximate
solution such that IEP (Ew minw Pa(w) is (n= pTu+t log 4) Moreover, we can
sel -2T. and m& 961 + 2 in practice.
Proof:
First note that x+1T l(w) is L-smooth since
( - Σ
&e S )++xall((x))- (.(i)l = L| yll,
1=1
the last inequality we use Ei A I 1 due to AR+1 II and L-smoothness of l. Moreover, it is not hard to see that Ps(w) is μ + Tk -strongly convex. By Xiao & Zhang 2014 Theorem 1) we get the desired result.
for V'z, y Rdd
A.1
PROOF OF LEMMA
Proof: From the update of A and Lemmal we have
1
0
[1I Aull2 - 112 1l21 -11x++1 - >xo17] + (Uk Act1 - A).
(11)
2Tμ
From the update of wx+1 and Lemma 2 we have
Ex (0(w)+1) + (A&+1, ((we++1) - g(w) - (Ae+1, ((w)))
S Ex
1
[ - w
11 wx+1ll -1/w8+1 - -w0113
4
w
wx+1ll
2T
2
(T + n)on (D- 1/ we+t + DI
+5p +
(12)
2
Taking the conditional expectation Eş of both sides of 11 and summing with
12
we obtain that
Ex (L(Wk+1, A) - L(w, )x+1)}
Ex (9(wx+1) + (A, e(20++1) g(w) (As+1, {(w))}
1
Ex (A A Me41,e(wx-t e(wx++1)
[||--
-11--111--1 1|1 1111~~112-
-
A2+1ll2 1|x+11 - -
21T
(13)
+ 2n
|||w w -11 wo+1ll
|1 -wxl13 + (Dk, Akt1 - A)
(Tr -1 +
n)du
wk+11 1|2 002 w|0
(D- wx+1 1 DD)
16

---

Published as a conference paper at ICLR 2025
A.2
PROOF OF THEOREM 1
Lemma Under the same assumptions as Lemma for any w E IRd and X E lI. we have
Ex [L(Wi+11 A) L(w, AR+1)}
1
1
EE
||A->all 1| AR+1ll 11
+
1/0 wxll 2
1/w wk+1 11
277
2Tk
Tk
+ (e(w)+11 -((w)), A Ax+11 -lu(e(ux)) -
AA)
1
1
vnG
vnG0Raa
0k
|| Ax+1ll2 2Tk
1/w0 wk+1112
w 1,,
1k-1
2
akk
2
[Tr -1 ujdn (D-1 ww wx+ill 112 D)
+ōx
+
2
(14)
Proof:
First, we have
(ok, Ax+1 - A)
=(e(wx) + On (e(wx)) - ((wx-1)), Au+1 A)
(e((wx+1)) AR+1) + (l(W)+11) - [((ux); A6t1)
-0 (e(wu())) - e((vk-1) 1), - An) - 02 (e(((()))) E(wx- A) ARtI).
Then we obtain that
Auti, ((ur++)) + (Wk: Ax-1 - A) S (e(wx+1) L(ww), Akt1) Oz (e(wx) f(wk-1);d- - do) (x(w()x))))))))) 1(wwx1), Ao= A
(15)
Next bound the last term the right- right-hand side of [15
(E(w)) e(wok-1), Ax - Akt1)
SvnGi| w - Ast1ll
(16)
VnGak I|wk wk-1l1 +
VnG
|| Abt1ll?
20
where the first inequality is due the G-Lipschitz continuity of l; and in the second inequality use Young's ' inequality with og > 0.
Combing 115 and (16) obtain that
A {(wx++)) + (Wk, A - 2)
([(wx+1) L(uo)), Ar+1) -x((((wx) E(wk--); Ac)
(17)
VnGanok Ok
VnGOn
2 1wk 1k-1112 +
||
Abt1l12
2ax
Taking the conditional expectation E, of both sides of 17) and combing it with Lemma the desired result.
I we get
We remark that O% does not need to be computed in the actual algorithm but only exists in the theoretical analysis. Next, try telescope the terms the right hand side of (14) by multiplying
each term by 7k. To ensure that the adjacent terms in the sequence k = O.... K - can be canceled during summation, need the parameters of the algorithm satisfy the following conditions.
17

---

Published as a conference paper at ICLR 2025
Condition 1 For & 0, 1, rithm 7
the following conditions for parameters in the analysis and Algo-
7k- 1
7ke
(18a)
+ 1 1/k
7h-1 7
1
+
22 + To )0xD)
(18b)
Th+1
Tk
7kk 7 10++10m 00-1;
(18c)
VnGax+1 5
(18d)
Tk
VnG
1
0k
-
(18c)
0kk
Lemma Assume Assumption 1 À II we have
holds and Condition satisfied.
Then for all E Rd and
K-1 22
NK Bll""
wx|1
wx
2
70
||- |
T0
1| woll 2+
Σ
847K + 7h V22 TN 2='))x
2TK
27j0
2To
where w" arg min (ww + g(w) and X 0--1. Here, is the permutation that arranges ( (ww)).... (w=) in ascending order, that is, (111((=0) S ... S
Proof: Taking expectations with respect to w....., Wi in (1) and using the law of total expecta- tion yields
E [[(Wk+11 A) I(W,Ax+1)) A++1)}
1 1 vnGO2
< E
[[| - Axel2 - 11> A 11
1A - A
21jk
2 116 On
+ (l(w)+1) - {(2xx) A - )b+1) - -bx(e(wk)) -e(w)-1))
- -
(19)
+ 2Tk
||2
wxl? 2
+ F1 - v 2(4 + Tx TT)DD=-11 ||1
wx+1ll
Tk
VnG0&00
|m - wi 11 + 8x + / 2(1 + + T6))
|
11 +
2T
2
Multiplying both sides of (19 by 7k and summing over k 0 K obtain that
18

---

Published as a conference paper at ICLR 2025
7x (L(Wx+1,)) L(w, )x+1))
K-
E
70
20112
+
7k+11
7h.
a1
Ak+1ll
-K-1
1 > 11
2770
77
17k
21
k=0
A
+
70
wol
+
K-2
7
7kk
1
+
22
Tx 16x D-11 )] 1|w-- wk+1|1 112
2TO
2
Tk+1
7k
k=U
1K-1
2(n + Tx- -0k-1 1/m0 - wxl
+ 1z
2
TK-1
K-2
+
(7k - 1++10++1 (7=-7)+++:=))((((n)+++)) - L(urk); d Ax+1) + 7 ( f(uox-111 x 2x)
K-2
% 1w0k wk+1ll
7K-1
|wk WK-111
Tk
2TK-1
0=0
D
K
/nG
K- 1
+
7kk
0
A
A
8876 + 7
22 + Jxx 18, 2
2
17k
k=
k=
Here we use f(wo) f(w-1)
by wy w and Ao >_ By Condition
we have
A, D. < 0 and C' = 0.
Then we have
K K-1
E [[(wk+11 A) L(w, Ab+1)}
A 0
E
To
||
Anll2 - -K-1 1| Axl1 +
To
||w -woll woll
21j0
21
2To
7K-1 -1
111
+ - 222Hu + -
|120 wx 1|
(20)
TK-1
+YK- (l(wx) - -l(ux - >xx)
-1
||
1x-1
-
K-1
86 + 7t V /2(H+ + T=')0aD) )}
2
k=0
Next we bound (K-w()((K)) - [(wwx(())))-) X -Ax) similar to 16 We have
(l(wk) 1(Wx-1), Ax) VπGax Iww wx-1112 2
1 VTG
aκ 1| Ax
19

---

Published as a conference paper at ICLR 2025
Taking the expectation and plugging this into 20
obtain that
K-1
B (L(Wk+1, A) - L(w, xx+1))++))
k=
<E
70
dall2
7K-1
7K
VnG
|| -xxx
21Ju
-1
ak
A
70
1
wol
-K-1
+ j V 2( + -1
Tk
|/20 wxl
2TD
2
TK-1
B
-K-1
aKViG
1
100k
wk- 1
Qk +
7h
@V2
2( + Tv )0xD
TK-1
2
k=
(21)
We analyze À-D under Condition
1
Ā
18a
7K
7K-1
VTG
18c
7K
0K
VTG
18c
0,
!KK
ak
7]
Ok
186
YK
2TK
18c
0.
We obtain that
E (L(W0+111) L(w, A++1)}
K K-1
< 70 27j0
20112 +
7o 1| woll 2n
7K EE |w wxll 1|
+
SETE + 7 v 2(2 + Tr 11% 1)
2TK
2
(22)
For any w E Rd and A E 1o. we have L(w", A²) maxxell, L(w" ; A) 2 L(w",
On the other hand, we have L(w, X*) 2 L(w" X²) min L(w, x*). Thus we obtain that L[w++1, X*) ([=="At+) 2 0 for Vk = O..... K - Let = w" and X = X in 22 we
the desired result.
Now we are ready to prove Theorem 1 By choosing appropriate parameters in Algorithm to we can achieve the desired convergence rate.
satisfy Condition |
Proof of Theorem
Proof: First, we obtain an 6₁ approximate solution to 11 through T& updates to w Algorithm by Lemma 3
We then verify that Condition Dis is satisfied by the parameters.
not hard to see that 72+1
D6+1
k+ and Ox+1 = k+1
Th 76-1
2
Thus
18a and
18c
are
satisfied.
Since 8v 8
D2, we have /2(u To T01DD - / 24 +
k+1
DD² B(R+5)
D
<
#. Then
obtain that
7++1
k: +2
k+4 H.
p
11 S
7kk Tx+1
4
4(k + 1)
and
/2(u
Tx
-1 D-1
>
h: +
p1 μ1
k - 4
4 μ.
Tk
20

---

Published as a conference paper at ICLR 2025
Thus (8bb holds.
Furthermore, 18d and 18eh hold due to vnGa++1
n²aTT
k+1 S
A+1
1 and
VRG 0g
Mp-1
Now Condition satisfied. By Lemma 5 we have
K-1 Σ
7K E || w wxl 1 S
To | - -ool
+
70 2TO
I woll
64Th + %
V 22 + Tx 16x ')on
2TK
2110
2
km0
Since δū $ Su(A: + 1) we have Ex=o 8 S 1DD2 12D2>>=0 + 1) D2 and
8
V2 D
20
22
Σ k=
Th (1+ + (M 10oD S
(k+1) (k+1)
D
Σ (k+1) (V++I+2) S v2pD2.
k=0
+1K+1)2
Finally, by
7K 27k 8
To n
SnGa
and D
we get the desired result.
A.3 PROOF OF COROLLARY II
Proof: Recall that Tk = p(k+1) It is not hard to see that uTx m(k+5] S
Lr.
4L
p(k+1)"
By Lemma 3 we get du approximate solution with the sample complexity of C
0 n p(k+1)/ log (ox (5) We set 6% D2 min (अ(ी5)) u(k u(k 1)-0)
Ga n (k + 1)-6 for
k 2 1. And 60 4040. The total sample complexity is
K-
Σ
Owr+
Σ
K-1
o
(( n
u(k + 11) )
(1og(*+1)++0) + 1)+ +1)+ log
G²
km
k=
uk
HK G2
0
nK log
+ 1
log K log
G2
In the last equality, we calculate
Σk
log
o (log k)²). Σx log OK (Kloog K) and
k=
Σ (log K). By Theorem Therefore, the total sample complexity is O
to achieve c-optimal solution, need K 0
VTG Hve
nnā pve
log 1 (log (log1)²)
B EXPERIMENTAL DETAILS AND ADDITIONAL EXPERIMENTAL RESULTS
We now outline the details of our experimental setup. Our experimental setup mainly follows that of Mehta et 2024b).
Datasets.
We use the same five datasets from the regression task in Section 5.1 and the ama on dataset Section 5.3 as in Mehta et al. (2024b). The statistical characteristies are summarized in
Table
Other two datasets in Section 5.2 are as follows:
1. acs: predicting whether an American adult is employed.
2. law: predicting student's GPA.
In the experiments, normalize the features of the sample matrix X E Bxdd so that each feature has a mean of 0 and a variance 1. The test sets are normalized using the statistics the training set.
21

---

Published as a conference paper at ICLR 2025
Dataset
features
# samples
Source
yacht
6
244
Tsanas & Xifara
2012
energy
8
614
Baressi Segota et al.
(2019)
concrete
8
824
Yeh (2006)
kin8nm
8
6,553
Akujuobı Zhang
(2017)
power
4
7,654
Tüfekci (201
acs
16
10000
Ding et al. (2021
law
10
20800
Wightman
1998)
amazon
535
20000
Mehta et al.
a (2024b)
Ni ct al.
2019
Table 3: Statistical details of real datasets and sources.
Objectives. We use linear models our experiments. For spectral risks, we adopt three types: ESRM, Extremile, and CVaR, specified in Table [ Additionally, set the regularizer g(w) to /|1l1 with 14 n: where n donates the number of sample points in the taining set. Thus, Problem (T) can be written as
11 11101
min
(w)
where ((-) is the loss function, which will be chosen in different forms for different tasks.
Hyperparameter Selection. We use similar hyperparameter selection method as in Mehta et al. 20246). We set the batch size for SGD to 64. For the selection of step size a, we set the random seed s SS). For single seed s, we calculate the average training loss of the last epochs, donated by I., (a). We choose a that minimizes & S (a),, where a E (1 x 10-4,3 x 10-1, 10-3, x 10-3, $ x 10-2,3 10-2, x 10-1, x 10-1). For LSVRG, we set the length of epoch n. For SOREL, set Tg mg Moreover, we batch size 64 for all algorithms with mini-batching.
For SOREL, we follow the parameter values given in Theorem In particular, set 0g 20n in all experiments. Therefore, there are only two parameters and 7 left to tune. K+T
and тk
2, 2,2 x 10 2, x 10 x 10-1, 10-1, 1 x 10-1, x 10 x 10",4 4 x 100, 1 x 10"), with two orders of magnitude higher numbers used in law, since the Lipsehitz constant G is hard estimate. We grid search to select and C, with the selection criteria being the same as the previous paragraph. We apply stochastic gradient descent solve instead of proximal stochastic gradient descent.
We set 7k C(k+1) and choose from {1 x 10-2,
Experimental Environment. run all experiments on a laptop with 16.0 GB RAM and Intel i7-1360P 2.20 GHz CPU. All algorithms are implemented in Python 3.8.
B. EXPERIMENTAL DETAILS ON LINEAR REGRESSION
Dataset. We use the same dataset as that used in Mehta et (024b)), as previously described.
Objectives. We use the least square loss in this experiment. For spectral risks, we adopt three types: ESRM (p 2), Extremile (r 2.5), and CVaR (a 0.5).
Evaluation. We set random seeds (1, 2,, as the seeds for the random algorithms. We compare the suboptimality versus passes (the number of samples divided by n) and runtime. The suboptimality is defined as
Ro (wx) + g(wx) - Ro (w=)) - g(ww)
Suboptimality(nn:)
Rs (wo) g(wp) Ro (w+) g( )(w*)*
where un is calculated L-BFGS (Nocedal & Wright 1999)
22

---

Published as a conference paper at ICLR 2025
B.2 EXPERIMENTAL DETAILS ON FAIR MACHINE LEARNING
Dataset. We two datasets, acs (Ding al. 2021 and law (Wightman) 1998), which for classification and regression tasks, respectively. For acs, we randomly selected 10, 000 sample points from the California data. We use data from four states Connecticut, Hawaii, West Virginia and Florida in Ding et al. (2021) as the test dataset to explore the out-of-distriuttion performance of models trained with spectral risks, with each state having 36287, 14400, 18066, and 202160 sample points, respectively.
Objectives. For the regression and classification tasks, we use the least squares loss and the binary logistic loss, respectively. For css, set the spectral risks to CVaR (ar 0.75), ESRM (p 1.75) and Extremile (r 2.1). For law, we set the spectral risks to CVaR (a = 0.05), ESRM (p = 20) and Extremile (r 10).
Evaluation. We fix the number of training passes 100. We split the training and test set in a 4:1 ratio and used five-fold cross voos-vaaiiationn to report the average results on the test set. For each training and test set split, set random seeds { {1, 2,3} as the seeds for the random algorithms. All algorithms are implemented using mini-batching. We set race as the sensitive feature. For acs, the sensitive feature includes Black and White. For 1aw, the sensitive feature includes non- White and White. For the task of exploring models' out-of-domain performance, we directly use the models obtained from the acs experiments the models trained on California dataset. Then, we test these models on all data points from the other four states.
B.3 EXPERIMENTAL DETAILS ON OUT-OF-DISS DISTRRIUITIINI GENERALIZATION
Dataset. amazon Ni et 2019) is for the multi-class classification task. We use the prepro- cessed data in Mchta et al. (2024b). They fine-tuned a BERT model on 10, 000 held-out examples and applied PCA to the deep representations produced by BERT. The training set and test set each contain 10,000 samples. #features in Table 3 refers to the total dimension of the parameter vectors for 5 classes
Objectives. We use linear model and the multinomial logistic loss. In amazon, we set the spectral risks to CVaR (a = 0.75) and Extremile (r = 2.0).
Evaluation. We set random seeds E 21, 4, as the seeds for the random algorithms. We evaluate the worst group classification error (Sagawa al.) (020) the test set. Each group is classified based on the true labels. We fix the number of passes during training to 500 and report the average worst group classification error of the last ten passes. All algorithms are implemented using mini-batching.
B.4 ADDITIONAL EXPERIMENTAL RESULTS
we present results of the algorithms with mini- batching for tasks in Section 5.1 Mini- bini-batching has a significant improvement on the convergence rate of all the algorithms. Similar to what is shown in Figure 2 SGD, LSVEG and Prospect fail to converge to the true optimal points, especially in the first two datasets. SOREL converges to the optimal solutions in all settings, and achieves the best competitive results, in terms of sample complexity, runtime, or both, except in the setting of CVaR and power dataset. Still SOREL performs competitively for the suboptimality of 10-7 in this setting.
Algorithms with mini-batching. In Figure 5
Training curves in fair machine learning. Figure 6 shows the training curves for the task in Section [.2] The training curves are extended to illustrate convergence. SOREL is able to achieve low suboptimality in the shortest amount of time.
23

---

Published as a conference paper at ICLR 2025
10
20%5
energy
10--
10"1
10:2
16"3
20-1
10"
1017-
400
10.4
10'
20-14
16-
400
0.25
0.2
3.75 1.20
220
1.00
650
0.75
6.35
650 035
180
300
10-1
10:4
2015
10--
10-1-
10
10th
20th
10t
30"9
10-1
10:
10-1
10-1
10-44
20-**
10.11
10-1
20-2
kmnBrm
1001
10-1-
10-1
16-5-
10-1
10--
10"41
30:11
10-11
10-1
1.0
10
101
100
power
10-4.
16-1
10
2017
10
10
12-4
20-4
12
10:
10-*
100
0.0
2.5
200
7.5
16.0
5o
102
165
Passes
Time
[s]
Passes
Time (s)
Passes
Time (5)
5GD
LSVRG
Prospect
SOREL
Figure 5: Suboptimality of spectral risks for different algorithms with mini-batching. The x-axis represents the effective number of samples used by the algorithm divided by (odd columns) or CPU time (even columns).
CWAR
ESRM
Extremile
Emgloyyment
30:11
30
70-1
10
30
20-1
10-1
10a
School
10-4
20-1
30
00-1
10-1
3044
10-4
13:1
107
1.5
10-1
Time
Prospect
Figure 6: Suboptimality spectral risks for different algorithms on fairness benchmarks. The r- axis represents the CPU time.
C EXAMPLE
To illustrate the necessity of stabilizing the trajectory of the primal variable in Section 3.1 we provide a toy example. For simplicity, we consider a one-dimensional problem
min a (w)) + (w))
(23)
WER
where 0, 02 1 and e, = (w 1)2 (2(w) (w 1) We use the following deterministic method, similar to Algorithm]
Example 1 For any 0 sufficiently large. In that case, the iterative sequence {wk} can not converge to the optimal solution for any initial point wo-
< 2, suppose solve Problem (23 using Algorithm 2 and T is
24

---

Published as a conference paper at ICLR 2025
Algorithm 2 Simplified Algorithm for Solving the Example Problem.
for 0, I.... do
2: Update 111+ 1x+1,2 = foi, if & (wx) 2 (2(1)) else 012 Set w = wk-
3:
for t 0, 1, .....
do
4:
Compute the gradient g" = A (ei(w() + ARt1,2 (
5: Update wt+1 wt ag'.
6: end for
7: Set Wh++1 = T
8:
end for
Without loss of generality, we assume wi > O, in which case A [0, 1]] We solve min ER 2 [w1 + 1)² through sufficient steps of gradient descent to obtain wi = -1. At this point, A [1. 0 By iterating this process, Wy always oscillates between -1 and 1, unable to converge to w* = 0. If wp O, we set σ, = 1 and 02 O, reaching the same conclusion. similar conclusion be extended to stochastic methods in the expectation sense.
We know that (1w") = f2(w") at the optimal point w* = 0. Clearly, the iterative sequence of the algorithm oscillates at w" and cannot converge to the optimal solution. Although Mehta et al. [2022] 2024b) employ a similar approach to update À for subgradient estimations, they consider the smoothed spectral risk by adding strongly concave term with respect However, for the original spectral risk minimization problems, updating À with their method results in discontinuities, thereby lacking convergence guarantees.
D SOREL WITH MINI-BATCHING
In this section, present the results of SOREL with mini-batching. To apply mini-batching. We only need to change Line 13 of A Algorithm replacement, and change Line
to: Sample a mini-batch by C (I,...,n) without
to
dy.t
[nd V4, (Wk,t) -A Vl((w)]
where 6 [be] is the mini-batch size.
We first present the main result of SOREL with mini-batching.
Corollary Use the same conditions in Therorem y Additionally, set the step-size a 400L(m=b) bL(n-b] my = [K+S))b(n-I] + 8 and Tk = O log +.). Then we obtain an output w of SOREI. with mini-batching such that El|eu wn 112 in total sample complexity of nd log + L(n-b) pVe m(n-1) 2)2
b(n-1)
O
D.1 PROOF OF COROLLARY
We first discuss the inner loop Lines 17 Algorithm This an extension SVRG (Johnson
& Zhang 2013 Xiao & Zhang 2014h. To illustrate more clearly, consider the problem
min P(w): F(w) + h(w). w
((ww,, each fa convex and I-smooth, and is y-strongly convex. We rewrite Lines 6 17 of Algorithm [ to Algorithm 3 Note that, by setting th W., m
where F(w)
F(w)= = A w and h(w) = g(w) 27 w -w Algorithm is the same as Lines 17
of Algorithm
Assumption Each fs Rdd + I is convex and L-smooth. h Rd R {oo} is proper, lower semicontinuous and ph. -tronnyyy convex.
The following two results are adopted from Xiao & Zhang 2014), which will be used the proof of the main result.
25

---

Published as a conference paper at ICLR 2025
Algorithm 3 Simplified Inner Loop of Algorithm | with Mini-batching.
Input: initial Wo. the learning rate a, mini-batch size 6, and the inner-loop length m.
2: for 0. do
3: w 1.,-1. g (())
4: Wp = w.
5:
for 1= 0, 00l......
do Sample b, C cl,,..,, n) of size b uniformly at random without replacement. d, = :/ Lieo, [Vf((w,) - [[()]]] + g.
6:
7:
Wr+1 = Proxan (w: ad:). 9: end for
8:
10: W. Em= Wt.
11:
end for
Lemma 6
(iaao & Zhang 2014
Lemma 1) Suppose Assumption holds, and let w.
arg min P(w). Then for all w E Rd
1
Vi((w) Vf...)) ( P(w.)).
Lemma 7
(iiao & Zhang 2014 Lemma 3) Suppose Assuption holds, let A. = de VF(w.)
and w. arg min P(w). Then
| - w. 1| S w. - -w,l= 2 2a [P - P (w.)] - 20d (wi+1 W.). (24)
The following lemma bounds the variance of the stochastic gradient de.
Lemma Let E, be the conditional expectation given w, and w. arg min P(w). We have
2(n 2(n b (P(w:) - P(w.) + P(w) P(w.)) b(n ((n-1) 1)
E,idd; [F(w:)] -
Proof:
Define & = Vf((w,)) V(((8).
Ez|lch VF(w:)11
1
= =Bell b i.bb.
(ws) - (w))
(Vi(()) Vf((w.)) l
n
=Bell
1
Σ
E1,1
- Σ
1 12
n
Eb
E, ba
Σ
Si
T
Eis
1
Σ
ET
n²
ieE
i==1
b(b 1)
b n Σ
ETE E3
TT &
Σ
ET
62
n2 (n1 1) iデf
n1
i=1
أزز=1
b-1 1
n
11-b-1
b
n Σ
Σ
c Es +
E7 &
Σ
nb
n 1
m
n
i.
n - b
1 x2
n
Σ
<T 5 + Σ &T &
nb(n-
1)
71 :j=1
where the second equation is due E|fg
Rgll2
E
||E/|
26

---

Published as a conference paper at ICLR 2025
n|l E 2 Note that ! - Ey obtain that
0. Combing the above result with Lemma 6
n-
Ex|ld; [F(w))]1
V (i(ww)) - V(((w))
Im(n - 1) ==
(IV[)(m);) - Vs((w,))) )12 + [V V.((w.))13)
bn(n - 1)
2(n b) (P(un)) P(nn.) P(w) P(w.))
b(n - 1)
This completes the proof.
Lemma Suppose Assumption 2 holds and 2o n-b
b(-11 1. Let w. arg migmin P(w). Then
obtain an output w. of Algorithm such that
EP(w.)) P(w.)= S p² (P(wa) P(w.)),
where p
U D U 2am (1 - 2 1- B[n-15)
n-b
and D + 4a I(m + 1) n b(--11)
Pm
We have that W3-1- We define Wi+1 = Proxah (w - F(w)), which is independent of the mini-batch b. First we bound the last term in (24
Proof: We first consieder the s-th outer iteration of Algorithm 3
A (We+1 w.) -2 (w--1 Wi+1 + Wi -w.)
- 2x A, ||ll We+1 - W1+1/l 2 (Wi+1 W..)
(25)
$ 2o| A, ||l|| w. ad, - w9 + aV (w))l -2ad, (Wi+11 - -w.,
2a | 2 [w411 w.
where the second inequality we use the non- canniveesss the projection operator. Note that E,A, (Wr+1 w.)
A.) (W:+1 w.) 0. Taking the conditional expectation E, on both
sides of 25 and using Lemma 8 we obtain that
-2aE, (W++1 - w.) s 4a2 b)L
(P(w)) - (Pw.)) P(w.-1) P(w.))
b(n - 1)
Taking the conditional expectation E, both sides of (24 and plugging in the above result, obtain that
E||lw;+1 w.12 < 1|w, w.1l2 20( P(w.))
4a² (n b) (P(w.) P(w.) P(w..-1 P(w.))
(26)
+ b(n 1)
Taking the expectation on both sides of (26). using the law of total expectation and summing over t O....,m we obtain that
E W| w. 22 (2((E)( P(w.)) 2a 1 2al n- b
[EP(w:) - P(w.))
b(n
< ||wo 2 + 4a² L n -
b(n 1] (P(wo) - P(w.)) + 4a² Lm n-
b(n ((n-1) 1) (P(w,-1) -Pot.)
(27)
Since w w.-1 and 2x > 2a 1 2a (( by the assumption, obtain that
n2 - b b(n 1)
Bl|w w. 2 + 2a 1 1-2aL 2al
(IE((w:) P(w.))
t=1
(28)
< 10,11 w. 4a L(m + 1) b(n -
n
(P(w.-1) -P(w.))
27

---

Published as a conference paper at ICLR 2025
By the n4 strsong convexity of P and the definition of st obtain that
2aL 1-6
2am
b(n - 1) (BP(w,s) - P(w.))
< (22 + + 4a L(m + b(n 1(n-1) ---))
(P(w.-1)- P(w.)).
Finally, by applying the above inequality recursively, we get the desired result.
Corollary 3 Let w. arg ming, P(w). With the same conditions Lemma setting the step size 100L(m-b) b(n-1) and the loop length m = p4 + 8, we obtain an output w, of Algorithm such a b[(n-b] that E.((w. P(w.) < in a total sample complexity of O ((n (n-b)L (n-1)
log l
Proof: Through simple calculations, convergence. We need s 2 log 3 log P(w.) to obtain an e-optimal solution in expectation. The total sample complexity is s(n bm) O
obtain that p 4 Thus Algorithm has geometric
((n
(n-6)L [n-1]p log l
Now we are ready to prove the main result for SOREL with mini-batching based on Theorem Proof of Corollary 2
Proof: By Corollary we get a dæ approximate solution of the k-th outer loop SOREL with mini-batching with the sample complexity of O ((" (n-b)) [8+1)(n-1)w log k- Similar to the proof of Corollary | through simple calculations we obtain the total sample complexity of Go WVC log L(m-b) pin-1) (log 1)²
E ADDITIONAL EXPERIMENTS ON NONCONVEX OBJECTIVES
In this section, we empirically explore the performance of SOREL optimizing nonlinear models. We train two-layer neural network with ReI.U activation function and set the hidden layer's dimen- sion equal to the feature dimension of the input data. We use the regression task from Section 5.1 Thus, the loss function and the model can be written as
((x) 2 (z y
and
2 == W2 (ReLU(W1x + b1)) - b2, where x E Rd, E IR are the feature and label, W1 E Rdxdd b1 E R2d W2 E IR 1xd and b2 E IR are trainable parameters. The experimental setup is identical that in Section 5.1 The initial points are generated from Gaussian distribution, and for the same spectral risk setting, the initial points for all algorithms are the same.
Figure 7 shows the training curves using three spectral risk measures the energy and concrete datasets. Note that none of the four algorithms have theoretical guarantees in the non-convex setting. However, SOREL achieves the optimal or near-optimal results across various settings. On the energy dataset, SOREL achieves the lowest losses, significantly outperforming LSVRG and Prospect. On the concrete dataset, SOREL also achieves slightly lower loss val- ues compared to LSVRG and Prospect. Table reports the mean losses and standard deviations over the last ten passes. We observe that SOREL achieves the lowest mean losses, demonstrating the effectiveness optimizing non-convex functions, even though theoretical guarantees are not available.
F FURTHER DISCUSSION ON THE COMPLEXITY IN COROLLARY I
In Section 4 we discussed the optimality of the complexity in Corollary D with respect to e. this section, further discuss the dependence of the complexity in the Corollary onn The sample
28

---

Published as a conference paper at ICLR 2025
3.20
0.18
0.5
311
2.12
032
0.2-
0.0
2.05
3.00
0.99
3.04
0.04
Plaseiss
0.44
0.3
2.13-
0.33
2.12
0.12
012
2.11-
213-
3.00
0.10
3.09
2.00
100
200
160
436
560
632
160
230
160
402
500
602
160
202
360
402
500
602
Passes
5GD
LSVRG
Prospect
SOREL
Figure 7: Results of training two-layer neural networks using different algorithms.
Table 4: The mean function values over the last ten passes (and standard deviations in parentheses).
Datasets
energy
concrete
SGD
LSVRG
Prospect
SOREL
SGD
LSVRG
Prospect
SOREL
0.05533
0.06986
0.06715
0.04787
0.09573
0.09149
0.09099
0.08888
CVaR
(0.02004)
(0.00027)
(0.00024)
(0.00045)
(0.00299)
(0.00276)
(0.00188)
(0.00104)
0.05463
0.06253
0.06594
0.04464
0.08942
0.08417
0.08443
0.08275
ESRM
(0.01268)
(0.00882)
(0.00006)
(0.00020)
(0.00253)
(0.00006)
(0.00039)
(0.00013)
0.05153
0.07544
0.07155
0.04792
0.09832
0.09132
0.09261
0.09073
Extremile
(0.00329)
(0.00005)
(0.00005)
(0.00005)
(0.00325)
(0.00012)
(0.00097)
(0.00077)
Since SOREL requires computing the projection onto the permutahedron II, in each outer iteration, which takes On log n) time, the total time complexity of SOREL includes an additional O(Kn log n) term, where K O VMC
complexity with respect to n and in Corollary 1 iss (nn /VE)
nya
given in the proof of Corollary [ Therefore, the total complexity SOREL with respect to n and e O(n3/2 /V)..
We then discuss the complexity of baselines in Section with respect and SGD has been shown to fail to converge to the optimal solution the spectral risk minimization problem, while LSVRG only guarantees convergence for 2 S2 (nnG (Mehta al. 2022). For Prospect, by setting O(e), we obtain its sample complexity with respect to n and e as Ö(n²/E2) or ((n/e²) (depending on the size of E). Moreover, Prospect requires computing the projection onto the permutahedron II, at each step with a cost of (n log n) time, which results its total time complexity an additional Ó(n² /c3) )) or Ó(n3 /c2). Therefore, SOREL also has an advantage in terms of the total time complexity with respect to n. This is consistent with the experimental results in Section 5 where SOREL significantly outperforms Prospect in terms of runtime.
Beyond the above, after our original submission this work we have also recently become aware that Mehta et al. (2024a) proposed primal-dual stochastic algorithm to solve the smoothed version of the spectral risk minimization problem. By setting the smoothing parameter to e, sample complexity is
nG"
In (t)) where b is the batchsize. Considering that each step of their
algorithm requires a projection, the total time complexity includes an additional δ latest manuscript of Mehta et al. (2024a), their improved algorithm also solve the original spec- tral risk minimization problem. Their theoretical analysis focuses on deriving a linear convergence rate for the smoothed specral risk minimization problem and does not provide convergence rate for the original problem.
2.5
In
by
29


Reviews:
[{"review_id": "QFYFk330Dl", "reviewer": "Reviewer_CGGB", "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.", "questions": "See the section above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\nOther comments:\n1. 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?\n2. $w^*$ is not defined in Theorem 1.", "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": "", "extra_scores": {}}, {"review_id": "HARhltMBfk", "reviewer": "Reviewer_fKff", "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.", "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.\n\n2. See weaknesses 1 and 2.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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:\n\n1. 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.\n\n2. 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.\n\n3. 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.", "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": "", "extra_scores": {}}, {"review_id": "HE0SQyWDdy", "reviewer": "Reviewer_YNq6", "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.", "questions": "n/a", "limitations": "", "rating": 6, "confidence": 5, "soundness": 1, "presentation": 4, "contribution": 2, "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.\n- 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.\n- 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,\n$$\n\\frac{\\sqrt{n}(10G)}{(100\\mu)^2\\sqrt{\\epsilon}} = \\frac{1}{1000}\\frac{\\sqrt{n}G}{\\mu^2\\sqrt{\\epsilon}}.\n$$\nThis 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.\n\nMatters 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.", "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": "", "extra_scores": {}}, {"review_id": "tG02VCPSsE", "reviewer": "Reviewer_TvDg", "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.", "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?\n- 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.\n- 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?\n- In Theorem 1, can you please define $w^*$? I do not understand what it is.\n- 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.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Sections 1, 2 and 3.1 are truly well-written, it has been a pleasure to read it\n- The idea of using a primal dual method based on Lemma 1 of (Blondel et al. 2020) is clever and elegant\n- Algorithmic performances are convincing and are accompanied by sound theory\n- It is great to propose a mini batching version of SOREL", "weaknesses": "See Questions part", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)