Finally, note that once the pseudoinverse of the sample covariance matrix is computed, pointwise evaluation of the non-linear estimator (REF ) can be done in \(O(d^{2})\)  operations. In contrast, only \(O(d)\)  operations are needed to evaluate a linear function. It is unknown whether a more computationally efficient algorithm that matches the upper bounds (REF ) and (REF ) exists and, more broadly, whether there exist inherent statistical-computational trade-offs needed to attain the optimal rate in the distribution-free setting. The search for computationally efficient improper algorithms in a related phenomenon observed for logistic regression (cf. Section REF ) is currently an active line of research [1]}, [2]}, [3]}.
