- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The authors present SADA, a single-pass method for generalized linear prediction that integrates a data-driven stochastic proximal update with inner- and outer-loop momentum. The theoretical analysis claims accelerated optimization convergence, minimax-optimal statistical risk, and a higher-order bound on model misspecification, backed by synthetic simulations and image classification tasks.
Critical strengths
- The underlying algorithmic design is compelling: using fresh samples to construct a covariance-informed proximal operator, and then applying acceleration to both the inner subproblem solver and the outer proximal trajectory. This cleanly decouples the optimization overhead from the localized statistical error.
- The layer-peeled covariance argument seems genuinely novel and effectively handles model misspecification—a regime where standard quadratic proofs relying on commuting Hessians and noise covariances break down.
Critical weaknesses
- As written, the main convergence proof contains critical gaps. Right after Eq. (38), the right-hand side features instead of the preceding iterate's suboptimality; similarly, the proof of Theorem E.1 applies the exponential decay factor to rather than the initial error. Because of this, the stated outer recursion and Theorem 5.1 do not logically follow from the derivation shown. Even if these are typographical or indexing slips, they sit right at the heart of the acceleration argument. Additionally, Appendix G contains a flaw when invoking Mourtada’s minimax bound: the noise variance is omitted initially, and the resulting expression is quietly swapped out when taking the limit. Since Mourtada's actual bound scales as , the claim of minimax optimality is not properly substantiated in the current text.
- The experimental setup does not align with the theoretical assumptions. Assumption 1 imposes a strict positive lower bound on globally, yet the curvature of the logistic loss approaches zero in the tails. Despite this, all logistic regression benchmarks appear to evaluate standard SADA rather than the SADA-NonSC variant (which requires explicit parameters and extra regularization). Moreover, on real-world datasets, SADA benefits from a much broader multi-parameter grid search compared to the baselines, and the CIFAR/MNIST evaluations are averaged over just three random seeds. Consequently, the empirical results neither directly verify the theoretical guarantees nor provide a fully fair comparison against variance-reduced methods.
Questions for authors
- Could you supply a corrected step-by-step derivation linking Eqs. (35) and (38) to the stated energy recursion, clarifying whether the objective gap should be evaluated at ? Please also revise the proof of Theorem E.1 so the exponential contraction multiplies the initial optimality gap.
- In Appendix G, shouldn't the equation cited from Mourtada include a factor? Once included, please specify the valid regime for and walk through how the steps leading to Theorem G.1 hold up.
- Which specific variant was run in the logistic regression experiments—standard SADA or SADA-NonSC? If it was SADA-NonSC, please specify the values used for and the two auxiliary regularizers. If standard SADA was used, how do the paper's theoretical results apply to those runs?
6 comments
(2/3)
The following two terms are nonpositive and can be dropped.
\frac{3L_{\mathrm{eff}}L_\ell h_k+2L_\ell h_k-1}{4L_\ell h_k} \mathbb E_{k-1}\lVert\tilde{\mathbf x}_k-\tilde{\mathbf y}_{k-1}\rVert_{\mathbf H}^2 &\leq 0,\\\\ -\frac{3L_{\mathrm{eff}}L_\ell h_k}{8\alpha} \mathbb E_{k-1}\lVert\tilde{\mathbf z}_k-\mathbf x^*\rVert_{\mathbf H}^2 &\leq 0. \end{aligned}$$ **Step 3.** Lemma D.30, applied to the tail iterates under the hyperparameter schedule in Appendix C, yields $$\mathbb E_{k-1}\lVert\mathbf r_k\rVert_{\mathbf H}^2 \leq \frac{L_\ell^3h_k}{16\alpha} \lVert\nabla F(\tilde{\mathbf y}_{k-1})\rVert_{\mathbf H^{-1}}^2.$$ Since $1+3L_{\mathrm{eff}}L_\ell h_k/2\leq 9/8$, the negative gradient term absorbs the bias. $$\left(1+\frac{3L_{\mathrm{eff}}L_\ell h_k}{2}\right) \frac{\alpha}{L_\ell^2}\mathbb E_{k-1}\lVert\mathbf r_k\rVert_{\mathbf H}^2 -\frac{L_\ell h_k}{8}\lVert\nabla F(\tilde{\mathbf y}_{k-1})\rVert_{\mathbf H^{-1}}^2 \leq -\frac{7L_\ell h_k}{128}\lVert\nabla F(\tilde{\mathbf y}_{k-1})\rVert_{\mathbf H^{-1}}^2 \leq 0.$$ **Step 4.** Finally, $(1+3L_{\mathrm{eff}}L_\ell h_k/2)(1-\theta_k)\leq(1+\theta_k/4)(1-\theta_k)\leq 1-\theta_k/2$. This yields the desired energy recursion $$\begin{aligned} &\mathbb E_{k-1}F(\tilde{\mathbf x}_k)-F(\mathbf x^*) +\frac{1}{4\alpha}\mathbb E_{k-1}\lVert\tilde{\mathbf z}_k-\mathbf x^*\rVert_{\mathbf H}^2\\\\ &\leq \left(1-\frac{\theta_k}{2}\right) \left(F(\tilde{\mathbf x}_{k-1})-F(\mathbf x^*) +\frac{1}{4\alpha}\lVert\tilde{\mathbf z}_{k-1}-\mathbf x^*\rVert_{\mathbf H}^2\right) +\frac{3h_k\sigma^2}{2}. \end{aligned}$$ Taking total expectations and using $h_k=2\alpha\theta_k^2/L_\ell$, we telescope the recursion as in Lemma E.2 with $a=1/2$, $c=3\alpha\sigma^2/L_\ell$, and $\theta_{\max}=\tilde\theta_{\max}$. Since $\tilde{\mathbf z}_0=\tilde{\mathbf x}_0$, strong convexity bounds the initial energy by $\frac32(F(\tilde{\mathbf x}_0)-F(\mathbf x^*))$. We obtain the bound in Theorem E.1 (Appendix E.2) $$\mathbb E F(\tilde{\mathbf x}_K)-F(\mathbf x^*) \leq \frac53\exp\left(-\frac{K\tilde\theta_{\max}}4\right) \left(F(\tilde{\mathbf x}_0)-F(\mathbf x^*)\right) +\frac{144\alpha\sigma^2}{L_\ell K}.$$ > [W1] Additionally, Appendix G contains a flaw when invoking Mourtada’s minimax bound: the noise variance $\sigma^{2}$ is omitted initially, and the resulting expression is quietly swapped out when taking the limit. Since Mourtada's actual bound scales as $\sigma^{2}d/(n-d+1)$, the claim of minimax optimality is not properly substantiated in the current text. > > [Q2] In Appendix G, shouldn't the equation cited from Mourtada include a $\sigma^{2}$ factor? Once included, please specify the valid regime for $n,d,\sigma$ and walk through how the steps leading to Theorem G.1 hold up. **Our response:** Thank you for pointing out the missing $\sigma^2$. We restored it in the squared prediction risk and corrected the conversion to excess risk in Lemma G.1 (Appendix G.1, p. 43). The bound you highlight from Corollary 1 of Mourtada [1], $\sigma^2d/(n-d+1)$, sharpens the coarse bound $\sigma^2d/n$ used in our original proof. The coarser bound already suffices to match the leading statistical term. Hence, minimax optimality holds. We verify the claimed minimax optimality below using the sharper bound. For the Gaussian design in Appendix G, Theorem 1 and Eq. (17) of [1] yield the exact minimax squared prediction risk for $d\geq1$, $\Sigma\succ0$, $\sigma>0$, and $n>d+1$. $$\inf_{\widehat{\mathbf x}}\sup_{\mathcal D_n\in\mathcal P_n} \mathbb E_{\mathcal D_n}\Vert\widehat{\mathbf x}-\mathbf x^*\Vert_\Sigma^2 =\frac{\sigma^2}{n}\mathbb E\operatorname{tr}\left(\Sigma\widehat\Sigma_n^{-1}\right) =\frac{\sigma^2d}{n-d-1}.$$ Here $\widehat\Sigma_n=n^{-1}\sum_{i=1}^n\mathbf a_i\mathbf a_i^\top$. Since $\ell_\delta$ is $\mu_\ell$-strongly convex and $\ell_\delta(0)=\ell'_\delta(0)=0$, we have $\ell_\delta(z)\geq\mu_\ell z^2/2$. Averaging over the Gaussian design and independent noise yields $F_\delta(\mathbf x)\geq(\mu_\ell/2)(\Vert\mathbf x-\mathbf x^*\Vert_\Sigma^2+\sigma^2)$. Subtracting $F_\delta^*=F_\delta(\mathbf x^*)$ and taking the minimax yields the revised bound in Lemma G.1. $$\mathcal R_n(\mathcal P_n) \geq \frac{\mu_\ell\sigma^2d}{2(n-d-1)} +\frac{\mu_\ell\sigma^2}{2}-F_\delta^*.$$ In the proof of Theorem G.1 (Appendix G.1, p. 43, lines 2309–2316), we subtract $\alpha\operatorname{tr}(H^{-1}Q_\delta)/(2n)$ from both sides of this inequality before taking the lower limit. Using $F_\delta^*\to\mu_\ell\sigma^2/2$, $Q_\delta\to\mu_\ell^2\sigma^2\Sigma$, $H=L_\ell\Sigma$, and $\alpha=L_\ell/\mu_\ell$, we obtain $$\begin{aligned} \liminf_{\delta\downarrow0} \left\\{\mathcal R_n(\mathcal P_n) -\frac{\alpha\operatorname{tr}(H^{-1}Q_\delta)}{2n}\right\\} &\geq \frac{\mu_\ell\sigma^2d}{2(n-d-1)} -\frac{\mu_\ell\sigma^2d}{2n}\\\\ &=\frac{\mu_\ell\sigma^2d(d+1)}{2n(n-d-1)}>0. \end{aligned}$$(3/3)
Q2 (continued).
Using the bound from Corollary 1 in the same calculation yields a lower bound of for the limit inferior, which is positive for . The exact Gaussian bound above also covers . Thus, Theorem G.1 holds for all sufficiently small at each fixed , i.e., $\mathcal R_n(\mathcal P_n) \geq\frac{\alpha\operatorname{tr}(H^{-1}Q_\delta)}{2n}$.
The claimed minimax optimality still holds. The condition does not undermine the minimax argument. The optimization budget in Corollary 5.1 includes a term of order , which is greater than for constant , since and . Thus is a natural sample size condition.
[W2] The experimental setup does not align with the theoretical assumptions. Assumption 1 imposes a strict positive lower bound on globally, yet the curvature of the logistic loss approaches zero in the tails. Despite this, all logistic regression benchmarks appear to evaluate standard SADA rather than the SADA-NonSC variant (which requires explicit parameters and extra regularization). [...]
[Q3] Which specific variant was run in the logistic regression experiments—standard SADA or SADA-NonSC? If it was SADA-NonSC, please specify the values used for and the two auxiliary regularizers. If standard SADA was used, how do the paper's theoretical results apply to those runs?
Our response: The logistic benchmarks use the standard SADA update. We now explain how the paper's theoretical results apply to these runs.
The strong-convexity constant of the loss can be obtained by a high-probability argument. While the binary logistic loss is not strongly convex on , it is strongly convex on any bounded interval. Suppose . On a high-probability event where the input data norms are bounded, the iterate norm is bounded with high probability by . The logit is then bounded in magnitude by with high probability. On , the loss is -strongly convex with . In our experiment, , so our theory is applicable to the logistic regression setting.
To see what range of logits SADA encounters in practice, we computed for SADA on the simulated logistic task, where is the training block used at outer iteration . The table summarizes the per-run maxima over repeats.
| Training samples | Maximum absolute logit |
|---|---|
| 20,000 | 5.23 |
| 40,000 | 6.21 |
| 60,000 | 7.10 |
The observed values of are consistent with a constant-order bound. This empirically supports the local strong-convexity argument above and shows that our analysis is applicable to this logistic regression setting.
[W2] [...] Moreover, on real-world datasets, SADA benefits from a much broader multi-parameter grid search compared to the baselines, and the CIFAR/MNIST evaluations are averaged over just three random seeds. Consequently, the empirical results neither directly verify the theoretical guarantees nor provide a fully fair comparison against variance-reduced methods.
Our response: We revised CIFAR-10 and MNIST experiments to align the grid search budget. SADA and variance-reduced methods (ROOT-SGD, Streaming SVRG) all evaluate configurations per sample budget. We also increased the number of seeds from to .
The revised results are shown in Figure 1(c) (p. 8, lines 378-391) and Figure 2(a) (p. 46, lines 2430-2445). SADA achieves the lowest test loss among the compared methods at all four budgets on both datasets. On CIFAR-10, at the largest budget of training samples, SADA achieves a mean test loss of , compared with for the best baseline. On MNIST, at the largest budget of training samples, SADA achieves a mean test loss of , compared with for the best baseline.
References
[1] Jaouad Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices. The Annals of Statistics, 50(4), 2157–2178, 2022.
(1/3)
Thank you for reviewing our paper and providing detailed feedback. We address your concerns and questions point by point below.
Our response: Thank you for pointing out these errors in the proof.
We derive the stated energy recursion from Eqs. (35) and (38).
- Eq. (35) reads
\mathbb E_{k-1}F(\tilde{\mathbf x}_k)-F(\mathbf x^*) &\leq \left(1+\frac{3L_{\mathrm{eff}}L_\ell h_k}{2}\right) \left(F(\tilde{\mathbf y}_{k-1})-F(\mathbf x^*)\right) +\frac{3h_k\sigma^2}{2}\\\\ &\quad-\frac{3-2L_\ell h_k}{4L_\ell h_k} \mathbb E_{k-1}\lVert\tilde{\mathbf x}_k-\tilde{\mathbf y}_{k-1}\rVert_{\mathbf H}^2 -\frac{L_\ell h_k}{8} \lVert\nabla F(\tilde{\mathbf y}_{k-1})\rVert_{\mathbf H^{-1}}^2. \end{aligned} \tag{35}$$ Eq. (38) reads $$\begin{aligned} F(\tilde{\mathbf y}_{k-1})-F(\mathbf x^*)&\leq (1-\theta_k)\left(F(\tilde{\mathbf x}_{k-1})-F(\mathbf x^*)\right) +\frac{\alpha}{L_\ell^2}\mathbb E_{k-1}\lVert\mathbf r_k\rVert_{\mathbf H}^2\\\\ &\quad-\left(\frac{\theta_k}{4\alpha}-\frac{\theta_k^3}{2L_\ell h_k}\right) \lVert\tilde{\mathbf y}_{k-1}-\mathbf x^*\rVert_{\mathbf H}^2\\\\ &\quad+\frac{\theta_k^2}{2L_\ell h_k} \left( (1-\theta_k)\lVert\tilde{\mathbf z}_{k-1}-\mathbf x^*\rVert_{\mathbf H}^2 +\mathbb E_{k-1}\lVert\tilde{\mathbf z}_k-\tilde{\mathbf w}_{k-1}\rVert_{\mathbf H}^2 -\mathbb E_{k-1}\lVert\tilde{\mathbf z}_k-\mathbf x^*\rVert_{\mathbf H}^2 \right). \end{aligned} \tag{38}$$ **Overview.** The derivation proceeds in four steps: 1. We substitute Eq. (38) into Eq. (35) and collect terms. 2. We use the step-size bounds to drop two nonpositive squared-norm terms. 3. We apply Lemma D.30 to bound the bias $\mathbf{r}_k$ so that the negative gradient term absorbs it. 4. We bound the amplification factor $1+3L_{\mathrm{eff}}L_\ell h_k/2$ from Eq. (35) by $1+\theta_k/4$. Eq. (38) contributes the contraction factor $1-\theta_k$ on the previous iterate's gap, so the combined factor is at most $1-\theta_k/2$. Telescoping the resulting energy recursion proves the bound in Theorem E.1. **Step 1.** With the momentum schedule in Appendix C, the auxiliary iterates satisfy $\tilde{\mathbf z}_k=\tilde{\mathbf x}_k+(1-\theta_k)(\tilde{\mathbf x}_k-\tilde{\mathbf x}_{k-1})/\theta_k$ and $\tilde{\mathbf w}_{k-1}=(1-\theta_k)\tilde{\mathbf z}_{k-1}+\theta_k\tilde{\mathbf y}_{k-1}$. The same schedule implies $\theta_k(\tilde{\mathbf z}_k-\tilde{\mathbf w}_{k-1})=\tilde{\mathbf x}_k-\tilde{\mathbf y}_{k-1}$. Since $\theta_k^2/(2L_\ell h_k)=1/(4\alpha)$, the term proportional to $\lVert\tilde{\mathbf y}_{k-1}-\mathbf x^*\rVert_{\mathbf H}^2$ vanishes. Substituting Eq. (38) into Eq. (35) yields $$\begin{aligned} &\mathbb E_{k-1}F(\tilde{\mathbf x}_k)-F(\mathbf x^*) +\frac{1}{4\alpha}\mathbb E_{k-1}\lVert\tilde{\mathbf z}_k-\mathbf x^*\rVert_{\mathbf H}^2\\\\ &\leq \left(1+\frac{3L_{\mathrm{eff}}L_\ell h_k}{2}\right)(1-\theta_k) \left(F(\tilde{\mathbf x}_{k-1})-F(\mathbf x^*) +\frac{1}{4\alpha}\lVert\tilde{\mathbf z}_{k-1}-\mathbf x^*\rVert_{\mathbf H}^2\right) +\frac{3h_k\sigma^2}{2}\\\\ &\quad+\left(1+\frac{3L_{\mathrm{eff}}L_\ell h_k}{2}\right) \frac{\alpha}{L_\ell^2}\mathbb E_{k-1}\lVert\mathbf r_k\rVert_{\mathbf H}^2 -\frac{L_\ell h_k}{8}\lVert\nabla F(\tilde{\mathbf y}_{k-1})\rVert_{\mathbf H^{-1}}^2\\\\ &\quad+\frac{3L_{\mathrm{eff}}L_\ell h_k+2L_\ell h_k-1}{4L_\ell h_k} \mathbb E_{k-1}\lVert\tilde{\mathbf x}_k-\tilde{\mathbf y}_{k-1}\rVert_{\mathbf H}^2 -\frac{3L_{\mathrm{eff}}L_\ell h_k}{8\alpha} \mathbb E_{k-1}\lVert\tilde{\mathbf z}_k-\mathbf x^*\rVert_{\mathbf H}^2. \end{aligned}$$ **Step 2.** The step-size schedule in Appendix C ensures $$0\leq \frac{3L_{\mathrm{eff}}L_\ell h_k}{2} \leq \frac{\theta_k}{4\sqrt{2}} \leq \frac{\theta_k}{4} \leq \frac18, \qquad 0<L_\ell h_k\leq\frac16.$$