acceptodds
Under review as a conference paper at ICLR 2027

A Proximal Stochastic Gradient Method for Doubly-regularized Spectral Risk Minimization

Abstract

Spectral risk minimization (SRM) is an important category of distributionally robust optimization. Recent works in this field elaborate on either distribution shift regularization (DSR) on the spectrum or non-differentiable regularization (NDR) on the parameters. However, few methods can simultaneously handle double regularization. The main difficulty lies in suppressing the bias and variance of the stochastic gradient when double regularization is present. To solve this problem, we develop a novel proximal stochastic gradient method (PSG-SRM) that simultaneously handles double regularization, reduces bias and variance along with iterations, and achieves linear convergence. It has lower computational complexity than two state-of-the-art methods that handle DSR or NDR separately. Experimental results indicate that it achieves competitive performance in both regression and classification tasks, and shows stable performance with respect to randomness.

Primary area:
learning theory
Keywords:
Spectral risk minimization, proximal stochastic gradient, double regularization, linear convergence

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_aT6sOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the spectral risk minimization (SRM) problem with non-differentiable regularization (NDR). Theoretical analysis is provided, showing that the computational complexity scales linearly with the sample size nn. Overall, I find the proof reasonable and the theoretical results meaningful. However, I have some concerns regarding the motivation. While the original SRM problem itself is challenging, introducing DSR can be viewed as a relaxation that makes the problem easier to optimize. From this perspective, SRM+DSR+NDR appears to be a relaxed version of SRM+NDR. Given that SRM+NDR has already been studied in the literature, the motivation and additional benefit of introducing DSR could be better justified.

Critical strengths

The paper is well organized and clearly written. The background and related work are introduced thoroughly, and the comparison table provides a clear summary of the theoretical results of different methods. The high-level ideas and key techniques underlying the theoretical analysis are also well explained.

Critical weaknesses
  1. The motivation for considering SRM+DSR+NDR is not very clear to me. In particular, if the goal is to handle a non-differentiable regularizer such as an L1L_1 penalty, a natural choice would be to directly consider SRM+NDR. It is unclear why DSR is also needed. Is DSR introduced because it is useful for the learning problem itself, or mainly because it makes the optimization easier and helps achieve linear convergence? I think the paper could explain this point more clearly.

  2. The difficulty of handling DSR also needs more explanation. The paper states that standard proximal stochastic gradient methods such as SOREL can handle NDR but cannot handle DSR. However, adding a strongly convex DSR to the inner maximization seems to make the inner problem easier to solve. Therefore, it is unclear to me why introducing DSR leads to additional optimization difficulty. The authors could provide more explanation on why SOREL cannot be directly applied in this case.

  3. The experiments do not clearly show the benefit of using both DSR and NDR. Different methods use different regularizers and therefore solve different optimization problems, which makes the comparison less direct. It is difficult to tell whether the improvement comes from the proposed algorithm or from the choice of regularization. Since one of my main questions is why DSR is needed in addition to NDR, it would be helpful to compare SRM+NDR with SRM+DSR+NDR using the same NDR and the same experimental setting. This comparison would more directly show the benefit of adding DSR.

Questions for authors

Please consider my concerns in weaknesses, especially the numerical results part. I am happy to improve my score if my concerns are solved.

4 comments
AuthorsOpenReview ↗

Reply to Reviewer [1/2]

Thank you for recognizing the organization of the paper and the significance of its theoretical analysis. Your questions concern the modeling role of DSR, its interaction with stochastic optimization, and the interpretation of the experiments. We address these points separately below.

1. DSR and NDR encode complementary modeling choices.

The doubly-regularized objective is

F_\nu(w) = \max_{q\in\mathcal P(\sigma)} \left\\{ \langle q,\ell(w)\rangle-\nu D(q\\|u) \right\\} +g(w), \qquad u=\mathbf 1_n/n.

The spectrum determines the admissible adversarial reweightings, DSR assigns a cost to deviations from the empirical distribution, and NDR imposes structure on the predictor. For example, g(w)=λ∣w∣1g(w)=\lambda\\|w\\|_1 promotes sparsity in the model parameters, while νD(q∣u)\nu D(q\\|u) regulates the concentration of adversarial sample weights. These penalties act on different variables and express different learning preferences.

This distinction also explains the relationship to SRM+NDR. Setting ν=0\nu=0 recovers the unpenalized worst-case spectral objective. A positive ν\nu retains the same spectral uncertainty set while assigning an explicit price to distributional shifts. In the χ2\chi^2 specification used in our experiments, that price is νn∣q−u∣22\nu n\\|q-u\\|_2^2. Thus ν\nu calibrates the balance between emphasizing high-loss samples and departing from the empirical distribution, while λ\lambda controls the structural penalty on ww.

The modeling value of DSR is therefore present in the learning objective itself. Its smoothing effect supplies an additional computational benefit: the strongly convex divergence yields a unique Lipschitz-continuous weight map. PSG-SRM exploits this property to make incremental optimization of the composite objective provably convergent. The contribution is a method for a specified positive-shift-cost learning problem, with general convex NDRs and a linear-convergence guarantee.

2. The optimization challenge is controlling stale spectral weights during proximal stochastic updates.

Strong concavity makes the inner maximization better behaved. With all current losses and gradients available, the resulting smooth, strongly convex ff and convex gg admit linearly convergent proximal gradient descent, as stated in the revised Appendix B.8. The full-gradient evaluation costs O(nd)\mathcal O(nd) per update under the stated oracle model.

PSG-SRM instead maintains loss and gradient memories and updates individual entries. Its implemented weights are

q(t)=qopt(l(t)),li(t)=ℓi(ζi(t)),q^{(t)}=q^{\mathrm{opt}}(l^{(t)}), \qquad l_i^{(t)}=\ell_i(\zeta_i^{(t)}),

while the current gradient depends on

q^(t)=qopt(ℓ(w(t))).\widehat q^{(t)} = q^{\mathrm{opt}}(\ell(w^{(t)})).

The resulting finite-iteration conditional bias must be controlled together with sampling variance and the nonsmooth proximal update. Revised Lemma 2 establishes

\left\\| \mathbb E_t[v^{(t)}]-\nabla f(w^{(t)}) \right\\|_2^2 \le K R_t, \qquad R_t=\frac1n\sum_i \\|\zeta_i^{(t)}-w^{(t)}\\|_2^2.

Theorem 1 then proves a joint contraction of the iterate, objective, and memory errors. This identifies the specific stochastic difficulty and the mechanism that resolves it.

For SOREL, the relevant distinction is its objective and update. Its dual step has an iterate-centered proximal stabilization but no persistent −νD(q∣u)-\nu D(q\\|u) term. Adding DSR changes that dual subproblem and calls for a corresponding convergence analysis. The fixed-reference modeling penalty and the moving-center stabilization serve different purposes (SOREL, Eqs. (3)–(5) and Algorithm 1). PSG-SRM supplies a direct incremental algorithm and analysis for Eq. (5) of our paper.

AuthorsOpenReview ↗

Reply to Reviewer [2/2]

3. Adding DSR with the same NDR improves the achieved test performance.

The revised Appendix B.12 evaluates the contribution of DSR in PSG-SRM while retaining the same composite formulation,

F_{\nu}(w)=\max_{q\in\mathcal{P}(\sigma)}\left\\{\sum_{i=1}^{n}q_i\ell_i(w)-\nu n\left\\|q-\frac{\mathbf{1}_n}{n}\right\\|_2^2\right\\}+\lambda\\|w\\|_1.

The parameter regularizer remains g(w)=λ∣w∣1g(w)=\lambda\\|w\\|_1. The DSR coefficient controls the penalty on concentrating spectral weights away from the empirical distribution, while the NDR acts on the model parameters. The ablation tests the practical value of combining these two components.

For the prediction experiment, we compare ν=1\nu=1 with the negligible-DSR setting ν=10−15\nu=10^{-15}, which approaches SRM+NDR. Both configurations use PL-MNIST, constructed by randomly permuting the labels of 30% of the MNIST training samples. We hold λ=10−4\lambda=10^{-4} and the training budget of 16 epochs fixed, and use the same validation-based learning-rate selection from 10−4,10−3,10−2\\{10^{-4},10^{-3},10^{-2}\\} following the revised Appendix B.11. The revised Table A7 reports the following worst-group test errors over three independent runs:

PSG-SRM settingESRMExtremileCVaR
ν=1\nu=10.1789±0.000560.1789\pm0.000560.1925±0.00240.1925\pm0.00240.2022±0.00110.2022\pm0.0011
ν=10−15\nu=10^{-15}0.7193±0.000410.7193\pm0.000411.0000±0.00001.0000\pm0.00001.0000±0.00001.0000\pm0.0000

With the same NDR, training budget, and selection procedure, retaining DSR yields substantially lower test error across all three spectral risks. Thus, the benefit appears in the predictive performance achieved under the common training protocol as well as in optimization behavior.

Table A7 also provides SOREL as a separate baseline without explicit DSR. Its extremile and CVaR errors are 0.26070.2607 and 0.76430.7643, compared with 0.19250.1925 and 0.20220.2022 for PSG-SRM at ν=1\nu=1. These correspond to reductions of 6.82 and 56.21 percentage points, respectively.

3a. The DSR sweep identifies its contribution to optimization stability

Figures A6-A9 examine the optimization effect of DSR with the NDR fixed. We use λ=1\lambda=1 on yacht and λ=0.005\lambda=0.005 on amazon, and vary

ν∈1,0.01,10−5,10−10,10−15.\nu\in\\{1,0.01,10^{-5},10^{-10},10^{-15}\\}.

Every setting uses the learning-rate candidates η∈0.1,0.01,10−3,10−4,10−5\eta\in\\{0.1,0.01,10^{-3},10^{-4},10^{-5}\\} and ten independent runs. The plots track normalized suboptimality relative to an L-BFGS numerical reference solution computed for each objective.

On yacht, the very small DSR coefficients produce oscillatory or stalled progress at relatively large learning rates. Larger coefficients enable faster and more stable decreases in suboptimality with suitable learning rates. On amazon, the sweep likewise shows that stronger DSR can support a larger learning rate and reach lower suboptimality within the evaluated budget.

These controlled trajectories explain a practical advantage of DSR: it improves the stability and progress of training while preserving the same nonsmooth parameter regularizer. Together with Table A7, they provide empirical motivation for including DSR alongside NDR.

4. Fixing the entire objective identifies the optimizer's contribution.

To address the concern about comparing different regularizers, the revised Appendix B.10 compares PSG-SRM, SGD, and Prox-SGD on exactly the same doubly-regularized objective, Eq. (102). For each comparison, the spectral risk, DSR coefficient, and ℓ1\ell_1 regularizer are identical across methods. All three methods use

\lambda\in\\{0.001,0.01\\},\qquad \eta\in\\{0.001,0.003,0.01,0.03\\}.$$ The revised Figures A2-A5 cover `energy` under CVaR, extremile, and ESRM, and `amazon` under extremile. Each configuration is evaluated over ten seeds. For each fixed $(\nu,\lambda)$ pair, the methods share the same L-BFGS reference solution, and the plots report the objective gap against passes through the data. With suitable learning rates, PSG-SRM generally reduces the objective gap more rapidly than SGD and Prox-SGD over comparable data passes. **This improvement is observed with the entire objective held fixed, directly supporting the effectiveness of the proposed optimization method.** The revised experiments therefore identify the contribution of DSR through the within-method ablation and the contribution of PSG-SRM through the common-objective comparison.

My concerns are partly solved: I am appreciated that the author adds more details and experiments. However, the motivation for considering SRM+DSR+NDR is not clear to me. Thus, I decide to change my score to 3.

AuthorsOpenReview ↗

Thank you for your thoughtful follow-up

Thank you for your follow-up and for updating your assessment. We sincerely appreciate your careful consideration of the revised submission and your recognition of the additional explanations and experiments.

Reviewer_PG7jOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper studies doubly-regularized spectral risk minimization, combining a divergence penalty and a potentially nonsmooth convex regularizer on model parameters. The proposed PSG-SRM algorithm integrates spectral weights computation, gradient variance reduction, and proximal updates. Under smoothness and strong-convexity assumptions on losses, the paper obtained linear convergence in expected squared distance to the optimum and improved computational complexity over existing SRM methods. Experiments cover five regression datasets, fairness evaluation on ACSIncome, and distribution-shift classification on Amazon and iWildCam using frozen pretrained representations. Across ten random seeds, the authors report competitive predictive performance, improved fairness and group-level classification errors, and favorable runtime and variability compared with PROSPECT, SOREL, and LSVRG.

Critical strengths
  1. Doubly-regularized formulation is novel. The formulation retains divergence-penalized adversarial reweighting while accommodating nonsmooth convex parameter regularization. This allows distributionally robust risk modeling to coexist with structural preferences such as sparsity, without requiring the parameter regularizer itself to be strongly convex. The separation into a smooth spectral-risk term and a proximable regularizer provides a natural optimization structure.

  2. A well-motivated theoretical analysis Understanding how proximal updates interact with risk weights and variance reduction is a meaningful optimization question. The paper makes convergence analysis a central component and develops explicit descent and estimator-error arguments. The proposed Lyapunov construction is particularly interesting, jointly tracking iterate error and gradient-estimation error to study their coupled evolution under the doubly-regularized formulation.

Critical weaknesses
  1. The convergence analysis does not account for the bias between the computed and optimal risk weights. Algorithm 1, lines 235–238, uses iteratively updated risk weights, which generally differ from the exact optimal weights associated with the current loss vector. However, in Appendix A.6, page 17, Eq. (53), lines 868–870, the first expansion makes the replacement ∇f(w(t))→∑iqi(t)∇ℓi(w(t))\nabla f(w^{(t)})\rightarrow \sum_i q_i^{(t)}\nabla\ell_i(w^{(t)}), implicitly identifying the two weight vectors. This enables the subsequent cancellation and the zero-bias assertion in Lemma 2, Eq. (16). The correct conditional bias is $ \mathbb E_t[\Delta^{(t)}]= \sum_i \left[ (q_i^{(t)} -q_i^{\mathrm{opt}})\right]\nabla\ell_i(w^{(t)})$, which is generally nonzero. Even if the weight discrepancy vanishes asymptotically, its effect at finite iterations must be controlled. The analysis therefore needs a quantitative bound on this bias and its contribution to the descent and Lyapunov inequalities before the claimed linear convergence rate can be justified.
  2. Limited experimental evidence. The empirical evaluation is restricted to relatively small datasets. The five regression benchmarks contain only 244–7,654 training examples with 4–8 features, while the Amazon and iWildCam experiments use 10,000 and 20,000 examples, respectively, to train linear classifiers over frozen representations. These settings provide limited evidence of scalability to larger sample sizes and feature dimensions. I recommend additional experiments on standard benchmarks such as MNIST, CIFAR-10/100, or Tiny ImageNet. Controlled distribution shifts and adversarially perturbed input images could also provide complementary tests of robustness.
Questions for authors

Please see the weaknesses section. All major concerns need to be satisfactorily addressed for me to recommend acceptance. In particular, please clarify whether the bias between the computed and optimal risk weights reflects a notation inconsistency or a substantive error affecting the convergence analysis. On first reading, this appears critical, because the proof relies on exact conditional unbiasedness. Please explain how the notation is consistent with Algorithm 1 or, if the estimator is biased, provide the necessary analysis to establish whether the claimed linear convergence rate still holds. I am willing to increase my score if the authors convincingly resolve this concern.

5 comments
AuthorsOpenReview ↗

Reply to Reviewer [1/2]

Thank you for identifying the distinction between the computed spectral weights and the exact-current weights. The revised analysis establishes linear convergence while retaining and controlling the finite-iteration bias in Algorithm 1. The proof now quantifies that bias, propagates it through the proximal descent inequalities, and proves its geometric decay jointly with the iterate, objective, and memory errors. Please also check the revised manuscript for the detailed deductions.

1. The finite-iteration estimator is conditionally biased, and the revised proof analyzes that bias directly.

Equation (16) now distinguishes

q(t)=qopt(l(t)),li(t)=ℓi(ζi(t)),q^(t)=qopt(ℓ(w(t))).q^{(t)}=q^{\mathrm{opt}}(l^{(t)}), \qquad l_i^{(t)}=\ell_i(\zeta_i^{(t)}), \qquad \widehat q^{(t)} = q^{\mathrm{opt}}(\ell(w^{(t)})).

Algorithm 1 uses q(t)q^{(t)}, obtained from the stored loss table. The exact-current weights q^(t)\widehat q^{(t)} appear only in the analysis. For

Δ(t)=v(t)−∇f(w(t)),\Delta^{(t)} = v^{(t)}-\nabla f(w^{(t)}),

the conditional bias is exactly

bt:=Et[Δ(t)]=∑i=1n(qi(t)−q^i(t))∇ℓi(w(t)).b_t := \mathbb E_t[\Delta^{(t)}] = \sum_{i=1}^n (q_i^{(t)}-\widehat q_i^{(t)}) \nabla\ell_i(w^{(t)}).

This is the discrepancy raised in your question. Its finite-iteration contribution is now an explicit part of the analysis.

Let

Rt=1n∑i=1n∣ζi(t)−w(t)∣22,Lq=(αnnν)−1,R_t = \frac1n\sum_{i=1}^n \\|\zeta_i^{(t)}-w^{(t)}\\|_2^2, \qquad L_q=(\alpha_n n\nu)^{-1},

where RtR_t is the loss-memory error. The Lipschitz continuity of the weight map gives

∣q(t)−q^(t)∣22≤nG2Lq2Rt.\\|q^{(t)}-\widehat q^{(t)}\\|_2^2 \le nG^2L_q^2R_t.

Using ∣∇ℓ(w(t))∣2≤n,G\\|\nabla\ell(w^{(t)})\\|_2\le\sqrt n\\,G yields

∣bt∣22≤KRt,K=n2G4Lq2=G4αn2ν2.\\|b_t\\|_2^2\le KR_t, \qquad K=n^2G^4L_q^2 = \frac{G^4}{\alpha_n^2\nu^2}.

This is Lemma 2, Eq. (19). The detailed derivation is in Appendix A.6. It controls the bias at every iteration by a memory error whose evolution is analyzed explicitly.

2. Bias and centered sampling variance are controlled separately.

Defining ξt=Δ(t)−bt\xi_t=\Delta^{(t)}-b_t gives

Et[ξt]=0,Et∣Δ(t)∣22=Et∣ξt∣22+∣bt∣22.\mathbb E_t[\xi_t]=0, \qquad \mathbb E_t\\|\Delta^{(t)}\\|_2^2 = \mathbb E_t\\|\xi_t\\|_2^2+\\|b_t\\|_2^2.

With Q(t)Q^{(t)} and S(t)S^{(t)} denoting the component and gradient-memory errors in Eq. (22), Lemma 2 proves

Et∣ξt∣22≤2Q(t)+2S(t),Q(t)≤Aet+2KRt,\mathbb E_t\\|\xi_t\\|_2^2 \le 2Q^{(t)}+2S^{(t)}, \qquad Q^{(t)}\le Ae_t+2KR_t,

where

et=∣w(t)−w∗∣22,A=4(n∣σ∣22Lℓ2+K).e_t=\\|w^{(t)}-w^*\\|_2^2, \qquad A=4\left(n\\|\sigma\\|_2^2L_\ell^2+K\right).

Consequently, the complete estimator error satisfies

Ut:=Et∣Δ(t)∣22≤2Aet+2S(t)+5KRt.U_t := \mathbb E_t\\|\Delta^{(t)}\\|_2^2 \le 2Ae_t+2S^{(t)}+5KR_t.

Both memory processes have feasible recursions:

Et[S(t+1)]=(1−1n)S(t)+1nQ(t),Et[Rt+1]≤(1−12n)Rt+2nDt,\begin{aligned} \mathbb E_t[S^{(t+1)}] &= \left(1-\frac1n\right)S^{(t)} +\frac1nQ^{(t)},\\\\ \mathbb E_t[R_{t+1}] &\le \left(1-\frac1{2n}\right)R_t+2nD_t, \end{aligned}

where

Dt=Et∣w(t+1)−w(t)∣22.D_t = \mathbb E_t\\|w^{(t+1)}-w^{(t)}\\|_2^2.

These relations describe how the sampling error and stale-loss bias interact with the iterate movement.

3. The proximal descent inequalities retain the bias contribution.

Writing Pt=F(w(t))−F(w∗)P_t=F(w^{(t)})-F(w^*), together with revised Lemma 4, Eqs. (25)–(26), proves for 0<η≤1/(4Lf)0 < \eta\le1/(4L_f) that

Et[et+1]≤(1−μη2)et−2ηEt[Pt+1]−14Dt+2η2Ut+2ηKμRt,Et[Pt+1]≤Pt−12ηDt+ηUt.\begin{aligned} \mathbb E_t[e_{t+1}] &\le \left(1-\frac{\mu\eta}{2}\right)e_t -2\eta\mathbb E_t[P_{t+1}] -\frac14D_t\\\\ &\quad +2\eta^2U_t +\frac{2\eta K}{\mu}R_t, \\\\[2mm] \mathbb E_t[P_{t+1}] &\le P_t-\frac1{2\eta}D_t+\eta U_t. \end{aligned}

The term 2ηKRt/μ2\eta KR_t/\mu is the explicit contribution of the nonzero conditional bias. The objective-descent inequality supplies a negative movement term that absorbs the 2nDt2nD_t contribution in the loss-memory recursion. This is why the revised Lyapunov function includes both the composite objective gap and the loss-memory error.

4. The four-term Lyapunov contraction proves the claimed linear convergence.

Under the assumptions in Section 3, choose

0<η≤μ96nA,a=μ48A,τ=μη4.0 < \eta\le\frac{\mu}{96nA}, \qquad a=\frac{\mu}{48A}, \qquad \tau=\frac{\mu\eta}{4}.

Theorem 1 uses

V(t)=et+(a+2η)Pt+cSS(t)+cRRt,V^{(t)} = e_t+(a+2\eta)P_t+c_SS^{(t)}+c_RR_t,

with the positive coefficients from Eq. (86):

ω=η(a+2η),cS=4nω,cR=4nK(13ω+2ημ).\omega=\eta(a+2\eta), \qquad c_S=4n\omega, \qquad c_R=4nK\left(13\omega+\frac{2\eta}{\mu}\right).

Combining the two descent inequalities and both memory recursions gives

Et[V(t+1)]≤(1−τ)V(t)−14Dt.\mathbb E_t[V^{(t+1)}] \le (1-\tau)V^{(t)}-\frac14D_t.

The complete coefficient calculation and movement absorption are provided in Appendix A.9, Eqs. (86)–(99). It follows that

E∣w(t)−w∗∣22≤(1−τ)tV(0),E[F(w(t))−F(w∗)]≤(1−τ)tV(0)a+2η,E∣bt∣22≤KcR(1−τ)tV(0),E∣ξt∣22≤(2A+4KcR+2cS)(1−τ)tV(0).\begin{aligned} \mathbb E\\|w^{(t)}-w^*\\|_2^2 &\le (1-\tau)^tV^{(0)},\\\\ \mathbb E[F(w^{(t)})-F(w^*)] &\le \frac{(1-\tau)^tV^{(0)}}{a+2\eta},\\\\ \mathbb E\\|b_t\\|_2^2 &\le \frac K{c_R}(1-\tau)^tV^{(0)},\\\\ \mathbb E\\|\xi_t\\|_2^2 &\le \left( 2A+\frac{4K}{c_R}+\frac2{c_S} \right) (1-\tau)^tV^{(0)}. \end{aligned}

AuthorsOpenReview ↗

Reply to Reviewer [2/2]

Asymptotic unbiasedness is a result of this joint contraction. The analysis proves linear convergence of the implemented proximal stochastic updates while accounting for their bias throughout the trajectory.

For the choice η=μ/(96nA)\eta=\mu/(96nA), the iteration bound is

O!(nAμ2log⁡V(0)ε)\mathcal O\\!\left( \frac{nA}{\mu^2} \log\frac{V^{(0)}}{\varepsilon} \right)

for expected squared-distance accuracy ε\varepsilon. The simpler O(nlog⁡(V(0)/ε))\mathcal O(n\log(V^{(0)}/\varepsilon)) expression follows under the uniform-constant conditions stated after Theorem 1. The theorem assumes the regional regularity and per-sample strong convexity in Section 3, a proper closed convex gg, exact proximal and stored-loss weight solves, and the specified independent sampling.

5. A larger standard image benchmark with higher-dimensional inputs.

We followed your standard-benchmark recommendation by adding MNIST, a ten-class classification task with 42000 training examples, 18000 validation examples, and 10000 test examples. Each image is flattened into a 784-dimensional pixel vector.

This increases the largest evaluated training-set size from 20000 to 42000 examples and extends the experiments beyond the 4--8 feature regression benchmarks to a substantially higher-dimensional image task. The MNIST evaluation uses the image pixels as the model inputs.

We compare PSG-SRM, PROSPECT, SOREL, SGD, and LSVRG under CVaR, extremile, and ESRM. The protocol uses 16 epochs, λ=10−4\lambda=10^{-4}, and ν=1\nu=1 where applicable. Each optimizer selects its learning rate from

η∈10−4,10−3,10−2\eta\in\\{10^{-4},10^{-3},10^{-2}\\}

by minimizing the mean validation loss across seeds 1,2,3\\{1,2,3\\}. The revised Table A6 reports mean and standard deviation over three independent runs.

On clean MNIST, PSG-SRM achieves the lowest mean worst-group test error under CVaR, 0.1364±0.00130.1364\pm0.0013. Its corresponding errors under extremile and ESRM are 0.1371±0.000650.1371\pm0.00065 and 0.1375±0.000650.1375\pm0.00065. These results show competitive predictive performance on the standard image benchmark at the expanded sample size and input dimension.

5a. A controlled corruption experiment on the image benchmark.

For the additional robustness evaluation, we construct PL-MNIST by randomly permuting the labels of 30% of the training samples. This explicitly defined intervention tests learning under corrupted supervision while retaining the image inputs and the same training and evaluation procedure.

The revised Table A6 shows that PSG-SRM attains the lowest mean worst-group test error across all three spectral risks, sharing the best extremile mean with PROSPECT:

Spectral riskPSG-SRMPROSPECTSORELSGDLSVRG
ESRM0.1789±0.000560.1789\pm0.000560.1799±0.000560.1799\pm0.000560.1796±0.00110.1796\pm0.00110.2116±0.00890.2116\pm0.00890.1802±0.000970.1802\pm0.00097
Extremile0.1925±0.00240.1925\pm0.00240.1925±0.00150.1925\pm0.00150.2607±0.0390.2607\pm0.0390.2229±0.00520.2229\pm0.00520.3995±0.0720.3995\pm0.072
CVaR0.2022±0.00110.2022\pm0.00110.2035±0.00190.2035\pm0.00190.7643±0.260.7643\pm0.260.2358±0.0150.2358\pm0.015Does not converge

Relative to SOREL, PSG-SRM reduces the extremile error from 26.07% to 19.25% and the CVaR error from 76.43% to 20.22%. Relative to SGD, it reduces the error by 3.27, 3.04, and 3.36 percentage points for ESRM, extremile, and CVaR, respectively. It also matches or improves the mean error of PROSPECT across all three measures. The LSVRG nonconvergence entry refers specifically to CVaR under the reported PL-MNIST protocol.

The added results show effective learning under a precisely specified corruption of the training supervision, alongside competitive performance on clean MNIST.

6. Complementary evidence for distribution shifts and perturbations

The new label-corruption study complements the natural distribution-shift evaluations on Amazon and iWildCam in Section 4.3 and Table 4. Those experiments report an Amazon worst-group test error of 0.76740.7674 and an iWildCam median-group test error of 0.70850.7085 for PSG-SRM, the lowest reported means among the compared methods in Table 4. For the complementary perturbation tests suggested in your review, the revision implements controlled training-label corruption. The reported evidence therefore covers both natural group shifts and corrupted supervision.

Reviewer_PG7jOpenReview ↗

Thanks for rebuttal

I would like to thank the authors for their clarification. I have no further questions. Given the revised proof, it seems the manuscript should undergo major revision for proofreading. At the current stage, I have improved the technical soundness part but have to maintain the original score.

If other reviewers and the AC have different opinions on technical modifications, please reply to this, and I may change my overall evaluation later.

For authors, could you please highlight your changes in blue. It seems you updated manuscript but doesn't highlight the major changes?

Reviewer_tf1pOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces PSG-SRM, a proximal stochastic gradient method for doubly-regularized Spectral Risk Minimization (SRM), which for the first time jointly handles two previously separate regularization terms: a distributional-shift regularizer (DSR) on the spectrum and a non-smooth regularizer (NDR) on the parameters. It achieves lower computational complexity than two methods that handle DSR or NDR separately, with competitive performance in experiments.

Critical strengths
  1. The combination of spectral risk smoothing and nonsmooth parameter regularization is practically relevant.
  2. By leveraging the non-expansiveness of proximal mappings and a tailored variance control scheme, the proposed PSG-SRM algorithm handles both regularizations simultaneously.
  3. Theoretical guarantees of linear convergence.
Critical weaknesses
  1. PSG-SRM is essentially built on PROSPECT, and somewhat combinatorial.
  2. The paper compares mainly against SOREL and PROSPECT — methods that cannot solve (5), which limits the significance of the experimental justification.
  3. Furthermore, the comparison is not run under matched conditions, with different regularizes across different methods, which is a little confusing.
  4. In the experimental setting, PSG-SRM receives a dedicated hyperparameter grid search and main baselines use default criteria
Questions for authors

See weaknesses

5 comments
AuthorsOpenReview ↗

Reply to Reviewer [1/3]

Thank you for recognizing the practical relevance of combining spectral-risk regularization with nonsmooth parameter regularization, as well as the linear-convergence guarantee. We address your four concerns below, with particular emphasis on the analytical contribution beyond PROSPECT and the experimental comparisons in the same modeling framework.

1. Contribution beyond PROSPECT: a direct composite update with a tailored Lyapunov contraction

PSG-SRM develops a direct proximal stochastic algorithm for the doubly-regularized objective in Eq. (5):

w(t+1)=prox⁡ηg(w(t)−ηv(t)).w^{(t+1)}=\operatorname{prox}_{\eta g}(w^{(t)}-\eta v^{(t)}).

This update separates the smooth spectral-loss component from the structural regularizer gg. For g(w)=λ∣w∣1g(w)=\lambda\\|w\\|_1, the proximal step is closed-form soft-thresholding with O(d)\mathcal O(d) cost. With the incremental gradient-memory maintenance and spectral-weight update specified in the paper, the total per-iteration cost is O(n+d)\mathcal O(n+d).

The central analytical contribution is a four-term Lyapunov construction tailored to the interaction between this composite update and the evolving memory tables. The revised Theorem 1 uses

V^{(t)} ={}& \underbrace{\\|w^{(t)}-w^*\\|_2^2}_{\text{iterate error}} + \underbrace{(a+2\eta) \bigl(F(w^{(t)})-F(w^*)\bigr)}_{\text{composite objective gap}} \\\\ &+ \underbrace{c_S S^{(t)}}_{\text{gradient-memory error}} + \underbrace{c_R R_t}_{\text{loss-memory discrepancy}}, \end{aligned}$$ where $$R_t=\frac1n\sum_{i=1}^{n}\\|\zeta_i^{(t)}-w^{(t)}\\|_2^2.$$ $S^{(t)}$ controls the stored weighted-gradient errors, while $R_t$ controls the discrepancy between the stored loss locations and the current iterate, and hence the error in the spectral weights. The composite-objective term has a specific mathematical role. In our proof, **proximal objective descent supplies a negative multiple of the squared iterate movement**, $$D_t=\mathbb E_t\\|w^{(t+1)}-w^{(t)}\\|_2^2.$$ **This decrease absorbs the positive movement contribution in the loss-memory recursion**. Combining this relation with iterate descent and the gradient-memory recursion yields $$\mathbb E_t[V^{(t+1)}] \le (1-\tau)V^{(t)} -\frac14D_t.$$ Under the assumptions and coefficient choices of Theorem 1, this contraction establishes linear convergence of the iterates and composite objective values, together with geometric decay bounds for the conditional bias and centered sampling variance. The regularizer $g$ may be any proper closed convex function covered by those assumptions. $g$ itself need not be strongly convex. This gives a concrete structural distinction from the Lyapunov construction of PROSPECT in its Appendix D.1: our analysis **incorporates the full composite objective gapand uses its proximal descent to control the moving loss memory** . The direct loss-gradient/$\operatorname{prox}_g$ split also differs from the sampled regularized-loss proximal construction in PROSPECT-Moreau, described in its Appendix E.1. **Our contribution is the direct composite stochastic solver and the coupled convergence analysis that establishes its guarantee.** The shared spectral-weight and gradient-memory architecture provides an efficient implementation, while the objective-gap-memory coupling supplies the analytical mechanism for the proposed proximal update. # 2. The evaluation includes a baseline optimizing the same doubly-regularized model **Appendix B.8 and Table A4 compare PSG-SRM with SGD optimizing the same doubly-regularized model and following the same hyperparameter-selection procedure.** Thus the evaluation includes a direct comparison in the modeling framework of Eq. (5), addressing your concern about the relevance of the comparison methods. The classification results show: - **Amazon:** worst-group test error decreases from **80.70% to 76.74%**, an improvement of **3.96 percentage points**. - **iWildCam:** median-group test error decreases from **73.51% to 70.85%**, an improvement of **2.66 percentage points**. PSG-SRM also improves all four reported ACSIncome fairness criteria relative to SGD. Across the fifteen regression dataset--risk settings, it achieves lower mean test spectral risk in nine settings and lower reported standard deviation in all fifteen. These results support the practical value of the proposed optimization scheme in the doubly-regularized model.
AuthorsOpenReview ↗

Reply to Reviewer [2/3]

3. The experiments provide controls for both regularizer choice and optimizer performance

Your concern about different regularizers is addressed through two complementary comparisons.

First, Appendix B.6 uses the same ℓ1\ell_1 form of parameter regularization, g(w)=λ∣w∣1g(w)=\lambda\\|w\\|_1, for PSG-SRM and SOREL. It measures optimization progress in single-sample oracle passes, providing a comparison with the same form of structural regularizer and a common measure of oracle usage.

Second, Appendix B.8 compares PSG-SRM and SGD within the same doubly-regularized model, covering both DSR and NDR. Table A4 therefore provides the evidence most directly relevant to the optimization contribution when the model form is matched.

These comparisons give the experimental results a precise interpretation: the main comparisons evaluate established method–model configurations on common tasks, Appendix B.6 controls the form of parameter regularization, and Appendix B.8 evaluates the proposed optimizer in the same modeling framework.

4. Direct baselines for the doubly-regularized objective.

The revised Appendix B.10 adds SGD and Prox-SGD as direct comparators, with all three methods targeting the same complete objective as PSG-SRM:

F(w)=\max_{q\in\mathcal{P}(\sigma)}\left\\{\sum_{i=1}^{n}q_i\ell_i(w)-\nu n\left\\|q-\frac{\mathbf{1}_n}{n}\right\\|_2^2\right\\}+\lambda\\|w\\|_1.

This is Eq. (102), the experimental instance of the doubly-regularized formulation in Eq. (5). The comparison includes both the spectrum regularization and the nonsmooth ℓ1\ell_1 parameter penalty. Prox-SGD provides a particularly direct comparison because it also uses proximal updates for the nonsmooth objective.

The revised Figures A2--A5 evaluate energy under CVaR, extremile, and ESRM, and amazon under extremile. Thus the revised evaluation directly compares algorithms targeting the full proposed optimization problem across both regression and classification.

The existing Appendix B.8 and Table A4 provide additional predictive evidence from SGD optimizing the same model with the same hyperparameter-selection procedure. PSG-SRM achieves an Amazon worst-group test error of 0.7674, compared with 0.8070 for SGD, and an iWildCam median-group test error of 0.7085, compared with 0.7351. These correspond to improvements of 3.96 and 2.66 percentage points, respectively.

5. Identical regularization and direct measurement of optimization progress.

The new same-objective experiments evaluate every method at the six combinations of

ν∈0.1,1,10,λ∈0.001,0.01.\nu\in\\{0.1,1,10\\},\qquad \lambda\in\\{0.001,0.01\\}.

For each fixed pair, the data, spectral risk, DSR coefficient, and ℓ1\ell_1 parameter regularizer define one common optimization problem. We compare the objective gap F(wk)−F(w∗)F(w_k)-F(w^*) against passes through the data, using the same L-BFGS numerical reference w∗w^* for that objective. Every configuration is repeated over ten independent seeds. The plots show the mean and the minimum-to-maximum range.

The revised Figures A2--A5 show that suitable PSG-SRM learning rates produce substantially faster reductions in the observed objective gap than SGD and Prox-SGD over comparable data passes. This behavior appears across all three spectral risks on energy and on the amazon classification task.

Because the complete objective is fixed in each comparison, these curves directly show the empirical contribution of the optimizer. They resolve the attribution question raised by comparisons involving different regularizers.

6. Common hyperparameter grid search and validation-based selection

We have added a systematic grid-search comparison in which PSG-SRM, PROSPECT, LSVRG, SOREL, and SGD all receive validation-based hyperparameter tuning on acsincome, amazon, and iwildcam (Appendix B.13, Tables A8-A9). PSG-SRM achieves the best mean performance in five of the six comparisons in this comparison.

Common search and selection protocol. The learning rate η\eta, regularization strength λ\lambda, and shift cost ν\nu are searched over the following candidate sets wherever applicable:

λ,ν∈0.01,0.1,1,10,100,\lambda,\nu\in\\{0.01,0.1,1,10,100\\},

η∈10−5,3×10−5,10−4,3×10−4,10−3,3×10−3,0.01,0.03,0.1.\eta\in\\{10^{-5},3\times10^{-5},10^{-4},3\times10^{-4},10^{-3},3\times10^{-3},0.01,0.03,0.1\\}.

Specifically, we search (η,λ,ν)(\eta,\lambda,\nu) for PSG-SRM, PROSPECT, and SGD; (η,ν)(\eta,\nu) for LSVRG; and (η,λ)(\eta,\lambda) for SOREL. Every candidate configuration is evaluated using the same ten random seeds {1,…,10}\{1,\ldots,10\}, and the configuration of each method is selected by the lowest mean validation loss across these runs. We then report the corresponding test metrics as mean ±\pm standard deviation over ten runs. Thus, the competing optimizers receive systematic searches over the same candidate values for their applicable parameters with the same validation criterion.

AuthorsOpenReview ↗

Reply to Reviewer [3/3]

Results after tuning the competing optimizers.

  • Fairness on acsincome (Table A8): PSG-SRM achieves the lowest statistical parity score in all four comparisons, covering race and gender under both CVaR and ESRM. Its scores are 0.70300.7030 and 0.70140.7014 for race, and 0.04520.0452 and 0.04760.0476 for gender, respectively. These results indicate that its fairness advantage persists after the competing methods are tuned.

  • Out-of-distribution classification on amazon (Table A9): PSG-SRM achieves the lowest worst-group test error, 0.76740.7674, compared with 0.77900.7790 for the strongest tuned competitor PROSPECT, having an improvement of 0.0116.

  • Out-of-distribution classification on iwildcam (Table A9): PSG-SRM achieves a median-group test error of 0.7085±0.00000.7085\pm0.0000, compared with 0.7084±0.00300.7084\pm0.0030 for PROSPECT. The difference in mean error is only 0.00010.0001, while PSG-SRM has a smaller reported standard deviation across the ten runs.

These results show that the good performance of PSG-SRM persists against systematically tuned competitors. The added experiments directly address the concern about preferential tuning via shared parameter grids, a common validation criterion, and explicit test results for all five optimizers.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.