acceptodds
Under review as a conference paper at ICLR 2027

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

Abstract

Analysis of Stochastic Gradient Descent and its variants typically relies on the assumption of uniformly bounded variance, a condition that frequently fails in practical non-convex settings, such as neural network training, and in several elementary optimization settings. While several relaxations are explored in the literature, the classical Blum-Gladyshev (BG-0) condition, which permits the variance to grow quadratically with distance, has recently been shown to be the weakest condition. However, the study of the oracle complexity of stochastic first-order non-convex optimization under BG-0 has remained underexplored. In this paper, we address this gap and establish information-theoretic lower bounds, proving that finding an -stationary point requires stochastic BG-0 oracle queries for smooth functions and queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e., and for smooth and mean-square smooth cases, respectively. To match these lower bounds, we consider Proximally Anchored STochastic Approximation (PASTA), a unified algorithmic framework whose problem-dependent instantiations combine dynamic batching and gradient estimation with Halpern anchoring and Tikhonov regularization. We prove that suitable PASTA instantiations achieve minimax optimal complexities across numerous non-convex regimes, including standard smooth, mean-square smooth, weakly convex, star-convex, and Polyak-Lojasiewicz functions, entirely under an unbounded domain and unbounded stochastic gradients.

Primary area:
optimization
Keywords:
Stochastic Optimization, Non-Convex Optimization, Variance Reduction, Blum-Gladyshev Condition, Proximal Methods, Halpern Iteration, Tikhonov regularization

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_V54vOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper analyzes nonconvex optimization of SGD under BG-0 conditions, which extends the uniformly bounded variance. The authors provide Ω(ϵ−6)\Omega(\epsilon^{-6}) bounds for smooth functions and Ω(ϵ−4)\Omega(\epsilon^{-4}) for mean-square smoothness. The authors futher provide a unified framework which achieve minimax optimal complexities across various non-convex regimes. Overall, the paper is clear and well-written, and provide useful insights for the community.

Critical strengths

This paper focuses on an important question of BG-0 analysis, which closely relates to the deep learning regimes. The authors further provide a unified framework, which is interesting. This paper is well-written, and easy-to-follow.

Critical weaknesses

I did not find clear weakness of this paper. But I do suggest the authors providing theoretical challenges on the BG-0 analysis, and how these challenges stop the analysis of non-convex optimization.

Questions for authors

See above, what is the main challenges on the BG-0 analysis under non-convex optimization?

2 comments
AuthorsOpenReview ↗

Response to Reviewer V54v

W1 & Q1

We thank the reviewer for this valuable suggestion. The main challenges of analyzing non-convex optimization under BG-0 arise both in establishing convergence guarantees and in establishing the fundamental oracle complexity.

Challenges in convergence analysis. Unlike the classical bounded-variance assumption, BG-0 allows the stochastic gradient variance to grow quadratically with the distance from initialization. This introduces an additional term proportional to B2∥xt−x0∥2B^2\Vert{}x_t-x_0\Vert{}^2 in the standard descent analysis. Under bounded variance, this noise contribution is uniformly controlled. However, in general non-convex optimization, a decrease in the objective value does not necessarily control the distance traveled by the iterates. As a result, the standard descent-based arguments cannot directly take care of this additional variance term, particularly over unbounded domains.

Alacaoglu et al. (2025) address BG-0 noise in convex optimization through Halpern anchoring, leveraging convexity to obtain the geometric control needed to stabilize the iterates. Extending this approach to non-convex problems is challenging because the underlying convexity-based contraction is no longer available. Moreover, anchoring the iterates to a fixed reference point can introduce a persistent bias relative to the stationary points of the original objective. Our work addresses these difficulties through dynamic batching and variance reduction for smooth non-convex objectives, and through coupled proximal anchoring with epoch-wise anchor updates for weakly convex objectives.

Challenges in establishing lower bounds. Beyond upper bound convergence guarantees, a more important question is whether these classical non-convex oracle complexities remain optimal under BG-0. The lower-bound constructions of Arjevani et al. (2023) rely on uniformly bounded stochastic gradient variance, where the difficulty of revealing successive coordinates of a stochastic zero-chain is independent of the distance from initialization. Under BG-0, however, the oracle noise can increase substantially as the algorithm moves through the optimization landscape. To capture this additional difficulty, we need a fundamentally different hard-instance construction.

To address this, we introduce a one-dimensional travel function coupled with a smoothly activated and shifted stochastic zero-chain. The construction forces any algorithm seeking an ϵ\epsilon-stationary point to reach a region at distance Θ(Δ/ϵ)\Theta(\Delta/\epsilon) from initialization, where the permitted variance scales as Θ(B2Δ2/ϵ2+G2)\Theta(B^2\Delta^2/\epsilon^2+G^2). This increased variance makes discovering the subsequent zero-chain coordinates significantly harder, while the construction must still preserve global smoothness and the initial function-gap constraint. Under mean-square smoothness, the additional challenge is to maintain the stochastic gradient-difference regularity while exploiting the distance-dependent variance.

Our lower bounds show that these challenges are intrinsic to the BG-0 oracle model, rather than merely limitations of existing convergence analyses. Specifically, the classical bounded-variance lower bounds of Ω(ϵ−4)\Omega(\epsilon^{-4}) and Ω(ϵ−3)\Omega(\epsilon^{-3}) remain valid but are no longer tight. We establish the stronger bounds of Ω(ϵ−6)\Omega(\epsilon^{-6}) under smoothness and Ω(ϵ−4)\Omega(\epsilon^{-4}) under mean-square smoothness, and provide matching upper bounds. We expanded the discussion in the revised manuscript to make these theoretical challenges and their distinction from prior work clearer.

I read the reponse and the other reviewers' comments. I keep my score unchanged (3).

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

The paper studies stochastic optimization under the BG-0 condition, which allows gradient noise variance to grow quadratically with distance from the initial point. It claims oracle lower bounds of Ω(ε⁻⁶) for smooth nonconvex objectives and Ω(ε⁻⁴) under mean-square smoothness. It introduces PASTA, a framework combining dynamic batching, variance reduction, anchoring, and proximal regularization, with instances intended to match these bounds. Additional results address convex, PL, strongly star-convex, and weakly convex objectives. Validation consists primarily of theoretical constructions and convergence proofs.

Critical strengths
  1. A meaningful complexity question. The BG-0 model captures a consequential departure from uniformly bounded variance. Establishing matching complexity bounds would clarify the fundamental cost of this relaxation.

  2. A natural approach to controlling trajectory-dependent noise. Dynamic batching adjusts sampling effort to the variance permitted at the current iterate. The framework connects this mechanism with anchoring and proximal regularization across several objective classes.

Critical weaknesses
  1. The PL proof incorrectly controls distance to a fixed minimizer. Appendix C.7 uses PL to infer ‖x − x*‖² ≤ (2/μ)(f(x) − f*), and then derives Eq. (110). In general, the relevant quadratic-growth statement concerns distance to the minimizer set, not an arbitrary fixed minimizer. For example, f(u,v) = u²/2 satisfies PL with μ = 1, but x = (0,M) has zero suboptimality and positive distance from x* = (0,0). Choosing nearest minimizers separately does not justify the subsequent bound on ‖x_t − x_0‖. This invalidates a key step supporting Theorem 6, although it does not by itself disprove the theorem.

  2. The general randomized-algorithm lower bounds are not fully established. Appendix B.1 concludes by applying a randomized orthogonal transformation and asserting that the zero-respecting lower bound extends directly. Preservation of Euclidean geometry is insufficient to justify this reduction. The proof needs to specify the dimension and probability requirements, control arbitrary adaptive queries, and verify that the relevant reduction preserves the modified BG-0 construction and oracle assumptions. The mean-square smooth lower bound inherits this concern. Since minimax optimality is a central contribution, this missing argument materially affects my assessment.

Questions for authors
  1. Proof clarification: How can Eq. (110) and Theorem 6 be established when the minimizer is nonunique? Does the result require a stronger assumption than PL?

  2. Proof clarification: Which precise randomized-algorithm reduction supports Theorems 1–2, and how does the proposed construction satisfy its dimension, query-control, and oracle requirements?

  3. Claim clarification: Is the condition in Theorem 4 necessary for the stated contraction, or sufficient for closing the particular upper-bound recursion? If necessary, where is necessity proved?

2 comments
AuthorsOpenReview ↗

Response to Reviewer CbhC (1/2)

W1 & Q1

We thank the reviewer for their comments. We agree that Eq. (110) is not justified under the general PL inequality. We observed that Eq. (110) is not needed for Theorem 6, the BG-0 variance can be controlled directly as follows:

Reanalyzed Theorem 6:

Let us retain Assumptions 1 (BG-0), 2 (smoothness), and 4 (PL) and the same update used in Theorem 6, xt+1=xt−ηgt,x_{t+1}=x_t-\eta g_t, where gtg_t is an unbiased stochastic gradient satisfying the BG-0 variance condition. The descent argument leading to Eq. (109) remains unchanged. Combining LL-smoothness, PL condition, and BG-0 variance bound we get

\mathbb{E}[f(x_{t+1})-f^*] \leq (1-\eta\mu)\mathbb{E}[f(x_t)-f^*] + \frac{L\eta^2}{2}\left(B^2\mathbb{E}\\|x_t-x_0\\|^2+G^2\right). \tag{1}

provided that η≤1/L\eta\leq 1/L.

This is where Eq. (110) was used. Now, instead of quadratic growth around a fixed minimizer, we bound E∥xt−x0∥2\mathbb E\Vert{}x_t-x_0\Vert{}^2 by unrolling the SGD recursion:

xt−x0=−η∑j=0t−1∇f(xj)−η∑j=0t−1(gj−∇f(xj)).\begin{aligned} x_t-x_0 ={}&-\eta\sum_{j=0}^{t-1}\nabla f(x_j) -\eta\sum_{j=0}^{t-1} \bigl(g_j-\nabla f(x_j)\bigr). \end{aligned}

Because the stochastic gradient is conditionally unbiased, the gradient-estimation errors form a martingale-difference sequence. Hence, their cross terms vanish in expectation, and

E∥∑j=0t−1(gj−∇f(xj))∥2=∑j=0t−1E∥gj−∇f(xj)∥2≤∑j=0t−1(B2E∥xj−x0∥2+G2).\begin{aligned} \mathbb E\left\Vert{} \sum_{j=0}^{t-1}(g_j-\nabla f(x_j)) \right\Vert{}^2 &=\sum_{j=0}^{t-1} \mathbb E\Vert{}g_j-\nabla f(x_j)\Vert{}^2 \\ &\leq\sum_{j=0}^{t-1} \left(B^2\mathbb E\Vert{}x_j-x_0\Vert{}^2+G^2\right). \end{aligned}

Furthermore, LL-smoothness and the lower boundedness of the objective imply ∥∇f(x)∥2≤2L(f(x)−f∗).\Vert{}\nabla f(x)\Vert{}^2 \leq 2L(f(x)-f^*). Combining these observations with the triangle inequality in the mean-square norm we get

\begin{aligned} \sqrt{\mathbb E\Vert{}x_t-x_0\Vert{}^2} &\leq \eta\sum_{j=0}^{t-1} \sqrt{2L\mathbb E[f(x_j)-f^*]} +\eta\sqrt{ \sum_{j=0}^{t-1} \left( B^2\mathbb E\Vert{}x_j-x_0\Vert{}^2+G^2 \right)}. \end{aligned} \tag{2}

Hence, Eq. (2) replaces Eq. (110), it fixes no minimizer and thus holds when minimizers are nonunique.

Consider the nontrivial case 0<ϵ≤Δ0<\epsilon\leq\Delta, where Δ≥f(x0)−f∗\Delta\geq f(x_0)-f^*. Choose the constant step size

\eta = \min\left\\{\frac{1}{L},\frac{\mu\epsilon}{2L\left(G^2+\frac{64LB^2\Delta}{\mu^2}\right)}\right\\}.

and the total number of iterations

K=⌈2ημlog⁡(3Δϵ)⌉.K=\left\lceil \frac{2}{\eta\mu} \log\left(\frac{3\Delta}{\epsilon}\right) \right\rceil.

We prove by induction that, for every 0≤t≤K0\leq t\leq K,

\mathbb E\Vert{}x_t-x_0\Vert{}^2 \leq\frac{64L\Delta}{\mu^2}. \tag{3}

The statement holds at initialization because xt=x0x_t=x_0 when t=0t=0.

Suppose that the displacement bound holds for all iterations preceding tt. Substituting this bound into the descent recursion (1) and using the selected step size we get E[f(xj)−f∗]≤(1−ημ)jΔ+ϵ4\mathbb E[f(x_j)-f^*] \leq (1-\eta\mu)^j\Delta+\frac{\epsilon}{4} for every 0≤j≤t0\leq j\leq t.

We can now substitute these bounds on function suboptimality and iterate displacement into Eq. (2). Using the geometric-series inequality

η∑j=0t−1(1−ημ)j/2≤2μ,\eta\sum_{j=0}^{t-1}(1-\eta\mu)^{j/2} \leq\frac{2}{\mu},

we obtain

\begin{aligned} \sqrt{\mathbb E\Vert{}x_t-x_0\Vert{}^2} &\leq \frac{2\sqrt{2L\Delta}}{\mu} +\eta t\sqrt{\frac{L\epsilon}{2}} +\eta\sqrt{ t\left(G^2+\frac{64LB^2\Delta}{\mu^2}\right)}. \end{aligned} \tag{4}

The chosen iteration horizon satisfies ηt≤2log⁡(3Δ/ϵ)+1μ.\eta t\leq \frac{2\log(3\Delta/\epsilon)+1}{\mu}.

For 0<ϵ≤Δ0<\epsilon\leq\Delta, we also have

ϵ(2log⁡3Δϵ+1)≤4Δ,ϵ(2log⁡3Δϵ+1)≤4Δ.\begin{aligned} \epsilon\left(2\log\frac{3\Delta}{\epsilon}+1\right) &\leq4\Delta, \\ \sqrt{\epsilon}\left(2\log\frac{3\Delta}{\epsilon}+1\right) &\leq4\sqrt{\Delta}. \end{aligned}

Applying these inequalities together with the step-size restriction to Eq. (4) yields E∥xt−x0∥2≤52LΔμ.\sqrt{\mathbb E\Vert{}x_t-x_0\Vert{}^2} \leq\frac{5\sqrt{2L\Delta}}{\mu}.

Consequently, E∥xt−x0∥2≤50LΔμ2<64LΔμ2,\mathbb E\Vert{}x_t-x_0\Vert{}^2 \leq\frac{50L\Delta}{\mu^2} <\frac{64L\Delta}{\mu^2}, which completes the induction.

Therefore, the expected squared displacement remains uniformly bounded throughout the optimization horizon, despite the possibility of nonunique minimizers and unbounded stochastic gradient variance.

Substituting the established displacement bound into Eq. (1), we obtain

E[f(xt+1)−f∗]≤(1−ημ)E[f(xt)−f∗]+Lη22(G2+64LB2Δμ2).\mathbb{E}[f(x_{t+1})-f^*] \leq (1-\eta\mu)\mathbb{E}[f(x_t)-f^*] + \frac{L\eta^2}{2}(G^2+\frac{64LB^2\Delta}{\mu^2}).

Unrolling this recursion over KK iterations

E[f(xK)−f∗]≤(1−ημ)KΔ+Lη2μ(G2+64LB2Δμ2).\mathbb{E}[f(x_K)-f^*] \leq (1-\eta\mu)^K\Delta + \frac{L\eta}{2\mu}\left(G^2+\frac{64LB^2\Delta}{\mu^2}\right).

By the selected step size and iteration count,

E[f(xK)−f∗]≤ϵ29Δ+ϵ4≤ϵ9+ϵ4<ϵ.\begin{aligned} \mathbb E[f(x_K)-f^*] &\leq\frac{\epsilon^2}{9\Delta}+\frac{\epsilon}{4} \leq\frac{\epsilon}{9}+\frac{\epsilon}{4}<\epsilon. \end{aligned}

Since each iteration uses one stochastic gradient and η=Θ(ϵ)\eta=\Theta(\epsilon) when G>0G>0, the oracle complexity is $ K=\mathcal{O}\left(\epsilon^{-1}\log(\epsilon^{-1})\right).$

AuthorsOpenReview ↗

Response to Reviewer CbhC (2/2)

In summary, we agree that Eq. (110) incorrectly applies quadratic growth relative to a fixed minimizer. Our corrected proof establishes the same asymptotic convergence rate using the SGD trajectory and the BG-0 variance condition directly, no uniqueness assumption or stronger geometric condition is necessary. We replaced the argument surrounding Eq. (110) in Appendix C.7 and updated the sufficient step-size constants in Theorem 6 accordingly, while preserving its stated oracle-complexity order.

W2 & Q2

We thank the reviewer for their comments. While the orthogonal transformation preserves the relevant Euclidean geometry, our presentation did not explicitly justify the extension to arbitrary randomized algorithms or verify the associated oracle conditions. We have now expanded the proof in Appendix B.3, following the randomized zero-chain reduction of Arjevani et al., and explicitly address the dimension requirements, query control, and preservation of the BG-0 and MSS assumptions.

Specifically, we use the unrestricted-query reduction of their Lemma 6. We draw a random matrix U∈Rd×TU \in \mathbb{R}^{d \times T} with orthonormal columns and replace the zero-chain by its randomly embedded, softly projected, and quadratically regularized counterpart. The soft projection is

ρ(x)=x1+∥x∥2/(2302T).\rho(x) = \frac{x}{\sqrt{1 + \Vert{}x\Vert{}^2 / (230^2 T)}}.

For a progress probability pp, failure probability δ\delta, and KK simultaneous queries sharing an oracle seed, we choose

d≥⌈18⋅2302KT2plog⁡(2KT2pδ)⌉.d \ge \left\lceil \frac{18 \cdot 230^2 K T^2}{p} \log\left(\frac{2 K T^2}{p \delta}\right) \right\rceil.

Lemma 6 then controls all adaptive randomized queries without any restriction on their norms for the corresponding Ω(T/p)\Omega(T/p) query horizon. We use K=1K = 1 for individual stochastic-gradient queries and K=2K = 2 for same sample evaluations in the MSS setting. The quadratic regularization prevents large-norm queries from circumventing the gradient lower bound.

We retain our original travel function f0f_0, activation function ϕ\phi, and distance D=Δ/(4ϵ)D = \Delta / (4\epsilon). Only the zero-chain component is replaced by the embedded construction, with adjusted scaling. In particular, for the smooth case we set

λ=8ℓ1ϵL,T=⌊LΔ3072ℓ1ϵ2⌋,1p=1+B2Δ21024ς2ϵ4+G216ς2ϵ2.\lambda = \frac{8\ell_1\epsilon}{L},\qquad T = \left\lfloor\frac{L\Delta}{3072\ell_1\epsilon^2}\right\rfloor,\qquad \frac{1}{p} = 1 + \frac{B^2\Delta^2}{1024\varsigma^2\epsilon^4} + \frac{G^2}{16\varsigma^2\epsilon^2}.

The resulting composite oracle is a deterministic transformation of the compressed zero-chain oracle, so it does not provide additional information about the hidden random subspace. We explicitly verify unbiasedness, the initial objective gap, and global smoothness. More importantly, its variance satisfies

E∥G(u,y,z)−∇F(u,y)∥2≤ϕ(u)2(B2Δ264ϵ2+G2)≤B2∥(u,y)−x0∥2+G2.\mathbb{E}\Vert{}G(u,y,z) - \nabla F(u,y)\Vert{}^2 \le \phi(u)^2 \left(\frac{B^2\Delta^2}{64\epsilon^2} + G^2\right) \le B^2\Vert{}(u,y) - x_0\Vert{}^2 + G^2.

The final inequality holds globally because ϕ(u)=0\phi(u) = 0 for u≤D/2u \le D/2, whereas u>D/2u > D/2 implies u2>Δ2/(64ϵ2)u^2 > \Delta^2 / (64\epsilon^2).

For the MSS result, we use the MSS zero-chain estimator and choose L=(ℓ1/ℓˉ1)LˉpL = (\ell_1 / \bar{\ell}_1)\bar{L}\sqrt{p}, with the compressed-chain constants ℓ1=155\ell_1 = 155 and ℓˉ1=336\bar{\ell}_1 = 336 from Lemma 7 of Arjevani's paper. The revised proof verifies the mean-square smoothness inequality for the complete composite oracle, including the activation-coordinate terms, using the same random seed at both query points.

Finally, Appendix B.3 applies the high-probability lower bound to the algorithm's output and establishes an expected oracle-query lower bound of Ω(T/p)\Omega(T/p). Separate statistical estimation constructions satisfying BG-0 globally handle the case where the rescaled zero-chain is too short; in the MSS setting, they also establish the additional B2Δ2/ϵ4B^2\Delta^2/\epsilon^4 and G2/ϵ2G^2/\epsilon^2 terms. Thus, the revised proofs address the dimension requirement, unrestricted adaptive queries, preservation of BG-0 and MSS, and the parameter ranges stated in Theorems 1–2.

Q3

We thank the reviewer for their comments. We clarify that the conditions in Eq. (6) are sufficient, rather than necessary, for establishing the contraction in Eq. (5) under the smooth convex setting.

Specifically, in Appendix C.5, Eq. (91) contains the distance-dependent term (−βt+2βt2+η2B2Nt)∥xt−x0∥2.\left(-\beta_t+2\beta_t^2+\frac{\eta^2B^2}{N_t}\right)\Vert{}x_t-x_0\Vert{}^2.

Requiring its coefficient to be nonpositive yields the first condition in Eq. (6), ensuring that the unbounded variance term is eliminated from our upper-bound recursion. The accompanying step-size condition guarantees the desired contraction factor.

Thus, Eq. (6) provides sufficient conditions for our analysis, and we do not claim universal necessity. We have clarified this distinction in the theorem statement and the surrounding discussion.

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

The paper analyzes stochastic optimization under the BG-0 condition on noise, deriving lower bounds and providing an algorithm that matches those along certain aspects.

Critical strengths

The paper provides lower complexity bounds and derives algorithms that match the lower bounds in certain cases under the BG-0 noise condition. The condition is a meaningful practical relaxation of the uniformly bounded noise variance, hence the results may be of interest.

Critical weaknesses

The construction of the Pasta algorithm for which guarantees are shown explicitly depends on some global constants that are hard to acquire beforehand.

Related work is much better to be included in the main paper body.

It would be useful to better clarify the role of the convex set in Assumption 1.

The sampling size N_t may be large, so practical usefulness of the algorithm should be better justified.

Questions for authors

N/A

2 comments
AuthorsOpenReview ↗

Response to Reviewer rRTG

W1: Dependence on global constants

We thank the reviewer for this comment. The parameters of PASTA use LL, Δ\Delta, BB, and GG, which is standard for minimax-optimal methods in stochastic optimization. For example, the optimal SGD rates of Ghadimi & Lan (2013) and the methods matching the lower bounds of Arjevani et al. (2023) use the smoothness constant, the initial gap, and the variance bound in the same way. Our guarantees are robust to these constants in the following sense:

  1. The only trajectory-dependent quantity, ∥xt−x0∥\Vert x_t-x_0\Vert, is computed online from the iterates.
  2. Any upper estimates of BB, GG, LL, and Δ\Delta preserve the guarantees and the complexity order, with only constant-factor changes.
  3. The target variance σ2\sigma^2 in Theorem 3 is a free parameter, and it trades the batch size against the step size without changing the total complexity.

Fully parameter-free methods under the BG-0 noise are an interesting direction for future work. We added a paragraph on this after Theorem 3.

W2: Related work in the main body

We agree. The revised manuscript now has a related work paragraph in the introduction, covering variance assumptions, the optimal rates and lower bounds under bounded variance, and prior BG-0 results based on Halpern anchoring. The extended discussion remains in Appendix A, which may move to the main text for the final version given the extra page.

W3: Assumption 1: Role of convex set

We thank the reviewer for pointing this out. The original assumption was stated for a general convex set (for which Rp\mathbb R^p is a special case), which we have now modified to match the unconstrained problem (X=Rp\mathcal X=\mathbb R^p), consistent with our unconstrained problem formulation in Eq. (1). We have made this explicit in the revision.

W4: Practicality of the batch size NtN_t

We thank the reviewer for this question. The batch size NtN_t grows with ∥xt−x0∥2\Vert x_t-x_0\Vert^2. However, our lower bound in Theorem 1 shows that Ω(ϵ−6)\Omega(\epsilon^{-6}) oracle queries are necessary for any algorithm under BG-0 in the smooth case. Thus, the large total sampling cost is intrinsic to the problem and not a limitation of PASTA. The dynamic batching matches this cost up to constants, and it does not waste samples near x0x_0, where NtN_t stays small. Also, the NtN_t samples at each step are independent and can be evaluated in parallel, so the wall-clock cost per iteration scales well on modern hardware. When more structure is available, PASTA instances with Nt=1N_t=1 apply: the anchored instance for convex problems (Section 4.2, as in Alacaoglu et al. (2025)) and the PL and star-convex instances (Section 4.4). We added this discussion after Theorem 3.

Thank you for the response, much appreciated, I will maintain the score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.