We apologize for leaving some remarks unanswered. Please let us know if we missed any additional questions you had or if anything is not clear.
### About the CSQ Lower Bound
We attempted to make explicit throughout the paper that the lower bound only applies to CSQ algorithms (e.g. lines 6-7 in the abstract and lines 31-32, 52-53 in the introduction). Regarding the claims of optimality, learning single index models falls under the class of problems in which there is a conjectured statistical-computational gap. In particular, the information theoretic lower bound for learning a single index model is $n \gtrsim d$, independent of $k^\star$. However, it is widely believed that no computationally efficient algorithm can solve the problem given only $O(d)$ samples for complicated link functions. Similar problems that exhibit a computational-statistical gap are tensor PCA, community detection, sparse PCA, and planted clique [1,2,3,4].
None of these problems have rigorous lower bounds of the form: no polynomial time algorithm can solve this problem with fewer than $X$ samples. Such rigorous lower bounds are out of reach for current techniques. The strongest lower bounds for such problems generally use either the statistical query, low degree polynomial, or sum-of-squares framework to limit the class of learning algorithms so that a lower bound can be proven. However, it is widely believed that these statistical-computational gaps extend to all computationally efficient algorithms in the presence of mild label noise.
We will update the introduction to add a discussion of the conjectured computational-statistical gap and to emphasize that $d^{k^\star/2}$ is the conjectured statistical threshold for this problem among computationally efficient algorithms, although we only prove the lower bound for the class of CSQ algorithms.
[1] Feldman et al., 2012, Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
[2] Diakonikolas & Kane, 2017, Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures
[3] Goel et al., 2020, Statistical-Query Lower Bounds via Functional Gradients
[4] Dudeja & Hsu, 2020, Statistical Query Lower Bounds for Tensor PCA
### Tensor Notation
Our tensor notation is defined in Appendix A – explicitly, if $T$ is a $k$ tensor and $A$ is a $j$ tensor in $d$ dimensions with $j \le k$ then
$$
T[A] = \sum\_{i\_{k-j+1},\ldots,i\_k} T\_{i_1,\ldots,i\_k} A\_{i\_{k-j+1},\ldots,i\_k}
$$
This can also be interpreted as “flattening” $T$ into a $d^{k-j} \times d^j$ dimensional matrix, flattening $A$ into a $d^j$ dimensional vector, computing the matrix vector product, then “unflattening” the resulting $d^{k-j}$ dimensional vector into a $k-j$ tensor.
Due to space constraints we cannot add Appendix A to the main paper but we will add a sentence in Section 7 that provides a reference to Appendix A for our tensor notation.
### Additional Remarks
Due to the character limit our response overflowed into the next comment.