Exact linear-rate gradient descent: optimal adaptive stepsize theory and practical use
gradient descent;adaptive stepsize/learning rate;universal optimal choice;exact convergence rate
Yes
No ethics review needed.
1. Does Theorem 2.1 and Corollary 2.2 assumes $L$-smoothness?
This paper uses several examples to demonstrate the benefits of using the proposed step size rules.
This paper studies some adaptive size rules for smooth functions, including some theoretical optimal ones and practical approximations. Experiments show some advantages of these rules.
1. This paper lacks a comprehensive comparisons with prior art. A similar rule to the proposed step size rule is studied at least in reference [1] and revisited in [2]. For example, in [2], algorithm 2 is similar to the algorithm for practical use in this paper, and to compare rates with [2], can the authors provide details on how to interpret the term $\Pi_{t = 0}^k \delta_t$ in equation 3.2? 
2. The optimal choice is not shown to be optimal in detail and not fully understandable to me, i.e., in what sense this choice if optimal, does it achieve fastest global convergence rate or fastest one-step descent?
3. The experiments in Figure 3 rely on a good guess of $\bar{f}_0$, and this introduces another parameter for a step size rule designed for tuning free case.

[1]. Boris T. Polyak. Introduction to optimization. Optimization Software, Inc., New York, 1987.
[2]. Hazan, Elad, and Sham Kakade. "Revisiting the Polyak step size." arXiv preprint arXiv:1905.00313 (2019).

Based on these weakness, I think this paper can be significantly enhanced by a thorough comparison with related works and detailed explanations of the improved convergence rates.
Yes
No ethics review needed.
What are the weakest assumptions that are required about the function f, in order for you to guarantee your results hold? 

What is the relationship to the Polyak step size (e.g., paper by Hazan and Kakade)?
The paper considers a significant and important problem.
The problem is of current interest -- there are papers appearing about related topics every year.
The proposal of a new step size is related to well studied step sizes like Polyak step size, but it seems to have some novel aspects.
The paper considers selecting a stepsize for gradient descent, in particular when we cannot compute global quantities like smoothness parameters. Though there has been considerable work, including recently, on adaptive step size selection methods such as Adagrad, this paper takes a different view. The idea is to approximate the a step size that looks a lot like the Polyak step size, by quantities that can be estimated (the Polyak step size requires knowing f(x*)). 

They use this step size on various experiments, including on the non-convex problem of training a 2 layer MLP.
The writing could be significantly improved. There are many examples where the writing deviates from grammatical English, even from the very beginning of the paper. For instance, “due to quantity is not a priori knowledge.” — lines 75-76. In some places this does not impede the understandability of the paper, but in others the problems with the writing indeed make it hard to properly understand what the paper is about, and what its contributions are. 

The introduction is generally loose and imprecise, in areas where it should be specifying exactly what the area of contribution is, precisely because this is such a well-researched area. For example, the paper says that though there are several adaptive algorithms implemented and available, “an adaptive stepsize theory has not been established.” This is confusing, since there are many theoretical papers about AdaGrad and other adaptive step size schedules in the last few years in ML and Optimization venues (not to mention that it is also a fairly classical topic). 

Then we are told that their optimal stepwise yields a linear rate with factor sin^2 \eta_k — but we do not know what \eta_k is at this point in the paper. They they gone on to say that the theory applies to non-convex functions, but we are not told what is guaranteed in this case. At least an informal statement should be made explaining what is happening, if the authors wish to talk about it directly. 

Proposition 2.1 says it guarantees convergence to a global optimum of GD, yet does not require in the statement that the function being optimized be convex. The proof also does not mention convexity, and indeed does not prove anything about global convergence. 

In line 146, the paper says that they assume that the gradient is non-zero unless GD has already converged; but then they say that this means that it has converged to x*, but which I understand that the assumption is that they assume they are minimizing a function that has no stationary points other than the unique global optimum. 

The experiments are also not particularly convincing. They need to better point to where the weaknesses are of other related methods, where this approach succeeds.
Yes
No ethics review needed.
**Q1.** Could the authors provide theoretical analysis (e.g., oracle or iteration complexity) for the proposed adaptive stepsize strategy in the case where $f(x)$ is non-convex?

**Q2.** The authors mention using a commonly adopted mini-batch size of 128. Is this setting specific to ADAM? The proposed method may not directly extend to stochastic settings if it requires a dynamic estimation of $f(x^*)$.
**S1:** The paper is well-written and easy to follow, with a clear presentation of the introduction and background on line-search-free first-order methods.

**S2:** This paper proves a simple line-search-free variant of gradient descent to minimize smooth convex functions. The proposed stepsize can be dynamically adjusted to capture the curvature information of the problem, allowing for faster convergence.

**S3:** The paper provides a rigorous proof of the linear convergence rate under the convex settings.

**S4:** The paper includes empirical comparisons with other popular optimizers, such as Adam and N-AGD.
This paper proposes a new adaptive stepsize for gradient descent that achieves exact linear convergence rates for convex optimization.

The key contribution is a novel stepsize formula based on the gradient and objective function.

The authors provide two versions of the stepsize: a theoretical version and a practical version.

They demonstrate the efficacy of this approach through some preliminary examples.
**W1.** The theoretical analysis relies on strong assumptions, namely that the objective function is convex and the optimal objective value $f(x^*)$ is known.

**W2.** The only practical solution proposed in this paper is Algorithm 1. However, the authors do not provide a theoretical analysis for it. In particular, does Algorithm 1 converge in convex settings? What is its iteration complexity in an ergodic sense when the objective function is convex and non-convex?

**W3.** Additional detailed discussion and analysis are necessary and would be beneficial to further clarify and present Algorithm 1.  
1. For example, the auto-correction mechanism in Algorithm 1 explicitly requires $g(x) \geq 0$; otherwise, $\overline{f}_0$ may not serve as a reliable estimate of $f(x^*)$.  
2. Taking the least squares problem in Problem (3.16) as an example, when $\alpha >0$ and $\alpha \approx0$, Algorithm 1 could get stuck at a point that is neither a local nor a global minimum, as the second correction in Line 322 is never invoked. This can result in a less accurate estimation of $f(x^*)$.

**W4.** Other issues: 

1) The proposed algorithm is only suitable for deterministic optimization problems, as it requires calculating the objective function value, making it incompatible with stochastic optimization models. Comparing it with stochastic optimizers like ADAM may be unfair, as ADAM is designed for stochastic settings while the proposed method is deterministic.

2) It would be beneficial for the authors to include comparisons with other leading deterministic algorithms, such as AdaGrad-Norm (AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, JMLR 2020), APGM (Adaptive Proximal Gradient Methods Are Universal Without Approximation, ICML 2024), and AdaBB (Adaptive Barzilai-Borwein method for convex optimization, 2024).
Yes
No ethics review needed.
- Why are there no citations to relevant works on Polyak stepsize and tuning-free methods?
- What are the assumptions made on f for each of the results, and do they depend on x* being unique?
- Can you actually verify the assumptions you make on alpha_k in any way if you know in advance f or at least properties that it satisfies, e.g., Lipschitz-smoothness or gradient domination?
- Numerical experiments are performed and their plots are reported
The paper proposes an adaptive stepsize selection scheme for gradient descent (GD). The main theoretical contribution is providing an expression for what is claimed to be an optimal stepsize choice, which depends on the (implicitly assumed to be unique) solution to the problem. For practical implementation, they propose approximating this with a Polyak-like stepsize estimating inf_x f(x). The authors provide convergence analysis and some numerical experiments on MNIST and quadratic optimization.
- The definition of the theoretical stepsize proposed depends on x* but it's not clear that x* is unique or that this stepsize is well-defined if x* is not unique. No further assumptions on the objective function f are ever stated to ensure uniqueness of x*. No discussion of what will happen if x* is not unique is given.

- The practical use stepsize given is just a Polyak stepsize approximating inf f by \bar{f}_0. Yet, no reference to Polyak is made nor to any papers studying the Polyak stepsize and related variants, which are quite numerous. In this way the discussion of related work is severely lacking.

- The quality of writing is far below a level that is acceptable for publication. Many statements are mathematically incomplete (e.g., line 155 and many others) or outright incorrect (e.g., the Baillon-Hadad theorem on line 650). Many statements have implicit assumptions that are never stated and not always satisfied or verifiable (e.g., line 146 and many others). None of the convergence results make sense mathematically as there is no reason for x* to be unique - how can \|x_k-x*\|^2 go to 0 for two different x*?

- There is no comparison of the tuning-free algorithm to other tuning-free gradient descent algorithms, of which there is a significant body of work.
We established a general adaptive stepsize theory for gradient descent, including feasible selection range, optimal choice, and convergence rate.
@inproceedings{
anonymous2024exact,
title={Exact linear-rate gradient descent: optimal adaptive stepsize theory and practical use},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=1NYhrZynvC},
note={under review}
}
Consider gradient descent iterations $ {x}^{k+1} = {x}^k - \alpha_k \nabla f ({x}^k) $. 
Suppose gradient exists and $ \nabla f ({x}^k) \neq {0}$.
We propose the following closed-form stepsize choice:
\begin{equation}
	\alpha_k^\star =  \frac{ \Vert  {x}^\star - {x}^k  \Vert }{\left\Vert \nabla f({x}^k)  \right\Vert} \cos\eta_k , \tag{theoretical}
\end{equation}
where $ \eta_k $ is the angle between vectors $ {x}^\star - {x}^k  $ and $ -\nabla f({x}^k)  $.
It is universally applicable and admits an exact linear  convergence  rate  with factor $ \sin^2\eta_k  $.
Moreover, if $ f $ is  convex and $ L $-smooth,  then $ \alpha_k^\star \geq {1}/{L} $.

For practical use,  we approximate (can be exact) the above  via 
\begin{equation}
	\alpha_{k}^\dagger = \gamma_0 \cdot \frac{ f({x}^k) - \bar{f}_0  }{\Vert  \nabla f (	{x}^k )   \Vert^2 } ,
	\tag{practical use}
\end{equation}
where  $\gamma_0 $ is a tunable parameter; $ \bar{f}_0 $ is  a guess on the smallest objective value (can be auto. updated).
Suppose  $ f $ is convex and $ \bar{f}_0 = f ( {x}^\star )   $, then 
any choice from $\gamma_0 \in (0,2] $ guarantees an exact linear-rate convergence to the optimal point.

We consider a  few examples.
(i) An $ \mathbb{R}^2 $ quadratic program, where a well-known ill-conditioning bottleneck is  addressed, with a rate strictly better than $ O(1/2^k) $. (ii) A geometric program, where an inaccurate guess $ \bar{f}_0  $ remains powerful.
(iii) A non-convex MNIST classification problem via neural networks, where preliminary tests show that ours admits better performance than the state-of-the-art algorithms,  particularly a  tune-free version is available in some settings.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
gradient descent adaptive stepsize/learning rate universal optimal choice exact convergence rate
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/82793568484fbe7230becb00e2fbac16a140707d.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/d00ef376b8ab5b99057a300b2c4a20fd303aec57.pdf
Exact linear-rate gradient descent: optimal adaptive stepsize theory and practical use
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission