acceptodds
Under review as a conference paper at ICLR 2027

Online Bootstrap for Averaged Stochastic Approximation with Momentum

Abstract

We develop an online multiplier bootstrap for inference on parameters estimated by Polyak–Ruppert averaging in two classes of stochastic approximation algorithms: fixed momentum with fixed preconditioning, and dynamic preconditioning without momentum. The procedure updates weighted replicas alongside the original recursion, preserving one-pass computation and avoiding explicit estimation of the asymptotic covariance. Under mean and score regularity and rate conditions for both the original and weighted paths, we show that fixed momentum and fixed preconditioning do not affect the first-order influence function, and the resulting bootstrap remains valid for nonsmooth problems such as quantile regression. For dynamic preconditioning, we establish conditions under which the evolving preconditioner is asymptotically negligible, allowing bootstrap replicas to either reuse the original preconditioner sequence or maintain their own curvature states. This flexibility makes it possible to trade computational cost against how closely the replicas reproduce the original algorithm, without changing first-order inference. The framework supports valid inference with a fixed number of replicas as well as empirical bootstrap quantiles when more replicas are available. We also show that multiple evaluations generated from the same observation should share a common multiplier to preserve the correct covariance structure. Simulations and an application to the UCI Adult data illustrate the finite-sample performance and practical implementation of the proposed approach.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bootstrap, Momentum, Online learning, Stochastic Approximation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_SF6EOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies online multiplier bootstrap inference for Polyak–Ruppert averaged stochastic approximation. The analysis covers fixed momentum with fixed preconditioning as well as dynamic preconditioning without momentum. The authors establish bootstrap validity under suitable regularity and stability conditions. For dynamic preconditioning, they also show that bootstrap replicas could share the original preconditioner sequence without changing the first-order inference. The proposed method is evaluated through regression simulations and an application to the Adult data.

Critical strengths
  1. The paper extends online bootstrap inference to averaged stochastic approximation with fixed momentum or dynamic preconditioning. Their analysis also allows nonsmooth scores such as the quantile regression score.

  2. The first-order equivalence between frozen and joint replicas is practically useful. Replicas could share the original preconditioner sequence, which reduces computation and storage.

Critical weaknesses
  1. The bootstrap guarantees require mean-square convergence rates for the original and weighted recursions. These rates are not verified for the quantile and logistic regression applications, which might limit how the results could be applied to these settings.

  2. The experiments provide limited evidence for practical inference. The momentum comparison uses the true parameter to select step sizes, and the dynamic preconditioning experiment uses the true response probabilities in its curvature update. The correlated Gaussian experiments indicate severe undercoverage. In addition, it remains unclear whether the proposed method provides reliable inference with feasible tuning and curvature estimation.

Questions for authors
  1. In the dynamic preconditioning experiment, do frozen and joint replicas give similar coverage when the curvature update uses the current parameter estimates instead of the true response probabilities?

  2. I wonder if there's a tuning rule that does not use the true parameter? If so, does it give reliable coverage in the correlated Gaussian settings of Table 1?

4 comments

Thank you for your time and valuable comments.

Note: Because of the 5000-character limit, we divided our response into two comments.

W1. Condition (40) provides a sufficient global quadratic drift route. For the logistic and quantile examples, the following convex risk argument supplies an alternative primitive rate result.

Let FF be the finite population excess loss, with F(θ⋆)=0F(\theta_\star)=0, and let g=∇Fg=\nabla F. Assume that FF is globally convex, g(θ⋆)=0g(\theta_\star)=0, ∣g(θ)∣≤M\\|g(\theta)\\|\le M, and gg is globally LL-Lipschitz. Assume also that, for some r,μ>0r,\mu > 0,

\qquad (\\|e\\|\le r).$$ A positive-definite derivative of $g$ at the target implies this local radial-drift condition. For the recursion without momentum, use deterministic finite initialization and $\eta_t=\eta_0t^{-\alpha}$ with $1/2 < \alpha < 1$. The preconditioner is predictable and symmetric, with deterministic bounds $$0 < p_- I\preceq P_t\preceq p_+ I < \infty.$$ Write $H_t=W_tG(\theta_{t-1},Z_t)$, where the fresh observation and multiplier are independent of the past, the multiplier is independent of the observation, and $\mathbb E W_t=1$. Assume $\mathbb E(H_t\mid\mathcal F_{t-1})=g(\theta_{t-1})$ and a state-uniform envelope $\\|H_t\\|\le J_t$, where the fresh envelopes have a common law satisfying $\mathbb E\exp(\lambda J_t) < \infty$ for some $\lambda > 0$. The original recursion uses $W_t\equiv1$. To verify the rate, put $s=\\|\theta-\theta_\star\\|$. Convexity along rays and the local drift give $$F(\theta)\ge \frac{\mu s^2}{2}\quad(s\le r), \qquad F(\theta)\ge \mu r s-\frac{\mu r^2}{2}\quad(s\ge r),$$ and $\\|g(\theta)\\|\ge\mu\min\\{s,r\\}$. Also $F(\theta)\le Ls^2/2$ locally. Consequently, for $V(\theta)=\exp\\{aF(\theta)\\}-1$ and any fixed sufficiently small $a > 0$, there are positive constants such that $$\\|\theta-\theta_\star\\|^2\le C V(\theta), \qquad \nabla V(\theta)^\top P_tg(\theta)\ge c_0V(\theta).$$ Indeed, near the target $\\|g\\|^2\ge 2\mu^2F/L$, and outside the radius-$r$ ball $\\|g\\|\ge\mu r$. These bounds imply $\\|g\\|^2\ge c(1-e^{-aF})$, which yields the second inequality. The bounded Lipschitz gradient gives the Taylor bound $$\lvert V(\theta+h)-V(\theta)-\nabla V(\theta)^\top h\rvert \le C(1+V(\theta))\\|h\\|^2e^{aM\\|h\\|}.$$ Choose $a$ so that $aMp_+\eta_0 < \lambda/2$. The envelope then bounds the conditional expected remainder for $h=-\eta_tP_tH_t$ by $C\eta_t^2(1+V(\theta_{t-1}))$, and ensures finite exponential Lyapunov moments at every finite time. Thus, for all sufficiently large $t$, $$\mathbb E[V(\theta_t)\mid\mathcal F_{t-1}] \le (1-c_0\eta_t+C\eta_t^2)V(\theta_{t-1})+C\eta_t^2 \le (1-c\eta_t)V(\theta_{t-1})+C\eta_t^2.$$ Taking expectations and using $\eta_{t-1}/\eta_t=1+O(t^{-1})=1+o(\eta_t)$ shows that $\mathbb E V(\theta_t)/\eta_t$ is bounded: its recurrence is eventually bounded above by $(1-c\eta_t/2)\mathbb E V(\theta_{t-1})/\eta_{t-1}+C\eta_t$. Therefore $$\mathbb E\\|\theta_t-\theta_\star\\|^2=O(\eta_t).$$ *Continued in Part 2/2: W1 continued: fixed momentum and model verification; W2 and Q1–Q2.*

Part 2/2 of our response to Reviewer SF6E (continued): W1 continued: fixed momentum and model verification; W2 and Q1–Q2.

For fixed normalized momentum, assume in addition a uniformly bounded score and bounded multipliers, a fixed symmetric positive-definite PP, deterministic finite initial states, and 0≤β<10\le\beta < 1. With

\qquad z_t=\theta_t-\frac{\beta}{1-\beta}\eta_tPm_t,$$ the filter states are uniformly bounded and the exact transformed update is $$z_t=z_{t-1}-\eta_tP W_tG(\theta_{t-1},Z_t) +\frac{\beta}{1-\beta}(\eta_{t-1}-\eta_t)Pm_{t-1}.$$ Here $\\|\theta_{t-1}-z_{t-1}\\|=O(\eta_{t-1})$ and $\eta_{t-1}-\eta_t=O(\eta_t/t)$. Lipschitz continuity of $g$ therefore changes the conditional mean increment from $-\eta_tPg(z_{t-1})$ by $O(\eta_t^2)$. Since $\\|\nabla V(z)\\|\le aM(1+V(z))$, this perturbation and the Taylor remainder contribute at most $C\eta_t^2(1+V(z_{t-1}))$. Absorbing its $V$-dependent part into the negative drift gives $$\mathbb E[V(z_t)\mid\mathcal F_{t-1}] \le(1-c\eta_t)V(z_{t-1})+C\eta_t^2$$ eventually. The comparison argument in Part 1/2 yields $\mathbb E V(z_t)=O(\eta_t)$, and $\\|\theta_t-z_t\\|=O(\eta_t)$ gives the same mean-square rate for $\theta_t$. For logistic regression, assume a finite identified target with positive-definite population Hessian. Its convex loss has $\\|G(\theta;X,Y)\\|\le\\|X\\|$ and a globally Lipschitz mean gradient whenever $\mathbb E\\|X\\|^2 < \infty$. Bounded covariates and bounded nonnegative mean-one multipliers therefore verify the fixed-momentum conditions. Without momentum, bounded multipliers and an exponential moment of $\\|X\\|$ verify the envelope condition, including Gaussian covariates, for predictable preconditioners satisfying the two-sided spectral bounds in Part 1/2. For quantile regression, use bounded covariates, bounded nonnegative mean-one multipliers, conditions (i)–(iii) of the submitted Corollary C.5, and a uniform global upper bound on the conditional density. The quantile excess risk is convex, the score is bounded, and the global density bound makes its mean gradient Lipschitz. The positive-definite target Jacobian supplies the local radial drift. This verifies the fixed-momentum rate without projecting or changing the score. The inference result retains $\alpha(1+\nu) > 1$. These are sufficient path-rate results under additional assumptions. Curvature variation remains a separate requirement for dynamic-preconditioning inference, and the broader finite-moment corollaries remain conditional on separately verified path rates. **W2.** Feasible current-parameter curvature works favorably in the specified logistic cells, whereas this truth-free tuning criterion does not deliver reliable inference in the correlated Gaussian linear cells. **Q1.** We have evaluated curvature at the current primary parameter and, for Joint replicas, at each replica's current parameter. Parameter updates use the previous curvature states; Frozen replicas share the evolving primary curvature. On matched streams with $B=20$, feasible-curvature Frozen/Joint coverage is 0.940/0.948 at $n=10^4$ and 0.956/0.956 at $n=5\times10^4$, compared with oracle values 0.946/0.950 and 0.956/0.958. This gives similar marginal coverage in the tested diagonal positive-margin logistic cells. **Q2.** The original momentum pilot uses the true parameter and remains explicitly an oracle device. We have tested held-out squared prediction loss plus mean squared replica displacement on 80 independent training/holdout pairs, each stream of length $n$ ($160n$ additional observations per cell, shared across candidates). Selection is frozen before evaluating streams held out from that pilot; these validation seeds reuse the original Gaussian experiment. This paired diagnostic uses the stated additional pilot data. At $r=0.9$, dense contrast coverage across the three momentum values ranges from 0 to 0.006 for $n=2000$, and from 0.106 to 0.140 for $n=10000$; at $r=0.98$, all reported coverages are zero. Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Thank you again for your careful review and constructive feedback. We hope that our responses and revisions have addressed your concerns and questions. If you find that they resolve your main concerns, we would be grateful if you would reconsider your assessment and score in light of these changes. We would be happy to clarify any outstanding points.

Thank you for the response and additional experiments. The new rate arguments under the additional assumptions and the results using estimated curvature address part of my concerns. However, the tuning rule without the true parameter still gives poor coverage in the correlated Gaussian settings, so my concern about practical inference remains. I will maintain my rating of weak acceptance.

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

This paper proposes an online multiplier-bootstrap framework for inference with Polyak-Ruppert averaged stochastic approximation (SA) algorithms. The authors consider two main settings: fixed momentum with fixed preconditioning, and dynamic preconditioning without momentum. In each case, bootstrap replicas evolve alongside the original algorithm, preserving the one-pass nature of the algorithm, and avoiding explicit estimation of the asymptotic covariance.

The main theoretical results show that the original estimator and its weighted replicas have the same first-order asymptotic behaviour. In particular, fixed momentum and fixed preconditioning do not affect the leading-order sampling distribution. For dynamic preconditioning, the authors provide conditions under which the dynamic preconditioner is also asymptotically negligible. This allows bootstrap replicas to either maintain their own curvature states ("joint" replicas), or else to reuse the preconditioner sequence from the original algorithm ("frozen" replicas). The latter can substantially reduce computation and storage. The paper also considers inference with both fixed and growing numbers of bootstrap replicas, as well as extensions to nonsmooth settings (e.g., quantile regression), approximate and finite-difference score evaluations, and settings in which several evaluations are based on the same observation.

The proposed methods are evaluated through linear-regression simulations, a logistic-regression experiment with dynamic preconditioning, and an application to the UCI Adult dataset.

Critical strengths
  • The authors provide a careful theoretical justification for online bootstrap inference when stochastic approximation is augmented with momentum or dynamic preconditioning. The result showing that bootstrap replicas may reuse the preconditioner sequence from the original algorithm appears particularly useful, since it avoids maintaining a separate curvature state for every replica.
  • The theoretical framework is reasonably broad, extending beyond smooth SGD to locally nonsmooth estimating equations such as quantile regression, while also providing sufficient conditions for stability of the original and weighted recursions in some settings.
Critical weaknesses
  • Some of the more difficult conditions required for the theoretical results (e.g. the L2L^2 rate for the original and weighted recursions) are assumed directly rather than established for some of the main examples of interest (e.g., quantile regression).
  • I found the paper very difficult to read in places. The exposition introduces a large amount of notation and terminology, often before the relevant objects have been properly defined. Further, many of the main results require substantial cross-referencing between assumptions, equations, and appendices. For me, this makes the central message (i.e., when the online bootstrap remains valid in the presence of momentum or dynamic preconditioning) more obscured than it needs to be.
  • The empirical validation is somewhat limited. First, the finite-sample results are in several cases quite poor, and it is difficult to tell whether the bootstrap itself is working well. For example, in some of the correlated Gaussian examples, nominal 95% intervals have coverage close to 0. This appears to be driven by bias in the averaged iterate (cf Table 7), which the centred bootstrap can't capture, so it is hard to judge how well the bootstrap itself is working here. Second, the main "frozen versus joint" experiment uses the true response probabilities to construct the curvature input, rather than an estimate which would actually be available during optimisation. In this sense, the experiment doesn't really test the setting in which each bootstrap copy would estimate its own curvature from its own parameter value. Third, the real-data experiment does not appear in the main paper, despite being mentioned in the abstract. Finally, there are limited comparisons with other online inference methods; and no runtime or memory measurements.

[1] Y. Fang, J. Xu, and L. Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. JMLR, 19(78):1–21, 2018.

[2] K. Tang, W. Liu, Y. Zhang, and X. Chen. Acceleration of stochastic gradient descent with momentum by averaging: Finite-sample rates and asymptotic normality. arXiv:2305.17665, 2023.

[3] S. An and X. Huo. When does dynamic preconditioning preserve the Polyak–Ruppert CLT? A stabilization threshold. arXiv:2604.23498, 2026.

[4] H. Lam and Z. Wang. Cheap bootstrap for fast uncertainty quantification of stochastic gradient descent. JMLR, 27(93):1–42, 2026.

Questions for authors
  • For the momentum vs SGD comparison (e.g. Table 1), could the authors explain more carefully the role of the step size? In the bounded r=0.9r=0.9 design, momentum selects η0=3\eta_0=3 while SGD selects η0=1\eta_0=1, and β=0.5\beta=0.5 and β=0.9\beta=0.9 give very similar results (Table 8). Results for SGD at η0=3\eta_0=3 might help to separate the effect of momentum and step size. On a related point, tuning here uses knowledge of the true θ∗\theta_{*}; how would this be done in practice?
  • For quantile-regression examples, is it possible to provide more primitive conditions under which the required convergence rates hold (both for the original and weighted recursions)? While the authors provide some sufficient conditions in the Appendix under stronger global stability assumptions, it's not clear to me that these provide the required rates for quantile regression.
  • In the dynamic preconditioning experiment, can the authors provide results using a feasible curvature estimate, rather than the oracle construction currently used? This for me would be an important addition.
  • Could the authors provide a more direct empirical demonstration of the computational benefit of using frozen replicas, e.g., in terms of wall-clock time or memory in a realistic dynamic preconditioning problem?
7 comments

Thank you for your time and valuable comments.

Note: Because of the 5000-character limit, we divided our response into four comments.

W1. We distinguish local score regularity from stability of the full, unprojected recursions and give the sufficient conditions and rate argument in Q2 (Parts 3/4–4/4).

The convex risk argument is given in Q2. Under the convex risk and score conditions stated and proved in Q2, bounded regressors and bounded nonnegative mean-one multipliers give O(ηt)O(\eta_t) mean square rates for the original and weighted unprojected logistic and quantile recursions with deterministic finite initial states, fixed symmetric positive definite preconditioning, and 0≤β<10\le\beta < 1. The quantile result includes a global conditional density upper bound in addition to its local density and identification conditions. Without momentum, the logistic result permits exponential tail regressors and predictable symmetric preconditioners satisfying p−I⪯Pt⪯p+Ip_-I\preceq P_t\preceq p_+I for fixed 0<p−≤p+<∞0 < p_-\le p_+ < \infty. It supplies the original, Frozen, and Joint rates for the Gaussian logistic curvature experiment; the curvature variation condition is verified separately. Both results analyze the stated score, algorithm, and target. The general finite moment corollaries require separately verified path rates: a Pareto multiplier counterexample shows that local model regularity and finite multiplier variance alone need not imply the weighted rate. The fixed momentum sufficient result assumes bounded regressors; the adaptive preconditioning result covers logistic regression.

W2. We introduce the replica index and multiplier before the updates, define direct scores before approximate scores, and separate score regularity from path stability. The explanation now reads:

The multiplier Wt(b)W_t^{(b)} weights observation tt in replica bb. These multipliers are independent and identically distributed across observations and replicas, independent of the original inputs, and have mean one and variance one; equiprobable 0,20,2 is one choice. We write WtW_t for a generic replica's multiplier. All paths start at the same deterministic θ0\theta_0, use ηt=η0t−α\eta_t=\eta_0t^{-\alpha}, and report θˉn=n−1∑t=1nθt\bar\theta_n=n^{-1}\sum_{t=1}^n\theta_t and θˉn(b)=n−1∑t=1nθt(b)\bar\theta_n^{(b)}=n^{-1}\sum_{t=1}^n\theta_t^{(b)}.

For direct scores, G^t(θ)=G(θ,Zt)\widehat G_t(\theta)=G(\theta,Z_t), where GG is measurable and has mean g(θ)g(\theta). More generally, G^t\widehat G_t may approximate this score. Writing Ht−1\mathcal H_{t-1} for either pre-update history, assume EG^t(θ)∣Ht−1=g(θ)+bt(θ)\mathbb E\\{\widehat G_t(\theta)\mid\mathcal H_{t-1}\\}=g(\theta)+b_t(\theta) at the target and at the predictable parameter values used, where btb_t is a predictable approximation bias.

We also separate the inferential argument into score regularity and path stability: score regularity controls the local mean expansion and quadratic mean score continuity, while path stability supplies E∣θt−θ⋆∣2=O(ηt)\mathbb E\\|\theta_t-\theta_\star\\|^2=O(\eta_t) and the corresponding weighted path rate. When the assumptions are only local, auxiliary paths must satisfy uniform bounds, agree with the actual paths after kn=o(n)k_n=o(\sqrt n) with probability tending to one, and have uniformly bounded initial block moments. With these conditions, summing the normalized updates makes the weighted endpoints and momentum boundary terms negligible at the root-nn scale, leaving the same target innovation for the original and weighted paths.

Continued in Part 2/4: W3 and Q1: empirical comparisons and tuning diagnostics.

Part 2/4 of our response to Reviewer pgqi (continued): W3 and Q1: empirical comparisons and tuning diagnostics.

W3. The original correlated Gaussian comparison has near zero finite sample coverage and substantial estimator bias. We have decomposed this behavior into empirical bias and interval scale for both contrasts across the original correlations, sample sizes and momentum values. For the correlated dense contrasts, leave one out empirical bias centering raises diagnostic coverage from 0--0.140 to 0.954--0.976, but the root mean square scale used by the Student intervals is still 1.152--1.286 times the sampling standard deviation. The diagnostics identify bias as a major source of undercoverage and a somewhat conservative bootstrap scale. This simulation diagnostic uses repeated runs and the true target for centering.

We report the Adult working-logistic analysis directly, including online plug-in and batch-GLM comparisons. The final analysis uses 38,842 records held out from preliminary tuning, with B=999B=999 bounded multipliers. Adjusted odds ratios and their intervals are:

Contrastβ\betaMultiplierOnline plug-inBatch GLM
Education code +1+101.457 (1.431, 1.476)1.457 (1.437, 1.478)1.444 (1.424, 1.464)
Education code +1+10.81.458 (1.437, 1.475)1.458 (1.437, 1.478)1.444 (1.424, 1.464)
Recorded hours +10+1001.379 (1.336, 1.419)1.379 (1.342, 1.418)1.368 (1.331, 1.406)
Recorded hours +10+100.81.380 (1.341, 1.419)1.380 (1.343, 1.419)1.368 (1.331, 1.406)

Multiplier intervals use empirical bootstrap calibration; plug-in and batch intervals use normal calibration. The education contrast is a one-unit change in the ordered education code, and the hours contrast is a ten hour difference holding the included covariates fixed. These are conditional working model associations. The close results across β=0\beta=0 and 0.80.8 show stability of these contrasts under the chosen pilot selected schedules. The SGD comparator is the zero-momentum special case under the same multiplier construction.

The feasible curvature results and computational comparison are given in Q3 and Q4 (Part 4/4).

Q1. We reran the bounded r=0.9r=0.9 setting with the common schedule (α,η0)=(0.6,3)(\alpha,\eta_0)=(0.6,3) for SGD and both momentum values on paired validation streams. The common schedule results give, at n=2000n=2000, full-vector 103MSE10^3\mathrm{MSE} of 10.762, 10.594, and 10.782 for β=0,0.5,0.9\beta=0,0.5,0.9; at n=10000n=10000 the respective values are 1.258, 1.236, and 1.255. The original tuned MSE gap therefore arises mainly from separately selected schedules. Under the common schedule, SGD dense contrast intervals have much larger mean lengths (2.188 and 1.089 at the two sample sizes) than the β=0.5\beta=0.5 intervals (0.396 and 0.112), but this is specific to the design and the interval length distribution is skewed. Normalized momentum multiplies the incoming score by 1−β1-\beta, preserving its mean scale; the first-order averaged influence function is independent of fixed β\beta. This helps interpret the similar MSEs for β=0.5\beta=0.5 and 0.90.9; finite-sample calibration differs: at n=2000n=2000 their coverages are 0.956 and 0.898, respectively.

The bias centering diagnostics in W3 concern the original oracle-selected schedules. The original comparison evaluates each algorithm together with its tuning. The original pilot rule uses the true θ⋆\theta_\star and is an oracle simulation device. We additionally tested a data-only pilot rule using held out squared prediction loss plus replica displacement on 80 independent pilot/hold-out pairs, then validation streams held out from pilot selection. Each pilot and holdout stream has length nn, so the extra selection budget is 160n160n observations per cell, shared across candidates. The validation reuses the original Gaussian streams for a paired diagnostic. The data-only pilot yields the following strong correlation coverage: at r=0.9r=0.9, coverage ranges from 0 to 0.006 for n=2000n=2000 and from 0.106 to 0.140 for n=10000n=10000 across the three momentum values; at r=0.98r=0.98 all reported coverages are zero. This pilot rule uses the stated additional data budget.

Continued in Part 3/4: Q2: convex risk conditions and the rate without momentum.

Part 3/4 of our response to Reviewer pgqi (continued): Q2: convex risk conditions and the rate without momentum.

Q2. Condition (40) provides a sufficient global quadratic drift route. For the logistic and quantile examples, the following convex risk argument supplies an alternative primitive rate result.

Let FF be the finite population excess loss, with F(θ⋆)=0F(\theta_\star)=0, and let g=∇Fg=\nabla F. Assume that FF is globally convex, g(θ⋆)=0g(\theta_\star)=0, ∣g(θ)∣≤M\\|g(\theta)\\|\le M, and gg is globally LL-Lipschitz. Assume also that, for some r,μ>0r,\mu > 0,

\qquad (\\|e\\|\le r).$$ A positive definite derivative of $g$ at the target implies this local radial drift condition. For the recursion without momentum, use deterministic finite initialization and $\eta_t=\eta_0t^{-\alpha}$ with $1/2 < \alpha < 1$. The preconditioner is predictable and symmetric, with deterministic bounds $$0 < p_- I\preceq P_t\preceq p_+ I < \infty.$$ Write $H_t=W_tG(\theta_{t-1},Z_t)$, where the fresh observation and multiplier are independent of the past, the multiplier is independent of the observation, and $\mathbb E W_t=1$. Assume $\mathbb E(H_t\mid\mathcal F_{t-1})=g(\theta_{t-1})$ and a state-uniform envelope $\\|H_t\\|\le J_t$, where the fresh envelopes have a common law satisfying $\mathbb E\exp(\lambda J_t) < \infty$ for some $\lambda > 0$. The original recursion uses $W_t\equiv1$. To verify the rate, put $s=\\|\theta-\theta_\star\\|$. Convexity along rays and the local drift give $$F(\theta)\ge \frac{\mu s^2}{2}\quad(s\le r), \qquad F(\theta)\ge \mu r s-\frac{\mu r^2}{2}\quad(s\ge r),$$ and $\\|g(\theta)\\|\ge\mu\min\\{s,r\\}$. Also $F(\theta)\le Ls^2/2$ locally. Consequently, for $V(\theta)=\exp\\{aF(\theta)\\}-1$ and any fixed sufficiently small $a > 0$, there are positive constants such that $$\\|\theta-\theta_\star\\|^2\le C V(\theta), \qquad \nabla V(\theta)^\top P_tg(\theta)\ge c_0V(\theta).$$ Indeed, near the target $\\|g\\|^2\ge 2\mu^2F/L$, and outside the radius-$r$ ball $\\|g\\|\ge\mu r$. These bounds imply $\\|g\\|^2\ge c(1-e^{-aF})$, which yields the second inequality. The bounded Lipschitz gradient gives the Taylor bound $$\lvert V(\theta+h)-V(\theta)-\nabla V(\theta)^\top h\rvert \le C(1+V(\theta))\\|h\\|^2e^{aM\\|h\\|}.$$ Choose $a$ so that $aMp_+\eta_0 < \lambda/2$. The envelope then bounds the conditional expected remainder for $h=-\eta_tP_tH_t$ by $C\eta_t^2(1+V(\theta_{t-1}))$, and ensures finite exponential Lyapunov moments at every finite time. Thus, for all sufficiently large $t$, $$\mathbb E[V(\theta_t)\mid\mathcal F_{t-1}] \le (1-c_0\eta_t+C\eta_t^2)V(\theta_{t-1})+C\eta_t^2 \le (1-c\eta_t)V(\theta_{t-1})+C\eta_t^2.$$ Taking expectations and using $\eta_{t-1}/\eta_t=1+O(t^{-1})=1+o(\eta_t)$ shows that $\mathbb E V(\theta_t)/\eta_t$ is bounded: its recurrence is eventually bounded above by $(1-c\eta_t/2)\mathbb E V(\theta_{t-1})/\eta_{t-1}+C\eta_t$. Therefore $$\mathbb E\\|\theta_t-\theta_\star\\|^2=O(\eta_t).$$ *Continued in Part 4/4: Q2 continued: fixed momentum and model verification; Q3–Q4.*
Reviewer_d1DBOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors developed an online multiplier bootstrap approach for inference on parameters estimated by Polyak-Ruppert ASGD in two classes of stochastic approximation algorithms: fixed momentum with fixed preconditioning, and dynamic preconditioning without momentum. Bahadur representations are proved for the estimates, which imply the CLT. Numeric studies and real data analysis are performed.

Critical strengths

Theorems 3.3 and 3.4 show that, under explicit stability and variation conditions, bootstrap replicas can reuse the original evolving preconditioner instead of maintaining their own curvature matrices, without changing first-order inference. This reduces storage from O((B + 1)d²) to O(d² + Bd) and avoids replica-specific projections and inversions, which is a practical benefit for online uncertainty quantification.

Critical weaknesses

I suspect that Condition (40) is not satisfied for their logistic and quantile examples.

Questions for authors

develop a rigorous theory so that their logistic and quantile examples can be worked out.

4 comments

Thank you for your time and valuable comments.

Note: Because of the 5000-character limit, we divided our response into two comments.

W1. We distinguish local score regularity from stability of the full, unprojected recursions and give the sufficient conditions and rate argument below.

Condition (40) provides a sufficient global quadratic-drift route. For the logistic and quantile examples, the following convex risk argument supplies an alternative primitive rate result.

Let FF be the finite population excess loss, with F(θ⋆)=0F(\theta_\star)=0, and let g=∇Fg=\nabla F. Assume that FF is globally convex, g(θ⋆)=0g(\theta_\star)=0, ∣g(θ)∣≤M\\|g(\theta)\\|\le M, and gg is globally LL-Lipschitz. Assume also that, for some r,μ>0r,\mu > 0,

\qquad (\\|e\\|\le r).$$ A positive definite derivative of $g$ at the target implies this local radial-drift condition. For the recursion without momentum, use deterministic finite initialization and $\eta_t=\eta_0t^{-\alpha}$ with $1/2 < \alpha < 1$. The preconditioner is predictable and symmetric, with deterministic bounds $$0 < p_- I\preceq P_t\preceq p_+ I < \infty.$$ Write $H_t=W_tG(\theta_{t-1},Z_t)$, where the fresh observation and multiplier are independent of the past, the multiplier is independent of the observation, and $\mathbb E W_t=1$. Assume $\mathbb E(H_t\mid\mathcal F_{t-1})=g(\theta_{t-1})$ and a state-uniform envelope $\\|H_t\\|\le J_t$, where the fresh envelopes have a common law satisfying $\mathbb E\exp(\lambda J_t) < \infty$ for some $\lambda > 0$. The original recursion uses $W_t\equiv1$. To verify the rate, put $s=\\|\theta-\theta_\star\\|$. Convexity along rays and the local drift give $$F(\theta)\ge \frac{\mu s^2}{2}\quad(s\le r), \qquad F(\theta)\ge \mu r s-\frac{\mu r^2}{2}\quad(s\ge r),$$ and $\\|g(\theta)\\|\ge\mu\min\\{s,r\\}$. Also $F(\theta)\le Ls^2/2$ locally. Consequently, for $V(\theta)=\exp\\{aF(\theta)\\}-1$ and any fixed sufficiently small $a > 0$, there are positive constants such that $$\\|\theta-\theta_\star\\|^2\le C V(\theta), \qquad \nabla V(\theta)^\top P_tg(\theta)\ge c_0V(\theta).$$ Indeed, near the target $\\|g\\|^2\ge 2\mu^2F/L$, and outside the radius-$r$ ball $\\|g\\|\ge\mu r$. These bounds imply $\\|g\\|^2\ge c(1-e^{-aF})$, which yields the second inequality. The bounded Lipschitz gradient gives the Taylor bound $$\lvert V(\theta+h)-V(\theta)-\nabla V(\theta)^\top h\rvert \le C(1+V(\theta))\\|h\\|^2e^{aM\\|h\\|}.$$ Choose $a$ so that $aMp_+\eta_0 < \lambda/2$. The envelope then bounds the conditional expected remainder for $h=-\eta_tP_tH_t$ by $C\eta_t^2(1+V(\theta_{t-1}))$, and ensures finite exponential Lyapunov moments at every finite time. Thus, for all sufficiently large $t$, $$\mathbb E[V(\theta_t)\mid\mathcal F_{t-1}] \le (1-c_0\eta_t+C\eta_t^2)V(\theta_{t-1})+C\eta_t^2 \le (1-c\eta_t)V(\theta_{t-1})+C\eta_t^2.$$ Taking expectations and using $\eta_{t-1}/\eta_t=1+O(t^{-1})=1+o(\eta_t)$ shows that $\mathbb E V(\theta_t)/\eta_t$ is bounded: its recurrence is eventually bounded above by $(1-c\eta_t/2)\mathbb E V(\theta_{t-1})/\eta_{t-1}+C\eta_t$. Therefore $$\mathbb E\\|\theta_t-\theta_\star\\|^2=O(\eta_t).$$ *Continued in Part 2/2: Q1: fixed normalized momentum and logistic/quantile verification.*

Part 2/2 of our response to Reviewer d1DB (continued): Q1: fixed normalized momentum and logistic/quantile verification.

Q1. For fixed normalized momentum, assume in addition a uniformly bounded score and bounded multipliers, a fixed symmetric positive-definite PP, deterministic finite initial states, and 0≤β<10\le\beta < 1. With

\qquad z_t=\theta_t-\frac{\beta}{1-\beta}\eta_tPm_t,$$ the filter states are uniformly bounded and the exact transformed update is $$z_t=z_{t-1}-\eta_tP W_tG(\theta_{t-1},Z_t) +\frac{\beta}{1-\beta}(\eta_{t-1}-\eta_t)Pm_{t-1}.$$ Here $\\|\theta_{t-1}-z_{t-1}\\|=O(\eta_{t-1})$ and $\eta_{t-1}-\eta_t=O(\eta_t/t)$. Lipschitz continuity of $g$ therefore changes the conditional mean increment from $-\eta_tPg(z_{t-1})$ by $O(\eta_t^2)$. Since $\\|\nabla V(z)\\|\le aM(1+V(z))$, this perturbation and the Taylor remainder contribute at most $C\eta_t^2(1+V(z_{t-1}))$. Absorbing its $V$-dependent part into the negative drift gives $$\mathbb E[V(z_t)\mid\mathcal F_{t-1}] \le(1-c\eta_t)V(z_{t-1})+C\eta_t^2$$ eventually. The comparison argument in Part 1/2 yields $\mathbb E V(z_t)=O(\eta_t)$, and $\\|\theta_t-z_t\\|=O(\eta_t)$ gives the same mean-square rate for $\theta_t$. For logistic regression, assume a finite identified target with positive-definite population Hessian. Its convex loss has $\\|G(\theta;X,Y)\\|\le\\|X\\|$ and a globally Lipschitz mean gradient whenever $\mathbb E\\|X\\|^2 < \infty$. Bounded covariates and bounded nonnegative mean-one multipliers therefore verify the fixed momentum conditions. Without momentum, bounded multipliers and an exponential moment of $\\|X\\|$ verify the envelope condition, including Gaussian covariates, for predictable preconditioners satisfying the two sided spectral bounds in Part 1/2. For quantile regression, use bounded covariates, bounded nonnegative mean-one multipliers, conditions (i)–(iii) of the submitted Corollary C.5, and a uniform global upper bound on the conditional density. The quantile excess risk is convex, the score is bounded, and the global density bound makes its mean gradient Lipschitz. The positive definite target Jacobian supplies the local radial drift. This verifies the fixed momentum rate without projecting or changing the score. The inference result retains $\alpha(1+\nu) > 1$. These are sufficient path rate results under additional assumptions. Curvature variation remains a separate requirement for dynamic-preconditioning inference, and the broader finite moment corollaries remain conditional on separately verified path rates. Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.
Reviewer_d1DBOpenReview ↗

response to rebuttal

I retain my rating of 3 (weak acceptance). My main concern was how to establish the required mean-square rates for logistic and quantile regression, since the bounded population scores in these models preclude the global quadratic drift in Condition (40). The authors’ alternative Lyapunov argument satisfactorily addresses this concern. Under the additional assumptions stated in the rebuttal, it establishes the O(ηt)O(\eta_t) mean-square rate for both the original iterates and the weighted bootstrap replicas. The argument covers the Gaussian logistic experiment without momentum and gives sufficient conditions for quantile regression with fixed momentum. I ask the authors to include the proposition and its proof in the paper and to make clear in Corollaries C.5 and C.22 when the rates follow from these conditions and when they remain assumptions.

Thank you for your feedback and for acknowledging the improvements to our manuscript. We appreciate your time and consideration.

Comments on the paper

1 comment

Thank you for your time and valuable comments. We have clarified the distinction between local score regularity and trajectory stability, supplied primitive rate arguments for bounded-score regression and predictable logistic preconditioning, and made the conditions for the original and multiplier paths explicit. We have also added common-schedule and data-based tuning comparisons, bias and interval-scale diagnostics, feasible-curvature and timing results for Frozen and Joint replicas, and an Adult working-logistic illustration. These results distinguish tuning effects from momentum effects and document when sharing curvature gives comparable coverage with less computation. The changes are incorporated into the paper and marked in blue. We hope the detailed responses below address your concerns. Thank you again for your valuable feedback; we welcome further questions and discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.