Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new adaptive variant of the classic trust region method, named FLAT. The proposed scheme preserves the strong convergence guarantee without requiring the knowledge of problem dependent constants like the Lipschitz constant. To achieve a first order stationary point, when compared with previous adaptive second order methods, FLAT enjoys a better depends on the Lipschitz constant and removes the dependence on a regularization parameter which potentially makes the previous guarantees vacuous. 
strengths_and_weaknesses: Strengths:

This paper is well written and the major contribution of this work is well articulated: The proposed FLAT method, as an adaptive method, is able to achieve the same dependence on key parameters $(L, \epsilon)$ as methods that have the exact information of the Lipschitz constant of the Hessian. Moreover, it removes the dependence on $1/\sigma_\min$ which is a potentially unbounded quantity present in previous approaches.

Weaknesses:

The weakness of this work is also pretty clear: As a second order method, it lacks the guarantee of converging to the second order stationary point which is the key advantage when compared against the significantly more efficient first order method. This drawback is acknowledged by the authors as well.

Also, the experiments in Figure 2. seems to suggest that ARC has a better performance than FLAT, in all regards.
questions: It would be great if the authors can comment on the intuition of the newly constructed adaptive rule in Eq. (9). It seems that the additional term $||\nabla f(x_k + d_k)||\cdot||d_k||$ is specifically tailored to quickly achieve a first order stationary point. Is this the reason why the second order guarantee of FLAT is absent? Is it possible to revise the adaptive rule to also include the second order information in order to establish the second order guarantee?
limitations: There is no potential negative societal impact.

As a second order method, the proposed method lacks the guarantee of converging to the second order stationary point. This drawback is acknowledged by the authors as well.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This manuscript studies adaptive trust-region methods and makes an argument that a large bulk of existing literature has an underlying dependency on an arbitrarily small parameter that renders available bounds vacuous. Moreover, dependency on problem parameters is suboptimal, e.g., the Lipschitz constants. The result lies in a modified threshold or ratio for the search direction. Quadratic convergence is shown when the iterates are sufficiently close to the optimal point. Some numerical results are provided.
strengths_and_weaknesses: Strengths
- A weakness of existing methods is clearly identified and solved.
- The originality lies in the definition of new search parameters.
- The paper is well written and the result can serve as the base of future work in adaptive methods.
- Some minimal numerical results are shown

Weaknesses
- At the core of the main argument is the suboptimality of existing approaches. However, the discussion and subsequent argument about it are relegated to a footnote, with very limited discussion.
- Contributions 2 and 4 do not read as contributions.
- The numerical section is very limited. The argument is that the provided method is better than the literature but the provided numerical evidence only explores some minimal examples rather than a comprehensive exposition of the computational advantages. 
questions: Can the developed techniques be applied to other adaptive methods beyond cubic regularization?

Is there a function class for which the advantage of the proposed method is more evident than existing approaches? 
limitations: No potential negative societal impact
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper presents an adaptive trust method region whose complexity in terms of iterations matches that of non adaptive trust region methods. Crucially, this method has the right exponents in terms of the Lipschitz constant of the Hessian and the error. 

More specifically, the introduction of a factor controlling the size of the direction and gradient in the update rule allows to not pay the regularisation parameter and to control more finely the different stages of the algorithm. 

The proof of convergence towards and epsilon approximate stationary point is divided into different phases. 

Additionally, a proof of quadratic convergence near a local optimum is given.

Experiments to support the fact that this method compares with existing methods while having better theoretical guarantees are given, 
strengths_and_weaknesses:     * Originality:

The method is new in the introduction of the term controlling the size of $d_k$ in this context. 



    * Quality: I read most of the proofs and they are sound. Globally, I think the paper is very thorough. One thing missing from the main paper is perhaps how to get the trust region solution to satisfy 7 (it is mentioned in the references and in the appendices) but I am not a specialist. 



    * Clarity: 

Relatively clear. I just believe the part about $\rho_k < \beta$ or $>= \beta$ should be made slightly clearer in the discussion about the different phases. Otherwise, super clear. 




    * Significance: For me, the work is significant theoretically, and is backed by good experiments. 
questions: 
- I believe in lemma 2, typo between $\gamma_1$ and $\gamma_2$ in the second term of the constant (first bound in the appendix). Also, another typo is that lemma 2 applies if the inequality is strict, while in the next proofs it is used for large inequality (but OK since in the algorithm the case distinction implies that the inequality is strict.
- In the proof of lemma 5, I believe the third term should be an inequality and not an equality ? 
- Are there cases where ARC fails because of the sigma problem, where you could show that your method is better ? 

limitations: Exposed by the authors.
review_title: null

Meta-review: metareview: The paper proposes a new adaptive trust region method. Because most of the reviewers think the paper is interesting, I recommend an acceptance.
confidence: Less certain
Decision: Accept