Venue: NeurIPS 2022 Conference

Reviews:

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: The paper proposes a second-order method for minimizing second-order smooth and convex problems, based on an extra-gradient template (thus term it as ExtraNewton). The key feature of this method is that it uses a new stepsize rule that is independent of the smoothness modulus, variance bounds and the diameter of the compact set, which, as the authors claimed, makes the proposed method adaptive and universal. By introducing an optimistic weighting strategy for the decision variables as well as the gradients, they show that the proposed method can enjoy an accelerated rate of O(\sigma/\sqrt{T} +1/T^3) for a stochastic oracle so long as the sequence of weights are properly chosen and the above stepsize rule is employed. Numerical experiments have illustrated the performance of the proposed method in comparison to several existing well-known methods.
strengths_and_weaknesses: Strengths:
- The algorithm is new to the reviewer and it is a very nice property that the stepsize can be adaptive to the smoothness modulus which is usually hard to estimate. In addition, the algorithm is shown to enjoy a rate of O(\sigma/\sqrt{T}+1/T^3) for a stochastic oracle, which is not obtained before for existing second-order methods to the best of the reviewer’s knowledge.
- The paper is technically sound and some proof techniques seems interesting. The reviewer have checked most of the proofs which seems correct.
- The paper is well written and organized in a way that is very easy to follow; and the authors have demonstrated an excellent understanding of the existing literature on second-order optimization. 


Weakness
- In the proof for the main results, the diameter of the compact set “D” seems very important to obtain the O(1/T^3) rate. However, this is quite restrictive for smooth problems, especially when the Hessian is also smooth.
- It follows from Fig. 3 that numerical performance of the proposed method seems not working very well when it comes to stochastic problems.
- The design of the adaptive stepsize rule lacks some intuition. 

questions: - Will it be possible to remove the assumption of a set being compact, and what the rate will become if the assumption is void.
- How does the performance of the proposed method compared to those accelerated methods using cubic regularization for deterministic cases. The reviewer did not see such comparison in this paper.
- Except for the choice of a_t and b_t in this work, is there any other choice that may leads to better convergence performance (numerically)?
- In Figure 3, it can be observed that AcceleGrad outperforms others, including ExtraNewton in both least-square and logistic regression problems; is there any proper explanation on this since it should be better according to the theorectical rate obtained for the stochastic oralce?
- Since the algorithm employs second-order information, the reviewer would like to know (just for curiosity) if it is scalable to high-dimensional problems and if the analysis can be extended to stochastic problems with finite sum structure involving a great number of samples?  

limitations: - The authors are suggested to make comparison (at least via numerical experiments) to the closely related accelerated method such as those relying on cubic regularization. 
- The part of transiting implicit algorithm to explicit one (line 234- line240) lack of some intuitition and the authors are suggested to elaborate on this.
- In the statement of theorem 3.1 and 3.2, the reviewer guess that the Taylor condition and H-smoothness are both need to ensure (1), which most of the proofs rely on. Besides, the proofs for these above two theorems share a lot of similarity, thus it is suggested to, if possible, properly combine them.
- It would be of great interest if the authors can remove the assumption of compact sets and extend their analysis, if possible, to account for finite-sum problems.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This manuscript proposes an algorithm for constrained smooth optimization that achieves simultaneously $O(1 / \sqrt{T})$ convergence rate for stochastic gradient and Hessian estimators and $O(1/T^3)$ convergence rate in the deterministic setting. The keys are a combination of the extragradient and the Newton method as well as a carefully chosen adaptive step size scheme.
The general idea is interesting and it leverages techniques from online learning/optimization so the context is indeed relevant to machine learning.
The manuscript is well-motivated with a clear explanation of its derivation, but the idea of adding a constraint set actually makes the algorithm non-implementable in practice, and thus, although interesting in theory, I doubt the usefulness of the proposed method.
There are also some unclear technical definitions in the theorems that need to be clarified. See the detailed comments.
Another concern is that the amount of experiments is far from sufficient to sufficiently support the performance of the proposed algorithm. I also have some concerns with the experimental results.
strengths_and_weaknesses: Strength:
1. The work is well-motivated with a detailed explanation of its derivation.
2. The result seems to be novel up to my knowledge and of certain importance.

Weakness:
1. Insufficient numerical results
2. The algorithm is nonimplementable
3. There are key symbols used in the text that are undefined and hindered understanding of the results
questions: 1. My biggest concern is about line 2 of Alg. 1. When there is a constraint, clearly this subproblem is in general difficult to solve, especially since H(X) is in general nondiagonal. Thus it looks to me that this algorithm is still not implementable, just like the conceptual one in sec 3.1.

2. Another issue is surely the applicability of this algorithm and how to do a fair evaluation. The authors selected only low-dimensional problems, surely because the cost to invert the Hessian will otherwise be too high. In a more practical setting, usually the Newton step is obtained through an iterative algorithm like CG that queries the 2nd-order oracle n times (assuming that the exact Newton step is needed), where n is the problem dimension. I wonder how the convergence figure would change in that setting.

3. I also would like to know about the running time comparison of these algorithms, especially in the setting of higher-dimensional problems.

4. I am very confused about the results of Newton for least-square. Shouldn't the classical Newton's method take only 1 iteration to find the optimal solution? (And this also shows how this oracle call evaluation for least square is pointless.)

5. Thm 3.1 mentioned $\sigma$ in the assumptions, but the bound seems to be irrelevant to any stochasticity or expectation. I am thus wondering if there are any typos or missing things.

6. I don't quite see where the 1st equation after L. 236 is from. What does it mean and why out of nowhere this thing "to be simplified" appears.

7. Starting from Alg. 1, there suddenly is a quantity $B_t$ that is never defined in the text. What exactly is this?

8. Surely it is appealing theoretically to have a universal algorithm for all settings, but in what real-world application does one face such a situation such that we don't know whether the oracle is noisy or not?

9. This is not directly relevant to the evaluation of this work, but I am also curious about what would happen if the variance changes over iterations. Would it be possible to get a better rate in terms of the sum or so of the iteration-wise variances?

10. After reading others' reviews, I realized that I previously missed the point that this method does not apply to unconstrained optimization, and thus my first comment becomes vital, so I am lowering the evaluation. Also D is not defined in the main paper.

---
I am happy that the authors are willing to make the assumption on the constraint set explicit, so I'm increasing my score to 4.
limitations: As mentioned in the comments, the authors did not mention at all that solving a constrained second-order optimization problem to optimality is actually something difficult and thus also not implementable, just as the existing work they criticized.

They then went on to ignore this fact and conducted experiments on unconstrained problems, which is deceptive.
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: In this work, the authors propose a new accelerated second-order method for
convex optimization. The convergence rate of this algorithm on the standard
class of convex functions with Lipschitz continuous second derivative is $O(1 /
T^3)$, which is exactly the same as that of the standard Accelerated Cubic
Newton Method. However, in contrast to the latter, the new method neither
requires the knowledge of the Lipschitz constant, nor uses any "line search"
for estimating it. Instead, the method accumulates certain quantities, that
measure the deviation of the gradients from their linear approximations, and
uses this information for computing the next iterate. The main feature of the
new method is that it can work not only with a deterministic oracle but also with a
stochastic one. Moreover, the method is "universal" in the sense that it
automatically adapts to the actual variance of the oracle, and therefore
requires no changes in its algorithmic scheme compared to the deterministic
case.
strengths_and_weaknesses: This work presents a new approach for constructing accelerated second-order
methods. An unusual feature of this approach is that it does not rely on any
"line search" and can be easily extended to the case of the stochastic oracle.
Despite many similarities to the already existing acceleration techniques, the
construction, proposed in this work, definitely has a few novel elements.
Overall, I find this paper very interesting and believe that the ideas,
presented there, could be useful in a broader context.

The main drawback of the new method is that it works only with a bounded
feasible set. In particular, it cannot be directly applied for unconstrained
optimization problems. Also, the convergence rate $O(L D^3 / T^3)$ of the new
method depends on the diameter $D$ of the feasible set, in contrast to the $O(L
D\_0^3 / T^3)$ rate of the standard Accelerated Cubic Newton Method which depends
on the distance $D\_0$ from the initial point to the solution ($L$ is the
Lipschitz constant of the second derivative). Nevertheless, in my opinion, this
drawback is not really significant and can be addressed in future work.

Please see my detailed remarks in the next section. I will be happy to increase my score further if the authors address these remarks.
questions: Major remarks:

1. The notation $g(x)$ and $H(x)$ for stochastic gradients and Hessians is
   confusing as it does not highlight the randomness in the stochastic oracle.
   For example, it is not clear whether you use the same random variable for
   generating $g(\\tilde{X}\_t)$, $H(\\tilde{X}\_t)$ and $g(\\bar{X}\_{t + 1/2})$ in
   Algorithm 1, or different ones. A better notation would be $g(x, \\xi)$ and
   $H(x, \\xi)$, where $\\xi$ is a random variable from a certain distribution
   $\\mathcal{D}$. In this case, you can explicitly state in Algorithm 1 that you
   sample, e.g., $\\tilde{\\xi}\_t, \\bar{\\xi}\_{t + 1/2} \\sim \\mathcal{D}$, and then
   compute $\\tilde{g}\_t \= g(\\tilde{X}\_t, \\tilde{\\xi}\_t)$, $\\tilde{H}\_t \=
   H(\\tilde{X}\_t, \\tilde{\\xi}\_t)$ and $\\bar{g}\_{t + 1/2} \= g(\\bar{X}\_{t + 1/2},
   \\bar{\\xi}\_{t + 1/2})$.

2. I do not see the purpose of presenting the "implicit algorithm". To me, it
   looks rather confusing. Furthermore, as far as I understand, it is completely
   identical to Algorithm 1 (considering the deterministic oracle). If this is
   indeed the case, then what is the need for introducing such redundancy in the
   paper (1 extra page in the main part, and 6 extra pages in the supplementary
   material)? In my opinion, Algorithm 1 is sufficiently simple in itself.
   Therefore, I would suggest to completely remove the "implicit algorithm" (and
   its convergence analysis), and use the free space to better describe
   Algorithm 1 and its convergence analysis. To make the method easier to
   understand, instead of splitting it into "implicit" and "explicit" versions,
   it might be reasonable to first discuss the deterministic case and then
   quickly describe what becomes different in the stochastic case.

3. I suggest incorporating the updates of $\\tilde{x}\_t$, $\\bar{x}\_{t + 1 / 2}$,
   $\\gamma\_t$ and $B\_t$ directly into Algorithm 1 to make it easier to
   understand. Otherwise, it is not clear that there are no cyclic dependencies
   in the definitions.

4. Algorithm 1, line 2: It would be better to add some comments about the
   complexity of this step, as this is no longer the standard Euclidean
   projection. For example, in the important case, when the set $\\mathcal{X}$ is
   a Euclidean ball, this step can be efficiently computed using a tridiagonal
   factorization of the Hessian; the complexity is then similar to that of the
   standard Cubic Newton step. Another interesting case is when $H(\\tilde{X}\_t)$
   has low-rank structure.

5. Eq. (8): Why is there "$1 + \\ldots $"? Can we have there any other constant
   instead of $1$? The problem with $1$ is that it is a "wrong" constant, as it
   does not correctly interact with the squared gradient terms (they have
   different physical dimensions). More precisely, in its current form, eq. (8)
   makes Algorithm 1 not scale-invariant. Indeed, if we multiply the objective
   function by some positive constant $\\tau > 0$, then all the gradients and
   Hessians will also be multiplied by $\\tau$, but $\\gamma\_t$ will not be
   divided by $\\tau$, and therefore the method will construct a completely
   different trajectory $x\_{t + 1 / 2}$ (although the problem did not really
   change). Note that we would not have this issue if there was, e.g., "$0 +
   \\ldots$".

6. Theorem 3.2: There are some typos in the formulas. In any case, I suggest
   presenting the complete 3-term guarantee which appears between lines 769 and 770.
   It would be good to emphasize that the first- and second-order noise
   terms decrease at different rates.

7. Why do we take $b\_t \= t^3$ in Theorem 3.2? If I understand correctly, a
   simpler choice $b\_t \= t^2$ also works.

8. Theorem 3.3 and Proposition 3.1: As far as I understand, we do not need the
   part "non-decreasing weights $a\_t$ and $b\_t$ such that $a\_t, b\_t \\geq 1$".

9. Why do we not choose explicitly $a\_t \= (B\_t / b\_t)^2$? As far as I
   understand, this is exactly what is needed in the proofs (plus the fact that
   $a\_t / b\_t$ is decreasing, which can be easily ensured by taking $b\_t \= t^p$
   with $p \\geq 2$).

10. Experiments: 1) What $f$ and $\\mathcal{X}$ do you use in the experiments?
   Please specify them using formulas. 2) Please clarify whether the methods use
   the stochastic oracle (and which), or not. 3) What is the point in doing
   regression and classification on the same data set (a1a)? 4) Why does Newton
   method not convergence in one iteration in Figure 1a)? Is it not a quadratic
   problem? 5) It is surprising that ExtraNewton exhibits superlinear
   convergence, as it is not common for accelerated second-order methods to
   possess such a property (e.g., Accelerated Cubic Newton does not have
   superlinear convergence). Do you have any explanation for this? 6) It might
   be reasonable to add Cubic Newton and its accelerated variant to your
   comparison.

Minor remarks:

1. The convergence rate of the new method should be $L D^3 / T^3$, not $L D^2 /
   T^3$. There are multiple such typos throughout the paper, see, e.g., lines
   78, 247, 255, etc.

2. Line 78: Please clarify what the constant $L$ is.

3. Line 81: It is not exactly true that the method is oblivious to the diameter
   of the constraint set since the "correct" value of the parameter $\\gamma$
   depends on the diameter. Please clarify this. The same applies to the
   Abstract.

4. Lines 97--102: You should assume that you work either in an abstract
   $d$-dimensional Euclidean space $\\mathcal{V}$, or in $\\mathbb{R}^d$; there is
   no point in mixing them up by stating that $\\mathcal{V} \= \\mathbb{R}^d$.
   Further, since you work with a smooth function $f$, instead of "proper, lower
   semi-continuous, ..." and "Lipschitz continuous selection ...", you should
   simply assume that $f$ is twice differentiable (over some open set containing
   $\\mathcal{X}$). Finally, note that Assumption 2.1 is satisfied automatically
   since $\\mathcal{X}$ is a compact set.

5. Section 2: Please clarify that you use standard Euclidean and operator norms.

6. Eq. (Taylor): I suggest removing it.

7. Eq. (EG): There should be capital $X\_t$ and $X\_{t + 1/2}$.

8. Eq. (5): Some constants ($L$ and $D$) are missing.

9. Algorithm 1, line 2: The coefficient should be $\\frac{a\_t b\_t}{2 B\_t}$. Also,
   the definition of $B\_t$ is missing.

10. Eq. (8): I suggest denoting $\\| g(\\bar{X}\_{s + 1 / 2}) -
    \\tilde{F}(\\bar{X}\_{s + 1 / 2}; \\tilde{X}\_s) \\|$ somehow (e.g.,
    $\\tilde{\\Delta}\_s$), and then use $\\tilde{\\Delta}\_s$ everywhere instead of
    the long expression that appears in multiple places throughout the paper.

11. Theorem 3.2: The definition of $D$ is missing.

12. Theorem 3.3: There should be $\\bar{X}\_{T + 1 / 2}$ instead of $\\bar{X}\_T$.

13. Proposition 3.1: The parentheses are missing after the sum sign. Also, it
    might be reasonable to remove "Let $\\{ X\_{t + 1 / 2} \\}\_{t \= 1}^T$ be
    generated by Algorithm 1", or rephrase it.

14. Eq. (11): In the first line, there should be no "$2$" in the denominator.

15. Display between lines 617 and 618: Please simplify it, as everything
    trivially follows from the fact that $\\mathbb{E}[ g(\\bar{X}\_{t + 1 / 2}) |
    X\_{t + 1 / 2} ] \= \\nabla f(\\bar{X}\_{t + 1 / 2})$.

16. Lemma F.1: There should be $\\alpha\_T$ instead of $\\alpha\_t$. Also, one
    should additionally assume that $\\alpha\_1 > 0$.

17. Display between lines 732 and 733: Expectation sign is missing in the
    right-hand side.

18. Display between lines 735 and 736: It would be better to remove the negative
    signs and rewrite everything in terms of positive quantities (reversing the
    inequalities). Also, please specify what $c$ is.

19. Eq. (20): There should be $-\\delta\_t$ instead of $\\delta\_t$.

20. Display between lines 747 and 748: I suggest introducing some notation for
    $\\min\\{ \\| \\tilde{\\nabla}\_t \\|, \\| \\nabla\_t \\| \\}$ to avoid repeating the
    same long expression everywhere.

21. Display between lines 756 and 757: Please clarify why $\\sqrt{1 + \\sum\_{t \=
    1}^T a\_t^2 \\min \\ldots} \\leq \\gamma^{-1} \\sum\_{t \= 1}^T \\lambda\_{t + 1}
    a\_t^2 \\min \\ldots$.

22. Display between lines 759 and 760: Can we guarantee that $T\_0$ is always
    finite? If not, please add some comments about the case $T\_0 \= \\infty$.

23. Display between lines 769 and 770: Expectation sign is missing.
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose an accelerated second-order method interpolating between global convergence rate of $O(\sigma/\sqrt{T})$ and $O(1/T^3)$ for minimizing Hessian-smooth, convex functions with stochastic / deterministic oracles, while being oblivious to knowledge of problem parameters. This is achieved by (1) extra-gradient framework incorporating second-order information; (2) careful iterate and gradients averaging for the updates that keeps memory of past iterates; (3) an adaptive step-size scheme that can automatically adapts to noisy feedback and bypass any potentially complicated line-search procedure needed for estimating relevant problem-dependent parameters. Numerical experiments are also presented showing speedup and stability compared to alternatives. 
strengths_and_weaknesses: The paper is well-written and relevant work thoroughly surveyed. As a practical globally convergent second order method that is both universal and adaptive, it is of clear significance and relevance. In terms of the technical contribution, I find the construction of the policy for the adaptive step-size particularly interesting and similar ideas might find application in other second-order methods as well.
questions: Minor comments / typos: (1) it's a bit unclear what line 115 "the operator F satisfies eq (1)" means here; (2) after line 122 (EG): I assume you mean $x_t -> X_t, x_{t+1/2} -> X_{t+1/2}$? (3) Cubic-regularized Newton might be another nice addition to benchmark for the numerical section, considering it is also a second-order method that is both implementable and stable.
limitations: Yes.
review_title: null

Meta-review: metareview: A solid theoretical paper that proposes a second-order method of iteration complexity O(\sigma T^{-1/2} + T^{-3}) for minimizing Hessian-smooth convex functions. A notable feature of the proposed method is its ability to adapt to problem parameters.

The paper has generated considerable discussion between the reviewers and the authors which helped clarifying several major concerns. Please make sure to take into account the important reviewers' feedback, and criticisms, in the revised version.
confidence: Certain
Decision: Accept