Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent

We thank the reviewer for the time and effort they spent reading and engaging with our paper. We are glad that the reviewer found our paper and proposed algorithms to be interesting.

Relative smoothness

Consider adding a remark immediately below Assumption 2.1 explaining how your definition of local curvature relates to the relative smoothness and relative convexity of Gower.

Thank you for this suggestion. In the final paragraph of the subsection, we have a sentence that states the discussion of related assumptions is in Appendix A. In Appendix A, we provide a detailed explanation about the connection to relative convexity and smoothness. We will modify this sentence to explicitly state that we discuss relative convexity and smoothness in the appendix.

Questions

Example 6.1: why would one want to consider the squared Huber loss? Are there any papers in the literature that do so? Similarly, perhaps a bit more motivation for absolutely convex functions could be provided.

We provide the squared Huber loss as an example of a simple function that satisfies our assumption with $L_C \leq L$ and provides intuition about this new class of functions. The square of the Huber loss is not strongly convex because $f''(x) = 0$ at $x = 0$. However, the function has a non-zero curvature matrix elsewhere, which can be employed by our algorithms. So this is a simple example where a function is not strongly convex (a common assumption in optimization) but satisfies our assumption with a non-trivial $\mathbf{C}(x)$ curvature matrix. In our assumption, the curvature matrix is allowed to vary with $y$, which makes it much more flexible. So, many functions relevant to optimization are included in this new class. The intuition regarding absolutely convex functions follows similarly.

In figures 2 and 3, how do you compute the ground truth solution x^*? Is this the solution to the regularized binary classification problem? Moreover, I think would be a more reasonable thing to plot on the y axis, as this aligns better with your theorems.

For these experiments, we first run Newton's method to determine the approximate $x^*$. The update step of LCD2 and Polyak step size method involves projections onto localization sets and is guaranteed to satisfy $||x_{k+1} - x^\star||_2 \leq ||x_k - x^\star||_2$. We plot $||x_k - x^\star||_2$ to highlight this fact.

I think the right hand side of equation 19 is missing a factor of -2. Thank you for verifying. That is a typo; the factor of -2 comes from Lemma B.1.

We appreciate the reviewer for finding the typos and have corrected them in an updated manuscript.

Concluding Remarks

We thank the reviewer again for their valuable feedback. We hope that our rebuttal addresses their questions and concerns, and we kindly ask the reviewer to consider a fresher evaluation of our paper if the reviewer is satisfied with our responses. We are also more than happy to answer any further questions that arise.

We are appreciative of the time and effort the reviewer spent engaging with our work. We are glad that the reviewer found LCD3 to be an interesting method and our work to be well written and easy to read. We now address the reviewer's concern.

$L_\mathbf{C}$-smoothness vs $L$-smoothness

The actual matrix correction used regularizes the C matrix with L, which for any interesting practical problem means that the actual step taken will be overwhelmingly corrected by L not C, essentially becoming a diagonal step...This is why the rates obtained are just the same as you would get using a simple 1/L step size for LCD1 - the step will behave virtually the same as that step!

Firstly, we emphasize that our rates are based on $L_\mathbf{C}$ and we know that $L_\mathbf{C} \leq L$ for functions that are smooth. Also, we would like to highlight that our goal is to leverage local curvature information to develop methods with adaptive step sizes. To that end, only one of our methods, LCD1, which is an analog of GD with constant step size, employs $L_C$ in the update step. LCD2 uses an adaptive term $C(x_k) + \beta_k I$, and LCD3 is also a fully adaptive method that does not depend on $L_C$. Furthermore, it is not the case that the update step is dominated by $L_C$. To illustrate this point, we consider a simple ill-conditioned example. Let $0 < \delta < 100$ and $h: \mathbb{R} \to \mathbb{R}$ be the huber loss,

$$h(y) = \begin{cases} \frac{1}{2}y^2 & |y| \leq \delta, \\\\ \delta(|y| - \frac{1}{2}\delta) &| y| > \delta \end{cases}$$

Let $f(x,y) = 50 \delta^2x^2 + h(y)^2$. Then $f$ is L-smooth with $L = 100\delta^2$. Additionally, $f$ satisfies Assumption 2.1 with $L_C = 3\delta^2$ and,

$$C(x,y) = \begin{bmatrix} 100 & 0 \\\\ 0 & g(y) \end{bmatrix}$$

where $g(y) = |y|$ if $|y| \leq \delta$ and $g(y) = \delta^2$ otherwise. Therefore, we can see that the update step of LCD1 will not be dominated by $L_C \cdot I$ term everywhere. Furthermore, we also have that $L_C << L$ and the gap can be made arbitrarly larger. The convergence rates we obtain for LCD1 and LCD2 are based on $L_C$ and not the classical $L$ smoothness constant. Therefore, we obtain better convergence rates up to constants than GD with constant or Polyak step size, especially when $L_C << L$. Furthermore, analogous to the polyak step size, LCD2 can often perform better in practice than suggested by the theoretical convergence rate.

LCD2 vs trust-region methods

LCD2 is a trust region method, i.e. the reduction to a 1D optimization over the beta parameter to set the step size is just well known trust region theory.

We recognize the reviewer’s observation regarding potential connections between LCD2 and trust region methods. However, we respectfully disagree with the claim that LCD2 is a trust-region method. Trust region methods minimize a quadratic approximation of $f$ subject to a local radius constraint,

$$\text{min}_x \ \{f(x_k) + \langle\nabla f(x_k), x - x_k \rangle + \frac{1}{2}(x - x_k)^T \nabla^2 f(x)(x-x_k)\} \\ \quad \text{s.t.} \ ||x - x_k||_2 \leq \Delta_k,$$

where $\Delta_k$ is the region radius. On the other hand, the update step of LCD2 is projection onto an ellipsoid,

$$\text{min}_x \ ||x - x_k||_2^2 \\ \text{s.t.} \ f(x_k) + \langle\nabla f(x_k), x - x_k \rangle + \frac{1}{2} \langle C(x_k)(x- x_k), x - x_k \rangle \leq f^\star$$

Instead of minimizing a quadratic function subject to a norm constraint on $x - x_k$, we are minimizing $||x - x_k||_2^2$ subject to a quadratic constraint. While there are some similarities in form, the underlying optimization problems are different.

To solve the constrained optimization problem in the update step of LCD2, we apply standard techniques from optimization theory. We derive the corresponding dual problem in terms of a scalar Lagrange multiplier. This reduces the update step to finding the unique root of a 1D function (which is different than the 1D function you would obtain from the trust-region method). We show that Newton’s method can be used to find the root, with guaranteed convergence, as detailed in Appendix C.1, where we also note similar derivations appear in trust-region literature [5]. However, the use of Lagrange multipliers and Newton’s rooting finding method are general tools and are not exclusive to trust-region methods. While the projection onto the ellipsoid in our case also reduces to a scalar root-finding problem—resembling a trust-region step in form, this similarity alone does not make LCD2 a trust-region method.

LCD3 + Evaluations

LCD3 is interesting, but without either theory for it, or far more comprehensive experiments, the investigations for that method is not sufficient for publication.

We provide many experiments demonstrating the superior empirical performance of LCD3. We perform logistic regression, linear regression, and Huber loss regression experiments with various regularizers across several datasets. Our experimental evaluations are based on standard setups and commonly used datasets in convex optimization literature.

The set of problems where C is known and tractable is very small, and the further requirement that we know either L or f* narrows the set even further. It looks like it won't be easier to compute than the Hessian in various practical cases (such as logistic regression). A Hessian-based trust-region baseline would need to be included if that's the problem being focused on.

We understand the reviewer's concern but politely disagree. Our assumptions regarding local curvature are weaker than the well-studied strong convexity and smoothness in the literature, and recover convexity and smoothness as a special case. Also, we show interesting examples satisfying our assumptions, which are not strongly convex or smooth.

Additionally, in many cases, the curvature matrix is diagonal e.g. for $p$-norms, so it is easier to compute than the full Hessian for $p$-norm regularized problems. For objective functions expressed as a sum of squared absolutely convex functions $\phi_i$, we have,

$ f(x) = \sum_{i=1}^n \phi_i(x)^2, \quad \mathbf{C}(x) = \sum_{i=1}^n \nabla\phi_i(x)\nabla_i\phi(x)^T. $

Computing the sum of outer products may be cheaper than forming the full Hessian. Notably, even computing this sum over a mini-batch of indices $S \subset \{1, \dots, n\}$ yields a valid curvature matrix: $\sum_{i \in S} \nabla\phi_i(x)\nabla_i\phi(x)^T$ satisfying Equation (5). Computing a mini-batch curvature matrix is more efficient, allowing for scalable approximations to the full curvature matrix in large-scale settings. A concrete instance of this setup is linear regression, where $\phi_i(x) = a_i^\top x + b$ (which is absolutely convex), demonstrating a practical scenario.

Our empirical focus is on comparing our methods to classical counterparts like gradient descent with the Polyak step size, as our approaches extend these adaptive strategies. In our experimental settings, such as regularized logistic regression, where the curvature matrix comes from the regularizer rather than the full Hessian, our methods still outperform adaptive baselines, including in wall-clock time, demonstrating the practical benefit of employing a readily available local curvature matrix.

Knowledge of $f^\star$

We acknowledge the reviewer’s comment that requiring knowledge of the minimum value poses a potential limitation for LCD2 and LCD3, which are extensions of the Polyak step size. We would like to clarify that in many modern machine learning settings, this requirement may not be as restrictive as it initially appears. There has been a growing body of work on stochastic Polyak step sizes for finite sum minimization $\min_x \sum_{i=1}^n f_i(x)$ where the requirement is relaxed to knowing each individual $f_i^\star$. This relaxation is particularly relevant for overparameterized models, which are now widespread. In such models, the training data can often be fit exactly, implying that $f_i^\star = 0$. As a result, future extensions of our work, particularly in the stochastic setting, can leverage these developments to broaden applicability. In light of this, we respectfully disagree that our methods are niche as there is a lot of promise for optimization methods in machine learning that use $f^\star$.

Another well-known example where we know that value of the global $f^\star$ is binary classification with linearly separable data ($f^\star = 0$). Additionally, when the value of $f^\star$ is not known we can estimate it as $f_{\text{best}} - \gamma^k$ where the sequence $\gamma^k > 0$, $\gamma^k \to 0$, $\sum_k \gamma^k = \infty$ and $f_{\text{best}}$ refers to the smallest objective value in the trajectory so far [1]. Furthermore, several works have proposed strategies to employ the Polyak step size in the stochastic setting for finite sum minimization without knowledge of $f_i^\star$. A common approach is introducing slack constraints, i.e. finding the smallest possible $s \in \mathbb{R}$ such that $f_i(x) \leq s$ [2] [3] [4] . Stochastic Polyak methods require knowledge of each $f_i^\star$, which is a weaker condition than knowing the global $f^\star$.

Concluding remarks

We hope that our responses were sufficient in clarifying all the great questions asked by the reviewer. We thank the reviewer again for their time, and we politely encourage the reviewer to consider updating their score if they deem that our responses in this rebuttal merit it.

References

[1] Stephen Boyd. Lecture notes: Subgradient methods, Jan. 2014. [2] R. M. Gower, A. Defazio, and M. Rabbat. Stochastic Polyak Stepsize with a Moving Target, Sept. 2021. [3] R. M. Gower, M. Blondel, N. Gazagnadou, and F. Pedregosa. Cutting Some Slack for SGD with Adaptive Polyak Stepsizes, May 2022. [4] S. Li, W. J. Swartworth, M. Takác, D. Needell, and R. M. Gower. SP2, July 2022. [5] Nocedal and Wright. "Numerical Optimization". 2006

We thank the reviewer for engaging with our paper during the review period! We are glad that the reviewer found our notions of growth to be different to the more canonical ideas in convex optimization and our methods interesting and original. We now address the reviewer's concerns.

Improving Organization

We appreciate the reviewer's detailed feedback on the organization of our paper. In particular, we will modify the section regarding summary of contributions and update Lemma 7.1 to include that the square of an absolutely convex function is convex which the reviewer found to be interesting.

Questions

How does (5) compare with self-concordance?

Self-concordance requires the function to be thrice differentiable and bounds the third derivative (which measures change in curvature) in terms of the second derivative i.e. $|f'''(x)| \leq |f''(x)|^\frac{3}{2}$. Specifically, self-concordance allows for better convergence analysis of Newton's method and related quasi-Newton methods. Although the self-concordance property bounds change in curvature, it is a different concept from (5). Assumption 2.1. does not involve the third derivative, but from Lemma E.6 and E.10 in the Appendix, we do know that,

$C(x) \preceq \nabla^2 f(x) \preceq C(x) + L_C\cdot I.$

While the local curvature matrix provides bounds on the Hessian, it does not say anything about third-order information.

While the conciseness of the update for LCD2 is nice, it would be useful to see how is defined without having to refer to the appendix, as it is an essential part of the update. It is also not immediately obvious why LCD2 becomes GD with Polyak stepsize when C = 0. Perhaps this has to do with the form of which emphasizes the need to include it in the main text.

We acknowledge the reviewer's concern regarding the clarity of the update step of LCD2. When minimizing a convex function $f$, the Polyak step size corresponds to projecting the current iterate, $x_k$, onto the halfspace,

$$\mathcal{L}(x_k) = \\{x \in \mathbb{R}^d \ | \ f(x_k) + \langle\nabla f(x_k), x - x_k \rangle \leq f^\star \\}.$$

This projection problem can be solved in closed form, and the update step corresponds to GD with Polyak step size.

The update step of LCD2 corresponds to projecting the current iterate, $x_k$ onto the ellipsoid,

$$\mathcal{L}_C(x_k) = \\{x \in \mathbb{R}^d \ | \ f(x_k) + \langle\nabla f(x_k), x - x_k \rangle + \frac{1}{2}\langle C(x_k)(x-x_k), x - x_k \rangle \leq f^\star \\}.$$

When $C = 0$, our assumption reduces to convexity and L-smoothness and $\mathcal{L}_C(x_k)$ becomes $\mathcal{L}(x_k)$. Then it is easy to see that the projection problems are the same so LCD2 reduces to GD with Polyak step size. However, LCD2 does not have a closed-form update step as the reciprocal of $\beta_k$ is a unique root of a scalar equation that does not have a closed-form solution. We will update Section 3.2 of the paper to include the more detailed explanation above.

How is LCD3 defined when C is non-invertible? Is it the case that there might be more than one solution to the problem, and in that case would any solution work?

In that special case, we can use the pseudo-inverse of $C(x_k)$ instead which means that there is not a unique solution.

I can see how LCD1 would be a descent method (i.e., ensures continuous decrease), but can the same be said for LCD2?

It is true that LCD2 and LCD3 are not guaranteed to decrease the function value at each step. LCD2 and LCD3 project the current iterate onto the localization set, which does not guarantee descent. For a specific example, it is well known that GD with Polyak step size is not a descent method [1] and LCD2 reduces to polyak step size when $C = 0$.

Comparing against Polyak's method for problems with regularization in Figures 3 and 4 is not a fair comparison in my opinion; considering this is not a setting where the gradients are not bounded.

We acknowledge the reviewer's concern about the unbounded gradients in some of our experiments. However, the Polyak step size is special and interesting because it is very robust in many settings, including problems that are not L-smooth or do not have bounded gradients. Many works have proposed stochastic extensions of the Polyak step size to train neural networks. Therefore, we do believe it is interesting and appropriate to compare how LCD2 and LCD3 (which are extensions of Polyak step size with local curvature) perform in the $L_3$ regularization setting.

How can you potentially circumvent the cost for O(d^3) in the methods, especially relative to Newton's method which also suffers from the same complexity. This leads me to another question (stated below)

We acknowledge the concern regarding the $O(d^3)$ computational cost associated with matrix inversion. However, in many of our examples, the curvature matrices often exhibit special structure, such as being diagonal, or even rank-one, which allows for efficient computation of $(C(x_k) + \beta_k I)^{-1}$.

The elegance of the Newton's method / quasi-Newton method is that with an oracle for Hessians and gradients, the method is pretty much black-box. In this case, there is a need to identify C for a given problem specification, and the authors discuss the case of $||\cdot||_p$. Can identifying C be more "automatic" in some way?

We appreciate the reviewer’s question regarding the potential for automatically determining the local curvature matrix $C$. While this is an interesting and valuable direction, it falls outside the scope of the present work. We comment that for curvature matrices of the form $C(x) = \mu(x) \cdot I$, it may be feasible to perform power iteration on the Hessian at current iterate $x_k$ to obtain an estimate of the local strong convexity constant, $\mu(x_k)$.

We focus on the setting where such a curvature matrix is assumed to be available. The main contribution of our work is introducing and demonstrating the value of this assumption. First, we show that in many convex optimization problems such as p-norms, certain convex loss functions, and squares of absolutely convex functions, the curvature matrix is readily available. Next, under these local curvature assumptions, we develop theoretically grounded adaptive algorithms such as LCD2 that improve upon their classical counter-parts such as GD with Polyak step size.

Exploring heuristic or data-driven methods for approximating C is indeed an intriguing direction, and we view this as promising future work. However, our current contribution and focus is developing principled algorithms built on rigourous theoretical foundations.

Why is the BB method behaving so irregularly? Is it an implementation difficulty or a procedural issue with BB?

The BB step size does not have convergence guarantees for convex smooth problems. Therefore, for certain problems, the BB step size method may behave irregularly.

Concluding Remarks

We thank the reviewer again for their valuable feedback. We hope that our rebuttal addresses their questions and concerns, and we kindly ask the reviewer to consider a fresher evaluation of our paper if the reviewer is satisfied with our responses. We are also more than happy to answer any further questions that arise.

References

[1] Stephen Boyd. Lecture notes: Subgradient methods, Jan. 2014.

I think it helps point out how the local curvature conditions might be useful and it would have been more interesting to see a comparison against (damped) Newton's method or a quasi-Newton method.

We thank the reviewer for suggesting a comparison against a quasi-Newton baseline. As requested by another reviewer, we include results with L-BFGS in our experimental setup below. We would like to politely remind the reviewer that new rebuttal rules prevent the sharing of images. Therefore, we provide tables showing the value of $||x_T - x^\star||_2$ at the last iterate $x_T$.

Additional experiments

Logistic regression with $\frac{\lambda}{2}||\cdot||_2^2$ regualrization on mushroom dataset. As done in the paper, we compute $\lambda$ as a factor of the $L$-smoothness constant of the logistic regression instance. The first table is with $\lambda \approx 0.05$ and second table is with $\lambda \approx 0.001$.

Logistic regression with $\frac{\lambda}{2}||\cdot||_2^2$ regularization on a2a dataset. The first table is with $\lambda \approx 0.06$ and second table is with $\lambda \approx 0.005$.

Sum of square of Huber Loss (absolutely convex) on mpg dataset with $\delta = 100$.

Sum of square of Huber Loss (absolutely convex) on mpg dataset with $\delta = 10$.

Logistic regression with $\frac{\lambda}{2}||\cdot||_3^3$ regualrization on mushroom dataset. The first table is with $\lambda \approx 0.01$ and second table is with $\lambda \approx 0.005$.

We find that our adaptive methods are competitive with L-BFGS and can outperform it, demonstrating that local curvature is a useful notion in settings where our assumptions hold.

Concluding Remarks

We thank the reviewer again for their feedback, which allowed us to strengthen our work with additional clarifications and experiments that we will include in the updated paper. We also invite the reviewer to ask any other lingering questions they may have or to potentially consider a fresher evaluation of our paper with these rebuttal responses in context.

We thank the reviewer for spending the time and effort engaging with our work. We appreciate that the reviewer found our convergence proofs of LCD1 and LCD2 to be solid results and our numerical experiments to be relatively extensive on functions that satisfy our assumption.

Justifying Local Curvature

The field of optimization theory really needs to focus on more natural classes of functions that appear in practice. It is less clear how natural the class of functions introduced is. For example, most functions we are interested in are not convex.

We acknowledge the reviewer's concern that the relevance of convex optimization theory for modern machine learning is not initially apparent. However, we would like to politely push back on this assertion, as developing theory in the convex setting is important for understanding methods and can lead to insights in more complex regimes, such as the non-convex case. Various adaptive methods that are the workhorse for modern machine learning, such as Adagrad (and its variants such as Adam) were developed with theory in the convex setting. Other powerful adaptive step sizes such as the MM step-size [6] and the Polyak step size were developed with theory for the convex setting.

Furthermore, we believe that Assumption 2.1 offers a natural way to incorporate a notion of curvature into the classical framework of convexity and smoothness without going down the route of fully-fledged second order methods. We demonstrate its applicability through several relevant examples in convex optimization, including $p$-norms, convex loss functions, and squares of absolutely convex functions, where this notion of local curvature can be effectively exploited to design adaptive algorithms with superior performance. Interestingly, some curvature matrices arising in these examples often exhibit special structure,such as being diagonal—which is particularly relevant in machine learning settings. For instance, recent work [5] has shown that the Hessians of deep neural networks often have a block-diagonal structure. A better understanding of these diagonal patterns can facilitate the design of more efficient and scalable adaptive optimization methods.

Extensions to Stochastic Setting

We agree that extensions to the stochastic setting are a very interesting and natural research direction that can be explored in future work. Specifically, one could explore the case of finite-sum minimization where we only have access to a stochastic version of the local curvature matrix.

Knowledge of $f^\star$

We acknowledge the reviewer’s comment that requiring knowledge of the minimum value poses a potential limitation. We would like to clarify that in many modern machine learning settings, this requirement may not be as restrictive as it initially appears.There has been a growing body of work on stochastic Polyak step sizes for finite sum minimization $\min_x \sum_{i=1}^n f_i(x)$ where the requirement is relaxed to knowing each individual $f_i^\star$. This relaxation is particularly relevant for overparameterized models, which are now widespread. In such models, the training data can often be fit exactly, implying that $f_i^\star = 0$. As a result, future extensions of our work, particularly in the stochastic setting, can benefit from utilizing these techniques. Another well-known example where we know that value of the global $f^\star$ is binary classification with linearly separable data ($f^\star = 0$).

Additionally, when the value of $f^\star$ is not known we can estimate it as $f_{\text{best}} - \gamma^k$ where the sequence $\gamma^k > 0$, $\gamma^k \to 0$, $\sum_k \gamma^k = \infty$ and $f_{\text{best}}$ refers to the smallest objective value in the trajectory so far [1]. Furthermore, several works have proposed strategies to employ the Polyak step size in the stochastic setting for finite sum minimization without knowledge of $f_i^\star$. A common approach is introducing slack constraints, i.e. finding the smallest possible $s \in \mathbb{R}$ such that $f_i(x) \leq s$ [2] [3] [4] . Stochastic Polyak methods require knowledge of each $f_i^\star$, which is a weaker condition than knowing the global $f^\star$.

Questions

I would love to understand better how to understand how general this class is. Are there even more qualitatively different optimization problems that people care about in practice that satisfy your assumptions? I suspect this is a difficult question though. But anything that can be said here would improve the significance and impact of the paper.

We believe that exploring the sum of squares of absolutely convex functions, $\phi_i$, has a lot of potential,

$$f(x) = \sum_{i=1}^n \phi_i(x)^2, \quad \mathbf{C}(x) = \sum_{i=1}^n \nabla\phi_i(x)\nabla_i\phi(x)^T.$$

For example, if $\phi_i(x) = a_i^Tx - b$ (which is absolutely convex), we obtain linear regression with $C(x)$ as the Hessian, so interestingly, our methods reduce to Newton's method. Instead, notice that if we select a specific $i$ we have that $C_i(x) := \nabla\phi_i(x)\nabla_i\phi(x)^T$ satisfies Equation (5) in Assumption 2.1 since for all $x \in \mathbb{R}^d$,

$$0 \preceq C_i(x) \preceq \mathbf{C}(x).$$

Although $C_i$ produces a looser lower bound, it is still a valid curvature matrix and is cheaper to compute than the full curvature matrix, which can be the Hessian in special cases. This opens up possibilities to explore the empirical performance and convergence properties of methods that randomly select indices/data points to form local curvature matrices. Such a family of methods would be relevant to large-scale machine learning problems (where $n$ is large) where forming or inverting the Hessian/full curvature matrix is not computationally feasible.

Another interesting result is that our class of functions leads to a convergence rate of $O(\frac{L_C}{k})$ for LCD1 and LCD2. We could have problems where $L_C << L$, which results in our methods having better convergence rates than their classical counterparts. To provide intuition with a simple example, consider $f(x,y) = 50\delta^2x^2 + h(y)^2$ where $\delta > 0$ and $h$ is the Huber loss function. Then $f$ is L-smooth with $L = 100\delta^2$. Additionally, $f$ satisfies Assumption 2.1 with $L_C = 3\delta^2$ and,

$$C(x,y) = \begin{bmatrix} 100 & 0 \\\\ 0 & g(y) \end{bmatrix}$$

where $g(y) = |y|$ if $|y| \leq \delta$ and $g(y) = \delta^2$ otherwise.

Concluding remarks

We thank the reviewer for their time and effort in reviewing our paper. We hope that our rebuttal here answers all the great points raised by the reviewer, allowing them to potentially upgrade their score if our responses merit it. We are also more than happy to answer any further questions that arise in the rebuttal period. Please let us know.

References

[1] Stephen Boyd. Lecture notes: Subgradient methods, Jan. 2014.

[2] R. M. Gower, A. Defazio, and M. Rabbat. Stochastic Polyak Stepsize with a Moving Target, Sept. 2021.

[3] R. M. Gower, M. Blondel, N. Gazagnadou, and F. Pedregosa. Cutting Some Slack for SGD with Adaptive Polyak Stepsizes, May 2022.

[4] S. Li, W. J. Swartworth, M. Takác, D. Needell, and R. M. Gower. SP2: A Second Order Stochastic Polyak Method, July 2022.

[5] Dong et al. "Towards Quantifying the Hessian Structure of Neural Networks" 2025.

[6] Malitsky and Mishchenko, "Adaptive Gradient Descent without Descent". 2019

[5] Dong et al. "Towards Quantifying the Hessian Structure of Neural Networks" 2025.

Dear Reviewer NYA3,

Please read the author rebuttal and let us know whether your concerns have been satisfactorily addressed. If not, kindly point out what remains inadequate.

The (extended) deadline for the Author-Reviewer discussion is approaching. If you do not respond, I will need to apply the “insufficient review” flag in accordance with the NeurIPS 2025 policy.

You can flag non-participating reviewers with the InsufficientReview button, and we will use the flag in accordance with possible penalties of this year's responsible reviewing initiative and future reviewing invitations.

Best, AC