OP1 [resolved] Open Problem 1: Are there competitive regret bounds for any of the priming methods? (Sec. 2 rules: (1) p_i = 1-dim LLS per feature, (2) p_i = Pearson correlation, (3) p = w_LLS = X^+ y, each followed by a second LLS on X diag(p), w_p = diag(p)(X diag(p))^+ y; also the primepower variant p = sign(p).*|p|^primepower; Sec. 3 variant with ridge regression as the second stage.) | remains open: Close the gap between Omega(min{T, sqrt d}) and O(min{T, d}) for multivariate-LLS and Pearson priming, characterize regret of the priming rules on non-realizable (noisy) sequences, and test whether regularized or iterative prime estimation escapes the Omega(sqrt d) barrier; the Xu et al. result is a
OP2 [open] Open Problem 2: What is the optimal priming function for sparse linear problems?
OP3 [open] Open Problem 3: Are there priming methods for learning sparse disjunctions (k out of n disjunctions, cf. Winnow's O(k log n) mistake bound)?
OP4 [open] Open Problem 4: Can kernels be primed efficiently? (Approximately prime in feature space and then compute the weights with the primed kernel, for LLS/Ridge Regression.)
OP5 [open] Open Problem 5: For which other losses can the expert algorithm be spindlified? (Randomized Weighted Majority/Hedge has been spindlified with O(log n) regret in Amid & Warmuth 2020b; for expected log loss, i.e. Bayes rule, it is not possible.)
OP6 [open] Open Problem 6: What does spindly converge to? Does it have a closed-form solution? (Specifically lim_{eta -> infinity} argmin_u (1/eta)||u||^2 + (X diag(u) u - y)^2 for the u*u spindly network in the noise-free case.)