103 problems

In the fictitious-play setting, let $A\in\mathbb{R}^{n\times n}$ be the identity matrix, and consider the convergence rate measured by the relevant gap function. Karlin's conjectur…

Higher-moment rate conjecture. The rate $O(\sqrt{\eta_n})$ can be improved by assuming that $\xi^i_k$ has a high-order moment.

For minimizing convex quadratics with gradient descent using stepsize schedules, the silver convergence rate is $O(1/n^{\log_2 (1+\sqrt{2})})$. Silver-rate optimality conjecture. T…

Let $(\rho_\delta,c_\delta)$ and $(\rho,c)$ be the solutions in Theorem 1.1, and suppose the convergence estimate … holds for every $\lambda>0$ and sufficiently small $\delta>0$. O…

Fixed-step-size convergence conjecture. The algorithm should converge with rate

Let $F$ be an unknown distribution function on ${\mathbb R}^d$, with observations from the multivariate in-out interval-censoring model, and let $\hat{F}_n(\underline{t}_0)$ denote…

Let $K$ be prefix Kolmogorov complexity, let $\boldsymbol{\vartheta}_0$ be the true parameter, and let $\Delta(k)$ denote the complexity difference used in the MDL setup. Strengthe…

Let $Y_n$ be the normalized number of comparisons used by Quicksort on $n$ items, and let $Y$ be its limiting random variable. Write $d_{\text{KS}}$ for the Kolmogorov–Smirnov dist…

Inflection-point conjecture. The convergence performance of NIDS should also have an inflection point.

Iteration-complexity conjecture. The $\kappa$-dependence of the iteration complexity for overparameterized DMD may be improved to $\mathcal{O}(\kappa)$ under the separated spectrum…

Let $H_x$ be the distribution function associated with the predictor value $x\in\mathcal{X}$, and suppose that $H_x$ is continuous for every $x$. Let $m$ satisfy the generalized Li…

Let $r_\text{conv}(s)$ denote the convergence rate as a function of the packet size $s$, and let $r_\text{conv}(r_\text{drop})$ denote the convergence rate as a function of the pac…

Let a Newton scheme use weak iterates, and consider its convergence rate under the setting described for the local-rate result. Unattainability conjecture. Superlinear rates are ge…

Conjecture 3. As $N,M\to\infty$,

Conjecture 2. As $N,M\to\infty$,

Maximum-eigenvalue slowdown conjecture. For more general data distributions, a weaker version of this theorem holds, perhaps only for the maximum eigenvalue of

General-distribution conjecture. Similar results hold for other data distributions.

Output-space rate conjecture. The tight rate for $\Delta_k^y$ should be

For a graph with fixed boundary values, consider the $\ell^p$-energy minimizing dynamics and let the $\epsilon$-approximation time denote the time required to reach $\epsilon$-appr…

In the convex composite problem with closed proper convex functions $f,g$, suppose the Douglas–Rachford operator has a fixed point $w^\star$ and $f$ is $L$-smooth. Let $\rho$ denot…

Consider the convex composite problem … where $f$ and $g$ are closed proper convex functions. Assume that the Douglas–Rachford operator has a fixed point $w^\star$, that $f$ is $L$…

Let $A$ and $B$ be operators satisfying the paper's standing Assumption, let $B$ be $\beta$-cocoercive, and let $A=\partial g$ for a closed proper convex function $g$. Let…

Let $\hat{\theta}_{\mathrm{KMMR}}$ and $\hat{\theta}_{\mathrm{KRAS}}$ denote the KMMR and KRAS estimators, respectively, and let $R_n$ denote the remainder term in the associated e…

Consider the Davis–Yin splitting method and the ergodic primal–dual gap bound established in Theorem \mathrm{dys\text{-}gf\text{-}conv), whose rate is…

Conjectured exact finite-iteration behavior. If $\mu_2<0<\mu_1<L_2$, so that $F$ is nonconvex-nonconcave, then