Transfer from full-information first-order to general binary oracles
Transfer from full-information first-order to general binary oracles
Let denote the worst-case information complexity of a query strategy under the full-information first-order oracle based on a first-order chart . Binary-oracle upper-bound transfer conjecture. If there exists such a query strategy with worst-case information complexity , then there exists a query strategy under the general binary oracle based on with worst-case information complexity bounded by
This would transfer upper bounds from full-information first-order oracles to general binary oracles. In particular, it could yield improved binary-oracle upper bounds if the full-information mixed-integer upper bound is improved.
Sources & referencesView supporting material
Primary source
Amitabh Basu, Hongyi Jiang, Phillip Kerger and Marco Molinaro, “Information Complexity of Mixed-integer Convex Optimization”, arXiv:2308.11153 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.