- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies stochastic monotone Lipschitz inclusions with a fixed number of oracle queries per iteration. It proposes VRAF, which achieves optimal stochastic variance dependence, and RRSEG, which achieves an optimal deterministic rate with a near-optimal stochastic rate. The paper also establishes a lower bound showing that the two optimal rates cannot generally be attained simultaneously.
Critical strengths
1. Meaningful theoretical contributions. VRAF achieves an expected squared residual bound with optimal variance dependence, while RRSEG achieves , both using only two oracle queries per iteration.
2. Interesting lower bound. The impossibility result provides useful insights into the tradeoff between deterministic acceleration and stochastic variance reduction, even under same-sample oracle access.
3. A coherent theoretical framework with detailed analysis. The paper connects variance reduction, anchoring, and recursive regularization in a coherent manner. In particular, the recentering mechanism in RRSEG provides an interesting way to control the movement of the solutions to successive regularized problems.
Critical weaknesses
1. Algorithmic novelty. RRSEG builds on the single-loop recursive regularization framework of RAIN-SL. While the new convergence guarantee is valuable, the paper could more clearly distinguish the essential algorithmic modifications from the improvements in parameter design and theoretical analysis.
2. Incomplete characterization of the optimal complexity. While the lower bound establishes the necessity of logarithmic factors, RRSEG achieves a stochastic term with a factor, leaving a gap to the lower-bound threshold. Moreover, the necessity of the additional dependence in VRAF is not established. A tighter characterization of these dependencies would further strengthen the theoretical contributions.
Questions for authors
Q1. Could the authors clarify which modifications from RAIN-SL are essential for establishing the convergence guarantee of RRSEG, particularly the choice of regularization centers and the horizon-dependent parameter schedule?
Q2. The lower bound rules out stochastic rates with a logarithmic factor for , while RRSEG achieves a factor. Could the authors comment on whether this gap is inherent to RRSEG or could potentially be reduced through a tighter convergence analysis?
3 comments
Thanks for your clarification. I would like to keep my score
We are glad to hear that our response clarified the points you raised. We appreciate your time and thoughtful feedback.
Response to Reviewer 36JK
We thank the reviewer for their positive assessment and questions about RRSEG's update and logarithmic rate.
Q1. Regularization centers and horizon-dependent parameters.
The main structural change from RAIN-SL is the center of each new regularization term:
=H_k^{\mathrm{RAIN\text{-}SL}}(z)+\rho_k(z-z_k), \qquad H_{k+1}^{\mathrm{RRSEG}}(z) =H_k^{\mathrm{RRSEG}}(z)+\lambda_k(z-z_{k+1}).$$ Here $a_k$ is the current regularization coefficient, $\lambda_k=a_{k+1}-a_k\ge0$, and $r_k$ is the zero of $H_k^{\mathrm{RRSEG}}+A$. Recentering at $z_{k+1}$ gives $$||z_{k+1}-r_{k+1}||^2\le||z_{k+1}-r_k||^2.$$ This is the central inequality in RRSEG's convergence proof (Lemma D.2). Centering the added term at $z_k$, as in RAIN-SL, gives an analogous bound with an extra multiple of $||z_{k+1}-z_k||^2$, which requires a separate estimate (Appendix D.1.2). The horizon-dependent schedule is the other ingredient in our proof. RAIN-SL was obtained by taking a single stochastic extragradient step at each regularization update of RAIN, without a convergence analysis of this variant. In contrast, RRSEG selects its horizon-dependent parameters to control the errors from these single-step updates in the proof (Appendix D). ### Q2. The gap between $\log N$ and $\log^3N$. We do not have a matching worst-case example, so our results do not establish that RRSEG's $\log^3N$ factor is inherent. A tighter analysis or a different parameter schedule could reduce the power.