Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes sparsifed online Newton method.

strength_and_weaknesses: Pros: It is easy to follow and the intuition of the algorithm is easy to understand.

Cons: Page 4, between Eq. 8 and Eq. 9, the optimality condition of Eq. 7 is not the gradient equal to zero because Eq. 7 is a constrained optimization problem. Thus, the derivation of Eq. 9 may be problematic.

This paper only considers the third term of Eq.3. This may be not enough because $X_t ^{-1}-X_{t-1}^{-1} $ which makes the regret large.

clarity,_quality,_novelty_and_reproducibility: This paper is easy to follow but seems lacking novelty.
summary_of_the_review: This paper proposes sparsifed online Newton method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes SONew, an online convex optimizer derived by combining the regret minimization based on the LogDet divergence measure and structured sparsity in the preconditioning matrix. The preconditioning matrix of the SONew is a shape of either diagonal, tri-diagonal, or banded and is calculated in linear flops and numerically stable ways, making it compatible with large deep neural networks. On the MNIST autoencoder training task, SONew achieved better convergence than the existing first-order adaptive gradient method. Furthermore, SONew shows better numerical stability than other methods, including the Shampoo optimizer, when training with bfloat16.

strength_and_weaknesses: Strengths
- This paper is clearly written.
- This paper highlights an interesting connection between the regret minimization in OCO and LogDet divergence of the preconditioning matrix, giving a novel insight into the online gradient descent and online Newton method.
- By taking advantage of structural sparsity in the preconditioning matrix, the proposed SONew method gives a way to solve the LogDet divergence subproblem fast enough (enough to be applied every step during training). It seems practical even with a large DNN model. 
- Also, thanks to the flexibility of the sparse structure in SONew, the form of the preconditioning matrix (diag, tri-diag, banded) can be determined according to the computational budget, and a straightforward trade-off between convergence speed and computation time is observed in the auto-encoder training experiments in MNIST.

Although SONew is based on solid mathematical intuition and the experimental results show good convergence and numerical stability, the empirical results are not strong enough to support SONew’s effectiveness as a ‘deep learning optimizer’, as described below.

Weaknesses
- Comparisons at different mini-batch sizes have not been made.
    - In mini-batch training, g_t in Equation 5 corresponds to the mini-batch gradient, and X_t^{-1} is known as the (mini-batch) empirical Fisher. It has been pointed out that the mini-batch empirical Fisher loses valuable second-order information for optimization as the mini-batch size increases (Equation 4 in https://www.cs.toronto.edu/~rgrosse/courses/csc2541_2022/readings/L05_normalization.pdf).
    - Therefore, comparisons with different (larger or smaller) mini-batch sizes are desirable, as differences in mini-batch size are expected to affect the convergence of SONew (and the optimization methods being compared). In particular, since large batches are desirable for large-scale training that takes advantage of data parallelism and distributed accelerators (e.g., https://arxiv.org/abs/1802.09941), how well SONew maintains convergence in large-batch training is useful information for practical (esp. large-scale) uses.
- Comparison of numerical stability needs improvement.
    - The numerical stability of the eigenvalue decomposition required by Shampoo depends largely on the condition number of the matrix, which can be significantly improved by the damping value to be added to the diagonal of the matrix. For example, in the experimental code of Anil et al. (2020) (https://arxiv.org/abs/2002.09018), the default value of damping is set to 1e-4 (https://github.com/jettify/pytorch-optimizer/blob/master/torch_optimizer/shampoo.py#L50) to improve the numerical stability. Similarly, large damping values are often used in K-FAC in practice (e.g., 1e-3 in https://github.com/gpauloski/kfac-pytorch/blob/main/kfac/preconditioner.py#L57). Therefore, it is desirable to use Shampoo with a large damping value as a baseline result in the bfloat16 setting.
    - K-FAC can also be implemented using Cholesky decomposition. In addition, there are second-order optimization methods that can take advantage of the low-rank nature of matrices and avoid explicit inverse matrix and eigenvalue decomposition calculations (e.g., SKFAC https://openaccess.thecvf.com/content/CVPR2021/papers/Tang_SKFAC_Training_Neural_Networks_With_Faster_Kronecker-Factored_Approximate_Curvature_CVPR_2021_paper.pdf, SENG https://link.springer.com/article/10.1007/s10915-022-01911-x). Since these methods can be expected to have more robust numerical stability in low-precision training, using only Shampoo (which is less numerically stable) as a baseline for low-precision second-order optimization seems inappropriate for evaluating the relative numerical stability of SONew. 
- It is unclear whether SONew is effective as a ‘deep learning optimizer’.
    - From the derivation, SONew is an online 'convex' optimizer. However, since the loss function in deep learning is nonconvex, it is unclear how effective regret minimization achieved by SONew is in minimizing loss. Since the MNIST autoencoder training is a very simple task by today's deep learning standards, training results in a larger, more realistic setting (e.g., training CNNs on ImageNet classification, Transformers on language tasks with cross-entropy loss) would be desirable.
    - Although only training loss is shown in the experiment, I believe that the evaluation of generalization performance is necessary to measure the performance of SONew as a deep learning optimizer. For example, not only the training convergence speed of the optimizer but also its compatibility with regularization, such as weight decay, is an essential subject of discussion (e.g., Adam vs. AdamW https://arxiv.org/abs/1711.05101).

Questions
- Why is there no result for “band-4” with bfloat16 in Figure1 and Table2?
- What are the damping values (espsilon) used for SONew, Shampoo, and other adaptive gradient methods?

clarity,_quality,_novelty_and_reproducibility: This paper clearly describes the proposed method's background, motivation, derivation, and significance. It provides a novel combination of LogDet divergence measure and structured sparsity in preconditioning matrix in online convex optimization settings. The quality of the empirical experiments needs to be improved to assess whether SONew is effective in more realistic deep-learning tasks than a simple autoencoder training task.

summary_of_the_review: This work proposes a compute- and memory-efficient online convex optimizer for deep neural networks based on solid mathematical insight. However, it is not clear from the given experimental results and theoretical justification alone that the proposed method is helpful in “Learning Representation.” I think more empirical results and discussion of non-convex optimization/generalization would improve the quality of this research, but it is currently the under the bar of acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposed SONew (Sparsified Online Newton), which is an efficient variant of online Newton step (ONS) by using $b$-banded sparsity graph. The time complexity of this method is $O(b^3 n)$, and the regret bound is $O(T^{3/4})$. The authors provide some simple experiments to verify the performance of the proposed method.
strength_and_weaknesses: #Strength
1) The authors proposed a new efficient variant of online Newton step (ONS) by using $b$-banded sparsity graph.
2) The proposed algorithm improves the time complexity of ONS from $O(n^2)$ to $O(b^3 n)$.

#Weaknesses
1) The authors only established a regret bound of $O(T^{3/4})$ for their method, which is far worse than the $O(\sqrt{T})$ regret bound of many existing first-order methods such as online gradient descent. Note that these first-order methods are more efficient than the proposed algorithm for $b>1$.
2) The experiments presented in this paper is too simple, which is not sufficient to verify the advantage of the proposed method. The authors at least consider some other datasets such as CIFAR10 and CIFAR100. Moreover, the authors should also consider other deep neural networks such as convolutional neural networks (CNNs).
3) In the experiments, some tricks including momentum and grafting are added to the proposed method, which may affect the evaluation of the proposed method.
4) There actually exist efficient variants of ONS [1][2], which enjoy the time complexity of $O(\tau n)$ for very small $\tau$. However, the authors do not discuss and compare the proposed method with them.

[1] Haipeng Luo et al. Efficient Second Order Online Learning via Sketching. In NeurIPS 2016.

[2] Luo Luo et al. Robust Frequent Directions with Application in Online Learning. In JMLR 2019.

clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to follow. However, the authors missed some very related work [1] [2]. Moreover, although the use of $b$-banded sparsity graph to accelerate ONS is new to me, I am not convinced that it is better than existing efficient variants of ONS.

[1] Haipeng Luo et al. Efficient Second Order Online Learning via Sketching. In NeurIPS 2016.

[2] Luo Luo et al. Robust Frequent Directions with Application in Online Learning. In JMLR 2019.

summary_of_the_review: By considering the $O(T^{3/4})$ regret bound of the proposed method and the existing efficient variants of ONS, I tend to reject this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This manuscript proposed SONew (Sparsified Online Newton), an online convex optimizer derived by combining the regret minimization based on the LogDet divergence measure and structured sparsity in the preconditioning matrix. The preconditioning matrix of the SONew is a shape of either diagonal, tri-diagonal, or banded, which is an efficient variant of online Newton step (ONS) by using b-banded sparsity graph. On the MNIST autoencoder training task, SONew achieved better convergence than the existing first-order adaptive gradient method. Furthermore, SONew shows better numerical stability than other methods, including the Shampoo optimizer, when training with bfloat16. Main concerns of reviewers are about: 1) theoretical justification of the algorithm may have some issues, e.g. in regret bound; 2) experimental evaluation is insufficient, especially comparisons with relevant literature etc. All reviewers unanimously agree the current version of the manuscript is not ready for publication, so is the decision.   

justification_for_why_not_higher_score: All reviewers unanimously agree the current version of the manuscript is not ready for publication (below the accept line), so is the decision.
Decision: Reject