Exponential mixed-integer lower bound for general binary oracles

About 3 years old · traced to

Let nn be the number of integer variables, let dd be the continuous dimension, and let MM, RR, ρ\rho, and ε\varepsilon be the problem parameters. A first-order chart G\mathcal{G} determines a general binary oracle. Mixed-integer binary lower-bound conjecture. There exists a first-order chart G\mathcal{G} such that the general binary oracle based on G\mathcal{G} has information complexity

Ω(2n(1+d2log⁡(MRρε))).\Omega\left(2^n \Big(1+d^2\log\left(\frac{MR}{\rho\varepsilon}\right)\Big)\right).

The conjecture transfers the proposed quadratic continuous-case binary-oracle lower bound to mixed-integer convex optimization; the cited continuous-case results motivate it, but it remains open.

References

Primary source

Amitabh Basu, Hongyi Jiang, Phillip Kerger and Marco Molinaro, “Information Complexity of Mixed-integer Convex Optimization”, arXiv:2308.11153 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.