Open Problems

I plan to maintain a list of open problems that arise from my work. In the following, I present the best-known upper bound (UB) and lower bound (LB) to show the gap for future work. Please do not hesitate to contact me if you have any thoughts on closing the gap.

1. Second-Order Optimization (and with $m$-Delayed Hessians) [COLT 2026]
   Convex. UB: $\tilde{\mathcal{O}}(m^{5/7} \epsilon^{-2/7})$ LB: $\Omega(\epsilon^{-2/7})$ Gap: $m^{5/7}$
   Nonconvex. UB: $\mathcal{O}(m^{1/3} \epsilon^{-3/2})$ LB: $\Omega(\epsilon^{-3/2})$ Gap: $m^{1/3}$
2. Second-Order Min-Max Optimization (and with $m$-Delayed Hessians) [COLT 2025]
   UB: $\tilde{\mathcal{O}}(m^{5/7} \epsilon^{-4/7})$ LB: $\Omega(\epsilon^{-2/5})$ Gap: $m^{5/7} \epsilon^{-6/35}$
3. Fully First-Order Bilevel Optimization [JMLR 2025]
   Deterministic. UB: $\tilde{\mathcal{O}}(\kappa^{7/2} \epsilon^{-6})$ LB: $\Omega(\kappa^2 \epsilon^{-2})$ Gap: $\kappa^{3/2}$
   Stochastic. UB: $\tilde{\mathcal{O}}(\kappa^{11} \epsilon^{-6})$ LB: $\Omega(\kappa^4 \epsilon^{-4})$ Gap: $\kappa^7 \epsilon^{-2}$
4. Monotone Variational Inequality (and with $m$-Delayed Jacobian) [ICLR 2025]
   UB: $\mathcal{O}(m^{2/3} \epsilon^{-2/3})$ LB: $\Omega(\epsilon^{-2/5})$ Gap: $m^{2/3} \epsilon^{-2/15}$.