acceptodds
Under review as a conference paper at ICLR 2027

Minimax-Optimal Update Rules for Stochastic Optimization

Abstract

We study the following question in stochastic optimization: given a single unbiased stochastic gradient observation with bounded variance, how should one design an update rule to achieve the strongest possible descent guarantee? We formulate a minimax problem in which the decision variable is a rule that maps a single observation to an update. Under a prescribed bound on the update norm, the goal is to maximize the worst-case expected one-step decrease guaranteed by smoothness. The worst case is taken over all gradient directions and observation distributions consistent with the available information. When the gradient norm is known, we derive the exact optimal descent guarantee and characterize all rules that attain it. When the gradient norm is unknown, we fix a positive calibration threshold and derive the best uniform guarantee for all gradient norms at or above that threshold, along with a fixed rule that attains this guarantee. The same rule yields a finite-time stationarity guarantee without requiring estimation of the current gradient norm at each iteration. These results establish a unified theory of optimal bounded updates under different levels of information about the gradient norm. Numerical experiments support the theoretical results.

Primary area:
optimization
Keywords:
Stochastic optimization, Minimax optimality, Bounded update rules, Gradient preprocess rules

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

This paper studies the minimax design of bounded stochastic update rules based on a single unbiased gradient observation with bounded variance. The authors derive an exact one-step minimax descent guarantee, characterize all optimal bounded measurable rules, and extend the analysis to unknown gradient norms through fixed-threshold calibration. They also establish a finite-time stationarity guarantee and provide numerical experiments. The paper presents a meaningful theoretical contribution. However, the broader significance of one-step minimax optimality for stochastic optimization and its practical benefits remain unclear.

Critical strengths

The exact minimax guarantee over all bounded measurable update rules is a meaningful theoretical contribution. The characterization of optimal rules, particularly the necessary local gain and differentiability at the origin, is technically interesting. The extension to unknown gradient norms further strengthens the theoretical results.

Critical weaknesses

The paper establishes exact one-step minimax guarantees, but their implications for global optimization remain unclear. Although Theorem 5 provides a stationarity guarantee, the resulting oracle complexity has the same order as that of standard stochastic gradient methods under comparable assumptions. The one-step minimax optimality does not establish a corresponding advantage in global convergence.

Questions for authors
  1. The paper establishes an exact minimax characterization of one-step stochastic updates. While the limitations section acknowledges that trajectory-level optimality remains open, the broader implications of the one-step results for stochastic optimization and algorithm design remain unclear. Beyond providing a sharp local descent guarantee, what additional insights does this characterization offer? A more detailed discussion of its implications for update rule design and optimization performance would help clarify the significance of the framework.

  2. Theorem 5 establishes a finite-time stationarity guarantee, but the resulting complexity is comparable to that of standard stochastic gradient methods. To what extent does one-step minimax optimality contribute to this convergence result? Could comparable guarantees be obtained using other bounded update rules without the minimax-optimality property?

5 comments
AuthorsOpenReview ↗

Implications for Update Design and Global Convergence

Thank you for recognizing the theoretical contribution and for your suggestions concerning update design and global convergence. Revisions primarily addressing your comments are highlighted in blue. We address your two questions below.

1. Implications for update design and performance

The complete characterization provides a design criterion across all bounded measurable maps: it identifies which response features are necessary to attain the strongest guarantee and which remain free. This yields concrete design conclusions:

  • With a positive variance bound, every optimal rule must apply the same first-order linear response to small observations. Optimality therefore determines how small observations must be scaled.
  • With a positive variance bound, tightening an active update cap requires reducing the gain before clipping. The gain and clipping radius must be calibrated jointly.
  • When the current gradient norm is unknown, calibration at a prescribed threshold m>0m>0 attains the best uniform guarantee over all norms at or above mm, providing a basis for selecting a fixed rule.

Joint calibration has a direct performance consequence. In the quadratic example of Section 6.2, it gives actual expected decrease 0.0527040.052704, whereas retaining the unconstrained gain before clipping gives −0.020-0.020 under the same oracle and update bound. Thus, the parameter requirements identified by the characterization can materially change descent behavior.

Changes: The introduction sharpens the contribution statement. Section 4.3 connects joint calibration to the example in Section 6.2. Section 6.3 discusses tuned-baseline comparisons, illustrating the tradeoff between fixed calibration and parameters tuned for a specified horizon.

2. The role of one-step analysis in convergence

Yes, bounded rules that are not one-step minimax optimal can obtain comparable convergence guarantees. Let TmT_m denote the fixed rule calibrated at the gradient-norm threshold mm. New Appendix D.5 shows that, for any fixed 0<α<10<\alpha<1, scaling every update of TmT_m by α\alpha gives T~=αTm\widetilde T=\alpha T_m, which, under the same assumptions, retains the same complexity order as Theorem 5.

Here, Wm(T)W_m(T) denotes the worst-case expected one-step descent guarantee of rule TT when the true gradient norm is mm, over all admissible gradient directions and observation distributions. The value VmV_m is the largest such guarantee over all bounded measurable rules under the same update cap. Appendix D.5 proves

Wm(T~)<Wm(Tm)=Vm.W_m(\widetilde T)<W_m(T_m)=V_m.

Thus, the scaled rule retains the same convergence order but has a strictly weaker worst-case one-step guarantee than TmT_m. The global complexity order alone does not distinguish these updates. Our characterization identifies the rules attaining the strongest one-step guarantee and their structural and parameter requirements.

The one-step analysis contributes to Theorem 5 by constructing TmT_m and providing its descent guarantee above mm. The rule's pointwise bound additionally controls possible loss below mm. Combining these bounds gives a conditional descent inequality valid for every gradient norm; summing it along the trajectory yields the stationarity guarantee.

With Theorem 5's accuracy calibration and R≥m/LR\ge m/L, where RR is the update norm cap and LL the gradient Lipschitz constant, the stochastic complexity matches the existing ε−4\varepsilon^{-4} oracle lower bound for a fixed positive variance bound and sufficiently small ε\varepsilon. Here, ε\varepsilon is the target expected gradient norm of a uniformly selected iterate. The design therefore retains the optimal global worst-case accuracy order while providing an exact one-step criterion that this order alone does not resolve.

Changes: Section 5.2 adds the complexity comparison and scaled-rule discussion. Appendix D.5 proves that the scaled rule retains the convergence order while being strictly suboptimal for the one-step criterion at the calibration threshold.

Thank you again for your valuable comments. We hope these clarifications address your concerns.

I would like to thank the authors for the detailed response and additional analysis. The new discussion on joint calibration and the results in Appendix D.5 provide useful clarifications and strengthen the theoretical contribution.

However, my main concern remains partially unresolved. While the authors establish a connection between the one-step descent guarantees and global stationarity, and show that the resulting algorithm achieves the optimal complexity order, it remains unclear whether one-step minimax optimality provides any additional advantage in overall optimization performance. In particular, the example of joint calibration demonstrates improved one-step descent in a specific setting, but does not establish a corresponding improvement over an entire optimization trajectory.

AuthorsOpenReview ↗

From One-Step Optimality to Multistep Guarantees

Thank you for following up on this point. We understand your question as follows: even if an update rule is optimal for one step, what does repeatedly applying it imply for the optimization process as a whole? This is an important question and a natural challenge in one-step PEP analysis: connecting a locally optimal descent guarantee to performance along an entire trajectory. We think there are two concrete ways to investigate this connection, and we would like to share our current thinking and the analyses we could develop.

Both directions concern the general class of lower-bounded smooth objectives under the paper’s conditional unbiasedness and variance assumptions. Consistent with our design space, we compare algorithms that repeatedly apply the same bounded observation-to-update map: xt+1=xt−T(Gt), ∥T(z)∥≤R.x_{t+1}=x_t-T(G_t),~ \|T(z)\|\le R. The map may be nonlinear, and its parameters may be calibrated to the target accuracy.

1. Comparing the actual number of iterations needed to reach the target

A direct approach is to study the first time the algorithm reaches ∥∇f(xt)∥≤ε\|\nabla f(x_t)\|\le\varepsilon. Let Hε(T)\mathcal H_\varepsilon(T) denote its worst-case expected value over admissible objectives and gradient oracles, and let Hε⋆\mathcal H_\varepsilon^\star be the best value among all fixed bounded maps.

We can investigate this comparison from both sides:

  • An upper bound for our rule. Before reaching the target region, the gradient norm exceeds ε\varepsilon, so our existing one-step result guarantees conditional expected descent of at least VεV_\varepsilon. Accumulating this descent up to the first hitting time gives the route to an upper bound Hε(Tε)≤Δ/Vε\mathcal H_\varepsilon(T_\varepsilon)\le\Delta/V_\varepsilon, where Δ\Delta bounds the initial objective gap.

  • A lower bound for every competing fixed rule. For any given rule, we can construct a smooth objective with a long constant-gradient region that transitions smoothly into a flat region. The oracle returns zero with a prescribed probability and a nonzero observation otherwise, while satisfying the moment constraints. The descent direction can be chosen so that the rule’s update on a zero observation cannot help it advance. Each nonzero observation permits progress of at most RR. This provides a way to lower-bound the time needed by any fixed rule to traverse the region.

Our preliminary calculations suggest that combining these arguments can establish, for R≤ε/LR\le\varepsilon/L and Δ>ε2/(2L)\Delta>\varepsilon^2/(2L),

{\mathcal H_\varepsilon^\star} \le \frac{1}{1-\varepsilon^2/(2L\Delta)} \frac{1}{1-LR/(2\varepsilon)}.$$ Such a bound would give a ratio of at most 4 when $\Delta\ge\varepsilon^2/L$, approaching 1 as $L\Delta/\varepsilon^2\to\infty$ and $LR/\varepsilon\to0$. It would therefore connect one-step minimax design to asymptotically minimax multistep performance within this algorithm class over smooth objectives. We will work through the stopped-process argument and the lower-bound construction in detail to establish this comparison rigorously. **2. Identifying the best cumulative guarantee obtainable from one-step descent** A second approach directly addresses the paper’s current criterion: $$\mathbb E\|\nabla f(x_J)\|\le\varepsilon,$$ where $J$ is uniformly selected from the first $N$ iterations. Suppose a rule admits a uniform affine descent bound $$W_\mu(T)\ge a\mu-b,\qquad \forall\mu\ge0,\quad a>0.$$ Here, $W_\mu(T)$ is its worst-case expected smoothness-based descent bound at gradient norm $\mu$. Telescoping gives $$\mathbb E\|\nabla f(x_J)\| \le \frac ba+\frac{\Delta}{aN}.$$ The sufficient iteration budget is therefore controlled by $a\varepsilon-b$. Our one-step minimax result immediately places an upper limit on this quantity: $$a\varepsilon-b\le W_\varepsilon(T)\le V_\varepsilon.$$ This suggests a concrete question to verify: **can our rule admit a descent bound that is valid at every gradient norm and attains this upper limit at the target accuracy?** Our preliminary analysis suggests that this is achievable when $R\ge\varepsilon/L$. Establishing the required uniform inequality would give, with the threshold calibrated directly to $\varepsilon$, $$N\ge\frac{2L\Delta(\varepsilon^2+\sigma^2)}{\varepsilon^4} \quad\Longrightarrow\quad \mathbb E\|\nabla f(x_J)\|\le\varepsilon.$$ It would also establish optimality of this budget constant within the framework of uniform affine descent bounds and objective-value telescoping. Any rule attaining that constant would necessarily be one-step minimax optimal at gradient norm $\varepsilon$. The main step is thus to verify the sharper descent inequality globally, rather than only at the calibration point. Your question encouraged us to explore these connections more deeply. We will develop these arguments in full and provide the precise statements and proofs in next revision. Thank you for your insightful question.
Reviewer_DVuCOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers the design of the update step used in first order stochastic optimization algorithms. While the typical SGD update takes the form x_{t+1} = x_{t} - \epsilon g_{t}, where g_t is a gradient estimate, they consider a general update of the form x_{t+1} = x - T(g_{t}) for a function T. They set up a minimax optimality criteria for T, and solve for the T under various assumptions. In one case, the norm of the true gradient is known exactly. In another scenario, only a non-zero lower bound on the true gradient norm is available. In each case, they characterize the optimal T among those T whose update magnitude is bounded |T(g)| \leq R, for a constant R.

Critical strengths

It is an interesting question to consider the foundational updating rules in first order gradient methods. While the standard gradient update is subject to optimality guarantees that are especially strong as \epsilon -> zero, it's worth looking at this question for non-zero step sizes.

The derived rules involves clipping; this could be especially interesting for analyzing algorithms that achieve differential privacy, like DP-SGD, where clipping introduces biases that complicate convergence analysis.

Critical weaknesses

The novelty in this analysis is not readily apparent. The analysis starts from the classic quadratic bound that is available for L-smooth functions, and the end results simply confirm that the best update rule is of the form T(g) = \eta(g) g where \eta(g) is a scalar factor depending on g and other available data.

The paper doesn't attempt to put these results into the context of current optimization approaches - do the presented results confirm what is currently done, or suggest better approaches? What about the vast work on lower bounds and optimality of first order gradient methods?

Furthermore, the final complexity bound deserves more discussion. It appears that in order to achieve a gradient less than \epsilon, we must set m=4\epsilon/9, which means the result only applies if the true gradient norm is at least 4\epsilon/9 at every step.

Questions for authors

A possible motivation is differential privacy and the DP-SGD algorithm. Can this approach be used improve the analysis for privacy-preserving algorithms that use clipping?

What would the values of H_{\mu}, Q_{\mu} be in concrete cases? It would appear feasible to work these out for quadratic and/or logistic regression settings.

Theorem 5 is claimed to hold "under the preceding assumptions". Given the various definitions and assumptions introduced, it would help to clarify what are these exactly. Does it include that the true gradients are greater than m?

4 comments
AuthorsOpenReview ↗

Clarifying the Contributions, Assumptions, and Extensions

Thank you for your careful reading. Revisions primarily addressing your comments are highlighted in green. We clarify the contributions and address your questions below.

1. Research objective and contributions

We believe the novelty concern reflects a misunderstanding of our research objective. Our aim is not to derive a new update algorithm by manipulating the quadratic smoothness bound. We optimize the entire bounded measurable observation-to-update map, using that bound as the benchmark for evaluating rules. The form T(g)=η(g)gT(g)=\eta(g)g, where gg is the observed gradient and η(g)\eta(g) a scalar gain, describes one optimal representative, not the full optimizer class.

Our two main contributions are:

  • With a known gradient norm, we determine the exact minimax value over all bounded measurable maps and characterize every attaining rule, identifying required response features and remaining freedom.
  • Without knowing the current norm, calibration at one threshold attains the best uniform guarantee over all norms at or above it; the resulting fixed rule also has a finite-time stationarity guarantee.

With a positive variance bound and an active update cap, the gain must be calibrated jointly with the cap. In Section 6.2, joint calibration gives actual expected decrease 0.0527040.052704, whereas retaining the unconstrained gain before clipping gives −0.020-0.020 under the same quadratic objective, oracle, and cap. These are concrete parameter requirements affecting performance.

Changes: The introduction states both contributions. Section 2 connects bounded-update analyses, performance estimation problems (PEP), one-step learning-rate selection, and moment-based distributionally robust optimization. Section 4 clarifies the complete characterization and Gaussian example.

2. Theorem 5: assumptions and complexity

Theorem 5 imposes no lower bound on trajectory gradient norms. Here μ\mu is the current gradient norm and m>0m>0 the calibration threshold. The region μ≥m\mu\ge m belongs to the uniform design problem in Theorem 4. Eq. (14) controls possible loss below mm, and Eq. (15) holds for every μ≥0\mu\ge0. Choosing m=4ε/9m=4\varepsilon/9 sets the target accuracy ε\varepsilon, not a gradient lower bound.

The assumptions are an objective ff with LL-Lipschitz gradient and lower bound finf⁡f_{\inf}, a fixed initial point x0x_0, conditionally unbiased observations with conditional variance at most σ2\sigma^2, and fixed threshold m>0m>0 and update norm cap R>0R>0.

Writing Δ=f(x0)−finf⁡\Delta=f(x_0)-f_{\inf} for the initial objective gap, a sufficient oracle budget for E∥∇f(xJ)∥≤ε\mathbb E\|\nabla f(x_J)\|\le\varepsilon, with xJx_J a uniformly selected iterate, is

+\frac{L\Delta\sigma^2}{\varepsilon^4}\right)$$ when $R\ge m/L$. This matches the standard stochastic gradient order; for fixed $\sigma^2>0$ and sufficiently small $\varepsilon$, the stochastic term matches the oracle lower bound of Arjevani et al. (2023, Theorem 3). **Changes:** Section 5.2 distinguishes the design region from trajectory assumptions, states Theorem 5's assumptions explicitly, and adds the complexity comparison. Appendix D.4 treats a restrictive update cap. **3. Concrete values of $H_\mu$ and $Q_\mu$** $H_\mu$ is the best smoothness-based descent with the true gradient known; $Q_\mu$ bounds the observation's second moment. The corresponding optimal deterministic update length is $b_\mu$: $$b_\mu=\min\{R,\mu/L\},\quad H_\mu=\mu b_\mu-\frac L2b_\mu^2,\quad Q_\mu=\mu^2+\sigma^2.$$ For the quadratic example in Section 6.2, $H_\mu=0.18$ and $Q_\mu=5$; for the logistic example, $H_\mu\approx0.00324447$ and $Q_\mu=0.565015093$. **Changes:** Section 3.1 points to new Appendix A.5, which works out both examples, including their smoothness and variance bounds. **4. Differential privacy** Per-example clipping bounds each sample's contribution and supports differential privacy when combined with appropriately calibrated noise. Our objective is optimal worst-case descent; privacy can be an additional requirement in an extended model. An extension to differentially private stochastic gradient descent (DP-SGD) would incorporate per-example aggregation and the randomized privacy mechanism, then optimize descent subject to privacy constraints. Whether the resulting rule has a closed form depends on those constraints. **Changes:** Section 2 explains the privacy connection. Section 3.2 adds a general remark on additional design constraints and the dependence of closed-form solvability on their form. Thank you again for your valuable comments. We hope these clarifications address your concerns.

We would like to briefly follow up as the discussion period draws to a close.

Our response clarifies the contributions: the exact minimax value, the complete characterization of all optimal bounded update maps, and the optimal uniform design for unknown gradient norms. We also clarify that Theorem 5 imposes no lower bound on gradient norms along the trajectory, and have made its assumptions explicit in the revision.

We would appreciate your feedback, and welcome any remaining points you would like us to clarify. Thank you for your time.

The reviewer appreciates the revision of Theorem 5 which reads more clearly now.

The reviewer appreciates that this is a theoretical paper not aiming to derive new algorithms and the authors may be assured that there was not a misunderstanding on this point. The expanded discussion of related work is also acknowledged.

There are several significant concerns that remain, however.

Firstly, the rules analyzed in the paper appear to be more aligned with clipping, normalized GD, and other forms of bounded updates, while the title gives the impression that the analysis is of a significantly more general nature. A paper title that reflects the two aspects - use of first-order information, and bounded updates - may better reflect the contributions of this paper.

Secondly, there deserves to be a stronger justification of the specific minimax set up. Unfortunately, equation (4) seems quite arbitrary. For instance, what is the motivation of the 'polar decomposition' in your problem setup, where the infimum is taken over all unit directions e, but not over the gradient magnitude \mu? Including \mu, which would cause the infimum to be simply over the gradient vectors, would seem to be like a more intuitive setup and therefore it calls for discussion.

Furthermore, the setting of section 4 concerns a scenario where the gradient norm is known, but only a unbiased stochastic estimate is available. As this is an unrealistic setting (to this reviewers' knowledge), there should be a clear description of why that setting is included. Otherwise, it appears to be an arbitrary setup. For instance, if it is a warm up or preliminary analysis that informs the more general setting of unknown gradient norm, that should be made clear.

Also, while the authors mention that there are rules that are not limited to T(g) = \eta(g)g, the rules currently demonstrated in the appear to be of that form (note that this includes clipping using \eta(g) = \min{1,\frac{1}{|g|}}. Respectfully this reviewer believes the strongest potential narrative for this paper could center around the minimax optimality of clipping. The authors may consider a revised title that considers that while reflecting the scope of the paper.

Fourthly, what is the purpose for assuming a lower bound on the gradient norm in Section 5? It would be arguably more intuitive to study the case where there is not a lower bound on the norm. It should at least be discussed by the authors if lower bound assumption is needed to derive interesting results. There seems to be related dicsussion in section 5.1 - "A positive threshold therefore identifies a region where nonzero uniform progress is possible" - this may benefit by being moved up earlier.

AuthorsOpenReview ↗

Response to the four significant concerns

Thank you for explaining your concerns about the scope and motivation of the paper, and for your feedback on the revised Theorem 5 and related work. We agree that the title should identify both the information used and the constraint on the update. We propose One-Step Minimax Design of Bounded Stochastic Gradient Updates. The paper asks how much descent a single stochastic gradient observation can guarantee under a bound on the update norm, and which rules attain that guarantee.

1. The criterion in Eq. (4) and the role of the gradient norm

Let g=∇f(x)g=\nabla f(x) and let u=T(G)u=T(G) be the update from observation GG. Smoothness guarantees f(x)−f(x−u)≥⟨g,u⟩−L2∥u∥2.f(x)-f(x-u)\ge \langle g,u\rangle-\tfrac L2\|u\|^2. This criterion has a direct worst-case interpretation. For any given xx and gg, there is an LL-smooth quadratic for which equality holds for every update uu (Appendix A.4). The infimum in Eq. (4) requires the chosen rule to provide its guarantee for every gradient direction and observation law consistent with the available information.

Your suggestion to take the infimum over all gradient vectors helps explain why we first fix the magnitude. Even with access to the exact gradient, the best smoothness-based guarantee satisfies

\le \frac{\|g\|^2}{2L}.$$ As $\|g\|$ approaches zero, so does this upper bound. Thus the minimax value over all nonzero gradient vectors is exactly zero, attained by the rule $T\equiv0$. Fixing $\mu$ lets us ask how much progress is possible **at a given gradient magnitude** when the direction and noise law are unknown. Writing $g=\mu e$ simply expresses the infimum over the sphere $\{g:\|g\|=\mu\}$. We will explain this motivation before Eq. (4). **2. How the known-norm benchmark informs the unknown-norm design** We agree that a single unbiased observation generally does not reveal the true gradient norm. Section 4 uses the known norm as an information benchmark. It gives the exact value $V_\mu$ at each magnitude and characterizes every rule attaining it. Section 5 then seeks a **single fixed rule** that works for every $\|g\|\ge m$, where $m>0$ is chosen in advance. Let $W_\mu(T)$ denote the worst-case expected descent guarantee of rule $T$ at norm $\mu$. Since the region includes $\mu=m$, its best uniform guarantee cannot exceed $V_m$. Theorem 4 shows that calibrating the rule at $m$ attains the optimal uniform guarantee over this entire region, giving $$\sup_{T\in\mathcal T_R}\inf_{\mu\ge m}W_\mu(T)=V_m.$$ The proof is in Appendix C.2. Thus Section 4 provides both the benchmark and the rule that solves the uniform design problem. The rule uses the prescribed threshold $m$ together with $L$, $R$, and $\sigma$, and can be applied without knowing the current norm. The reason for a positive threshold is made precise in **Proposition C.2 of Appendix C.3**. When $\sigma>0$, the only fixed bounded rule satisfying $W_\mu(T)\ge0$ for every $\mu>0$ is $T\equiv0$. The threshold specifies where we require positive progress. The iterates may enter the region $\|\nabla f(x_t)\|<m$, and Theorem 5 controls the possible loss there. Following your suggestion, we will move this motivation to the start of Section 5 and cite the proposition when introducing $m$. **3. An optimal rule whose update can be orthogonal to the observation** As you noted, the examples in the paper scale the observed gradient. We will add a continuous example illustrating the freedom allowed by Theorem 2. Take $d\ge2$ and $L=\mu=\sigma=R=1$. Let $e_1,e_2$ be orthogonal unit vectors, write $r=\|z\|$, and define $$T(z)= \begin{cases} z/2, & 0\le r\le2,\\ (2/r-1/2)z, & 2<r\le4,\\ \min\{1,(r-4)/2\}\,e_1, & r>4. \end{cases}$$ This rule is continuous and satisfies $\|T(z)\|\le1$. Since $T(5e_2)=e_1/2$, it cannot be written as $\eta(z)z$. For these parameters, Theorem 2 gives the necessary and sufficient condition $$\tfrac12\|T(z)\|^2+\|T(z)-z/2\|\le r^2/8 \qquad\text{for all }z.$$ Both branches for $r\le4$ satisfy it with equality. For $r>4$, writing $a=\min\{1,(r-4)/2\}$, the left-hand side is at most $a^2/2+a+r/2\le r^2/8$. Hence this rule attains the same minimax value $V_\mu=1/4$ as the clipping rule. This example shows that minimax optimality permits updates beyond clipping, including updates that change direction. Clipping received more attention in our presentation because it gives a particularly simple optimal rule. We will present the two examples together to clarify which features optimality requires and where the choice of update remains open. We hope these clarifications can address your concern. Thank you again for your valuable comments, which helped us see how we can organize the paper more clearly for readers.
Reviewer_1rDjOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies update rules for smooth stochastic optimization. At a high level, it formulates the problem of choosing an update at a given iteration of a stochastic optimization algorithm as an optimization problem, and then solves this problem. More specifically:

  • The decision variable is an update rule that maps a stochastic gradient observation to a step, subject to a bound on the step’s norm.
  • The objective is to maximize the expected value of a lower bound on the actual decrease in the objective function, where the lower bound comes from smoothness.
  • The problem is formulated in a minimax sense: given the true gradient norm and a variance bound, the rule is chosen to maximize this expected lower bound in the worst case over all gradient directions and stochastic gradient distributions that are unbiased and satisfy the variance bound.

The main contribution of the paper is to solve this optimization problem and show that one of its optimal solutions corresponds to a clipped SGD update with specific choices of learning rate and clipping threshold. Clipped SGD is a popular algorithm that has been studied previously. The optimal update rule is in general not unique, and the paper also characterizes all optimal rules.

Critical strengths

I think the way that the authors formulated the problem is quite elegant. The optimization problem used to solve for the step is natural, and it is cool that one of its optimal solutions recovers the clipped SGD algorithm. This gives a nice explanation for where clipping comes from.

I also like that the authors were able to exactly characterize the set of all update rules that solve the optimization problem. This is, in my opinion, one of the technical strengths of the paper.

Critical weaknesses

It is not clear to me whether the optimization problem solved in this paper is the 'right' optimization problem to solve if one's goal is to get the best possible stochastic optimization algorithm. The one-step minimax objective, while it feels natural, is greedy and can be conservative. It is not clear to me how well optimizing this objective aligns with the overall goal of obtaining the best possible solution by the end of a fixed optimization horizon.

Also, the algorithm that does not require knowing the true gradient norm uses a fixed stepsize parameter m. To guarantee high accuracy, m must be chosen small, which leads to a conservative learning rate and could lead to slow progress, especially when the current gradient norm is much larger than m.

Questions for authors

N/A

4 comments
AuthorsOpenReview ↗

Global Performance and Calibration

Thank you for your careful reading and positive assessment. We address your concerns about global performance and fixed-threshold calibration. Revisions primarily addressing your concerns are highlighted in red.

1. One-step worst-case design and global performance

Our guarantee must cover every observation distribution satisfying unbiasedness and the variance bound. Accounting for the least favorable distributions can make this design appear conservative compared with methods tuned to a particular distribution. Our minimax result determines the strongest one-step guarantee attainable under the same information and update constraints.

The one-step criterion is greedy, but greediness alone does not determine whether its global behavior is conservative or aggressive. The connection we establish is through global worst-case complexity. Let m>0m>0 be the calibration threshold, RR the update norm bound, and LL the gradient Lipschitz constant. With the accuracy calibration in Theorem 5 and R≥m/LR\ge m/L, the constructed rule achieves the ε−4\varepsilon^{-4} order matching the existing stochastic oracle lower bound, for a fixed positive variance bound and sufficiently small ε\varepsilon. Here, ε\varepsilon is the target expected gradient norm of a uniformly selected iterate. Thus, this local robust design retains the optimal global worst-case accuracy order in this regime.

Changes: The introduction clarifies the distributionally robust design objective. Section 5.2 adds the oracle lower-bound comparison. The conclusion identifies optimal decisions over a fixed horizon, accounting for future states and the remaining budget, as a further sequential design problem.

2. A small fixed threshold and calibration with an estimated norm

A fixed mm ties the update parameters to the final target accuracy, which can limit early progress when the current gradient norm is much larger than mm. This is a tradeoff of fixed calibration; the one-step minimax design itself allows the parameters to adjust to the current gradient scale.

We have added a calibration analysis that is robust to norm-estimation error. Let μ>0\mu>0 be the true gradient norm, s>0s>0 its estimate, and TsT_s the rule calibrated at ss. The quantity Wμ(T)W_\mu(T) is the worst-case expected one-step descent guarantee of rule TT at norm μ\mu, over admissible gradient directions and observation laws; VμV_\mu is the largest such guarantee over all bounded measurable rules under the same update cap. For relative-error tolerance δ\delta, we prove

\quad\Longrightarrow\quad W_\mu(T_s)\ge(1-\delta)^3V_\mu.$$ **Thus, when estimates with this accuracy are available, the parameters can track the current gradient scale, alleviating the conservativeness of calibration to a small fixed $m$ while retaining a quantified fraction of the optimal one-step guarantee.** **Changes:** The discussion after Theorem 5 explains the small-threshold tradeoff and adds a remark on estimated-norm calibration. Appendix D.6 proves the robustness bound and gives a trajectory-level stationarity guarantee under stated conditional moment and estimation-accuracy assumptions. It also notes that observations used for estimation must be counted separately from update observations. Thank you again for your valuable comments. We hope these clarifications address your concerns.
AuthorsOpenReview ↗

Further Thoughts on Multistep Performance

Following our earlier response, we would like to add some thoughts on the rationale for the one-step formulation discussed in your Weaknesses section.

You noted that, although natural, the one-step minimax objective is greedy and potentially conservative, and its alignment with the overall objective under a fixed optimization budget needs further explanation. This assessment encouraged us to consider how the formulation could be supported by quantitative evidence about multistep performance.

We see two directions: comparing actual times to reach a target accuracy, and examining how the one-step optimum translates into a cumulative convergence guarantee.

Both directions retain the paper's general smoothness, lower-boundedness, and conditional unbiasedness and variance assumptions. Consistent with our design space, we compare fixed bounded observation-to-update maps: xt+1=xt−T(Gt),∥T(z)∥≤R.x_{t+1}=x_t-T(G_t),\qquad \|T(z)\|\le R.

1. Comparing actual times to reach the target accuracy

Consider the first time the algorithm reaches ∥∇f(xt)∥≤ε\|\nabla f(x_t)\|\le\varepsilon. Let Hε(T)\mathcal H_\varepsilon(T) denote its worst-case expected value over admissible objectives and gradient oracles, and let Hε⋆\mathcal H_\varepsilon^\star be the best value among all fixed bounded maps.

Our preliminary calculations suggest that, when R≤ε/LR\le\varepsilon/L and Δ>ε2/(2L)\Delta>\varepsilon^2/(2L),

{\mathcal H_\varepsilon^\star} \le \frac{1}{1-\varepsilon^2/(2L\Delta)} \frac{1}{1-LR/(2\varepsilon)},$$ where $\Delta$ bounds the initial objective gap. This would give a ratio of at most four when $\Delta\ge\varepsilon^2/L$, approaching one as $L\Delta/\varepsilon^2\to\infty$ and $LR/\varepsilon\to0$. Thus, under these parameter conditions, one-step minimax design could achieve asymptotically minimax multistep performance within this algorithm class over general smooth objectives. The proof strategy is: - **For our rule**, before reaching the target region, the existing one-step result guarantees conditional expected descent of at least $V_\varepsilon$. Accumulating this descent up to the first hitting time provides the upper bound $\mathcal H_\varepsilon(T_\varepsilon)\le\Delta/V_\varepsilon$. - **For any competing fixed rule**, we can construct a smooth objective with a long constant-gradient region, with gradient norm slightly above $\varepsilon$, that transitions smoothly into a flat region. An admissible oracle returns zero with a prescribed probability and a nonzero observation otherwise. The descent direction can be chosen so that the rule's update on zero observations cannot help it advance; each nonzero observation permits progress of at most $R$. Consequently, every fixed rule must wait for sufficiently many informative observations to traverse the region. We plan to formalize this construction and combine its lower bound with the upper bound to verify the proposed ratio. **2. Translating the one-step optimum into a cumulative guarantee** The second direction concerns the paper's finite-budget stationarity criterion: for an iterate $x_J$ selected uniformly from the first $N$ iterations, $$\mathbb E\|\nabla f(x_J)\|\le\varepsilon.$$ Suppose a rule admits a uniform affine descent bound $$W_\mu(T)\ge a\mu-b,\qquad \forall\mu\ge0,\quad a>0,$$ where $W_\mu(T)$ is its worst-case expected smoothness-based descent bound at gradient norm $\mu$. Telescoping gives $$\mathbb E\|\nabla f(x_J)\| \le\frac ba+\frac{\Delta}{aN}.$$ The sufficient budget is therefore controlled by $a\varepsilon-b$: a larger value gives a smaller budget. The one-step minimax value sets an upper limit: $$a\varepsilon-b\le W_\varepsilon(T)\le V_\varepsilon.$$ The key step to verify is whether our rule admits a descent bound valid at **every** gradient norm while attaining this limit at the target accuracy. Our preliminary analysis suggests this is achievable when $R\ge\varepsilon/L$. Establishing the required inequality and calibrating the threshold to $\varepsilon$ would yield $$N\ge\frac{2L\Delta(\varepsilon^2+\sigma^2)}{\varepsilon^4} \quad\Longrightarrow\quad \mathbb E\|\nabla f(x_J)\|\le\varepsilon.$$ This would also establish optimality of the budget constant within the framework of uniform affine descent bounds and objective-value telescoping. Any rule attaining it would necessarily be one-step minimax optimal at gradient norm $\varepsilon$, giving a precise connection between local optimality and the best cumulative guarantee within this framework. These analyses aim to provide further quantitative support for the one-step formulation through its multistep consequences. We will develop the arguments fully and provide the precise statements in the revised manuscript. Thank you for your time.

Thanks for your clarifications! Again I think this is a nice paper, and in my mind its main strength is the clean formulation of the optimization problem to be solved!

Thank you for your reply and positive assessment. We appreciate your recognition of the formulation and your constructive comments on its broader implications.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Discussion and Revisions

We thank the reviewers and the Area Chair for the discussion. The comments helped us clarify how the one-step design relates to multistep performance, why the analysis distinguishes different levels of information about the gradient norm, and which update rules the theory covers.

1. Multistep performance and fixed calibration (Reviewer 1rDj)

The review raised two concerns: how a one-step guarantee relates to performance over a fixed horizon, and whether calibrating to a small target threshold can slow progress early in optimization. Section 5.2 now identifies the regime in which our stationarity guarantee matches the stochastic first-order oracle lower bound in its dependence on the target accuracy. This guarantee concerns the gradient norm of a uniformly selected iterate. Optimal design for the final iterate at a prescribed horizon remains an open question.

For the calibration concern, Appendix D.6 quantifies how much of the optimal one-step guarantee is retained when the rule uses an estimate of the current gradient norm. This gives a way to adjust the update to the current scale when an estimate of sufficient accuracy is available.

2. What one-step optimality adds beyond the convergence order (Reviewer nG9w)

The new Appendix D.5 shows that scaling down the updates by a fixed factor preserves the convergence order while strictly weakening the worst-case one-step guarantee at the calibration threshold. The follow-up discussion focused on whether this distinction also matters over multiple iterations. We outlined two analyses: a comparison with the best fixed bounded rule in the expected time to first reach the target in the worst case, and a characterization of the best iteration budget obtainable from a uniform affine descent bound. Reviewer nG9w confirmed that the follow-up addressed the concerns. We will include the full statements and proofs of these preliminary results in the next revision.

3. Motivation and scope of the minimax formulation (Reviewer DVuC)

The revised manuscript states the assumptions of Theorem 5 explicitly, explains how the proof handles iterates below the calibration threshold, and expands the related work and examples. The follow-up discussion centered on why we first fix the gradient magnitude and how far the characterization extends beyond clipping.

Taking the worst case over all nonzero gradient vectors gives a minimax value of zero for absolute descent, since the gradient norm can approach zero. Fixing the magnitude lets us determine exactly how much descent one observation can guarantee at that scale. Theorem 4 then connects this benchmark to the unknown-norm setting: calibrating once at a threshold mm attains the best uniform guarantee over all gradient norms at least mm, without requiring the current norm at runtime. Proposition C.2 in Appendix C.3 explains why the threshold matters. With a positive variance bound, the zero rule is the only fixed bounded rule that guarantees nonnegative descent at every positive gradient norm.

We also gave an explicit continuous bounded rule that attains the same minimax value as clipping while sending some observations to updates orthogonal to them. We believe the benchmark result and this example address the concerns about the motivation and scope of the formulation. To make both points clearer on first reading, we will move the threshold motivation earlier and present the two optimal rules side by side. We also propose a more precise title, One-Step Minimax Design of Bounded Stochastic Gradient Updates.

We thank the reviewers again for their suggestions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.