13 problems

Extension conjecture. Theorem and Corollary remain valid (in substance) even under local oracles.

Let $P_{\mathcal{M}}$ range over stationary distributions with entropy $H$, and let $N$ be the number of queries. LAWS acquisition lower bound. No online inference caching algorith…

Let $p\geq 2$, and consider the class of $p$th-order algorithms for convex-concave minimax optimization defined in the paper. For the constructed hard instance, the paper proves an…

Let $N$ be the signal length, and let $m_1$, $m_2$, and $m_3$ be pairwise coprime moduli satisfying $m_1,m_2,m_3=Theta(\sqrt{N})$. For a $k$-sparse signal, apply 3-view CRT gating…

Optimality conjecture. By analogy with existing lower bounds, the optimization terms in the convex and strongly convex guarantees are the best unaccelerated rates one could hope fo…

Let $M$ clients play a multi-armed bandit for $T$ time slots. For client $m$, let $k'_{*,m}$ denote its optimal arm, let $X'_{k,m}$ denote the reward distribution of arm $k$ for cl…

Let $M$ be the number of machines, and consider the lower bound for the optimization error in the massively parallel regime described above. Logarithmic-factor conjecture. We conje…

Let $K>0$. Consider a method whose iterates have the form … where $\boldsymbol{x}_0\in\mathbb{R}^d$ is the initial point, $f$ is a convex function accessed through a gradient oracl…

Non-tightness conjecture. For $cmu>0$, the best bound attainable by Theorem for the absolute inaccuracy performance measure is not tight, and a more refined approach is required to…

Lower-bound extension conjecture. The lower bound can be extended to hold without the assumption that $s_{\mu,\epsilon}$ grows slower than $1/\epsilon^p$ for some $p<1$.

Let NAG denote Nesterov's accelerated gradient method in the stochastic optimization setting considered above. Lower-bound conjecture for NAG. A lower bound for NAG can be establis…

Hierarchical-counter lower-bound conjecture. There is no space-optimal hierarchical counter over $\mathbb{Z}_{m_1}\times \mathbb{Z}_{m_2}\times \mathbb{Z}_{m_3}$ unless $m_2$ and…

Constructed-family determinantal lower-bound conjecture. If $a>0$ is small enough, then, with high probability, $f_n$ cannot be expressed as a symbolic determinant of size at most…