Q_main [partially_resolved] Consider a non-adaptive algorithm (query point w_t = sum_{j<t} alpha_j^{(t)} grad f(w_j; xi_j) with all coefficients fixed before the run) with access to a stochastic first-order oracle. Does this algorithm have to query sub-optimal iterates (compared to the minimax rates) infinitely often, i.e. in a limsup sense? | remains open: Prove or refute, for a stochastic first-order oracle, that every non-adaptive method whose query points are arbitrary fixed linear combinations of past stochastic gradients (not only SGD iterates under a stepsize schedule; e.g., momentum-type or averaged query points) must be off the dimension-free
Q_a [partially_resolved] Special case (a): Can we bridge the log T factor indicated as necessary by Harvey et al. (2018) for non-smooth stochastic convex optimization (Shamir and Zhang, 2012; Jain et al., 2019)? | remains open: Determine the exact power of log T that any anytime stepsize schedule for SGD's last iterate must lose (lower bound log^{1/8} T vs upper bound log T), and decide whether a non-adaptive method with non-SGD query points (arbitrary fixed linear combinations of past stochastic gradients) can attain the
Q_b [open] Special case (b): Can we bridge the gap of a condition number for SGD's final iterate for least squares (Ge et al., 2019) under conditions satisfied by a non-adaptive algorithm?
Q_c [partially_resolved] Special case (c): With regards to gradient norm (as opposed to function value), can we make progress towards understanding query point sub-optimality in various cases of stochastic convex optimization? | remains open: Establish anytime (unknown-horizon) lower or upper bounds on the gradient norm at the query points of non-adaptive methods under a stochastic first-order oracle with bounded variance (assumption (2)) - e.g., whether the known-horizon rates of Allen-Zhu (2018) can be matched anytime by any fixed-coef