1. **Your claim that using Eq.8 and standard methods for reducing runtime when computing multiple partial sums, the runtime reduction is not surprising**
Your opinion on runtime reduction not being surprising is based on the assumption that you already have access to Eq.8.
However, before our submission, no one knows we could possibly write the 2nd-order partial derivatives in such a way.
Eq.8 is unique to the Cox model (Eq.8) and does not hold for a generic loss function.
**Since Eq.8 is not something already known/established, it's not possible to conclude our work ''is not surprising'' considering only what follows it**.
As mentioned before, the previous approaches rely on $\boldsymbol{\eta}^T \nabla_{\boldsymbol{\eta}} \ell(\boldsymbol{\eta}) \boldsymbol{\eta}$.
This is why we can reduce the complexity from $O(n^2)$ to $O(n)$ and why we say the runtime reduction is surprising.
2. **What is the benefit of our preprocessing?**
We do not perform this for the sake of creating a challenging dataset.
It does have a potential benefit for producing better models.
Due to the character limit, please see another post where we support this claim through experiments.
The origin of our preprocessing can be traced back to additive models in statistics (see Line 27, 257-258, and 280, with citations [1, 11, 27, 28, 49, 67]).
Additive models have been extensively used to capture nonlinear relationships between the target and continuous variables.
For example, on the ICU patients, death risks may not increase linearly w.r.t age, a continuous variable; the risk for older patients may increase at a much higher rate.
Using the original continuous variable would fail to capture this relationship.
Lastly, additive models can be created by other preprocessing procedures, such as splines and polynomials (see [27, 28, 67]).
However, no matter which procedure we use, the preprocessed features are likely much more correlated than the original ones.
As shown in Section 4.2 (variable selection), our method can handle highly correlated features much better than existing methods.
3. **Minimizing a cubic by finding the roots of a quadratic equation still does not constitute significant mathematical novelty**
We try to minimize the following cubic surrogate function:
$$h_x(\Delta x):= f(x) + f'(x) \Delta x + \frac{1}{2} f''(x) \Delta x^2 + \frac{1}{6} L_3 \vert \Delta x \vert^3.$$
Your opinion on our method not constituting significant mathematical novelty is based on the assumption that *$h_x(\Delta x)$ already exists*.
Specifically, you assume that $f'(x)$, $f''(x)$, and $L_3$ have already been given to you.
However, this is not the case, due to two things mentioned in our initial rebuttal:
a) $f''(x)$can be computed in $O(n)$ time. Previously, the best way takes $O(n^2)$. *If you compute $f''(x)$ in the old-fashioned way, it takes much longer to formulate $h_x(\Delta x)$*.
b) Previously, it is unknown, regarding the Cox model, whether $L_3$ (Lipschitz constant for $f''(x)$) exists and, if so, whether there exists an explicit way to compute $L_3$. In our work, we answer both questions positively, through Eq.9 and Eq.14. *Without our work, you cannot even compute $L_3$ and thus formulate $h_x(\Delta x)$, let alone minimize it*.
Moreover, *obtaining Eq.9 and Eq.14 are nontrivial mathematical tasks*.
No one has expected these nice structures (probabilistic formula for the 3rd-order partial derivatives and its connection to the 3rd-order central moment calculation) could pop up out of the Cox model.
Lastly, there are subjective opinions and objective facts.
Regarding subjective opinions, we accept that different researchers can have different research tastes on novelty.
However, objectively, the fact is that no one has written Eq.18, the analytical minimizer to $h_x(\Delta x)$. If you think they have, please point us to the literature where they publish this equation.
4. **Even with the addition of L1 regularization, this is reasonably behaved one-dimensional optimization problem which should not pose much challenge for standard approaches**
Our reasoning above also applies here.
*Without our work, you cannot even formulate this L1-regularized cubic surrogate function, let alone minimize it.*
Previous researchers didn't know that the cubic surrogate function could be useful to solving the L1-regularized problem.
All they had are the quasi and proximal Newton methods.
Again, we make a contribution here because Eq.22 has never been presented.
Moreover, our Eq.22 is one step further beyond the traditional soft-thresholding operator (well known as solving the L1-regularized problem with the quadratic surrogate function).
Our work opens the door to solving the L1-regularized problem with the cubic surrogate function.