acceptodds
Under review as a conference paper at ICLR 2027

Accelerating Single-Pass SGD for Generalized Linear Prediction

Abstract

We study generalized linear prediction under a streaming setting, where each iteration uses only one fresh data point for a gradient-level update. While momentum is well-established in deterministic optimization, a fundamental open question is whether it can *accelerate* such single-pass non-quadratic stochastic optimization. We propose the *first* algorithm that successfully incorporates momentum via a novel data-dependent proximal method, achieving dual-momentum acceleration. Our derived excess risk bound decomposes into three components: an *improved* optimization error, a minimax *optimal* statistical error, and a *higher-order* model-misspecification error. The proof handles mis-specification via a fine-grained stationary analysis of inner updates, while localizing statistical error through a two-phase outer-loop analysis. As a result, we resolve the open problem posed by Jain et al. (2018a) and demonstrate that momentum acceleration is more effective than variance reduction for generalized linear prediction in the streaming setting.

Primary area:
optimization
Keywords:
Momentum Acceleration, Data-dependent Proximal Method, Single-Pass SGD

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_fNTQOpenReview ↗
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
  1. 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.
  2. 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
  1. As written, the main convergence proof contains critical gaps. Right after Eq. (38), the right-hand side features F(x~k)−F(x∗)F(\tilde x_k)-F(x^{*}) instead of the preceding iterate's suboptimality; similarly, the proof of Theorem E.1 applies the exponential decay factor to EF(x~K)−F(x∗)\mathbb{E}F(\tilde x_K)-F(x^*) 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 σ2\sigma^2 is omitted initially, and the resulting expression is quietly swapped out when taking the limit. Since Mourtada's actual bound scales as σ2d/(n−d+1)\sigma^2 d / (n-d+1), the claim of minimax optimality is not properly substantiated in the current text.
  2. The experimental setup does not align with the theoretical assumptions. Assumption 1 imposes a strict positive lower bound on ℓ′′\ell'' 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 D,MD, M 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
  1. 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 x~k−1\tilde x_{k-1}? Please also revise the proof of Theorem E.1 so the exponential contraction multiplies the initial optimality gap.
  2. In Appendix G, shouldn't the equation cited from Mourtada include a σ2\sigma^2 factor? Once included, please specify the valid regime for n,d,σn, d, \sigma and walk through how the steps leading to Theorem G.1 hold up.
  3. 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 D,M,ϵD, M, \epsilon and the two auxiliary regularizers. If standard SADA was used, how do the paper's theoretical results apply to those runs?
6 comments

(1/3)

Thank you for reviewing our paper and providing detailed feedback. We address your concerns and questions point by point below.

[W1] As written, the main convergence proof contains critical gaps. Right after Eq. (38), the right-hand side features F(x~k)−F(x∗)F(\tilde{x}_{k})-F(x^{\ast}) instead of the preceding iterate's suboptimality; similarly, the proof of Theorem E.1 applies the exponential decay factor to EF(x~K)−F(x∗)\mathbb{E} F(\tilde{x}_{K})-F(x^{\ast}) 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.

[Q1] 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 x~k−1\tilde{x}_{k-1}? Please also revise the proof of Theorem E.1 so the exponential contraction multiplies the initial optimality gap.

Our response: Thank you for pointing out these errors in the proof.

  • The bound following Eq. (38) now uses the preceding iterate's gap F(x~k−1)−F(x∗)F(\tilde{\mathbf x}_{k-1})-F(\mathbf x^*) on the right-hand side.
  • In the proof of Theorem E.1, the exponential decay factor now multiplies the initial gap F(x~0)−F(x∗)F(\tilde{\mathbf x}_0)-F(\mathbf x^*).

We derive the stated energy recursion from Eqs. (35) and (38).

  1. 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.$$

(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 μℓσ2d(d−1)/(2n(n−d+1))\mu_\ell\sigma^2d(d-1)/(2n(n-d+1)) for the limit inferior, which is positive for d>1d>1. The exact Gaussian bound above also covers d=1d=1. Thus, Theorem G.1 holds for all sufficiently small δ>0\delta>0 at each fixed n>d+1n>d+1, 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 n≥d+1n\geq d+1 does not undermine the minimax argument. The optimization budget in Corollary 5.1 includes a term of order Ω(ακκ~log⁡(1/ε))\Omega(\sqrt{\alpha\kappa\tilde{\kappa}}\log(1/\varepsilon)), which is greater than 2d2d for constant ε>0\varepsilon>0, since α≥1\alpha\geq1 and κ≥κ~≥d\kappa\geq\tilde{\kappa}\geq d. Thus n>d+1n>d+1 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 ℓ′′\ell^{\prime\prime} 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 D,MD,M 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 D,M,ϵD,M,\epsilon 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 μℓ\mu_\ell of the loss ℓ\ell can be obtained by a high-probability argument. While the binary logistic loss ℓ(z,b)=log⁡(1+e−bz)\ell(z,b)=\log(1+e^{-bz}) is not strongly convex on R\mathbb{R}, it is strongly convex on any bounded interval. Suppose X=∥x∗∥ΣX=\Vert\mathbf x^*\Vert_{\mathbf{\Sigma}}. On a high-probability event where the input data norms are bounded, the iterate norm ∥y∥Σ\Vert\mathbf{y}\Vert_{\mathbf{\Sigma}} is bounded with high probability by O~(X)\tilde{O}(X). The logit z=a⊤yz=\mathbf{a}^\top\mathbf{y} is then bounded in magnitude by B=O~(X)B=\tilde{O}(X) with high probability. On [−B,B][-B,B], the loss is μℓ\mu_\ell-strongly convex with μℓ=1/(2+2cosh⁡B)\mu_\ell=1/(2+2\cosh B). In our experiment, X≍1X\asymp 1, so our theory is applicable to the logistic regression setting.

To see what range of logits SADA encounters in practice, we computed B=max⁡kmax⁡i∈Ik∣ai⊤y~k−1∣B=\max_k\max_{i\in I_k}|\mathbf a_i^\top\tilde{\mathbf y}_{k-1}| for SADA on the simulated logistic task, where IkI_k is the training block used at outer iteration kk. The table summarizes the per-run maxima over 2020 repeats.

Training samplesMaximum absolute logit BB
20,0005.23
40,0006.21
60,0007.10

The observed values of BB 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 1616 configurations per sample budget. We also increased the number of seeds from 33 to 2020.

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 8,0008{,}000 training samples, SADA achieves a mean test loss of 0.397630.39763, compared with 0.405630.40563 for the best baseline. On MNIST, at the largest budget of 10,13210{,}132 training samples, SADA achieves a mean test loss of 0.001640.00164, compared with 0.001880.00188 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.

Reviewer_y2AZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies generalized linear prediction in a streaming setting, where each update uses a fresh sample and requires O(d)O(d) computation. The proposed Stochastic Accelerated Data-Dependent Algorithm (SADA) combines an outer accelerated method in the covariance-induced geometry with an inner accelerated stochastic solver and tail averaging. The analysis separates the optimization error, the statistical error, and an additional term associated with model misspecification.

Critical strengths

The problem is important, and the proposed use of covariance geometry and two levels of acceleration offers a potentially significant theoretical contribution. The improvement in optimization complexity is substantive in the intended regime.

The covariance-induced geometry and two levels of acceleration are well motivated, and the condition-number improvement is meaningful when κ~≪κ\widetilde\kappa\ll\kappa and α\alpha is moderate.

Critical weaknesses

The connection to logistic regression is unclear. Ordinary logistic loss does not seem to satisfy the global positive curvature bound in Assumption 1.

The theoretical result seems to be solid, i do not check it by myself, but the implication of this algorithm can be exploited further. For example, can you use it in deep learning or LLM?

Questions for authors

Can the claimed improvement be achieved without knowing the distribution-dependent parameters, and what additional sample cost would parameter estimation introduce? It seems that the algorithm is more of theoretical value, and less practical for use.

2 comments

(1/2)

Thank you for your positive assessment of our paper and your valuable feedback. We address your concerns and questions point by point below.

[W1] The connection to logistic regression is unclear. Ordinary logistic loss does not seem to satisfy the global positive curvature bound in Assumption 1.

Our response: To address the curvature requirement in Assumption 1, we can derive a uniform positive curvature bound for the logistic loss over the range of logits encountered by SADA during training. Specifically, the strong-convexity constant μℓ\mu_\ell of the loss ℓ\ell can be obtained by a high-probability argument. While the binary logistic loss ℓ(z,b)=log⁡(1+e−bz)\ell(z,b)=\log(1+e^{-bz}) is not strongly convex on R\mathbb{R}, it is strongly convex on any bounded interval. Suppose X=∥x∗∥ΣX=\Vert\mathbf x^*\Vert_{\mathbf{\Sigma}}. On a high-probability event where the input data norms are bounded, the iterate norm ∥y∥Σ\Vert\mathbf{y}\Vert_{\mathbf{\Sigma}} is bounded with high probability by O~(X)\tilde{O}(X). The logit z=a⊤yz=\mathbf{a}^\top\mathbf{y} is then bounded in magnitude by B=O~(X)B=\tilde{O}(X) with high probability. On [−B,B][-B,B], the loss is μℓ\mu_\ell-strongly convex with μℓ=1/(2+2cosh⁡B)\mu_\ell=1/(2+2\cosh B). In our experiment, X≍1X\asymp 1, so our theory is applicable to the logistic regression setting.

To see what range of logits SADA encounters in practice, we computed B=max⁡kmax⁡i∈Ik∣ai⊤y~k−1∣B=\max_k\max_{i\in I_k}|\mathbf a_i^\top\tilde{\mathbf y}_{k-1}| for SADA on the simulated logistic task, where IkI_k is the training block used at outer iteration kk. The table summarizes the per-run maxima over 2020 repeats.

Training samplesMaximum absolute logit BB
20,0005.23
40,0006.21
60,0007.10

The observed values of BB 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] The theoretical result seems to be solid, i do not check it by myself, but the implication of this algorithm can be exploited further. For example, can you use it in deep learning or LLM?

Our response: Thank you for pointing out this connection. SADA's inner loop can serve as a stochastic solver for the local quadratic subproblems that arise in Gauss–Newton methods, as in the LLM pretraining approach of Abreu et al. [1]. Specifically, at each outer iteration, we linearize the network around a reference iterate. The linearized network is affine in the parameter displacement, so the inner problem has generalized linear prediction (GLP) structure, with the Jacobian as its feature map. A second-order expansion of the loss in the linearized outputs yields a Gauss–Newton quadratic, which we can solve approximately with SADA's accelerated stochastic inner solver. Hence, we expect an accelerated convergence rate for the inner loop. The resulting direction provides Gauss–Newton preconditioning for the outer update. We think applying our approach to LLM training is an interesting direction. Applying this approach at LLM pretraining scale would require substantial effort, so we leave it for future work.

(2/2)

[Q1] Can the claimed improvement be achieved without knowing the distribution-dependent parameters, and what additional sample cost would parameter estimation introduce? It seems that the algorithm is more of theoretical value, and less practical for use.

Our response: Yes, under a additional (4+ι0)(4+\iota_0)-moment assumption (ι0>0\iota_0>0), the claimed improvement can be achieved without knowing the distribution-dependent parameters. The additional sample cost is O~(d)\tilde{O}(d), whichi is dominated by the optimization term in Corollary 5.1. Specifically, we added a distribution-dependent parameter estimation (DPE) procedure using two independent unlabeled pilot batches of size m0m_0 each.

  1. Use the first batch ai(0)i=1m0\\{\mathbf a_i^{(0)}\\}_{i=1}^{m_0} to estimate the second moment and its smallest eigenvalue.

    Σ^=1m0∑i=1m0ai(0)(ai(0))⊤,μ^=λmin⁡(Σ^).\widehat{\boldsymbol{\Sigma}}=\frac{1}{m_0}\sum_{i=1}^{m_0}\mathbf a_i^{(0)}(\mathbf a_i^{(0)})^\top,\quad \widehat{\mu}=\lambda_{\min}\left(\widehat{\boldsymbol{\Sigma}}\right).

  2. Use the second batch aii=1m0\\{\mathbf a_i\\}_{i=1}^{m_0} to estimate the fourth-moment parameters. With moment parameter ι\iota (defined below) and failure probability δ\delta, use the thresholds

    A=(m0dlog⁡(12d/δ))4/(4+ι),TR2=Ad tr⁡(Σ^),Tκ~=Ad2.A=\left(\frac{m_0}{d\log(12d/\delta)}\right)^{4/(4+\iota)},\quad T_{R^2}=A d\,\operatorname{tr}\left(\widehat{\boldsymbol{\Sigma}}\right),\quad T_{\tilde{\kappa}}=A d^2.

    Define the whitened features zi=Σ^−1/2ai\mathbf z_i=\widehat{\boldsymbol{\Sigma}}^{-1/2}\mathbf a_i. Let clip⁡t(M)\operatorname{clip}_t(\mathbf M) cap each eigenvalue of a positive semidefinite matrix M\mathbf M at tt. We use the estimators

    R2^=∥1m0∑i=1m0clip⁡TR2(∥ai∥2zizi⊤)∥op,κ~^=∥1m0∑i=1m0clip⁡Tκ~(∥zi∥2zizi⊤)∥op,κ^=R2^μ^.\widehat{R^2}=\left\Vert\frac{1}{m_0}\sum_{i=1}^{m_0}\operatorname{clip}_{T_{R^2}}\left(\Vert\mathbf a_i\Vert^2\mathbf z_i\mathbf z_i^\top\right)\right\Vert_{\mathrm{op}},\quad\widehat{\tilde{\kappa}}=\left\Vert\frac{1}{m_0}\sum_{i=1}^{m_0}\operatorname{clip}_{T_{\tilde{\kappa}}}\left(\Vert\mathbf z_i\Vert^2\mathbf z_i\mathbf z_i^\top\right)\right\Vert_{\mathrm{op}},\quad\widehat{\kappa}=\frac{\widehat{R^2}}{\widehat{\mu}}.

We plug these estimates into the hyperparameter rules with η≤1/(16R2^)\eta\leq1/(16\widehat{R^2}) and γ=14η/(μ^ κ~^)\gamma=\frac{1}{4}\sqrt{\eta/(\widehat{\mu}\,\widehat{\tilde{\kappa}})}. See Appendices C.1 and J.2 for more details.

Theoretical Guarantees. Under a (4+ι)(4+\iota)-moment condition (ι>0\iota>0) in Appendix C.1, m0=O~(d)m_0=\tilde{O}(d) samples suffice to estimate R2R^2, μ\mu, κ~\tilde{\kappa} and κ\kappa. We note that the additional O~(d)\tilde{O}(d) is dominated by the optimization term ακκ~log⁡(1/ε)\sqrt{\alpha\kappa\tilde{\kappa}}\log(1/\varepsilon), which is at least of order dlog⁡(1/ε)d\log(1/\varepsilon), since κ≥κ~≥d\kappa\geq\tilde{\kappa}\geq d.

To support the practical feasibility of DPE, we compared the performance of SADA tuned by DPE with that of SADA tuned by validation grid search. In the d=20d=20 linear regression experiment, DPE achieves comparable test loss at all six budgets with either 100100 or 200200 additional unlabeled pilot samples (Figure 6, p. 51).

Another common method is validation grid search. The overhead is at most a logarithmic factor. The sensitivity analysis in Appendix I.1.4 suggests that the performance of SADA is robust to moderate changes in its hyperparameters, so a coarse grid search can suffice in practice.

In addition, SADA shows clear gains from acceleration in the ill-conditioned synthetic settings (Figures 3(a) and 4) and achieves the lowest mean test loss among the compared methods at all four training budgets on both CIFAR-10 and MNIST (Figures 1(c) and 2(a)). We think these experiments support the practical use of SADA.

References

[1] Natalie Abreu, Nikhil Vyas, Sham Kakade, and Depen Morwani. The Potential of Second-Order Optimization for LLMs: A Study with Full Gauss-Newton. ICLR, 2026. [2] Li, Chris Junchi, Wenlong Mou, Martin Wainwright, and Michael Jordan. Root-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm. COLT, 2022.

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

The paper studies Generalized Linear Prediction for Strongly convex functions with bounded feature covariance and 4th moment and proposes SADA, which combines an outer loop that uses momentum extrapolation with an inner loop that uses accelerated SGD to solve quadratic subproblems.

Critical strengths
  • The paper extends GLP in the streaming setting beyond quadratic objectives, while preserving a sharp statistical rate.
  • Replacing the optimization cost α2κ\alpha^2\kappa with ακκ~+α2κ~\sqrt{\alpha\kappa\widetilde{\kappa}}+\alpha^2\widetilde{\kappa} provides a substantial improvement when κ~≪κ\widetilde{\kappa}\ll\kappa. For constant α\alpha, this corresponds to an improvement by a factor of approximately κ/κ~\sqrt{\kappa/\widetilde{\kappa}}.
  • The setup proposed by the authors can have an impact in analysing logistic regression for linear softmax policies.
Critical weaknesses
  • The benefits can fade away when the statistically optimal rate term dominates. Also, the gains are modest when κ~\widetilde{\kappa} is comparable to κ\kappa.
  • The synthetic experiments do not vary κ~κ\frac{\widetilde{\kappa}}{\kappa} nor do they vary α\alpha.
  • In Appendix I, it looks like the experiments were tuned on the test set, also, ROOT-SGD seems to use smaller grids when compared to SADA.
  • The logistic experiments are not strongly convex with (a universal μ\mu), which is an assumption made by theory.
  • Also, the ablation in Appendix I to test outer momentum vs no outer momentum seems to remove outer momentum and replaces the quadratic objective with the actual gradient, the ideal experiment would only remove the outer momentum.
  • The statistical rate provided in Theorem 5.1$\frac{\alpha}{n}\text{Tr}(H^{-1}Q)$ is an upper bound on the one provided by ROOT-SGD 12ntr⁡(H∗−1Q)\frac{1}{2n}\operatorname{tr}(H_*^{-1}Q), so depending on the number of samples, this need not be a sharper rate.
  • The limit for QδQ_\delta omits σ2\sigma^2 and lδ(z)l_\delta(z) does not join continuously to the central branch, In Appendix G, while proving the necessity of α\alpha in the statistical rate.
Questions for authors
  • Can the authors vary κ~κ\frac{\widetilde{\kappa}}{\kappa} and α\alpha in the synthetic experiments?
  • Can the authors compare tuning budgets and use a separate validation split when comparing SADA and ROOT-SGD.
  • Can the authors redo the outer momentum vs no outer momentum experiment?
  • In practice, how would you tune parameters like eta and gamma since quantities like R2R^2, μ\mu, κ~\widetilde{\kappa} and κ\kappa are usually not known.
  • Solving quadratic sub problems have also been explored for LLM training [1], do the authors seen their results applicable in training and understanding LLM training?

[1] The Potential of Second-Order Optimization for LLMs: A Study with Full Gauss-Newton. Natalie Abreu, Nikhil Vyas, Sham Kakade, and Depen Morwani. ICLR, 2026

4 comments

(1/3)

Thank you for reviewing our paper and providing detailed feedback. We address your concerns and questions point by point below.

[W1] The benefits can fade away when the statistically optimal rate term dominates. Also, the gains are modest when κ~\tilde{\kappa} is comparable to κ\kappa.

Our response: SADA accelerates the decay of the initial error. Hence, its excess risk is smaller when the optimization error dominates. We note that κ≥κ~\kappa\geq\tilde{\kappa} always holds. In the Gaussian and sub-Gaussian setting, SADA achieves an optimization cost of αtr⁡(Σ)dμ+α2d\sqrt{\frac{\alpha\operatorname{tr}(\mathbf{\Sigma})d}{\mu}}+\alpha^2 d. The dependence on dd is natural because fewer than dd feature vectors leave some directions unobserved, even in noiseless linear regression. This resembles the finite-sum setting, where acceleration improves the rate from κ+n\kappa+n to κn+n\sqrt{\kappa n}+n, with the clearest gains only when κ≫n\kappa\gg n.

[W2] The synthetic experiments do not vary κ~κ\frac{\tilde{\kappa}}{\kappa} nor do they vary α\alpha.

[Q1] Can the authors vary κ~κ\frac{\tilde{\kappa}}{\kappa} and α\alpha in the synthetic experiments?

Our response: We added two synthetic experiments that vary κ~/κ\tilde{\kappa}/\kappa and α\alpha. The settings and results are detailed in Appendix I.1.2.

  • For the κ~/κ\tilde{\kappa}/\kappa sweep (Figure 3(a), p. 47, lines 2511–2521), we use the linear regression setting with data covariance eigenvalues λi=i−p,p∈1,2,3,4,5\lambda_i=i^{-p},p\in{1,2,3,4,5}. In the most ill-conditioned setting (p=5p=5), SADA achieves a mean test loss of 0.8720.872, compared with 1.1291.129 for the best baseline (ROOT-SGD).

  • For the α\alpha sweep (Figure 3(b), p. 47, lines 2522–2529), we fix p=4p=4 and use the loss ℓ(z,b)=12(z−b)2+(α−1)log⁡cosh⁡(z−b)\ell(z,b)=\frac{1}{2}(z-b)^2+(\alpha-1)\log\cosh(z-b). SADA achieves the lowest mean test loss at every tested value of α∈1,2,4,8,16\alpha\in\\{1,2,4,8,16\\} (Figure 3(b)). At α=16\alpha=16, the mean excess risk of SADA on the test set is 0.5370.537, which is 85.1%85.1\% lower than the best baseline.

These results demonstrate that SADA's acceleration yields clear gains in ill-conditioned settings.

Results are averaged over 2020 independent repeats at a sample budget of 60,00060{,}000.

Excess risk across condition-number ratios κ~/κ\tilde{\kappa}/\kappa. See also Figure 3(a) (p. 47, lines 2522–2529).

ppκ~/κ\tilde{\kappa}/\kappaSADAROOT-SGDStreaming SVRGSGDKatyushaOffline GD
32.08×10−32.08\times10^{-3}<10−3<10^{-3}<10−3<10^{-3}0.9110.0340.2471.458
41.15×10−41.15\times10^{-4}0.1300.3481.4220.6980.9861.677
56.03×10−66.03\times10^{-6}0.7471.0041.6191.2491.3741.765

Excess risk across loss curvatures α\alpha. See also Figure 3(b) (p. 47, lines 2522–2529).

α\alphaSADAROOT-SGDStreaming SVRGSGDKatyushaOffline GD
10.1300.3481.4220.6980.9861.677
20.0970.4792.1530.9911.5372.590
40.2160.9213.7101.4772.6374.396
80.3511.8666.7992.2994.8967.996
160.5373.74913.0043.6119.38915.189

[W3] In Appendix I, it looks like the experiments were tuned on the test set, also, ROOT-SGD seems to use smaller grids when compared to SADA.

[Q2] Can the authors compare tuning budgets and use a separate validation split when comparing SADA and ROOT-SGD.

Our response: We revised all experiments. Across all experiments, we now select hyperparameters on a separate validation set and evaluate the selected models on the test data. We also matched the grid sizes for SADA and ROOT-SGD on both datasets (Appendix I.2.3).

  • SADA. On CIFAR-10, we search η∈5×10−5,10−4,2×10−4,4×10−4\eta\in\\{5\times10^{-5},10^{-4},2\times10^{-4},4\times10^{-4}\\} and θ∈0,0.001,0.002,0.004\theta\in\\{0,0.001,0.002,0.004\\}. On MNIST, we search η∈6.25×10−4,1.25×10−3,2.5×10−3,5×10−3\eta\in\\{6.25\times10^{-4},1.25\times10^{-3},2.5\times10^{-3},5\times10^{-3}\\} and θ∈0,2.5×10−5,5×10−5,10−4\theta\in\\{0,2.5\times10^{-5},5\times10^{-5},10^{-4}\\}.
  • ROOT-SGD. We search the learning-rate multiplier cη∈1,2,4,8c_\eta\in\\{1,2,4,8\\} and decay parameter ρ∈0,5×10−5,10−4,2×10−4\rho\in\\{0,5\times10^{-5},10^{-4},2\times10^{-4}\\}, with η=cηη0\eta=c_\eta\eta_0 and ηt=η/(1+ρt)\eta_t=\eta/(1+\rho t).

SADA and ROOT-SGD each search 1616 configurations per budget. The following table reports the number of searched configurations and the total search time for each dataset across all four budgets on an NVIDIA GeForce RTX 3060 Laptop GPU.

Dataset# SADA hyperparameter configurationsSADA total search time (s)# ROOT-SGD hyperparameter configurationsROOT-SGD total search time (s)
MNIST16173.116137.8
CIFAR-1016139.416113.0

With these nearly matching search budgets, SADA achieves lower mean test loss than ROOT-SGD at all four training budgets on both datasets (Figure 1(c), p. 8, lines 378–391, and Figure 2(a), p. 46, lines 2430–2445).

(2/3)

[W4] The logistic experiments are not strongly convex with (a universal μ\mu), which is an assumption made by theory.

Our response: The strong-convexity constant μℓ\mu_\ell of the loss ℓ\ell can be obtained by a high-probability argument. While the binary logistic loss ℓ(z,b)=log⁡(1+e−bz)\ell(z,b)=\log(1+e^{-bz}) is not strongly convex on R\mathbb{R}, it is strongly convex on any bounded interval. Suppose X=∥x∗∥ΣX=\Vert\mathbf x^*\Vert_{\mathbf{\Sigma}}. On a high-probability event where the input data norms are bounded, the iterate norm ∥y∥Σ\Vert\mathbf{y}\Vert_{\mathbf{\Sigma}} is bounded with high probability by O~(X)\tilde{O}(X). The logit z=a⊤yz=\mathbf{a}^\top\mathbf{y} is then bounded in magnitude by B=O~(X)B=\tilde{O}(X) with high probability. On [−B,B][-B,B], the loss is μℓ\mu_\ell-strongly convex with μℓ=1/(2+2cosh⁡B)\mu_\ell=1/(2+2\cosh B). In our experiment, X≍1X\asymp 1, so our theory is applicable to the logistic regression setting.

To see what range of logits SADA encounters in practice, we computed B=max⁡kmax⁡i∈Ik∣ai⊤y~k−1∣B=\max_k\max_{i\in I_k}|\mathbf a_i^\top\tilde{\mathbf y}_{k-1}| for SADA on the simulated logistic task, where IkI_k is the training block used at outer iteration kk. The table summarizes the per-run maxima over 2020 repeats.

Training samplesMaximum absolute logit BB
20,0005.23
40,0006.21
60,0007.10

The observed values of BB 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.

[W5] Also, the ablation in Appendix I to test outer momentum vs no outer momentum seems to remove outer momentum and replaces the quadratic objective with the actual gradient, the ideal experiment would only remove the outer momentum.

[Q3] Can the authors redo the outer momentum vs no outer momentum experiment?

Our response: We added a momentum ablation in the logistic simulation (d=20d=20), comparing (1) full SADA with three variants that retain (2) only outer momentum (γ=η\gamma=\eta, θ=0\theta=0), (3) only inner momentum (βk=0\beta_k=0), or (4) no momentum. Disabling outer momentum is the sole change in the inner-momentum-only variant. It uses the same quadratic subproblem formulation and inner-loop solver. We show the full results in Appendix I.1.3 and Figure 4 (p. 48, lines 2549–2551 and 2572–2581). The "SADA" and "Inner momentum only" curves in Figure 4 show the requested comparison of "outer momentum vs no outer momentum". Full SADA achieves the lowest mean test loss at all six budgets, showing that removing either momentum term worsens performance. This indicates that both inner and outer momentum contribute to its performance in this setting.

The original ablation was designed to assess the contribution of the two-loop scheme, and our wording made it unclear what is removed. We now label them "Outer loop only" and "Inner loop only" in Figure 2(b), clarify the comparison in its caption (p. 46, lines 2443–2445), and describe their updates in the "Effect of the two-loop scheme" paragraph (Appendix I.1.3, p. 47, lines 2532–2537).

[W6] The statistical rate provided in Theorem 5.1 αnTr(H−1Q)\frac{\alpha}{n} \text{Tr}(H^{-1}Q) is an upper bound on the one provided by ROOT-SGD 12ntr⁡(H∗−1Q)\frac{1}{2n}\operatorname{tr}(H_\ast^{-1}Q), so depending on the number of samples, this need not be a sharper rate.

Our response: The ROOT-SGD guarantee with leading term tr⁡(H∗−1Q)/(2n)\operatorname{tr}(\mathbf{H}_{*}^{-1}\mathbf{Q})/(2n) requires an additional Lipschitz condition on the Hessian (Li et al. [2], Assumption 4). In contrast, SADA does not require such a condition. Appendix G establishes worst-case sharpness of the statistical bound αtr⁡(H−1Q)/n\alpha\operatorname{tr}(\mathbf{H}^{-1}\mathbf{Q})/n in our setting (without Hessian Lipschitz). With the additional Hessian regularity, we conjecture that a version of SADA that uses cubic regularization could attain the leading term tr⁡(H∗−1Q)/(2n)\operatorname{tr}(\mathbf{H}_*^{-1}\mathbf{Q})/(2n). We discuss cubic regularization at the end of Section 8 and leave this direction for future work.

[W7] The limit for QδQ_{\delta} omits σ2\sigma^{2} and lδ(z)l_{\delta}(z) does not join continuously to the central branch, In Appendix G, while proving the necessity of α\alpha in the statistical rate.

Our response: Thank you for pointing out the typos.

  • We corrected the sign of the linear term in the left branch of ℓδ\ell_\delta and restored the factor σ2\sigma^2 in the covariance limit. The corrected loss is
\begin{cases} \mu_\ell z^2/2-(L_\ell-\mu_\ell)\delta z-(L_\ell-\mu_\ell)\delta^2/2, & z < -\delta,\\\\ L_\ell z^2/2, & \vert z\vert\leq\delta,\\\\ \mu_\ell z^2/2+(L_\ell-\mu_\ell)\delta z-(L_\ell-\mu_\ell)\delta^2/2, & z > \delta. \end{cases}$$ The branches meet at value $L_\ell\delta^2/2$ and slope $\pm L_\ell\delta$ at $z=\pm\delta$.

(3/3)

W7 (continued).

  • The correct form of the limit for QδQ_{\delta} is lim⁡δ→0Qδ=μℓ2σ2Σ\lim_{\delta\to0}Q_\delta=\mu_\ell^2\sigma^2\Sigma. We added the missing σ2\sigma^2.

[Q4] In practice, how would you tune parameters like eta and gamma since quantities like R2R^{2}, μ\mu, κ~\tilde{\kappa} and κ\kappa are usually not known.

Our response: We added a distribution-dependent parameter estimation (DPE) procedure using two independent unlabeled pilot batches of size m0m_0 each.

  1. Use the first batch ai(0)i=1m0\\{\mathbf a_i^{(0)}\\}_{i=1}^{m_0} to estimate the second moment and its smallest eigenvalue.

    Σ^=1m0∑i=1m0ai(0)(ai(0))⊤,μ^=λmin⁡(Σ^).\widehat{\boldsymbol{\Sigma}}=\frac{1}{m_0}\sum_{i=1}^{m_0}\mathbf a_i^{(0)}(\mathbf a_i^{(0)})^\top,\quad \widehat{\mu}=\lambda_{\min}\left(\widehat{\boldsymbol{\Sigma}}\right).

  2. Use the second batch aii=1m0\\{\mathbf a_i\\}_{i=1}^{m_0} to estimate the fourth-moment parameters. With moment parameter ι\iota (defined below) and failure probability δ\delta, use the thresholds

    A=(m0dlog⁡(12d/δ))4/(4+ι),TR2=Ad tr⁡(Σ^),Tκ~=Ad2.A=\left(\frac{m_0}{d\log(12d/\delta)}\right)^{4/(4+\iota)},\quad T_{R^2}=A d\,\operatorname{tr}\left(\widehat{\boldsymbol{\Sigma}}\right),\quad T_{\tilde{\kappa}}=A d^2.

    Define the whitened features zi=Σ^−1/2ai\mathbf z_i=\widehat{\boldsymbol{\Sigma}}^{-1/2}\mathbf a_i. Let clip⁡t(M)\operatorname{clip}_t(\mathbf M) cap each eigenvalue of a positive semidefinite matrix M\mathbf M at tt. We use the estimators

    R2^=∥1m0∑i=1m0clip⁡TR2(∥ai∥2zizi⊤)∥op,κ~^=∥1m0∑i=1m0clip⁡Tκ~(∥zi∥2zizi⊤)∥op,κ^=R2^μ^.\widehat{R^2}=\left\Vert\frac{1}{m_0}\sum_{i=1}^{m_0}\operatorname{clip}_{T_{R^2}}\left(\Vert\mathbf a_i\Vert^2\mathbf z_i\mathbf z_i^\top\right)\right\Vert_{\mathrm{op}},\quad\widehat{\tilde{\kappa}}=\left\Vert\frac{1}{m_0}\sum_{i=1}^{m_0}\operatorname{clip}_{T_{\tilde{\kappa}}}\left(\Vert\mathbf z_i\Vert^2\mathbf z_i\mathbf z_i^\top\right)\right\Vert_{\mathrm{op}},\quad\widehat{\kappa}=\frac{\widehat{R^2}}{\widehat{\mu}}.

We plug these estimates into the hyperparameter rules with η≤1/(16R2^)\eta\leq1/(16\widehat{R^2}) and γ=14η/(μ^ κ~^)\gamma=\frac{1}{4}\sqrt{\eta/(\widehat{\mu}\,\widehat{\tilde{\kappa}})}. See Appendices C.1 and J.2 for more details.

Theoretical Guarantees. Under a (4+ι)(4+\iota)-moment condition (ι>0\iota>0) in Appendix C.1, O~(d)\tilde{O}(d) samples suffice to estimate R2R^2, μ\mu, κ~\tilde{\kappa} and κ\kappa. We note that the additional O~(d)\tilde{O}(d) is dominated by the optimization term ακκ~log⁡(1/ε)\sqrt{\alpha\kappa\tilde{\kappa}}\log(1/\varepsilon), which is at least of order dlog⁡(1/ε)d\log(1/\varepsilon), since κ≥κ~≥d\kappa\geq\tilde{\kappa}\geq d.

To support the practical feasibility of DPE, we compared the performance of SADA tuned by DPE with that of SADA tuned by validation grid search. In the d=20d=20 linear regression experiment, DPE achieves comparable test loss at all six budgets with either 100100 or 200200 additional unlabeled pilot samples (Figure 6, p. 51).

Another common method is validation grid search. The overhead is at most a logarithmic factor. The sensitivity analysis in Appendix I.1.4 suggests that the performance of SADA is robust to moderate changes in its hyperparameters, so a coarse grid search can suffice in practice.

[Q5] Solving quadratic sub problems have also been explored for LLM training [1], do the authors seen their results applicable in training and understanding LLM training?

Our response: Thank you for pointing out this connection. SADA's inner loop can serve as a stochastic solver for the local quadratic subproblems that arise in Gauss–Newton methods, as in the LLM pretraining approach of Abreu et al. [1]. Specifically, at each outer iteration, we linearize the network around a reference iterate. The linearized network is affine in the parameter displacement, so the inner problem has generalized linear prediction (GLP) structure, with the Jacobian as its feature map. A second-order expansion of the loss in the linearized outputs yields a Gauss–Newton quadratic, which we can solve approximately with SADA's accelerated stochastic inner solver. Hence, we expect an accelerated convergence rate for the inner loop. The resulting direction provides Gauss–Newton preconditioning for the outer update. We think applying our approach to LLM training is an interesting direction. Applying this approach at LLM pretraining scale would require substantial effort, so we leave it for future work.

References

[1] Natalie Abreu, Nikhil Vyas, Sham Kakade, and Depen Morwani. The Potential of Second-Order Optimization for LLMs: A Study with Full Gauss-Newton. ICLR, 2026.

I thank the authors for their detailed reponse, I have increased my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and Discussion

Dear Reviewers, ACs, SACs, and PCs,

Thank you for your time and effort. We summarize the additional evidence addressing the reviewers' concerns and the discussion status below.

Concerns and changes

  • Experimental setting and fairness. (1) We now use a separate validation set for hyperparameter search throughout the experiments. (2) On CIFAR-10 and MNIST, SADA, ROOT-SGD, and Streaming SVRG each evaluate 16 configurations per training budget, so the comparison uses matched tuning budgets. (3) To improve the reliability of the real-data results, we increased the number of independent runs from 3 to 20 (Appendix I.2).
  • Additional experiments. (1) We varied data conditioning and loss curvature in the synthetic experiments. SADA achieved lower test loss than the baselines in the two most ill-conditioned settings (Figure 3). (2) We also added an ablation that isolates the effects of inner and outer momentum (Figure 4).
  • Practical hyperparameter selection. We added a DPE procedure for tuning SADA with unlabeled pilot data. With 100 or 200 additional unlabeled samples, it achieved test loss comparable to or lower than that achieved by validation grid search in the linear regression experiment (Appendix J.2 and Figure 6).
  • Clarification of the assumptions in the logistic-regression experiments. We explained how a high-probability bound on the logit range yields the positive curvature required by our analysis. The logit ranges observed in the simulation support this argument.
  • Clarification of the derivation. We detailed how Eq. (35) and Eq. (38) yield the outer-loop energy recursion, and clarified the derivation of the minimax lower bound.

Discussion status

ReviewerRatingReviewer’s further feedbackCurrent status
mHd62 →\to 3The reviewer thanked us for the detailed response.We addressed the reviewer's concerns in our rebuttal. The reviewer thanked us for the detailed response and raised the rating to 33.
y2AZ3No follow-up received.We consider the concerns addressed. No further questions or concerns received.
fNTQ2The reviewer thanked the response, and raise a new concern that K=1K=1 in the CIFAR-10 experment cannot support the effectiveness of the "dual-momentum" mechanismWe reran the CIFAR-10 experiment with K=3K=3, enabling outer momentum. The updated results support the effectiveness of dual momentum (Figure 1(c), p. 8). Furthermore, our other experiments already used K>1K>1 (e.g., K=50K=50 on MNIST (Figure 2(a), p. 46)), and also support the effectiveness of dual momentum. In the ablation study of the momentum, disabling either momentum term increases test loss (Figure 4, p. 48). We think the revision and other experments well supports the effect of the "dual" momentum. We think these can resolve reviewer fNTQ's concerns, but we have not received further response.

Best regards,
The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.