@article{basu2025information,
author = {Basu, A. and Jiang, Hongyi and Kerger, Phillip A. and Molinaro, Marco},
title = {Information Complexity of Mixed-Integer Convex Optimization},
year = {2025},
month = {January},
abstract = {We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived as a corollary of a more fundamental ``transfer"result that shows how lower bounds on information complexity of continuous convex optimization under different oracles can be transferred to the mixed-integer setting in a black-box manner. Further, we (to the best of our knowledge) initiate the study of, and obtain the first set of results on, information complexity under oracles that only reveal \emph[partial] first-order information, e.g., where one can only make a binary query over the function value or subgradient at a given point. We give algorithms for (mixed-integer) convex optimization that work under these less informative oracles. We also give lower bounds showing that, for some of these oracles, every algorithm requires more iterations to achieve a target error compared to when complete first-order information is available. That is, these oracles are provably less informative than full first-order oracles for the purpose of optimization.},
url = {http://approjects.co.za/?big=en-us/research/publication/information-complexity-of-mixed-integer-convex-optimization-2/},
pages = {3-45},
journal = {Math. Program.},
volume = {210},
}