A Unified Framework for Rank-based Loss Minimization
Authors: Rufeng Xiao
Yuze Ge
Rujun Jiang
Yifan Yan
Venue: NeurIPS 2023 poster (2023)
Keywords: rank-based loss
ADMM
nonconvex nonsmooth optimization
conditional Value-at-Risk
human-aligned risk
ranked range loss

Abstract: The empirical loss, commonly referred to as the average loss, is extensively utilized for training machine learning models. However, in order to address the diverse performance requirements of machine learning models, the use of the rank-based loss is prevalent, replacing the empirical loss in many cases. The rank-based loss comprises a weighted sum of sorted individual losses, encompassing both convex losses like the spectral risk, which includes the empirical risk and conditional value-at-risk, and nonconvex losses such as the human-aligned risk and the sum of the ranked range loss. In this paper, we introduce a unified framework for the optimization of the rank-based loss through the utilization of a proximal alternating direction method of multipliers. We demonstrate the convergence and convergence rate of the proposed algorithm under mild conditions. Experiments conducted on synthetic and real datasets illustrate the effectiveness and efficiency of the proposed algorithm.

A Unified Framework for Rank-based Loss Minimization
Rufeng Xiao
Rujun Jiang' School of Data Science, Fudan University (rfxiao21, yzge23) Cm fudan. edu. cn jjjiang@fudan. edu. cn yanyf21 1mm fudan. edu. en
Yuze Ge
Yifan Yan
Abstract
The empirical loss, commonly referred to as the average loss, extensively utilized for training machine learning models. However, in order to address the diverse performance requirements of machine learning models, the use of the rank-based loss is prevalent, replacing the empirical loss in many cases. The rank-based loss comprises weighted sum of sorted individual losses, encompassing both convex losses like the spectral risk, which includes the empirical risk and conditional value-at-risk, and nonconvex losses such as the human-aligned risk and the sum of the ranked range loss. In this paper, we introduce unified framework for the optimization of the rank-based loss through the utilization of a proximal alternating direction method of multipliers. We demonstrate the convergence and convergence rate of the proposed algorithm under mild conditions. Experiments conducted on synthetic and real datasets illustrate the effecttiveness and efficiency of the proposed algorithm.
Introduction
The empirical risk function is the cornerstone of machine learning. By minimizing this function, machine learning models typically achieve commendable average performance. However, as these models find applications across diverse spectrum of real-world scenarios, the evaluation standards for machine learning performance have evolved to include factors such as risk aversion and fairness 49 19. This has led to the empirical loss function often being supplanted by other loss functions, many of which fall under the category of the rank-based loss, which consists of a weighted sum of sorted individual losses. We consider the following optimization problem in this paper, which minimizes the rank-based loss plus a regularizer:
min WER
Σo, o (- (Xw)) ((w).
(1)
Here, I(u)= A [[(u),.... (I.,)) Rd R" represents vector-valued mapping where I: R:R- R denotes an individual loss function and u; the element of u. (.1(.)) < .... & (mm() (-) denotes the order statistics of the empirical loss distribution, g IR - IR is regularizer that induces desired structures, E Rd represents the parameters of the linear model, X Ruxd is the data matrix, and y E [#1]" is the label vector. The subscript [i] denotes the i-th smallest element, a, E [0, 1] the weight corresponding the i-th smallest element, and "o" represents the Hadamard product. Depending on the values of o; the rank-based loss can encompass significant range of losses often
"qqual contribution
t CCoresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

used in machine learning and other fields: the L-risk or the spectral risk 22 the trimmed risk or the sum of the manked-range loss (27), the human- -lligned risk based on the cumulative prospect theory (31]
Related work. When the values of o, are constant and monotonically increase, i.e., 01 S... S On- the aank-baeed loss is referred to as the spectral risk (T. Several methods have been proposed in the literature, including: derivative-free method proposed by [25] that utilizes stochastic smoothing technique; an adaptive sampling algorithm proposed by [14] for the minimization of conditional value at risk (CVaR), which special case of the spectral risk; and a stochastic algorithm developed by [36] for minimizing the general spectral risk by characterizing the subdifferential of the rank based loss. In the case of nonconvex rank-based losses, [27] utilizes the difference of convex algorithm for minimizing the average of ranked-range (AoRR) loss. The nonconvex buman-aligne, risk was minimized by 33 by directly computing the gradient of the function, even though the rank-based loss is nondifferentiable, without any convergence guarantee. Despite the increasing applications of the rank-based loss, a unified framework for addressing the rank-based loss minimization remains elusive. Moreover, stochastic methods may encounter bias issues [36), existing methods for the spectral risk cannot deal with nonconvex rank-based losses, and existing methods for human-aligned risk lack convergence guarantee [11
Our Contributions. We present a unified framework for the minimization of the rank-based loss to overcome the challenges of existing methods. Specifically, we focus on monotone increasing loss functions, such as the hinge loss and the logistic loss, and use weakly convex regularizers. We leverage the alternating direction multiplier method (ADMM), which is widely used in solving To utilize the ADMM framework, we introduce an auxiliary variable to represent the product of the data matrix and parameter vector. The two subproblems are either strongly convex (with a proximal term), which can be solved by various existing methods, or can be efficiently solved by the pool adjacent violators algorithm (PAVA) [6]. We demonstrate that our algorithm can find an e-KKT point in at most ( iterations under mild conditions. To relax the assumptions further, we propose variant of the ADMM with smoothing technique when the regularizer is nonsmooth. Notably, when the Moreau envelope is applied to smooth the nonsmooth regularizer, we show that our algorithm can find k-KKT point within O(1/=t) iterations.
nonsmooth nonconvex composite problems g 32 48
Our contributions can be summarized as follows:
1) We propose unified framework for the rank-based loss minimization for monotonically increas- ing loss functions. This approach is versatile, effectively dealing with both convex and nonconvex loss functions by allowing different settings of weights o5.
2) Furthermore, the regularizer in our problem can be weakly convex functions, extending existing works that only consider convex or smooth regularizers, such as the I and l2 penalty.
3) We theoretically demonstrate that our ADMM algorithm converges to an e-approximate KKT point under different assumptions.
4) The experiments in three different aggregate loss function frameworks demonstrate the advantages of the proposed algorithm.
2 Preliminaries
In this section, we explore the wide variety of rank-based losses and introduce the Moreau envelope as a smooth approximation of weakly convex functions.
2.1 Rank-Basee Loss
Let ((X1,V1)..... VI....., (Xn, }n)} be an i.idd sample set from a distribution IP over a sample space (X,)), and L be the individual loss function. Then Y L(w, X, y) is also a random variable, and Y; = L(w, X;, v1) represents the i-th training loss with respect to the sample (X;, v.), i E [l....,n},
Let Vij S .... S Ynj be the order statistics. The rank-based loss function in problem ! equals
a
o
(2)
2

---

Spectral Risk
The spectral risk, as defined in [1] is given by:
R (w)) = =f/ (aRo(w))r(t) dt,
where (w) = inf (u: (u) 2 () denotes the quantile function, and Fw represents the cu-
mulative distribution function Y. The function 0 [0, 1] + R4 is a nonnegative. nondecreasing function that integrates to I, known as the spectrum of the rank-based loss. The discrete form of (3 is
consistent with 2). with o; = f fi--1)/ (t) dt [36]. The spectral risk builds upon previous aggregate losses that have been widely used to formulate learning objectives, such as the average risk [46], the maximum risk [3], the average top-k risk [1] and conditional value-at-risk [39] By choosing
different spectral (t), such as the superquantile [30]. the extremile [[5], and the exponential spectral
risk measure can be constructed for various spectral risks.
Human-Aligned Risk With the growing socictal deployment of machine learning models for aiding human decision-making, these models must possess qualities such fairness, in addition strong average performance. Given the significance of these additional requirements, amendments to risk measures and extra constraints have been introduced [28] 23 [9] Inspired by the cumulative prospect
theory (CPT) 45,, which boasts substantial evidence for its proficiency in modeling human decisions, investigations have been carried out in bandit (24] and reinforcement learning (41). Recently, [31] also utilized the concept of CPT to present novel notion of the empirical human risk minimization (EHRM) in supervised learning. The weight assigned (3) is defined o. w. where
3 a a +1 (3t² 2(a +)t+ +1.
Wa 6 (t)
These weights assign greater significance to extreme individual losses, yielding an S-shaped CPT- weighted cumulative distribution. Moreover, we consider another CPT-weight commonly employed
in decision making [45] 41. Let z = - y @ (Xw) and be a reference point. Unlike previous weight settings, o, is related to the value of 2|: and is defined
w (+) w- (²
2 S B,
(1(2)))
(4)
Wh (لمنت)) - w4 (4
211 > B,
where
pd
(p) =
w-(p) = (p' + (1 - pp)))
(5)
(pr + (1 (+-11))11 1/)
with 7 and 5 as hyperparameters.
Ranked-Ranc Loss ture 2 where
The average of ranked-range aggregate (AoRR) loss follows the same struc-
m-m i {m + + L.....,, k}.
0. otherwise,
with S m < k n. The ranked-range loss effectively handles outliers, ensuring the robustness of the model against anomalous observations in the dataset (27). It is clear that AoRR includes the average loss, the maximum loss, the average top-k loss, value-at-risk [39] and the median loss (34]. (27) utilized the difference-of-coovvex algorithm (DCA) (40) solve the AoRR aggregate loss minimization problem, which can be expressed as the difference of two convex problems.
2.2 Weakly Convex Function and Moreau Envelope
A function g Rd + IR is said to be c-weakly convex for some e > 0 if the function + 511 1| is convex. The class of weakly convex functions is extensive, encompassing all convex functions as well as smooth functions with Lipschitz-comtinuouss gradients [37]. In our framework, we consider weakly convex functions as regularizers. It is worth noting that weakly convex functions constitute rich class of regularizers. Convex LP norms with p 1 and nonconvex penalties such as the Minimax Concave Penalty (MCP) (52) and the Smoothly Clipped Absolute Deviation (SCAD) 20 examples of weakly convex functions [7].
3

---

Next, we define the Moreau envelope of c-weakly convex function g(w), with proximal parameter 7
Man(ww) min g(x) + 27
w 1|
The proximal operator with parameter y is given by
prox arg min ((x)) +
27 0 w/12
We emphasize that prox,, g.n (:) single-valued mapping, and Mo.r (w)) well-defined since the objective function in is strongly convex for y E (0,c=)) 77.
The Moreau envelope is commonly employed to smooth weakly convex functions. From 7 Lemma 3. 3.1-3.2 we have
(Mgn(w) = - (w prox,, E ag (prox,.y (w)).
(8)
Here @ represents Clarke generalized gradient TQ] For locally Lipschitz continuous function f: Rd + R. its Clarke generalized gradient is denoted by 0f(x). We say æ is stationary for if O 0f)).. For convex functions, Clarke generalized gradient coincides with subgradient in the sense of convex analysis. Under assumptions in Section 3.3 both Q(=) == >im J:lis] (z) and g(w) are locally Lipschitz continuous [2 47 Thus, the Clarke generalized gradients of (2(z) and g(w)
are well defined, and is that of Lp (, z; A) defined in Section 3.1
3 Optimization Algorithm
Firstly, we make the basic assumption about the loss function and the regularizer g:
Assumption The individual loss function U(-) D - R is convex and monotonically increas- ing, where DD C R is the domain of I. The regularizer g(-) Rd R U {oo} is proper, lower semicontinuous, and e-weakly convex. Furthermore, 1(-) and g(-) are lower bounded by 0.
Many interesting and widely used individual loss functions satisfy this assumption, such as logistic loss, hinge loss, and exponential loss. Our algorithm described below can also handle monotonically decreasing loss functions, by simply replacing o; with n in ( We assume I and are lower bounded, and take the infimum be 0 for convenience. The lower bounded property of implies that the Ω is also lower bounded by 0 since o, 2 0 for all i.
3.1 The ADMM Framework
By Assumption I
the original problem is equivalent to
min Σ 0il (D))) + g(w),
i=1
where is the individual loss function, whose diagonal entries are the vector y.
diag(y) (g) X and diag(y) denotes the diagonal matrix
To make of the philosophy of ADMM, by introducing an auxiliary variable Dwv, reformulate the problem as
min [(2) + g(w)
s.t. == =Dw
where [(2))= = onl (=p)
Note that for human-aligned risk, a; should be written as (z1)) since it is a piecewise function with two different values in (4) but for simplicity, we still write o,,
The augmented Lagrangian function can then be expressed as
Σ 2(()) + G1l= - Dw + 112 + g(ww)
||aa2
Lp z; A)
2p

---

The ADMM, summarised in Algorithm cyclically updates w, 2 and X, by solving the w- and 2- subproblems and adopting a dual ascent step for In Algorithm[[] we assume the w- subproblem can be solved exactly (for simplicity). When g(wr) is smooth function, the w-subproblem is smooth problem and can be solved by various gradient- based algorithms. Particularly, the w--subproblem the least squares and admits a closed-form solution if ((vr) = 0 or g(w) = # where 0 a regularization parameter. When g(w) nonsmooth, if proxg.7 (w) is easy to compute, we can adopt the proximal gradient method or its accelerated version [4]. Particularly, if g(w) = $1|w|||
then the subproblem of w becomes LASSO problem, solvable by numerous effective methods such as the Coordinate Gradient Descent Algorithm (CGDA) [22], the Smooth L. Algorithm (SLA) 42
and the Fast Iterative Saiinkaag--Trrsoooddngg Algorithms (FISTA) 44.
Algorithm ADMM framework
Input: y. wº, 2 2 p. r, and oi I,..., n.
1: for all k 0, l.... do
2 112. 2: z z+1 arg ming 02(z) + El1z Dw
3: w w+t = arg min E11 - Dw + 2 122 g(w) + fllw - 1013
4: A+1 x + p(zbt1 11)
5: end for
At first glance, the z-subproblem is nonconvex and difficult to solve. However, we can solve an equivalent convex chain-constrained program that relies on sorting and utilize the pool adjacent violators algorithm (PAVA). More specifically, we follow the approach presented in [I3 Lemma 3] and introduce the auxiliary variable m Dw X (we remove the superseript for m for simplicity). This enables us to express the z-subproblem in the equivalent form below
min Eor((ep +
P 2( mp.) s.t. Ep1 S Zp2 S ... S 2pm
where {pI, P Pm. is permutation of (1....,m) n) such that map < mps & .... & Mpn.
3.2 The Pool Adjacent Violators Algorithm (PAVA)
To introduce our PAVA, for case notation and without loss of generality, we consider my & m2 & may i.e., the following problem
min Σ -o,l(z)+ + f(2 ((4mmm)+
s.t. 21 S 22 S S Zn.
(10)
The above problem constitutes a convex chain contraccd program. Although it can be solved by existing convex solvers, the PAVA 66 is often more efficient.
The PAVA is designed to solve the following problem
min Σ (1(2))
s.t.
21 S
En.
where each 0g represents a univariate convex function. In our problem, 0z(2,) = ((z,,)==((z;))) + {z
m.) The PAVA maintains a set that partitions the indices 21. n.) into consecutive blocks and 8k+1 N. Here, [a, b) represents the index set {a, a + 1,....b) b) for positive integers a < b, and by convention, we define (a, a) = a. A block [p, q) is termed single-valued block if every 2; in the optimal solution of the following problem has the same value,
{[s1 + 1, s2], (82 + 1, (a)a),... [sk 11+)) with 81
min Spinnnig
Σ (zi))
s.t. 2p S Ep41 ... Zqg
i.e., =3 = 2p+1
zg. In line with existing literature, we use Upa4 to de- note this value. For two consecutive blocks [p.g] and + 1,r]. if Uppaa] ([g+1.)) the
5

---

two blocks are in-order; otherwise, they are out-of-order. Similarly, the consecutive blocks [sk, 8k+1), [ 1 + +, Sk42), ... [a++ s++++1]} are said to be in-order if Visussral Σ Mps otherwise they are out-of-order. Particularly, if Viezokesl (pesttLe > ... - the consecutive blocks are said be consecutive out-of- order. The PAVA initially partitions each integer from
into single-valued blocks [ for i= 1....... n. When there are consecutive out-of-order single-values valued blocks [p. g] and [q + 1, r), the PAVA merges these two blocks by replacing them with the larger block [p, r]. The PAVA terminates once all the single-valued blocks are in-order.
Algorithm 2 A refined pool pool-adjiacet-vvolatto violatoos algorithm for solving problem (10)
Input: J (1, 1), [2. .............................. [n, n.]. 0,, 1.2.......
Output: 1/. UNN .UN
for each [i E do
2: Compute the minimizer Vi.ii of (y)
3: end for
4: while exists out-of-order blocks in J do
5: Find consecutive out-of-order blocks C [lsk 0441 (8k+1 + 1, 8k422) ". [sk+e
1, 5k+++1)))..
6: J J- [[sk, sk+r+1]], compute the minimizer 01440844441l of 664441 (1(2).
Zimss
7: end while
8: for each [m, n] E J do
9: V.- =]m,n] Vi m, + 1...., n.
10: end for
Traditional PAVA processes the merging of out-of-order blocks one by one, identifying two consecu- tive out-of-order blocks and then solving a single unconstrained convex minimization problem to merge them. For constant dg our proposed Algorithm 2 however, leverages the unique structure of our problem to improve the PAVA's efficiency. Specifically, we can identify and merge multiple consecutive out-of-order blocks, thereby accelerating computation. This acceleration is facilitated by the inherent properties of our problem. Notably, in case the spectral risk and the rank-ranged loss, the function O (2;) demonstrates strong convexity due to the presence of the quadratic term 2 (2, -m,) and the convex nature of (zz.). This key observation leads us to the following proposition.
Proposition 1 For constant as, suppose U[m,n] V(n+1pp the blocks [m, n] and [n + 1, are consecutive out-of-order blocks. We merge these two blocks into {m. p). Then the block optimal value, denoted by p) satisfies U[++1pp] S 1/m.p)] S U/mmn]-
P provides a crucial insight: when encounter consecutive out-of-order blocks with length greater than 2, we can merge them simultaneously. rather than performing individual block merges. This approach significantly improves the efficiency of the algorithm. To illustrate this concept, consider scenario where we have a sequence values arranged as U/1,2 > U/3.4] > U]3.6]- Initially, we merge the blocks [1, 2] and [3, 4), resulting in 1[1,4] 2 2/3.4 | > V[5.6]- However, since 2/144 is still greater than U]5,6]. we need to merge the blocks [1, 4] and [5, 6] as well. Rather than calculating U[1.4] separately, we can streamline the process by directly merging the entire sequence into a single block, namely [1, 6]. in a single operation. By leveraging this approach, we eliminate the need for intermediate calculations and reduce the computational burden associated with merging individual blocks. This results in a more efficient version of the PAVA. Further details can be found in Appendix B.3
is worth noting that when (z(2)) is convex with respect to 2, the PAVA guarantees to find a global minimizer (6). However, when considering the empirical human risk minimization with CPT-weight in (4, the function (2()) is nonconvex, which is because d; is a piecewise function with two different still find point that satisfies the first-order condition 222 Theorem 3].
values. In such cases, In summary, we always have
0 E OgL, 2; )).
(1I)

---

3.3 Convergence Analysis of Algorithm
We now demonstrate that Algorithm I is guaranteed to converge to an c-KKT point of problem (
To this end, we shall make the following assumptions.
Assumption 2 The sequence (X*) is bounded and satisfies ==
|
1
< xo.
is worth noting that Assumption 2 is commonly employed in ADMM approaches [51 3].
Next, we present our convergence result based on the aforementioned assumptions. As mentioned in Section 3.2 the PAVA can always find a solution for the z-subproblem that satisfies the first-order
When is constant, which is the case of the spectral risk and the AoRR risk, the subproblems of PAVA are strongly convex, and we can observe the descent property of the z z-subproblem:
condition 111
(12) However, of has different values for z less than and larger than the reference point as in 4 the subproblems of PAVA may lose convexity, and the descent property may not hold. Thus, we assume that 12 holds for simplicity. By noting that the w-subproblen can be solved exactly as strongly convex, we make the following assumption.
Lp(="; wn ,²) 1,p(2=+), w= X²) 2 0.
Assumption The u--subrroblem solved exactly, and the z-subproblem is solved such that and 12 hold.
Assume that Assumptions 1 and Bhold. Then Algorithm Cean find an K-KKT point (2++1, w *+1, x of problem
Theorem
9 within ((1/e2) iterations, i.e.,
dist x (-X an (z (x)+))) < e, dist (DT k+1 .0g (w (w- Se. ||
Dw S
where dist(a, A) min
x E A} defines the distance of a point a to set A.
In the absence of Assumption 2 common assumption for nonconvex ADMM is that g(w) possesses a Lipschitz continuous gradient 48 32). e.g., ((w) b w| Under this assumption, Algorithm guarantees to find an <KKTT point within O(1/22) iterations
4 ADMM for a Smoothed Version of Problem
In Section 3.3 our convergence result is established under Assumption 2 when nonsmooth regular- izer g( () is present. In this section, to remove this assumption, we design variant of the proximal ADMM by smoothing the regularizer g(w). We employ the Moreau envelope to smooth g(wr and replace (w) in Algorithm| with Mg. (wr). We point out that (g,((w) is a y weakly convex function if 0 < ey S 3. Thus the w-subproblem still strongly convex and can be solved exactly.
See Appendix A.1 for proof. We assume that the sequence {X*} is bounded, which is much weaker than Assumption We will show that within O(1 ((1/c") iterations, (z* a X²) is an e-KKT point,
where xh proxox (
To compensate for the absence of Assumption 2 we introduce the following more practical assump- tions.
Assumption We assume z Im(() Vk, where Im(() = =(D : x E IRd).
stronger version of Assumption (xXXxxiagyy)
that DDT
diag(y) XX diag(y) 0 [32]. It is worth noting that the full rank property of the data matrix is often assumed in the high dimensional setting classification (m < d and each entry of belongs {-1, 13). Here we do not impose any assumptions on the rank of data matrix X.
Assumption (w) is bounded by M > 0, i.e., || (w)l < M, Yw e R".
Regarding nonsmooth regularizers, Assumption 5 is satisfied by weakly convex functions that are Lipschitz continuous 77], due to the fact that Lipschitz continuity implies bounded subgradients and g Common regularizers such as (n-orm, MCP and SCAD are all Lipschitz continuous.
7

---

The following proposition establishes the relationship between {(z", ,","") }²)} and {(z w" )²)).
Proposition 2 Suppose is c-weakly convex and Assumption 3 holds. Suppose the sequence {(z", w", }} and u prox proxg.;ww)) (w²)). Then have
} is produced during the iterations of Algorithm with replacing g(w) by Mg
00)(2*11 x -D(
D D +r( w w E Og(w (13)
Before presenting our main results, we introduce Lyapunov function that plays significant role in our analysis:
2r²
Φh = Lp("", z=" ,x,)
+
1 t
w 1
op
The following lemma demonstrates the sufficient decrease property for Th.
Lemma Letr 7-1 Under Assumptions
7 and if0 < or
E.. then have
2r - 7- 4 - -
op opy 120 w011 + || 1111.
2
(14)
2
The sufficient decrease property for the Lyapunov function is crucial in the proof of nonconvex ADMM. Using Lemma I we can control || w" and || [ | through the decrease of the Lyapunov function. We are now ready present the main result of this section.
Cg, where C₁ and C2 are constants such that C2 > 1 and C1 + Under the same assumptions in Lemma Algo- rithm i with replacing g(w) by (gn(()) finds an 6-KKT point (zk+1, bt1 x within O(1/c)) iterations, i.e.,
Theorem 2 Suppose {X*} } is bounded. Set p
o12C2-1))
dist (-xht1, 0n (2 sc, dist (D** .g (wntt)) Sc, 1| Di Sc..
5 Numerical Experiment
In this section, we perform binary classification experiments to illustrate both the robustness and the extensive applicability of our proposed algorithm.
When using the logistic loss or hinge loss as individual loss, the objective function of problem
can be rewritten > o; log (1 exp (=μ) + g(w) or > [1 mp1 + g(w), where
@ (Xw), and g(w) = i w [2 or g(w) = + /w/l1-
We point out some key settings:
1) For the spectral risk measures,
the logistic loss and hinge loss individual loss, and use l and & regularization with taken as 10-2 logistic
2) For the average of ranked range aggregate loss, use the logistic loss and hinge loss as individual loss and use l2 regularization with = 10-4
3) For the empirical human risk minimization, we the logistic loss as individual loss, and use &2 10-2
regularization with /
As shown in Section 2.1 we can apply our proposed algorithm to variety of frameworks such as the spectral risk measure (SRM), the average of ranked-range (AoRR) aggregate loss, and the empirical human risk minimization (EHRM). We compare our algorithm with LSVRG, SGD, and DCA: LSVRG(NU) denotes LSVRG without uniformity, and LSVRG(U) denotes LSVRG with uniformity, detailed in [36]: SGD denotes the stochastic subgradient method in [36): DCA denotes the difference- cofferrence-f-ccomeee -ofcvveex algorithm in [40]; SADMM refers to the smoothed version of ADMM.
The details of our algorithm setting, more experiment settings and detailed information for each dataset are provided in Appendix B Additional experiments with synthetic datasets are presented
in Appendix C
8

---

5.1 Spectral Risk Measures
In this section, we select (tt) in 3 generate the empirical risk minimization (ERM) and (t) = (t) (t) q) to generate superquantile, the latter having garnered significant attention in the domains of finance quantification and machine learning [30].
Setting. For the learning rates of SGD and LSVRG, we use grid search in the range (10-2, 10-3, 10-10-111 10-1,01/,,// 1/Nammppess 1/ (Naamples X Nieatures) }, which is standard for stochastic algorithms, and then we repeat the experiments five times with different random seeds.
Results. Tables D and 2 present the mean and standard deviation of the results in different regularizations. The first row for each dataset represents the objective value of problem ① and the second row shows test accuracy. Bold numbers indicate significantly better results. Tables and show that our ADMM algorithm outperforms existing methods in terms of objective values for most instances and has comparable test accuracy. In addition, we highlight the necessity of reselecting the learning rate for SGD and LSVRG algorithms, as the individual loss and dataset undergo modifications-40 highly intricate procedure. Conversely, our proposed algorithm circumvents the need for any adjustments in this regard.
Table 1: Results in real data with SRM superquantile framework and &e regularization.
Datasets
Lngiznic Lase
Hinge Loss
ADMM
LSVRGINU)
LSVRG(U)
SGD
ADMM
LSVRG(NU)
LSVRG(U)
SGD
0.6522 (0.0058) 0.6522 (0.0058) 0.6522 (0.0058) 0.6523 (0.0018) 0,7724 (0.02144) 0.7724 (0.0214) 0,7724 (0.0214) 0,7738 (0.0219)
SVMguide
0,9566 (0,0035) 0.9563 (0.0058)
(.0661) 0.9566 (0.0052)
0.9568 (0.0033) 0.9568 (0 (0:00133 0.9568 (0.00133) (0.0055)
0,1539 (0.0092) 0.1538 (0.0092) 0:1538 (0,0091) 0.1560 (4.0114)
0.07887 (0.0033) 0,0852 (0.0129) 0,0833 (0.0133) 0,0815 (0.0137)
0.9629 (0.0071) 0.9633 (0.0070) 0.9633 (0.0070) 0.9631 (0.0067) 0.9521 (0:0112) 0.9559 (0.0099) (0.0098)
(0.0097)
Table 2: Results in real data with SRM superquantile framework and 4 regularization.
Lagiole
Hoge
ARMM
AANMM
LSVROENU)
ESVRRRU)
SGD
ARMM
KATMM
LSVRGINU)
LSVRGU
SCiD
0A200 (1 00122 0.220 (0/0199)
0,220 (10129)
0.830 (00019)
11022 (0:118))
(.6799 (
1.67M (0.0275) ) 09121 (00033) 0.678M (1:073)
0,8569 (102100)
0.9563 (8 (097)
019511 (0.005T)
0.958 (10009) 0.963 (BU0057) (19561 (0.003))
0,5565 (BU0036)
0,9556 (0,0005) 0.958 (OL0029) 0.9563 (0.0055)
0,9555 (10000))
0.2601 (0.0079) 0,2612 (0,0079) 0.2614 (0,0080) 0,2614
(0.0050) 0.2641 (0/0105)
0,1352 (8U0594)
(0,0095)
(0.0110)
(0.0100)
(0.001))
0.9673 (0.0044) 0.9673 (0.0054) 0.9650 0,9680 (B.0054) 0.9673
0,9589 (0.0060)
0,9599 (0.0060)
(D.0045)
(0.0039)
0.9635
Figure T iillustrate the relationship between time and sub-optimality of each algorithm in the ERM framework with logistic loss, which is convex problem whose global optimum be achieved.
The learning rate of the other algorithms is the best one selected by the same method. The Figure []] depicts that ADMM exhibits significantly faster convergence towards the minimum in comparison to the other algorithms. Conversely, although SADMM fails to achieve the accuracy level of ADMM, it nevertheless demonstrates accelerated convergence when compared other algorithms.
5.2 Empirical Human Risk Minimization
Since [3]] utilizes gradient-based algorithms akin to those in [36], we compare our algorithm with the one referenced in Section 5.1
Results. The mean and standard deviation of the results are tabulated in Table SPD. DI, EOD, AOD, TI, and FNRD are faimess metrics detailed in Appendix(B.6] The bold numbers highlight the superior result. It is evident that our proposed algorithm outperforms the other algorithms in terms of objective values and test accuracy, and also shows enhanced performance across almost all fairness metries.
5.3 Average of Ranked Range Aggregate Loss
As mentioned in Section 2.1 DCA can be used to solve for AoRR aggregate loss minimization 27 Therefore, we compare our algorithm with the DCA algorithm in this section.
Results. Table 4 displays the mean and standard deviation of both the objective value and time results. Given that this is a nonconvex problem, the objective value may not be the optimal value.

---

carpll
outre Jeat
ON DiN
OP
(a)
(b)
FuT ratole 2000 suth Presatt 568
rur vample 2030 vum, Natue 1606
Pur cample Sree rus feaurr:
zum vample 10000 Paatuns 2003
(e)
(f)
(h)
Figure 1: Time vs. Sub-optimality gap in synthetic datasets with ERM framework. (a-d) for lz regularization, and (e-f) for & regularization. Sub-optimality is defined F F=, where F represents the objective function value at the k-th iteration or epoch and F denotes the minimum value obtained by all algorithms. Plots are truncated when p F 10-8
Table Comparison with EHRM framework. 'objval' denotes the objective value of problem
IT.
ADMM
LSVRGNN))
LSVRGU
SGD
ADMM
LSVRGINU)
LSVRG(
SGD
-bjool
IL4955 (8.0045)
0,5383 (B.002))
(0.002))
0,993 (0.0013)
FOD
.0,0521 (0.0150)
+0.0388 (0:01:4)
00031 (00110)
.0016000.018)
Ascunacy
(8,0076)
(0.0050)
0.748 (0.0054)
0.634 (0.020))
AGD
0.0499 (0.0199)
(0.0196)
0.0266 (0.075))
(.0071)
(0.0161)
(0.158)
(0,0050)
0,0933 (00018)
(0.0822)
L0S33 (8,0166)
1,1034 (0.0900)
(0.227))
1,0585 (0.0065)
FNRD
(0.0160)
0/0238 (00014))
0,0100
Nevertheless, as evidenced in Table 4 our proposed algorithm achieves better objective value in shorter time for all the instances.
Table 4: Comparison with AoRR framework. 'objval' denotes the objective value of problem
splioe
ADMI
DCA
ADMM
DCA
ATMM
DCA
ATMM
DCA
ADMM
DCA
Eagiohi
EJ8125
0.5857 1254)
81603 (L3891)
0L555
BUNCTT
DI001 (0
ILBIIS (QJN0))
0.5431
Sea X0
(8.11)
01.2)
1.5410.30
13335 (319:
25.36 (5,80)
(26.24127.10)
BL3 (9:30)
21.2512:11
17.28 (137)
53.91 (5
Aloee
0,0013 (81617))
0.3556 (0.17H)
0.8677 (80010))
0,594) (00012)
9.0060 (18955)
55842 (1.157))
B/117T (8.002)
D0925 (5/0015)
0.9335 (8,005)
0.9931 (000155
6 Conclusion
This paper considers bank- loss optimization with monotonically increasing loss functions and weakly convex regularizers. We propose unified ADMM framework for rank-based loss minimization. Notably, one subproblem of the ADMM is solved efficiently by the PAVA. Numer- ical experiments illustrate the outperformance of our proposed algorithm, with all three practical frameworks delivering satisfactory results. We also point out some limitations of our algorithm. To effectively utilize our algorithm, individual losses must exhibit monotonicity, use the PAVA to solve subproblems. If the sample size is large, the PAVA's computational efficiency may be hindered, potentially limiting its overall effectiveness. Future work may explore variant using mini-batch samples, potentially improving early-stage optimization performance and overall computational efficiency.
this allows to
Acknowledgement Rujun Jiang is partly supported by NSFC 12171100 and Natural Science Foundation of Shanghai 227.1 1405100
10

---

References
[1] Acerbi, C. (2002). Spectral measures risk: A coherent representation of subjective risk aversion. Journal of Banking & Finance, 26(7):1505-1518,
[2] Acerbi, C. and Simonetti, P. (2002). Portfolio optimization with spectral measures of risk. arXiv preprint cond-mat/0203607.
[3] Bai, X., Sun, J., and Zheng, X. (2021). An augmented lagrangian decomposition method for chance-constrained optimization problems. INFORMS Journal Computing. 33(3):1056-1000 1069.
[4] Beck, A. and Teboulle, M. (2009). A fast iterative saankkage-thresholdigg algorithm for linear inverse problems. STAM journal on imaging sciences, 2(1):183-20)
[5] Bellamy, R. K., Dey, K., Hind, M., Hoffmman, S. C.,, Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mojsilovic, A., et al. (2018). Ai fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. arXiv preprint axXiv:/8/0.0194
[6] Best, M. J., Chakravarti, N., and Ubhaya, V. A. (2000). Minimizing separable convex functions subject to simple chain constraints. SIAM Journal on Optimization, 10(3):658-61 -672.
[7] Böhm, A. and Wright, S. J. (2021). Variable smoothing for weakly convex composite functions. Journal of optimization theory and applications, 188:628-644
[8] Boyd, S., Parikh, N., Chu, E.,, Peleato, B., Eckstein, J., et al. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends Machine learning, 3(12
[9] Chow, Y., Tamar, A., Mannor, S., and Pavone, M. (2015). Risk-sensitive and robust decision- making: CVAR optimization approach. Advances in neural information processing systems, 28.
[10] Clarke, F. H. (1990). Optimization and nonsmooth analysis. SIAM.
[11] Cotter, J. and Dowd, K. (2006). Extreme spectral risk measures: An application to futures clearinghouse margin requirements. Journal of Banking & Finance, 30(12):3499-345.
[12] Cui, X., Jiang, R., Shi, Y., and Yan, Y. (2023). Decision making under cumulative prospect theory: An alternating direction method of multipliers. arXiv preprint arXiv:2210.02626.
[13] Cui, X., Sun, X., Zhu, S., Jiang R., and Li, D. (2018). Portfolio optimization with nonparametric value at risk: A block coordinate descent method. INFORMS Journal on Computing, 30(3):454- 471.
[14] Curi, S., Levy, K. Y., Jegelka, S., and Krause, A. (2020). Adaptive sampling for stochastic risk-averse learning. Advances in Neural Information Processing Systems, 13:1036-1047.
[15] Daouia, A., Gijbels, I., and Stupfler, G. (2019). Extremiles: A new perspective on asymmetric least squares. Journal of the American Statistical Association, 1 114(527):1366-15 1381.
[16] Davis, D. and Drusvyatskiy, D. (2019). Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1)207-2339
[17] Derrac, J., Garcia, S., Sanchez, L., and Herrera, F. (2015). Keel data-mining software tool: Data set repository, integration of algorithms and experimental analysis framework. Mult. Valued Logic Soft Comput, 17.
[18] Dua, D., Graff, C., et al. (2017). Uci machine learning repository, 2017. URL htp://rrchive. ics. uci. edu/ml, 7(1).
[19] Duchi, J. C., Hashimoto, T., and Namkoong, H. (2019). Distributionally robust losses against mixture covariate shifts. Under review, 2:1.
[20] Fan, and Li, R. (2001). Variable selection via nonconeave penalized likelihood and its oracle properties. Journal of the American statistical Association, 348-660
11

---

[21] Fan, Y., Lyu, S., Ying, Y., and Hu, B. (2017). Learning with average top-k loss. Advances in neural information processing systems, 30.
[22] Friedman, J., Hastie, T., and Tibshirani, R. (2010). Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1.
[23] Garcia, J. and Fernández, (2015). A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480.
[24] Gopalan, A., Prashanth, L., Fu, M., and Marcus, S. (2017). Weighted bandits or: How bandits learn distorted values that are not expected. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31.
[25] Holland, M. J. and Haress, E. M. (2022). Spectral risk-based learning using unbounded losses. International Conference on Artificial Intelligence and Statistics, pages 1871-1886. PMLR.
[26] HSU, C.-W. (2010), A practical guide to support vector classification. http://www. csie. ntu. edu, tw/ cjln/hpapessguudeelggudd pdf.
[27] Hu, S., Ying, Y., Lyu, S., et al. (2020). Learning by minimizing the sum of ranked range. Advances in Neural Information Processing Systems, 33:21013-21023.
[28] Kamishima, T., Akaho, S., and Sakuma, (2011). Fairness-aware learning through regulariza- tion approach. In 2011 IEEE 11th International Conference on Data Mining Workshops, pages 440- IEEE.
[29] Kushmerick, N. (1999). Learning to remove internet advertisements. In Proceedings of the third annual conference on Autonomous Agents, pages 175-181.
[30] Laguel, Y., Pillutla, K., Malick, J., and Harchaoui, Z. (2021). Superquantiles at work: Machine learning applications and efficient subgradient computation. Ser- Valued and Variational Analysis, 29(4):967-99
[31] Leqi, L., Prasad, A., and Ravikumar, P. K. (2019). On human-aligned risk minimization. Advances in Neural Information Processing Systems, 32.
[32] Li, G. and Pong, T. K. (2015). Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization, 25(4): 2460.
[33] Lin, Z., Li, H., and Fang, C. (2022). Alternating Direction Method of Multipliers for Machine Learning. Springer.
[34] Ma, Y., Li, L.,, Huang, X., and Wang, S. (2011). Robust support vector machine using least median loss penalty. IFAC Proceedings Volumes, 14(1):11208-112)
[35] Maurer, A., Parletta, D. A., Paudice, A., and Pontil, M. (2021). Robust unsupervised learning via I-statistic minimization. In International Conference on Machine Learning, pages 7524-7533, PMLR.
[36] Mehta, R., Roulet, V., Pillutla, K., Liu, L.., and Harchaoui, 7. (2023). Stochastic optimization for spectral risk measures. In International Conference on Artificial Intelligence and Statistics, pages 101 12-1199. PMLR.
[37] Nurminskii, F., A. (1973). The quasigradient method for the solving of the nonlinear program- ming problems. Cybernetics, 911):455-11
[38] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V.. Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 222825-2830..
[39] Pflug, G. C. (2000). Some remarks on the value-at-risk and the conditional value-at-risk. Probabilistic constrained optimization: Methodology and applications, pages 272-281.
12

---

[40] Phan, D. N. (2016). DCA based algorithms for learning with sparsity in high dimensional setting and stochastical learning. PhD thesis, Université de Lorraine.
[41] Prashanth, L., Jie, C., Fu, M., Marcus, S., and Szepesvári, C. (2016). Cumulative prospect theory meets reinforcement learning: Prediction and control. In International Conference Machine Learning, pages 1115-1415. PMLR.
[42] Schmidt, M., Fung. G., and Rosales, R. (2007). Fast optimization methods for 11 regularization: A comparative study and two new approaches. In Machine Learning: ECML 2007: 18th European Conference on Machine Learning, Warsaw, Poland, September 17-21, 2007. Proceedings 18, pages 286-297. Springer.
[43] Shalev-Shwartz, S. and Wexler, Y. (2016). Minimizing the maximal loss: How and why. In International Conference on Machine Learning, pages 993-801. PMLR.
[44] Shen, Y., Wen, Z.., and Zhang, Y. (2014). Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization. Optimization Methods and Software, 29(2):239-263.
[45] Tversky, A. and Kahneman, D. (1992). Advances in prospect theory: Cumulative representation uncertainty. Journal of Risk and uncertainty, 5:297-323.
[46] Vapnik, V. (2013.. The Nature of Statistical Learning Theory. Springer Science & Business Media.
[47] Vial, J.-P. (1983). Strong and weak convexity of sets and functions. Mathematics of Operations Research, 8(2):231-259,
[48] Wang, Y., Yin, W., and Zeng. J. (2019). Global convergence of admm in nonconvex nonsmooth optimization. Journal of Scientific Computing, 78:29-63.
[49] Williamson, R. and Menon, A. (2019). Fairness risk measures. In International Conference on Machine Learning, pages 6786-6797. PMLR.
[50] Wnek, J. (1992). MONK's Problems. UCI Machine Learning Repository. DOI: 24432/ C5R30R
[51] Xu, Y., Yin, W., Wen, Z., and Zhang. Y. (2012). An alternating direction algorithm for matrix completion with nonnegative factors. Frontiers of Mathematics in China, 7:365-384.
[52] Zhang, C.-H. (2010). Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, pages 894-942.
[53] Zhang, Z., Song. Y., and Qi, H. (2017). Age progression/reeression by conditional adversarial autoencoder. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5810-5818.
13

---

Appendix
A Proofs
A.1 Proofs for properties of Moreau envelope
Lemma Let g R" + (oo) be c-weakly convex function. For 0 < cy S 3. the Moreau envelope Man of g is y y -weakly convex.
A.1.1 Proof of Lemma
Lemma Let _ + R U foo}. Then is c-weakly convex if and only if the following holds
(v w. v) 2 -cla 1 -yll?
for x. y E RR, E 0g(x)), w Ög(y).
Proof: See 16 Lemma 2.1].
Lemma Suppose g(w) is c-weakly convex. If0 cy S 3/2 then we have
prox 9.7 (x) prox 3.7 ( | < 3 20|
Proof: Suppose a; y RR. By and Lemma we have
cll prox 9.7 (x: prox (arox,;(())) (2))l
< (1y
prox 9.7 (y)) - (x prox,, (x)) proxx,, (b) - ,,axx,,,
1 11y - prox g. (3) x prox (z) - prox,,, (1) - prox (x))1
27
+ || y
Thus we have
(1 2cy)] proxp.> prox, (x))1 -1yy prox, (3) + +poxx (x))1 + ||x y1
x y|l?
Note that (1 20y) < when 0 <0 S 5/4 Thus have
prox (3) prox p
(x) < (1 207) 1|0 -y12 - 3/ x y11
Proof of Lemma 2
Proof: For any x, E IR, we have
(V (z) (M, x - y)
=y (x prOx, n, (x) y + prox y,7 (y), x - y)
=y-
|| 2/12 + 7 - (prox, 1..0x,g,(110
(,7(1) (3) prox, 9.7 (x), x y)
1
1
2y-11p || - y/l
| - y1
prox 3.7 (x) - -prxx,, prox,,,(x)) (3)
2
2
1
3
y 1
2ry
2-
x
3112
where the first equality follows from (8) and the last inequality follows from Lemma y --eakllyy convex by Lemma 3
Thus g
14

---

A.2 Proofs for ADMM in Section 3
A.2.1 Proof of Proposition 1
Proof: First we define (z)) Ei 01(z). Due to convexity, we have
0 E ah (fmm,n)) and E + (M/+t
Noting that mm..n] 1. due the strong convexity of h, we further have
@h [m. (+ < O, and ahtp++1ap (f(m.n)) 0,
where we use the convention that set > 0 (or < 0) denotes that all elements g E A satisfies g > (or < 0). Therefore obtain that there exist [mm,n]= 1(n+1,p] IR such that
pm (f(m,.)) mm nn (1mm.))) ) + 001++1ppl (fmm,n)) mmm,n] >> 0,
oh m) (+()+1.p)) [m (vin+ 1p) + ahin. + (ap) (.p) (1))+1.))) 3 1(m+1.p) < 0.
As (mm.p) is strongly convex in [1]++1p))> 1,p "[m,a]] the subgradient @himpp is strictly increasing in
[v|=+ l.p. f/m,n]] That is, Vx, y E [U]n+ (.p) mim,n]]. Vsz E @h [m.p) E @hmm.p) (v). (5z
8y)(x - v) 2 0. The above facts, together with the strong convexity of h(mpp) the unique minimizer p| of hmm.p) must lie in the interval [*[++1,p): [m,,))]-
A.2.2 Proof of Theorem 1
Proof: We use the extended formula for Clark generalized gradient of sum of two functions in our proofs: 0(fi + (x) C (z) ff)(2) if fi and f2 are finite and f2 differentiable at æ. The equality holds if fi is regular at æ. [10 Theorem 2.9.8].
By Assumption have
((2*+1)= 1 b11=At1 D + A 11))
0 02
2
12( x² + p(z Dro*t)
(15)
001(2tt) kl) + x² + p(zht1 Dwn bt2 + pD (tn w
w)
00((* k+l) + A k+1 + pD(w ktl -w
and
kt1 w² x²) 2 0. Here the equality of 15 follows from X k+1 x + p(2 b1))
Lp(e* w X² Lxtttt
(16)
By Assumption 3 and (r c) -strong convexity of the ro-subproblem, we have
g11 1 ++1 + A
0
- 1|2 + g( g(w) F1lo un
E Uw
22
(17)
= @g(w++11 - TT -pD (2 - kt + r - -
Üg(w 1 DT k+1 r(w - -w*,,
and
Lp(2h w 2/) Lo
w k+1 x²) 2r
1 1
wx1l²
(18)
The second equality of (17) is due to the fact that weakly convex functions are regular 47 Proposition 4.5]. By the dual update we have
Lp(2*+1 R+1 x+1 ,xt) Lp(x* 1+11 2
(2 x x (a*t1 Dr
(19)
=- - _
15

---

Summing (16). 18 and (99)
we obtain that
Lp(=*, w ) Lp(=*t1 +11 wht A )
2 2
2r
1w
w² - 1 11*
12t1 (20)
By Assumptions Tand 2 we have that
Lp( w* >²) S2(=*) + g(w=)) + (A*) (a Dw= + [11 1|
A -13- 1
=1(2*t + g((0*)
+ L G1lezt Dw
2
p
2p
(21)
112
2p 00.
So T,p(2,, u X²) is bounded below by some Lt. Moreover, Σ
|
2 S
Ek=1 || ||
R+1 X 12 for AK 2 1.
L Lp("", 1 ) L + Σi 2 - 14112 < co. Then telescoping 20 from k
1
K, we obtain that
2 |
1> Lp(z" w/ w', ,,,)=
Lip wo .AK)
1112
+
p
k=1
(22)
K c
K
w
k+1
201 +
1
k+ - xx122.
2
This implies that
2r C
1 1| - - S L
min
2
1
k+1
p
K
Letting arg mingg - 1w0+11
20012+ + 111 - 11122, we have
2I.
1
w011 S V
K(2r - cc)
př.
x
V
K
Letting K 2. by 15 and 17 we further have
24.
dist (>xht1 on (2 (z)+))) s @||
w -1 sIDDIyyy
K(2r- = 0()),
21.
dist (DTx*+) ,0g 2g (wott)) < krllwk+1 - w*11 - S s
K(2r O(e),
1zb11 D+1
-
1
1 x
= O(c).
p
pK
The proof of Theorem
I is adapted from
33 Theorem 4.1].
16

---

A.3
Proofs for smoothed ADMM in Section
A.3.1
Proof of Proposition 2
Proof: By Assumption
B similar 15 have
0 E (00(2 + A k p(= Dw**
= -00((=*t)) + * + p( Dwe t 1 + pD DD ht1 w
00((**+1) 11) + A ++1 + pD h++1 w²),
where the last equality follows from X k+1 = xa p(z Dw
By the first order condition of the w-subproblem and Assumption 3 we have
0 V.g (w - D Xa pD (2 Dw r(w w* VMgn( (wo )- - DJ x + +((00+1 1 -w²).
(23)
Note that VM (1 E 0g (prox (wl+l)) = @g( This completes the proof.
A.3.2 Proof of Lemmal 1
Lemma 5 Under Assumption if0 < cy S 2/- then for mk = 0, 0,1,..., we have
|| - -2 ~0 +²)
w012 2 + 10-1,0 1/01 1 w $12.
where a is the smallest positive eigenvalue of DD
Proof:
By Assumption we have A x++ 2 p(ztt1 Dw E Im(DD. Then we obtain that
| A 12 Lo So T {A - { 112
50 -0- 1 M (w) k+1) VM 1 (w= (12 o _ w 112 0-1,21100* w011
So (0- ?²) || 112 + a 1 1| h-1 w w0111
where the second inequality follows from (23 and the last inequality follows from the fact that Mg.
has 7 Lipschitz continuous gradient when 0 < ey I (7].
Proof of Lemma 1
Proof: By Assumption
3 we have
[, w A²) [= _ X²) 0.
(24)
Since 0 < <c S 3.4 (w) is --sy-1-wekke convex by Lemma
2
By the optimality of w+++1 and
(r- ")----)-strony convexity of the w-subproblem we have
2r
Lp(2*+1, wh, x²) Lz(211 ++1 A 2
1 k+1
(25)
2
By the update of dual variable
Lp k+1 u+1 x²) Lz w+1 x+1
- | 1²112.
(26)
Summing
and (66) we have
Lp(x wº x
Lo k+1 w k+1
x+1) )
2r y-
1 k+1
wº
1 1 p
k+ x x (27)
Finally, we obtain that F.k_ xk+1
2r
2y
= == wh, .
(z(2111 h+1
11111 +
11000 k-1 212
1 10
P0
po
2r --
2,2
2,2
11112 + (- + 1
2(
)| 112
|| 1w 20
111
2
pa
po
P
2(
2r 7-1
4
2
)1
11/20
k+1
||
k+ 1-+1_1 x11
2
op
opr
where the first inequality follows from
27 and the second inequality follows from Lemma
17

---

A.3.3 Proof of Theorem 2
Proof: First note that 0 < ey S 1 so Lemma
holds. Let En == 3c and & ==
2-2
4r² 2
op
ap 2
Using the definitions of 7. p and we have
2r 71
4r2
&
2
00
opp
1
(20pr?² 0p7
8r2
20py
(28)
20C1C2
-01
802 -4
20C2c
En
1
>
20C
20C1
Since (X*) } bounded, we obtain that Lp(2", wh X²) is bounded below by a similar manner of (1 and Assumption Thus T is lower bounded by some $* as well, i.e., $ $*, for Ak Telescoping [14) from k = 1 to K we have:
K
K
1 Φ+ 2
& w h+1 20 +
a
R+1 - 11112.
k=1
k=1
Thus we have:
$1 $
min & E1 k+1 RSK
wx11 122 + || 1 S
K
Let k arg minggr E Eillw - 11111t+1
11 , we have
T : KE
1 1
p( [0] 4z*)
1
-
K
Recall w² prox 9.7 (w"
Note that by 28 & is upper bounded by the constant 2oC1, Letting K 2. by Propositon the definations and p and the above two equations, we have
dist
k+1 on (z*+1) s e|| w*1 = O(e).
DTTh M+1 0g 100 ( s rl| k+1 -0 =(E),
dist
|| Dü D++++1 +1|| < 1| k+1 Dw + + D( w x+1)||
X R+1 X D Oc))
where the second inequality follows from and Assumption This completes the proof.
Our proof of Theorem 2 draws inspiration from 33 Theorem 4.1] and [32]. In our method, we
employ the Moreau envelope Ma,1 instead of g(w) obtain smoothed version of Problem (I). However, the solution obtained through Algorithm may not satisfy the e-KKT conditions of the original problem. Nonetheless, our analysis demonstrates that by setting i prox,,, (w*), our algorithm guarantees an <-KKT point of the original problem in at most ((1/ct) iterations.
B
Additional Experimental Details
B.1
Source Code
The source code is available in the http:///whhlaaoookkkiii///////// basss
18

---

B.2 Experimental Environment
All algorithms are implemented in Python 3.8 and all the experiments are conducted on a Linux server with 256GB RAM and 96-core AMD EPYC 7402 2.8GHz CPU.
B.3 Details for the PAVA
Proposition 3 Given two consecutive blocks [m, ni] and [n 1, they are out-of-order, then we
have
Σ Dimm
Zien+10
P
m + p
Proof: Suppose on the contrary that 1mm.nz] > 1/m+1,pl but
E
E Ei=nt1 03
m
We use the conventions that (a.0) = Ei= (2). For any g E Öl (l(m))))) we must have g 2
because / is monotonically increasing (see the beginning of Section 3.1. Therefore we have
Σ 9
Σ i=m my
71 +1
U/m.n
11
> >
11=++
2 - my
9 +
2/m,n]]
n
11 m7 +
Σ 21=nt1 0;
Σ p
-in+1 mh
9 + 2[m.n]
where the first inequality is due to the non-negativity of and the second inequality due to the fact that m, S M,+1 for m, m mn I,..., P. Note also that
Σ 0s n m 11 + v/m.n)
Dr mi n m +1
E
Oh (m.))) (1)m.n)
n m +
and
L 2i=a+1 0i 9 +
Σ E
mi
1/m.x]]
E
ah +11] (7mm.))
p- n
We also have 0 E al (i) from the optimality condition. This implies that there exists some 8 E Oh|n+11p| (Pim.n)) such that <0. 0.
(1 such that s' > O, then we have 0 0hip-1.pi (1),,))), which contradicts with the uniqueness of the optimal point U|++1.p] hin+1.pl (due its strongly convexity). So must have < 0 for all must have U|m,n] I 1.p+1.p] from the optimality U|x+1.p) to hin+1.p 1.j and convexity hlatl.p) However, this contradicts the fact that [m, rı] and [n + 1, p] are out-of-order.
Now if there exists another s'
oh i 1.pl
(P(m,a)) Then
Proposition 3 presents an additional opportunity to accelerate the PAVA, particularly for the top-k loss and AoRR framework. Consider the case of top-k loss, where o; if 1 and o; 0 otherwise. In this scenario, the condition for merging blocks is satisfied only when i = k. Therefore, we only need examine the block containing k. its preceding block, and its subsequent block. Consequently, the time complexity of searching for out-of-order blocks in line 5 of Algorithm 2 is reduced to O(1).
By leveraging this insight, enhance the efficiency of algorithm, specifically for top-k loss. An analogous acceleration can also be applied to the AoRR loss. This optimization dramatically reduces computational complexity, thereby facilitating faster execution of the PAVA for both top-k loss and AoRR loss.
In our implementation of the PAVA, a minimizer of the convex function hmma)- Assuming the maximum number of iterations for these methods as T, the computation of the minimizer V/mmxs] exhibits time complexity of O(T). In the PAVA, merge out-of-order blocks, the size of the index set J decreases by at least one.
either the bisection method Newton's method to find
19

---

Initially, J comprises n blocks. Hence, the minimizer needs to be computed no more than (n) times throughout the algorithm. Furthermore. before each merge, we perform up ((n) comparisons. However, this complexity is reduced to ((1) for top-k loss and AoRR loss due to the structures of these losses. Overall, the time complexity of our PAVA On + n?). Notably, for top-k loss and AoRR loss, the time complexity is reduced to O(n + nT).
Moreover, in the empirical human risk minimization with CPT-weight in (4). (z(z)) is nonconvex with regard to because σ; is dependent on the value of 2;. Specifically, (z()) takes the form of two-piece function for 2; E (-o0, B] and (B, oo), where represents a certain threshold. However, despite its nonconvexity, 0g (24) remains convex within each piece. Exploiting this property, we can determine the minimizer of such function by comparing the minimizers the two separate pieces. Considering this observation, the overall time complexity of the PAVA for the empirical human risk minimization still O + n
B.4 Datasets Description
Datasets for our experiments generated in two ways.
Synthetic data. We construct synthetic datasets where the data matrix and label vector y are gen- erated artificially. We utilize the datasets makee_ lll_lsssafffaillllleeele cassiiicciio((( function from the Python package scikit-learn sions.
38 to generate two-class classification problem datasets of various dimen-
Real data. In the case of real data, the data matrix X and label vector y are derived from existing datasets. The 'SVMguide' [26] dataset, frequently used in support vector machines, is included in our experiments. We also employ "AD' [29], which comprises potential advertisements for Internet pages, and 'Monks' [50]. the dataset based on the MONK's problem that served as the first international
comparison of learning algorithms. The 'Splice' dataset from the UCI [18] used for the task of recognizing DNA sequences exons or introns. We additionally include 'Australion
'Phoneme' and 'Ti tanic' dataset from [17. Lastly, the 'UTKFace' dataset [53] is used to predict gender based
on facial images. Detailed statistics for each dataset are presented in Table
Table 5: Statistical details of eight real datasets.
Datasets
# Classes
# Samples # Features
Class Ratio
AD
2
2,359
1,558
0.20
SVMguide
3,089
4
1.84
Monks
2
432
6
1.12
Australian
2
690
14
0.80
Phoneme
2
5,404
5
0.41
Titanic
2
2,201
3
0.48
Splice
2
3,190
60
0.93
UTKFace
2
9,778
136
1.24
B.5 Details of Our Algorithm Setting
In the experiments, set the maximum iteration limit in our algorithm to 300. We utilize FISTA to solve the w-subproblem in our algorithm and L-BFGS for the smoothed w-subproblem. For varying frameworks, adopt different choices of [pt), which varies when the iteration number k increase, in Algorithm|] [] To enable the replication of our experiments, we provide a suggested selection for (px). J. The specifies regarding these choices for (px) are detailed in Table We set the y Section
to * max (10-5 x 0.9* 10-9).
B.6 Details of Experiments Setting
Spectral Risk Measures. Our objective demonstrate the versatility of our algorithm and its ability converge to globally optimal solution in the convex problem. Consequently, we utilize two real binary classification problem datasets and several synthetic datasets to highlight the advantages of our algorithm. We compare method with the algorithms in (36). We adapt their implementation
20

---

Table 6: The choices for {p*
Framework
Pa
Pk
SRM
10-5
1.2 Pn (L(k-1)/3] Pg
AoRR
2 10-7
if = D2 10 then Pk = 1.02pk
EHRM
10-4
else pk = 1.077p-1
by replacing the gradient of the Eg norm with the soft threshold operator to incorporate the ε regularization. For simplicity, we set the regularization parameter μa as 0.01 and g as 0.8. The datasets are divided into 60% for training and 40% for testing. Both SGD and LSVRG are run for 2000 epochs and the batch size of SGD is set 64, and the epoch lengths are We give an example of how we choose the learning rate. For comparative purposes, we have chosen the learning rate that yields the lowest objective value single randomized experiment among five different learning rates from {10-2, 110-3,10-3 10-1 smaples 1/ (Namples Nieauurs)): We illustrate this approach using the AD dataset under the SRM superquantile framework as an example. The results are compiled in Table 7 The learning rate corresponding to the bold values, indicating the minimal objective value, is subsequently chosen.
100 as recommended in [36].
Table 7: Objective value in different learning rates for SGD and LSVRG.
Logistic Loss
Hinge Loss
Learning Rate
LSVRG(NU)
LSVRG(U)
SGD
LSVRG(NU)
LSVRG(U)
SGD
g(w) =
0.49612
0.19169
0.16200
0.18016
0.22529
0.11009
0.001
0.15757
0.15753
0.16210
0.08600
0.09591
0.08702
0.0001
0.17936
0.17930
0.27038
0.09270
0.09261
0.11568
I/. samples
0.15761
0.15758
0.16755
0,08609
0.08940
0.08911
samples Nicatures)
0.65849
0.65849
0.68518
0,85333
0,85333
0.96771
g(w)
S |w|l
0.01
0.34731
0.37191
0.27573
0.56240
0,45764
0.17956
0.001
0.26991
0.26986
0.28041
0.16954
0.16959
0.15089
0.0001
0.30385
0.30385
0.38138
0.15621
0.15471
0.18250
I/N camples
0.27084
0,27078
0.28763
0.16805
0.15828
0.15198
1/(Nsamlee Namples Niearure)
0.66741
0.66743
0.68723
0.87358
0.87358
0.97219
Average of Ranked Range Aggregate Loss. We employ the same real datasets those used in 27 Consistent with their experimental setup, we randomly split each dataset into 50% training set, 25% validation set, and 25% test set. As [27] only considered l regularization with μ 10 our experiments in this section also utilize the AoRR aggregate loss with &g regularization. The choice of hyper-parameters i and m and the selection of inner and outer epochs for each dataset follow 27 Table presents the ppprr-parrmeters for individual logistic loss, while 9able/9dispaan those for individual hinge loss.
Empirical Human Risk Minimization. We set = 0.61 and = 0.69 in 5 based on the recommendations in (45) We set B log + exp (-5)) in (4). For simplicity, only &2 regularization. We employ the "UTTFFaee dataset [53], also used in [3T] for gender prediction. The experiments are performed five times with different random seeds. In this experimental segment, we exclusively use the logistic loss as the individual loss since hinge loss has most of the zeros so that it is not easy to determine the corresponding B in (4) which means that its distribution is not suitable for this framework. The cumulative distribution function of loss F is derived from synthetic data, and F(B) approximately equal 0.05. The datasets are divided into 60% for training and 40% for testing. Other settings are similar to those in [31]. In accordance with [31), we divide the population into two groups based on race (white G, and other race G2). However, for simplicity, we only obtain the parameters for gender prediction by minimizing the problem (T) without using a neural network. The parameter settings mirror those Section 5.T We use the same method to get the learning rate, and the learning rate for all three algorithms is set to 1/ (N saammps X N.ccaturs).
21

---

Let TPR denote the true positive rate, FPR the false positive rate, and FNR the false negative rate. Additionally, let X E X' represent the dataset and Y E (0. 1 the label. We utilize the same fairness metrics suggested by [5] as followed in [II. Considering the privileged group G1 S X and the
unprivileged group G2 S X, the definitions of the following metrics are from 31:
Statistical Parity Difference (SPD): P(Y=1) = -
Disparate Impact (DI): P
XeG=)
Equal Opportunity Difference (EOD): TPR (G2) - TPR (G1).
Average Odds Difference (AOD): (FPR (G2) - FPR (G1) + (TPR TPR (G1))).
Theil Index (TI): - In where b, Y; Y, and μ - b,. Here, Y; is the prediction of X; and n represents the number of samples.
False Negative Rate Difference (FNRD): FNR (G2) FNR (G1).
Table 8: AoRR hyper-parameters on real datasets for individual logistic loss.
Datasets
k
Outer epochs
# Inner epochs
Learning rate
Monk
70
2000
0.01
Australian
80
10
1000
0.01
Phoneme
1400
100
10
1000
0.01
Titanic
500
10
10
1000
0.01
Splice
450
50
10
1000
0.01
Table 9: AoRR soper--prameters real datasets for individual hinge loss.
Datasets
k
17
Outer epochs
# Inner epochs
Learning rate
Monk
70
45
1000
0.01
Australian
80
1000
0.01
Phoneme
1400
410
10
500
0.01
Titanic
500
10
500
0.01
Splice
450
50
10
1000
0.01
C Additional Experimental Results
In this section, synthetic datasets labeled 2, 3, and 4 are utilized. Detailed descriptions of datasets 1, 2, 3, and 4 can be found Table TO
Table 10: Details of the synthetic datasets.
Datasets
num sample
num feature
Datasets
num_ sample
num feature
1
1000
500
3
5000
1000
2
2000
1000
4
10000
1000
C.1 Experiments of Synthetic Datasets with ERM
The experimental settings implemented this section are consistent with those discussed in Sec- tion 5.1 The datasets are replaced with the synthetic datasets. We use the same method to get the learning rate for other algorithms. Tables [T [2 and 13 enumerate the mean and standard deviation of the results, primarily focusing on the objective value and test accuracy. 'sADMM' stands for the ADMM applied to the smoothed problem. Tables TT 12] and 13 show that under most scenarios
in the ERM framework, ADMM algorithm exhibits superior performance in terms of objective
22

---

values when compared to existing methods. This superiority is particularly evident in instances of hinge loss, with the algorithm demonstrating test accuracy that is analogous to other methods.
Figure ggrphicalll demonstrates the correlation between time and sub-optimality for each algorithm within the superquantile framework and hinge loss, which represents a convex problem whose global optimum is achievable. The figure indicates that ADMM displays more rapid convergence towards the minimum relative to other algorithms. While SADMM does not match the performance of ADMM, it does achieve a commendable rate of convergence when compared to other algorithms.
Table 11:
Results in synthetic datasets with SRM ERM framework and & regularization. 'objval' denotes the objective value of problem
Logistic
Hinge Lass
Datasets
ADMM
LSVRG(NU)
LSVRGUU)
SGD
ADMM
LSVRGINU)
LSVEGUU)
SGD
objval
0.0923 (0.055)) 0,0923 (0.0057) 0.0923 (0,0015)) 0.0923 (0.0057) 0,0088 (0.0011) 0.0095 (0.0013) 0.0066 (0,0012) 0.0091 (0.001
Accunacy
0,7875 (0.0113) 0.7875 (0.0113) 0.7875 (0,1113) 0,7875 (0.0113) 0,7590 (0.0185) 0.7770 (0.0143) 0.7765 (0.0153) 0,7760 (0.0171)
objval
0.0800) (0.0012) 0,0800 (0.0012) 0.0800 (0,0012) 0.08 (0.0012) 0.0068 (0 (000)))) 0.0075 (0.0004) 0.0075 (0.0003) 0.0071 (0.0002)
2
Accuracy
0,8483 (0.0115) 0,8485 (0.0111) 0.8485 (0.0111) 0,8485 (0.0111) 0,8193 (0.0079) 0,8350 (0,0072) 0,8325 (0.0065) 0,8303 (0. (0.0060)
objval
0,1704 (0.0037) 0.1704 (0.0037) 0.1704 (0.0037) 0,1704 (0.0033) 0,0732 (0.0045) 0.0807 (0.0047) 0.0809 (0.0044) 0,0756 (0.0046)
Accunacy
(0.0039) 0,8347 (0,0039) 0.8347 (0,0039) 0.8341 (0.0035) 0.7999 (0.0091) 0.8138 (0.0075) 0.8135 (0,0053) 0,8091 (0.0080)
objval
0.1395 (0.0014) 0.1395 (0.0014) 0.1395 (0,0014) 0.1395 (0 (0.0014) 0.0664 (0.0020) 0.0716 (0.0021) 0.0716 (0.0022) 0.0667 (0.0020)
Accuracy
0,9:100 (0.00141) 0.9401 (0.0014) 0.9401 (0.0014) 0,9102 (0.0014) 0.9250 (0.0016) 0,9330 (0.0029) 0,9330 (0.0023) 0,9261 (0.0019)
Table 12: Results in synthetic datasets with SRM ERM framework, l regularization, and logistic loss. 'objval' denotes the objective value of problem !I.
Datasets
ADMM
SADMM
LSVRG(NU)
LSVRG(U)
SGD
objval
0.1829 (0.012) 0.1829 (0.012) 0.1829 (0.012) 0.1829 (0.012) 0.1845 (0.0118)
Accuracy
0.8490 (0.0076)
0.8495 (0.0087) 0.8490 (0.0076)
0.8495 (0.008) 0.8500 (0.0079)
objval
0.1693 (0.0037) 0.1693 (0.0037) 0,1693 (0.0037)
0.1693 (0.0037) 0.1729 (0.0037)
2
Accuracy 0,9190 (0.0061) 0.9193 (0.0061) 0.9190 (0.0061) 0.9190 (0.0061) 0.9193 (0.0056)
objval 0,2584 (0.0049) 0.2584 (0.0049) 0.2585 (0.0049) 0,2585 (0.0049) 0.2596 (0.0049)
3
Accuracy 0,9005 (0.0053) 0.9005 (0.0053) 0.9005 (0.0053) 0.9005 (0.0053) 0.9005 (0.0051)
4 objval 0.1475 (0.0037) 0.1476 (0.0037) 0.14 (0.0037) 0.1479 (0.0037) 0.1495 (0.0037)
Accuracy 0.9599 (0.0026) 0.9599 (0.0027) 0.9599 (0.0027) 0.9599 (0.0027) 0.9599 (0.0025)
Table 13: Results in synthetic datasets with SRM ERM framework, L regularization, and hinge loss.
'objval' denotes the objective value of problem II.
Datasets
ADMM
SADMM
LSVRGNNU)
LSVRG(U)
SGD
objval
0.0777 (0.0075)
0.0782 (0.0074)
0.0856 (0.0087) 0.0856 (0.0088)
0.0802 (0.0076)
1
Accuracy
0.8095 (0.0200)
0,8085 (0.0181)
0,8000 (0.0181)
0.7995 (0.0181)
0.8045 (0.0192)
objval
0.0786 (0.0023)
0.0790 (0.0023)
0.0877 (0.0022)
0.0876 (0.0023)
0.0836 (0.0023)
2
Accuracy
0.8880 (0.0143)
0.8895 (0.0148)
0,8823 (0.0121) 0.8833 (0.0105)
0.8848 (0.0130)
objval 0.1983 (0.0058)
0. 0.1985 (0.0058)
0.2038 (0.0057) 0.2037 (0.0058)
0.2006 (0.0058)
3
Accuracy
0,8783 (0.0056)
0.8776 (0.0057)
0.8770 (0.0061) 0.8780 (0.0057)
0,8783 (0.0048)
objval
0.1192 (0.0031)
0.1199 (0.0031)
0.1229 (0.0042)
0.1221 (0.0027)
0.1206 (0.0030)
4
Accuracy
0.9563 (0.0018)
0.9565 (0.0015) 0.9564 (0.0020) 0.9564 (0.0021)
0.9561 (0.0019)
C.2 Experiments of Synthetic Datasets with AoRR
In the application of AoRR to synthetic data, we have configured the parameters i and m to be 0.8 and 0.2 times the size of the training set, respectively. In other words, = [0ainn and vn [0.2.Nr.an 7. We maintain the learning rate in the DCA at 0.01, and set the outer epoch at 10, and the inner epoch at 2000. The parameters for SGD and L.SRRG are identical to those employed in the preceding experiment (the learning rate is chosen from the same method). Tables 14 and 15
23

---

(b)
FuTs vemple 2000 suth Presurte 508
Fur vample 2030 vum, Natve 1006
num cample Sree rus feaurr
zum sample 10000 Ialuum:
(e)
(h)
Figure 2: Time vs. Sub-optimality gap in synthetic datasets with superquantile framework. (a-d) for l2 regularization, and (e-f) for E regularization. Sub-optimality is defined as F - FF where F represents the objective function value at the k-th iteration or epoch and F* denotes the minimum value obtained by all algorithms. Plots are truncated when pk. F 10-8
enumerate the mean and standard deviation of results for the objective value, accuracy, and time. careful examination of Tables 14 and 13 suggests that our algorithm, in most scenarios, achieves lower objective values and comparable accuracy shorter time span relative existing methods.
Table 14: Comparison with AoRR framework, k loss. objvva'' denotes the objective value of problem
1088 N. m [0.2 x Nirain and logistic
Datosess
LSVRGINU)
LSVRG(U)
objval
1.75x10-> ( 7.12x10"' (1.91x11-2) 2.10x10 210xx00"((556x00
2.14x10 (L.1xx00
1.65x10-"
Accumey
0.7641 (10429)
(00325))
0.7514 (0.0399)
0.7304 (0.0151)
0.7737 (0.0312)
Time
11.43 (087)
(2188
(8.13)
(7.56)
(1.17)
objval
141x10-> (2.9x10-2))
7.22x10-)
(2.73x10-2)
1.7x100
(3.85x0000))
181x10 1.81x10-"(7.6xx (7.96x
2.21
202
(5.86x 10-1)
Accumey
08283 (00073))
0.315 (0.190)
0.8248 (0.0158)
0.808 (0.0094)
0.8427 (0.0139)
Time
(1.98)
107.27 (2081)
(12.14
(2.62
(11.56)
objyal
2.75 2075x100" (6.8xx10-)) 7.49x 10 (122xx10-2)
3.00x 10 (
3.07x10-) 10
3.33 3.33 (1.3x0000((00000000100001 x1.09x100 10mf)
Accuracy
0,8149 (0.0109)
0,7936 (0.0112)
0,8083 (0.0095)
0.8075 (0.012)
0.8222 (0.0058)
Time
56.95 56.95 (2.07)
(27.18((1.86) (19.6)
(14.0))
149.78 (8.62)
746.75 (72.28
objyal
3.24x 10 (3.13x10**)
7.43x 12
3.23 10 x3.05x100>)
3.27 (3.99x 10
3.20
(3.39 x3.39x100' 10"2)
Accuracy
0,9417 (0.0039)
0,9302 (0.0045)
0,9325 (0.0066)
0.9273 (0.0018)
0.9385 (0.0044)
Time
222.35 (19.30)
154.46 (43.0)
222.37 (62.44)
(64.40)
3237.42237.7
C.3
Experiments about Figure
We increased the sample size to further observe the performance of our algorithm and the experimental results are shown in Figure It can be seen that both ADMM and SADMM exhibit relatively fast convergence compared to other algorithms. An interesting phenomenon is that in the case a large amount of data, random algorithms are able achieve decent results in the early stages of optimization. The underlying reason for this phenomenon may be that existing methods use mini-batch samples that are independent of the sample size to update model parameters, thereby reducing the computational cost per iteration. This allows existing methods to update parameters more frequently, leading to faster convergence in the early stages of optimization. In contrast, the proposed algorithm uses the entire batch of samples in each iteration, resulting in slower iteration speeds. This leads to suboptimal solutions the early stages compared to existing methods. In Appendix B.3] we provide detailed explanation of the time complexity of the PAVA, which is O(n + nT) for top-k loss and AoRR loss, where represents the maximum number of iterations when solving each PAVA subproblem, and n represents the sample size. Therefore, with an increase in
24

---

Table 15: Comparison with AoRR framework, k 10.8 x Nvrain
[0.2 x Nunin and hinge
loss. "objval' denotes the objective value of problem
ADMM
LSVRGINU)
LSVRG(U)
SGD
objeal
2097x10 > (1.92 11 9.9x10 (2.6610-3)
1.71 ( (1.49x10"9) 11.2x10-"11.Mx110 (1.38x10-1) 3.8x10 (2.34x10-))
Accuracy
0,7700 (0.0371)
(0.40))
0.7600 (0.0427)
0.7620 (0.415)
0.7680
Time
4.37 (0.56)
137.22 (28.90)
(3.66)
(14.37
286.19
objeal
2,12x 10"2x100" (6.51x100")
1.0x (2.66x10"9)
7,05x10"* (5.90x10-))
1,21 1.21 (3885:10-))
2.42x10-2
(5.20x10-7)
Accuracy
0,8320 (0,0093)
(0.009)
(0.0277)
0.8380 (0.0093)
Time
5.54 (0.64)
172.5 172.5
104.79 (2.87)
93.35 93.35(3300)
352.67 (4.98)
abjval
4.82 10 10
9.89x10-1 (1.90x10-9)
2 (9.19x10-5)
2.78x10-
(4-43x10-5)
6.30x10- (2-01x10-9)
Accuracy
0.8130 (0.0113)
(0.008))
0,8100 0.1100 (0.0101)
0.8070 (0.0135)
0.8180 (0.0066)
Time
15.36 (0.70)
290.7 290.7 (26.15)
112.68 (8.08)
99.52 (4.88)
540.62 (66.63)
objval
x (1.59x10 f> 9.82x10 (2.51x10*))
1,22110 (3.17x10'')
(3.85x10
8.16x10 (1.00x10"
Accuracy
0.9430 (0,0053)
0,9360 (0.0046)
0.9310 (0.0049)
0.9240 (0.0028)
0.9350 (0.0048)
Time
(3.44
396.03 (31.66)
129.22 (14.09)
115.06 (8.16)
(824422
sanaa 2000
OVtre we1
CN 204 UNG
Figure 3: Time vs. Sub-optimality gap in synthetic dataset with ERM framework and & regularization. The datasets with the same number of samples are generated by different random number seeds. Sub-optimality is defined as F F+, where F represents the objective function value at the k-th iteration or epoch and 1* denotes the minimum value obtained by all algorithms. Plots are truncated when pk P 10-8
sample size, the time required for our proposed algorithm will also increase. Nevertheless, compared to existing algorithms, we are still able achieve higher accuracy within a reasonable time frame.
25


Reviews:
[{"review_id": "FQzkTxjvS5", "reviewer": "Reviewer_Gyag", "summary": "This paper proposes a unified framework for rank-based loss minimization based on the ADMM algorithm. The paper proposes to apply a pool adjacent violators (PAV) algorithm to solve one of the subproblems of ADMM. Numerical experiments show that the proposed algorithm outperforms the existing ones.", "questions": "- Can the proposed method be applied to nonlinear models?", "limitations": "Limitations are not discussed in the paper.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The problem of rank-based loss minimization is very important.\n+ The proposed PAV algorithm looks interesting.\n+ Convergence of the algorithm is theoretically analyzed.", "weaknesses": "- It seems that Eq.(1) assumes a linear model and it is unclear how to generalize to non-linear settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer Gyag for the feedback and comments!\n\nEq. (1) indeed assumes a linear model. One reason for making this assumption is that currently, many studies or experimental parts related to rank-based loss predominantly concentrate on linear models [1-3]. So far, there has been limited research on ADMM with nonlinear constraints. However, as stated below, our method can be applied to non-linear models.\n\n**Applying the method to a non-linear model**\n\nThe linear model in Eq. (1) can be replaced with a non-linear model. The rank-based loss in Eq. (1) can be rewritten as follows: \n\\begin{equation}\n\\Omega(\\boldsymbol{w}):=\\sum_{i=1}^{n} \\sigma_i \\boldsymbol{l}_{[i]}\\left(- \\boldsymbol{y} \\odot (h(\\boldsymbol{w}))\\right)\n\\end{equation}\nwhere $h(\\boldsymbol{w}):\\mathbb{R}^d\\to\\mathbb{R}^n$ is a differentiable non-linear function.\n\nLet us explain how to adapt the ADMM algorithm. Now the constraint in eq. (9)  should be $\\boldsymbol{z} = Dh(\\boldsymbol{w})$, where $D = -\\text{diag}(\\boldsymbol{y})$. Information about the samples $X$ is encompassed in $h(\\boldsymbol{w})$, but to maintain consistency in notation, we still retain $D$. The $z$-subproblem is the same as the linear model version.\n\nIn order to keep our theory still valid, we need to make modifications in the following two aspects:\n\n**1. Solving $w$-subproblem**\n\nDue to the inclusion of the non-linear term $h(\\boldsymbol{w})$, the $\\boldsymbol{w}$-subproblem may no longer be strongly convex, leading to potential inability to exactly solve the $\\boldsymbol{w}$-subproblem. To overcome this limitation, we assume $\\boldsymbol{w}$-subproblem is solved inexactly such that $\\text{dist}\\left(0,\\partial_{\\boldsymbol{w}} L\\_\\rho\\left(\\boldsymbol{z}^{k+1},\\boldsymbol{w}^{k+1},\\boldsymbol{\\lambda}^{k}\\right)+r(\\boldsymbol{w}^{k+1}-\\boldsymbol{w}^{k})\\right)\\leq O(\\epsilon)$, where $\\epsilon$ is the accuracy in Theorems 1, 2.  Moreover, we assume the solution to the $\\boldsymbol{w}$-subproblem is an $\\epsilon_k$ optimal solution ($\\epsilon_k\\geq 0$) and $\\sum\\_{k=1}^{\\infty}\\epsilon\\_k<\\infty$. We say $\\hat{x}$ is an $\\tilde{\\epsilon}$ optimal solution for $\\min_x f(x)$ if $f(\\hat{x})\\leq \\min_x f(x) +\\tilde{\\epsilon}$. \n\nIn this way, we can obtain the descent of $\\boldsymbol{w}$-subproblem:\n$$\nL_\\rho(\\boldsymbol{\\boldsymbol{z}}^{k+1},{\\boldsymbol{w}}^k,\\boldsymbol{\\lambda}^k)\\geq L_\\rho(\\boldsymbol{\\boldsymbol{z}}^{k+1},{\\boldsymbol{w}}^{k+1},\\boldsymbol{\\lambda}^k) +\\frac{r}{2}\\\\|{\\boldsymbol{w}}^{k+1}-{\\boldsymbol{w}}^k\\\\|^2-\\epsilon_k.\n$$\n\n**2. Convergence guarantee of our algorithm**\n\nWe need the following additional assumptions to guarantee the convergence of the algorithm:\n- $h(\\boldsymbol{w})$ and $\\nabla h(\\boldsymbol{w})$ are Lipschitz continuous in any sublevel sets.\n- $\\boldsymbol{\\lambda}^k \\in Im(D\\nabla h(\\boldsymbol{w}^k))~ \\forall k$.\n\nThe first controls $\\\\|\\boldsymbol{w}^{k+1}-\\boldsymbol{w}^k\\\\|$ by $\\\\|h(\\boldsymbol{w}^{k+1})-h(\\boldsymbol{w}^{k})\\\\|$ or $\\\\|\\nabla h(\\boldsymbol{w}^{k+1})-\\nabla h(\\boldsymbol{w}^{k})\\\\|$. The latter is introduced to replace Assumption 4 in our paper.\n\nAs a result, our main findings can be rewritten as follows:\n\n**Theorem 1 (modified)**   Under the same assumptions and settings as in Theorem 1, along with the two additional assumptions mentioned above,  Algorithm 1 can find an $\\epsilon$-KKT point $(\\boldsymbol{\\boldsymbol{z}}^{k+1},{\\boldsymbol{w}}^{k+1},\\boldsymbol{\\lambda}^{k+1})$ within $O(1/\\epsilon^2)$ iterations, i.e.,\n      \\begin{equation} \n        \\text{dist}\\left(-\\boldsymbol{\\lambda}^{k+1},\\partial\\Omega\\left(\\boldsymbol{\\boldsymbol{z}}^{k+1}\\right)\\right)\\leq \\epsilon,\\quad\n                   \\text{dist}\\left(\\left(D\\nabla h(\\boldsymbol{w}^{k+1})\\right)^T{\\boldsymbol{\\lambda}}^{k+1},\\partial g\\left(\\boldsymbol{w}^{k+1}\\right)\\right)\\leq O(\\epsilon),\\quad\n        \\\\|\\boldsymbol{\\boldsymbol{z}}^{k+1}-D{\\boldsymbol{w}}^{k+1}\\\\|\\leq \\epsilon.\n    \\end{equation}\n\n**Theorem 2 (modified)** Under the same assumptions and settings as in Theorem 2, along with the two additional assumptions mentioned above (Assumption 4 is no longer required),  Algorithm 1 can find an $\\epsilon$-KKT point $(\\boldsymbol{\\boldsymbol{z}}^{k+1}, {\\tilde{\\boldsymbol{w}}^{k+1}},\\boldsymbol{\\lambda}^{k+1})$ within $O(1/\\epsilon^4)$ iterations, i.e.,\n\n\\begin{equation}\n        \\text{dist}\\left(-\\boldsymbol{\\lambda}^{k+1},\\partial\\Omega\\left(\\boldsymbol{\\boldsymbol{z}}^{k+1}\\right)\\right)\\leq \\epsilon,\\quad\n        \\text{dist}\\left(\\left(D\\nabla h(\\tilde{\\boldsymbol{w}}^{k+1})\\right)^T{\\boldsymbol{\\lambda}}^{k+1},\\partial g\\left(\\tilde{\\boldsymbol{w}}^{k+1}\\right)\\right) \\leq O(\\epsilon),\\quad\n        \\\\|\\boldsymbol{\\boldsymbol{z}}^{k+1}-D\\tilde {\\boldsymbol{w}}^{k+1}\\\\|\\leq \\epsilon.\n    \\end{equation}\n\n**The potential practical limitations of the proposed method**\n\nTo ensure the effective utilization of our algorithm, it is crucial for the individual loss to demonstrate monotonicity. This property enables the application of the PAV algorithm for solving the $z$-subproblems. Some examples of loss functions that satisfy this criterion include logistic loss, hinge loss, and exponential loss. On the other hand, when confronted with a substantially large sample size, the computational efficiency of the PAV algorithm could be impacted, thereby potentially constraining the overall effectiveness of the entire algorithm. We will point out the limitations in our paper.\n\n**References**\n\n[1] Mehta, R., Roulet, V., Pillutla, K., Liu, L., & Harchaoui, Z. (2023, April). Stochastic Optimization for Spectral Risk Measures. In International Conference on Artificial Intelligence and Statistics (pp. 10112-10159). PMLR.\n\n[2] Hu, S., Ying, Y., & Lyu, S. (2020). Learning by minimizing the sum of ranked range. Advances in Neural Information Processing Systems, 33, 21013-21023.\n\n[3] Leqi, L., Prasad, A., & Ravikumar, P. K. (2019). On human-aligned risk minimization. Advances in Neural Information Processing Systems, 32."}, {"review_id": "ADcRoRuGVc", "reviewer": "Reviewer_GkCz", "summary": "This paper presents a new ADMM algorithm that focuses on three specific cases of rank-based losses. The algorithm's convergence is theoretically analyzed in the paper. Additionally, the authors conducted comprehensive experiments to compare the new algorithm with traditional approaches. The results indicate that the proposed algorithm outperforms traditional methods in terms of both efficiency and effectiveness.", "questions": "Please see the above comments about  the Weakness. ", "limitations": "None", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors proposed a new algorithm that can address three specific cases of rank-based losses, whereas traditional algorithms like SGD, DCA, and LSVRG can only handle one. Additionally, the new algorithm permits the regularization term to be a weakly convex function.\n2. The authors' theoretical analysis of the new algorithm's convergence is a significant contribution that has not been achieved in previous work.\n3. To demonstrate the advantages of the new algorithm, the authors conducted comprehensive experiments. The results show that the new algorithm generally outperforms existing methods in terms of both efficiency and effectiveness. Overall, this study provides valuable insights into the development of more efficient and effective algorithms for rank-based losses.", "weaknesses": "Significant Issues (Detailed Explanation Required)\n1.The representation of the loss vector function in line 23 is unclear. If function l maps an n-dimensional column vector to a real number, how a comparison of magnitude can be made later on?\n\n2.As is widely known, due to the unknown underlying distribution of the data, we can only optimize the discrete form of risk expectation, which is the arithmetic mean of n observations. The theoretical basis for doing so is that the arithmetic mean converges in probability to the expectation. Therefore, could you please explain the theoretical basis for the discrete form of spectral risk that you employed in lines 78-79.\n\n3.Could you please clarify how the conclusion stated in line 116 was derived? If it is a result obtained from citing other papers, please provide the source. If it is a result you have proven yourself, please provide a detailed proof.\n\n4.In line 159, definitions for two consecutive blocks disorder are provided, but definitions for three or more consecutive block disorder are missing.\n\n5.In line 6 of Algorithm 2, it is not possible to select the disordered blocks because definitions for three or more consecutive blocks disorder have not been provided.\n\n6.In line 6 of Algorithm 2, you assume that the optimal solutions for  are equal to each other. Could you please a more detailed proof or a citation if the conclusion is derived from another paper?\n\n7.In line 225, you stated that Assumptions 4 and 5 are weaker than Assumption 2. Please provide a detailed explanation for this claim.\n\n8.Could you please provide specific information on the loss functions and regularizers used in the experiments in Sections 5.2 and 5.3?\n\nMinor issue (needs improvement).\n\n1.The \"l\" in line 23 and the \"l\" in line 71 have different meanings. It’s suggested to use distinct notations to indicate this difference.\n\n2.In Equation (1), the independent variable of  is , where  is a d-dimensional column vector. However, the independent variable of  is written as an n-dimensional column vector in line 24.\n\n3.Line 71 should use lowercase \"d\" instead of uppercase.\n\n4.In line 85, please provide a brief explanation of the term \"fairness\".\n\n5.There is a missing negative sign in line 127.\n\n6.In line 154, \"\" should be in lowercase.\n\n7.The explanations in lines 169-170 appear to contradict the explanations in lines 187-188.\n\n8.To avoid confusion among readers, please use a consistent notation for the loss function \"\" in lines 71, 125, and 194.\n\n9.Please provide an explanation for \"dist\" as used in line 249 at its initial occurrence in line 212.\n\n10.The placement of \"Dataset\" in Tables 1 and 2 is inconsistent.\n\n11.Please use the notation \"new-ADMM\" to distinguish the modified version of the traditional ADMM algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer GkCz for the feedback and comments!\n\n**The confusion in notations for the loss function**\n\nWe apologize for the confusion. We should only use the definitions of $l$  and $\\boldsymbol{l}$ as follows:\n\n1. $l$: $\\\\mathbb{R}\\\\to\\\\mathbb{R}$: a  function that represents the loss for an individual sample.\n2. $\\\\boldsymbol{l}$: $\\\\mathbb{R}^n\\\\to\\\\mathbb{R}^n$: a vector-valued function whose $i$-th element represents the individual loss for the $i$-th sample. \n\nWe will correct all the places where the loss function is used incorrectly.\n\n**Theoretical basis for the discrete form of spectral risk**\n\nThe discrete form of the spectral risk converges to the spectral risk of the population distribution, governed by Wasserstein distance. Please refer to [Proposition 1, 1].\n\n**Conclusion about Moreau Envelope**\n\nThe proximal operator of a $c$-weakly convex function $g$ is $\\\\operatorname{prox}_{g,\\\\gamma}(w)=\\\\arg\\\\min _{x\\\\in\\\\mathbb{R}^d}\\\\left\\\\{g(x)+\\\\frac{1}{2 \\\\gamma}\\\\|x-w\\\\|^2\\\\right\\\\}$. According to the definition of the weakly-convex function in line 106 and given $0 < \\\\gamma < \\\\frac{1}{c}$, the function $\\\\mathbb{R}^d \\\\ni x\\\\to g(x)+\\\\frac{1}{2\\\\gamma} \\\\|x-w\\\\|^2\\\\in\\\\mathbb{R}$ is strongly convex for all $w\\\\in\\\\mathbb{R}^d$, thus its argmin is always a singleton. \n\nFurthermore, $ M_{g,\\\\gamma}(w)=\\\\min_x\\\\left\\\\{g(x)+\\\\frac{1}{2 \\\\gamma}\\\\|x-w\\\\|^2\\\\right\\\\}=g(\\operatorname{prox}\\_{g,\\gamma}(w))+\\\\frac{1}{2\\\\gamma}\\\\|\\\\operatorname{prox}_{g,\\\\gamma}(w)-w\\\\|^2 $ is well-defined. A detailed proof can be found in [Proposition 3.1, 2].\n\n**Explanation of PAV algorithm**\n\nSorry for missing the definition for three or more consecutive out-of-order blocks, which is similar with two consecutive out-of-order blocks. That is, if $v_{[s_k,s_{k+1}]} > v_{[s_{k+1} + 1,s_{k+2}]} > \\cdots > v_{[s_{k+t}+1,s_{k+t+1}]}$, then $\\\\{[s_k,s_{k+1}],[s_{k+1} + 1,s_{k+2}], \\cdots , [s_{k+t}+1,s_{k+t+1}]\\\\}$ are consecutive out-of-order blocks. For example, if $v_{[1,2]}<v_{[3,3]}<v_{[4,5]}>v_{[6,6]}>v_{[7,7]}<v_{[8,8]}$, then $\\\\{[4,5], [6,6], [7,7]\\\\}$ are a consecutive out-of-order blocks. \n\n\nSorry that the statement in line 169-170 is unclear.\nWe should point out that in  $\\theta_i(z_i)=\\sigma_i l(z_i)+\\frac{\\rho}{2}(z_i-m_i)^2$,  $\\sigma_i$ is constant for the spectral risk loss or the ranked-range loss, but $\\sigma_i$ is a function of $z_i$ in the human risk loss as it depends on the value of $z$ being larger than or less than the reference point $B$ (see  eq. (4)).\nSo for cases that $\\sigma_i$ is a constant, $\\theta_i$ is a convex function, and the acceleration procedure via merging multiple consecutive out-of-order blocks is applicable. However, for human risk minimization, $\\theta_i$ is not convex, and we do not adopt this acceleration anymore.\n\nIn line 6 of Algorithm 2, we do not assume \"that the optimal solutions for are equal to each other.\"\nThis is a step of the PAV algorithm. In this step, we enforce to solve the problem $\\min_z \\sum_{i=s_k}^{s_{k+t+1}}\\theta_i(z)$, where the optimal solution is $v_{[s_k,s_{k+t+1}]}$. This step is called  \"merge the consecutive out-of-order blocks.\"\n\nWhen $\\theta_i$ are all convex functions, the PAV algorithm returns a global minimum, which is proved in [3]. For human risk minimization, the PAV algorithm finds a point that satisfies the first-order condition, which is proved in [Theorem 3, 4].\n\n**Statement about assumptions**\n\nSorry that the statement that Assumptions 4 and 5 are weaker than Assumption 2 may not be accurate. It is preferable to state that Assumptions 4 and 5 are more practical than Assumption 2, as they are easier to verify in practice. As mentioned in line 226-234, the full row rank property of the data matrix is often assumed in the high dimensional setting classification and Assumption 5 is satisfied by weakly convex functions that are Lipschitz continuous. \n\n**Specific information on experiments**\n\nSure. We will present the formulations in Section 5.2 in the manuscript.\nIn Section 5.2, we used logistic loss and $\\ell_2$ norm regularizer. In Section 5.3, we used both logistic loss and hinge loss and $\\ell_2$ norm regularizers as in [5]. Detailed information on loss functions, regularizers, and other settings can be found in Appendix B.5.  \n\n**Typos and Minore issues**\n\nThank you for pointing out our typos and suggestions in the Minor issue. We will make the necessary corrections in the subsequent manuscript. Here we provide a detailed explanation of two points.\n\nFor Minor issue 4, fairness means that our predictions remain consistent across different groups. For example, in the examples used in the experimental section, we examine whether there are differences in predictions between different races when predicting gender. The fairness metrics are detailed in Appendix B.5.\n\nFor Minor issue 5, since we set $D=-\\text{diag}(\\boldsymbol{y})X$ in line 125, the expression $\\boldsymbol{z}=D\\boldsymbol{w}$ in line 127 is correct.\n\n**References**\n\n[1] Mehta, R., Roulet, V., Pillutla, K., Liu, L., & Harchaoui, Z. (2023, April). Stochastic Optimization for Spectral Risk Measures. In International Conference on Artificial Intelligence and Statistics (pp. 10112-10159). PMLR.\n\n[2] Hoheisel, T., Laborde, M., & Oberman, A. On proximal point-type algorithms for weakly convex functions and their connection to the backward Euler method. Optimization Online.\n\n[3] Best, M. J., Chakravarti, N., & Ubhaya, V. A. (2000). Minimizing separable convex functions subject to simple chain constraints. SIAM Journal on Optimization, 10(3), 658-672.\n\n[4] Cui, X., Jiang, R., Shi, Y., and Yan, Y. (2023). Decision making under cumulative prospect theory: An alternating direction method of multipliers. arXiv preprint arXiv:2210.02626.\n\n[5] Hu, S., Ying, Y., Lyu, S., et al. (2020). Learning by minimizing the sum of ranked range. Advances in Neural Information Processing Systems, 33:21013–21023."}, {"review_id": "udM9kmQj2v", "reviewer": "Reviewer_G6DJ", "summary": "This submission focuses on efficient minimization of a group of loss functions called rank-based losses. It proposes to consider several related losses from the perspective of a genral unified framework with a regularizer. Then, focusing on the case of monotone increasing loss functions and wealy convex regularizers, it proposes an ADMM-based algorithm and shows its convergence rate under common assumptions. Furthermore, when the regularizer is non-smooth, it then extends the proposed algorithm with weaker assumptions and also shows its convergence rate. Sufficient numerical verification shows the satisfying empirical performance of the proposed algorithm compared with several existing methods.\n", "questions": "- Is equation (1) first proposed by this paper, or it has been somehow mentioned in related publications?\n- In Figure 1 (h), it seems like existing methods can take advantage of more data at the beginning of optimization. How this trend changes when more samples are available? Is there some theoretical explainable available for the phenomenon?\n", "limitations": "No potential negative societal impact needs to be addressed.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\n- The task provides a new perspective on an important problem and the proposed methods improving ADMM are novel.\n- Authors clearly address where exactly the improvements from existing methods are.\n- Related literature review is adequate and detailed.\n\nQuality:\n- The submission is technically rigid.\n- Claims are well-supported by its clear presentation. Adequate theoretical and empirical results are presented.\n\nClarity:\n- The submission is clearly written and easy to follow. It is very well organized and the story line expands naturally.\n\nSignificance:\n- The results are important to the field. Others are very likely to use the results as a baseline method or build extensions upon it.\n\n", "weaknesses": "- It would be more pursuative to elaborate on potential practical limitations of the proposed method. For example, under what case the proposed method may not function efficiently.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer G6DJ for the positive feedback and comments!\n\n**The potential practical limitations of the proposed method**\n\nTo utilize our algorithm effectively, it is essential for the individual loss to exhibit monotonicity, as this allows us to employ the PAV algorithm to solve the $z$-subproblems. However, on the other hand, when dealing with a considerably large sample size, the computational efficiency of the PAV algorithm might be affected, potentially limiting the overall effectiveness of the entire algorithm. We will point out the limitations in our paper.\n\n**More information about equation (1)**\n\nIn other papers, we have also observed similar equation representations. For example, in [1], the authors presented a similar equation as follows,\n\n\\begin{equation}\n\\mathcal{R}_\\sigma(\\boldsymbol{w})+\\frac{\\mu}{2}\\\\|\\boldsymbol{w}\\\\|_2^2 \\quad \\text { for }  \\\\mathcal{R}\\_\\\\sigma(\\\\boldsymbol{w}) = \\sum\\_i \\sigma_i \\boldsymbol{l}\\_{[i]}(\\boldsymbol{w})\n\\end{equation}\n\nwith $0 \\leq \\sigma_1 \\leq \\dots \\sigma_n \\leq 1, \\sum_{i=1}^n \\sigma_i=1$. We replace $\\boldsymbol{l}\\_{[i]}(w)$ by $\\boldsymbol{l}\\_{[i]}\\left(- \\boldsymbol{y} \\odot (X\\boldsymbol{w})\\right)$ in order to obtain easily solvable subproblems of the ADMM algorithm. Moreover, in equation (1), we only require $\\sigma_i\\geq 0$, which includes a wider range of ranked-based losses, and allow $\\sigma_i$ (in $\\sigma_i(z_i)l(z_i)$) have different values depending on the values of $z_i$ being larger than or less than the reference point, which includes the human risk loss. \n\nWe sincerely apologize for the typos in equation (1) which should be $\\boldsymbol{l}:\\mathbb{R}^n \\to \\mathbb{R}^n$ and $g: \\mathbb{R}^d \\to \\mathbb{R}$.  Here $\\boldsymbol{l}:\\mathbb{R}^n \\to \\mathbb{R}^n$ represents a vector-valued mapping, where its  $i$-th element represents the individual loss for the $i$-th sample.\n\n**The explanation about Figure 1 (h)**\n\nThis is a very interesting observation. Following your question, we varied the random seed to generate different datasets to eliminate the impact of randomness, and we still observed the same phenomenon across different datasets;\nmoreover, we increased the sample size to explore trends, but the phenomenon remained unchanged. \nThe corresponding experimental plots are included in the submitted PDF file.\n\n\nThe potential reason for this phenomenon could be that existing methods update their model parameters using a mini-batch of the sample that is independent of the sample size, resulting in lower computational costs per iteration. This enables other algorithms to update parameters more frequently, leading to faster convergence at the beginning of optimization. In contrast, the proposed algorithm uses the full batch of the sample in each iteration, so each iteration is slower. This, in turn, leads to inferior solutions compared to existing methods at the beginning of optimization. In Appendix B.2, we provide a detailed explanation of the time complexity of the PAV algorithm, which is $O(n + nT)$ for top-k loss and AoRR loss, where $T$ represents the maximum number of iterations when solving each PAV subproblem and $n$ is the sample size. As a result, as the sample size increases, the time required by our proposed algorithm increases. Nevertheless, we can still achieve higher accuracy within a reasonable time frame compared to existing algorithms.\n\nIn future research, we will aim to develop a variant of the proposed algorithm that uses a mini-batch of samples instead of using the full batch to achieve better initial solutions at the beginning of optimization. \n\n**Reference**\n\n[1] Mehta, R., Roulet, V., Pillutla, K., Liu, L., & Harchaoui, Z. (2023, April). Stochastic Optimization for Spectral Risk Measures. In International Conference on Artificial Intelligence and Statistics (pp. 10112-10159). PMLR.\n"}, {"review_id": "M6jpgFOjUr", "reviewer": "Reviewer_kXbu", "summary": "This paper presents rank-based loss as a popular replacement for empirical loss. The work develops how\noptimization of rank-based loss can be done by a proximal alternating direction method of multipliers. The authors also demonstrate the algorithm's features in terms of convergence under certain conditions. Experimentation which includes synthetic and real datasets is also added in the paper with some numerical simulations showing how the framework behaves. It supports the theoretical results.", "questions": "I would like the authors to compare the method with similar-purpose frameworks, even if not using rank-based loss, and see their differences in performance.\n\nI would appreciate the inclusion of the applicability of the result to a real machine-learning problem.\n\n", "limitations": "N.A.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is mathematically strong", "weaknesses": "The contribution doesn't seem significant enough\nThe applicability of the result is not clearly shown\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer kXbu for the constructive comments!\n\n**The applicability in machine learning**\n\nIt is noteworthy that rank-based loss is a highly valuable and extensively researched concept in the field of machine learning. Commonly encountered variations of rank-based losses include spectral risk measures [1], empirical human risk [4], and the average of ranked-range aggregate loss [3]. These losses have been demonstrated to be significant and applicable in various scenarios, as expounded in the literature. Spectral risk measures, which include the well-known CVaR loss,  the maximum risk [5], and the average top-k risk [2], are widely used risk metrics in the field of machine learning and finance. Empirical human risk is an aggregate loss framework inspired by cumulative prospect theory [6], which considers fairness performance across different groups. The average of ranked-range aggregate loss is particularly effective in handling outliers, ensuring the robustness of the model against anomalous observations in the dataset.\n\nThis paper considers a unified framework, equation (1), which encompasses all the aforementioned rank-based losses. Furthermore, we introduce a method to tackle problems within this unified framework. Our proposed algorithm exhibits comparable or even superior performance compared to algorithms specifically tailored for the three individual frameworks, as demonstrated in the experimental results.\n\nThe versatility of our framework, along with the promising results obtained in experiments, highlights the potential of our approach in addressing various rank-based loss scenarios in machine learning applications.\n\n**Comparison with the existing method**\n\nSorry that we may not understand your first question correctly. \nTo our best knowledge, there does not exist any method that can address a unified framework akin to equation (1). Our proposed algorithm is the first one that is applicable to this unified framework. Nevertheless, we have compared different algorithms for solving (1) with different risk measures in the current version of our paper.\n\nIn the experiments, we conducted comprehensive comparisons with algorithms used or proposed in prior work for the three application scenarios, i.e., LSVRG, SGD, and DCA . Our algorithm consistently demonstrated stability and superior performance in these experiments. Additionally, we examined the commonly used empirical risk minimization (ERM), which can be seen as not using rank-based loss, and presented the results in Figure 1 of Section 5.1 and Appendix C.1. In this setting, SGD refers to the standard stochastic gradient descent method, which is a commonly used optimization algorithm in machine learning.\n\nOnce again, we emphasize that our algorithm offers a comprehensive and effective solution for various rank-based loss scenarios within the unified framework presented in equation (1). The experimental results consistently demonstrate the robustness and efficacy of our proposed algorithm.\n\n**The real machine-learning problem**\n\nIn our study, we primarily focused on presenting the binary classification scenario to emphasize the effectiveness of our algorithm in solving problems within the equation (1) framework, with a particular focus on comparing the objective function values. However, we also included classification accuracy results to provide a comprehensive evaluation.\n\nIn Tables 1 and 2, we displayed the classification accuracies of the spectral risk measure minimization model on the 'SVMguide' and 'AD' binary classification datasets (detailed sources and statistical information are provided in the appendix). The results show that our algorithm achieves comparable classification accuracy with existing methods.\nAdditionally, in Table 3, we demonstrated the results of empirical human risk minimization on the 'UTKFace' dataset for the binary gender classification task. The results indicate that our algorithm outperforms existing methods in terms of test accuracy. Regarding fairness metrics, detailed explanations are available in Appendix B.5. For our analysis, we used race groups (white G1 and other race G2) to compare fairness metrics. The results reveal that our algorithm performs favorably on most fairness metrics compared to existing methods.\n\n\n**References**\n\n[1] Mehta, R., Roulet, V., Pillutla, K., Liu, L., & Harchaoui, Z. (2023, April). Stochastic Optimization for Spectral Risk Measures. In International Conference on Artificial Intelligence and Statistics (pp. 10112-10159). PMLR.\n\n[2] Fan, Y., Lyu, S., Ying, Y., and Hu, B. (2017). Learning with average top-k loss. Advances in neural information processing systems, 30.\n\n[3] Hu, S., Ying, Y., Lyu, S., et al. (2020). Learning by minimizing the sum of ranked range. Advances in Neural Information Processing Systems, 33:21013–21023.\n\n[4] Leqi, L., Prasad, A., and Ravikumar, P. K. (2019). On human-aligned risk minimization. Advances in Neural Information Processing Systems, 32.\n\n[5] Shalev-Shwartz, S. and Wexler, Y. (2016). Minimizing the maximal loss: How and why. In International Conference on Machine Learning, pages 793–801. PMLR.\n\n[6] Tversky, A. and Kahneman, D. (1992). Advances in prospect theory: Cumulative representation of uncertainty. Journal of Risk and uncertainty, 5:297–323."}]

Author rebuttal:
We truly thank all reviewers’ insightful and constructive suggestions, which helped to significantly improve our paper!

**The more experiments about Figure 1**

To explain the phenomenon observed in Figure 1(h), we conducted experiments with increased sample sizes. The corresponding results are included in the PDF file.

Meta-review: The paper proposes ADMM style algorithms for rank based losses such as spectral risks. The main contribution is to devise a new algorithm through Pool Adjacent violators.
Decision: Accept (poster)