- 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 . 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
-
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 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.
-
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.
-
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
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 . 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 with the negligible-DSR setting , which approaches SRM+NDR. Both configurations use PL-MNIST, constructed by randomly permuting the labels of 30% of the MNIST training samples. We hold and the training budget of 16 epochs fixed, and use the same validation-based learning-rate selection from following the revised Appendix B.11. The revised Table A7 reports the following worst-group test errors over three independent runs:
| PSG-SRM setting | ESRM | Extremile | CVaR |
|---|---|---|---|
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 and , compared with and for PSG-SRM at . 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 on yacht and on amazon, and vary
Every setting uses the learning-rate candidates 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 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.
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.
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∣1 promotes sparsity in the model parameters, while ν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 recovers the unpenalized worst-case spectral objective. A positive ν retains the same spectral uncertainty set while assigning an explicit price to distributional shifts. In the χ2 specification used in our experiments, that price is νn∣q−u∣22. Thus ν calibrates the balance between emphasizing high-loss samples and departing from the empirical distribution, while λ controls the structural penalty on w.
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 f and convex g admit linearly convergent proximal gradient descent, as stated in the revised Appendix B.8. The full-gradient evaluation costs 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)),
while the current gradient depends on
q(t)=qopt(ℓ(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) 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.