Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose to use second order method only on the loss function -- not throughout the whole network in the training process.
They are also putting a L2 term in the formulation.
strength_and_weaknesses: I don't see a strength in the formulation. Personally I have tried this method without introducing the L2 term and my finding is not quite satisfactory. Generally speaking when the Newton's method is only applied on the loss function it is a pretty weak method. Another way to think about it is if the loss function is a pure L2 loss, say for regression, then first order and second order methods are the same.

Also, if the authors are formulating the problem in a usable way, the L2 term should not be necessary. The second order information of the loss should be the only necessary thing to improve the training.

Lacking larger scale comparison is also a main problem with the paper. It is hard to say a piece of work is useful without scaling to imagenet-like datasets.

clarity,_quality,_novelty_and_reproducibility: Clarity is fair. Novelty is below the ICLR standard.
summary_of_the_review: Based on the limited novelty I vote for rejection.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes to formulate some algorithmic losses (e.g. sorting) as bi-level optimization problems and solve the inner problem with second-order optimization. It reports performance gains over regular optimization
strength_and_weaknesses: Strengths:
* The performance improvements are consistent across the experiments.

Weaknesses:
* I find it extremely hard to understand what the contribution of the paper is supposed to be. Is it simply to use second order optimization on the the inner loss in bi-level optimization? Is it formulating some algorithmic losses as bi-level optimization problems? I also don't understand why the introduction opens up with a discussion of second-order optimization for neural networks, this does not seem relevant at all to what (I think) the paper is doing.
* Related, I found it difficult to read the paper. The paper seems relatively practical to me, so I don't quite understand the choice to opt for a formal/mathematical style (Definition, Lemma, Theorem, Remark). Section 2 in particular seemed extremely verbose to me, while section 4 is lacking a lot of detail (without giving the reader a strong sense for what is going on in terms of the big picture).
* The positioning is similarly opaque to me. While the related work cites a bunch of papers, I did not find a clear statement as to what gap in the literature the paper is trying to close and where it is improving over prior works.

Minor comments:
* Based on the title, I would have expected the paper to propose a method that includes second order information in the objective of general objective functions (similar to e.g. sharpness-aware minimization). I would suggest altering the title to make it more descriptive of the contents.
* Inlining Tabs 2 & 3 makes reading the corresponding sections unnecessarily difficult.
clarity,_quality,_novelty_and_reproducibility: **Clarity** I found it extremely difficult to follow the paper and it is not clear to me where the line between background and newly introduced material is.

**Quality** Difficult to judge due to the lack of clarity.

**Novelty** See quality.
summary_of_the_review: The contribution of the paper is not clear to me, so I'm arguing for rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces an approach to efficiently computing updates that incorporate second-order information. The idea is to decompose the update into two parts: a second-order update of the loss function, and a first-order update of the model. Notably, this avoids having to compute the hessian wrt the model parameters, which would be expensive for complex models like neural networks. It's shown that the two-step scheme can be equivalent to gradient descent and to the newton step algorithm for certain choices of the updates. The approach is tested empirically on algorithmic supervision tasks.
strength_and_weaknesses: **Strengths** Breaking the update into an update wrt the loss function and an update wrt the model seems like an interesting and practical way to incorporate second-order information without computing the hessian wrt the model.

**Weaknesses** The main weakness is that the math felt very imprecise to me throughout. For instance, throughout the paper argmin's are computed by arguing that the gradient is 0 at the argmin, but this isn't necessarily true since that point might have been outside of the domain. Similarly, there's often an implicit assumption that the model's range covers the entire domain, since this is how we get equivalence of $f(x;\theta)=z^*\in\text{argmin}_z\ell(z)+\Omega(z,f(x;\theta))$, which is used in the proof of Lemma 1 showing that the iterative and two-step method converge to the same points. This is not necessarily true without additional assumptions on the model class.

Section 4 cataloguing various algorithmic supervision losses seemed mostly unnecessary and would potentially work better as an appendix
clarity,_quality,_novelty_and_reproducibility: I generally found the clarity low throughout, though this could be in-part due to my unfamiliarity with some of the problem settings. For instance, I've read the introduction to the experiments section several times and still have no idea what an "algorithmic supervision" task is. 

The main source of confusion was the math though; much of the math very hand-wavy and imprecise to me, as mentioned above. 

The approach seems somewhat novel, and the experimental results suggest that the newton loss can sometimes lead to strong performance improvements over using the regular loss function. 

The empirical results serve mostly as a sanity check and don't seem to reveal any new insights in their own right. As far as reproducibility is concerned, I'm not confident I could reproduce these results unless a code release is planned.
summary_of_the_review: The approach seems interesting and reasonably motivated, but I am not confident that the math actually checks out and would be hesitant to recommend acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose Newton losses, which breaks the loss optimization into two stages. The latent variable $z$ behaves as a target for the model output and is formed using a Newton step on the loss wrt the activations. The parameters are then optimized to match the target by minimizing a squared loss. The authors provide examples of different losses and validate the results experimentally.

strength_and_weaknesses: ### Strengths:  
* The motivation for the approach is clear.

### Weaknesses:  
* The authors have missed important previous work that introduces such techniques. Namely, lifted networks [1] propose a two-stage optimization scheme by introducing latent variables and matching the output of each later with the latent variables. More importantly, LocoProp [2] introduced the idea of setting layerwise targets and iteratively minimizing layerwise losses to match the targets. The method proposed in this paper is a special case of LocoProp where 1) only a single target is formed for the last layer via a Newton step (this was already discussed in LocoProp in terms of a natural gradient descent (NGD) targets, and the authors show that the final update wrt to the parameters corresponds to NGD), 2) the loss is set to be the squared loss whereas LocoProp uses more advanced Bregman divergences, 3) the model parameters are updated using a single step whereas, in LocoProp, the authors try multiple steps on the fixed point problem and show that the final update on the parameters corresponds to a preconditioned update.

[1] Miguel Carreira-Perpinan, and Weiran Wang. "Distributed optimization of deeply nested systems." In Artificial Intelligence and Statistics, pp. 10-19. PMLR, 2014.  
[2] Ehsan Amid, Rohan Anil, and Manfred Warmuth. "Locoprop: Enhancing Backprop via local loss optimization." In International Conference on Artificial Intelligence and Statistics, pp. 9626-9642. PMLR, 2022.

clarity,_quality,_novelty_and_reproducibility: There are a few unclear definitions and notations:
1) In Eq. (4), $\Omega$ is used to denote the regularizer both for the model parameters and outputs. This is confusing since these two are of different natures.
2) Page 4: what does element-wise Hessian mean? Does that mean diagonal approximation?
3) I could not find the definition of $\hat{y}$. Also, when defining expectations, please be more clear about what the expectation is wrt. For instance, Remark 1: the empirical Fisher should be an expectation wrt the training labels.
summary_of_the_review: The authors need to distinguish their work from lifted networks and LocoProp. Currently, their proposed method is a special case of LocoProp on the final layer with a single local iteration.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Overall, this paper has significant technical issues: Lemma 1 and the corresponding proof are wrong. The proof of $A\subset B$ is almost like saying "obvious we are right" without any analysis. In fact, unless much stronger assumptions are provided, the set $B$ can easily be empty if the minimizer of $\ell$ and $\ell\circ f$ does not match each other. 

One can consider a trivial problem where $f (x; \theta) = \theta^2$，$\ell(z) = z$, $\Omega (\theta, \theta') = 0.5\|\theta-\theta'\|^2$, $\Omega(z,z') = 0.5\|z-z'\|^2$. Suppose we only have 1 data $x$ and the output is $\theta^2$ is a scalar. Then the problem will be   $min_\theta \theta^2   ==> \theta*=0$. Now consider the set $A$:  $\theta/3 = (argmin_{\theta'} \|\theta'\|^2 + 0.5\|\theta-\theta'\|^2) = \theta$ ==> $A = 0 $ is the correct set.  However, the set $B$ is always empty. That is, $(argmin_z  z + 0.5\|z-\theta^2\|^2) = \theta^2 - 1$.  Therefore, $\theta^2 = f (x; \theta) = (argmin_z  z + 0.5\|z-\theta^2\|^2) = \theta^2-1$ will never hold. $B = \emptyset$.

If one thinks this example is too trivial, let us consider a simple regression problem $f (x; \theta) = x'\theta$. And let the loss be a simple MSE loss, with observation $Y$ encoded in the loss function:  $\min_\theta \|\|X\theta - Y\|\|^2$. Now suppose the observation has noise so that the optimal training loss is NOT 0, which is common. Then the set $B$ will be $argmin_z \|z - Y\|^2 + 0.5\|z-X\theta\|^2 = 2Y/3 + X\theta/3$. By requirement of B, we need $2Y/3 + X\theta/3 = f (X; \theta) = X\theta ==> Y = X\theta$. This is impossible since the optimal training loss > 0 in the noisy setting. 

Overall, unless extra assumptions on the losses function and the dataset itself are made, this key lemma of the paper is not correct.

justification_for_why_not_higher_score: Theoretically wrong analysis.
Decision: Reject