Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization

Amitabh Basu, Phillip Kerger, Marco Molinaro · 2025

Read Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization by Amitabh Basu, Phillip Kerger, Marco Molinaro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-02082.txt.

Introduction

Amitabh Basu, Phillip Kerger, and Marco Molinaro prove limits on how much information any algorithm must gather to solve constrained convex optimisation problems. They study two stingy oracles: one that returns first-order information bit by bit in coordinates, and one that answers only whether an inner product with a gradient or separating direction is positive. Each answer carries a single bit.

Under either oracle, they show the information needed grows quadratically with the number of continuous decision variables, a bound not previously known even for purely continuous problems. The bound is tight up to a logarithmic factor, matched by a discretised cutting-plane method. The moral is that the standard bit representation of gradient information is essentially the best possible choice.

Catalog record

CREATORAmitabh Basu, Phillip Kerger, Marco Molinaro
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02082

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization Amitabh Basu, Phillip Kerger, Marco Molinaro Abstract We establish new lower-bounds for the information complexity of mixed-integer convex optimization under two “bit-wise” oracles. The first oracle provides bits of first-order information in the standard coordinate model, and the second oracle answers whether the inner product of a specified vector with the gradient of the function at a point or the normal vector of a separating hyperplane for the feasible region is positive or non-positive, thus also providing one bit of first-order information. The new contribution is that under such oracles, the complexity is quadratic in the number of continuous decision variables, which was not known before even for continuous convex optimization. These new lower-bounds are tight (up to a logarithmic term), matched by a natural discretization of standard cutting-plane methods for convex optimization. These reveal that using a standard bit-representation of the first-order information is, in general, the best one can do with respect to the number of bits of information needed to solve constrained convex optimization problems. 1 Introduction We focus on mixed-integer convex optimization problems of the form \displaystyle\min\{f({\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}):({\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})\in C\cap({\mathbb{Z}}^{n}\times\mathbb{R}^{d})\}, (1) where f:\mathbb{R}^{n}\times\mathbb{R}^{d}\rightarrow\mathbb{R} is a convex function and C\subseteq\mathbb{R}^{n}\times\mathbb{R}^{d} is a closed, convex set. The goal is to design algorithms to obtain \varepsilon -approximate solutions for ( 1 ) for any given error tolerance \varepsilon>0 , i.e., return {\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}^{*}\in C\cap({\mathbb{Z}}^{n}\times\mathbb{R}^{d}) such that f({\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}^{*})\leq f({\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})+\varepsilon for all {\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in C\cap({\mathbb{Z}}^{n}\times\mathbb{R}^{d}) . To develop an algorithmic theory for problem ( 1 ) we must formalize how the instance is presented to the algorithm. This is not an issue if one considers subfamilies of instances with explicit algebraic descriptions (e.g., linear or polynomial optimization). In order to formally handle more general nonlinear instances, the algorithm is given access to the instances via oracles, i.e., the algorithm collects information about the given instance by querying oracles. In this paper, we consider only oracles using first-order information. These are oracles whose answers about the instance (f,C) , at a given query point {\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in\mathbb{R}^{n}\times\mathbb{R}^{d} , are some function of either f({\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}) , the subgradient of f at \textstyle\bf z , or of a separating hyperplane to the constraint set C if {\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\not\in C . For example, the standard first-order oracle returns the entire function value, subgradient, or separating hyperplane. In this paper, we wish to consider more fine-grained oracles that could potentially respond with lesser information about these objects. For example, in any computational setting one always only has access to a bit-representation of subgradients or separating hyperplanes. Given any such oracle access, a fundamental question then is the following: What is the smallest number of oracle queries one needs to provably report an \varepsilon -approximate solution? The smallest number of queries is called the information or oracle complexity for the given class of instances under that particular oracle. For the standard first-order oracle, this problem has been studied since the mid 70s and in the last few years, a fairly complete understanding has been achieved (which we summarize formally below). Other oracles are much less studied and yet are important to investigate from both a practical and theoretical perspective, connecting with other work on the communication and space complexity of convex optimization. The feasibility problem of checking whether a closed convex set C\subseteq\mathbb{R}^{n}\times\mathbb{R}^{d} contains a point from {\mathbb{Z}}^{n}\times\mathbb{R}^{d} or not, and reporting such a point if one exists is a special case of ( 1 ) by simply setting f to be the function that takes value 0 everywhere. Thus, the information complexity of the feasibility problem is a lower bound on the information complexity of ( 1 ), for any class of instances and for any oracle. In this paper, we focus on the feasibility problem. In other words, given some class \mathcal{I} of closed, convex sets, and a separation oracle for this class, we wish to understand the smallest number of separation oracle queries needed to either report a feasible point from the given instance, or conclude that the instance is infeasible, i.e., C=\emptyset . It is not hard to argue that if \mathcal{I} is the class of all possible closed, convex sets, then the information complexity is infinite. Indeed, even with n=0,d=1 (i.e., detecting feasibility in 1 dimensional continuous convex optimization) for any query point \hat{y}\in\mathbb{R} , one could report a separating hyperplane \{y\in\mathbb{R}:y\leq\hat{y}-1\} . After finitely many queries, if the algorithm reports infeasibility, then one can simply consider the instance \{y:y\leq y_{\min}-1\} , where y_{\min} is the smallest \hat{y} queried by the algorithm; on the other hand, if the algorithm reports any point y^{\star} as a potential feasible point, then one can say that the true instance was a convex set that is contained in \{y:y\leq y_{\min}-1\} that does not contain y^{\star} . Thus, one has to a priori fix R>0 and consider only instances C such that C\subseteq[-R,R]^{n+d} . Without such a bound on the norms of the feasible solutions, the information complexity is clearly infinite. However, this is not enough. By considering all possible singletons in the interval [0,1] , a similar argument shows that finitely many queries cannot succeed. Thus, one considers another parameter \rho>0 and focuses on the instances \mathcal{I}_{n,d,R,\rho} of all closed convex sets C\subseteq\mathbb{R}^{n}\times\mathbb{R}^{d} such that C\subseteq[-R,R]^{n+d} , and if C is feasible then there exist a “fat” set of feasible solutions, i.e., there exists ({\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}^{\star},{\mathchoice{\mbox{\boldmath$\displaystyle\bf y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\star})\in({\mathbb{Z}}^{n}\times\mathbb{R}^{d}) such that \{({\mathchoice{\mbox{\boldmath$\displaystyle\bf x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}^{\star},{\mathchoice{\mbox{\boldmath$\displaystyle\bf y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})\in\mathbb{R}^{n}\times\mathbb{R}^{d}:\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}-{\mathchoice{\mbox{\boldmath$\displaystyle\bf y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\star}\|_{\infty}\leq\rho\}\subseteq C . The information complexity can then be obtained as a function of n,d,R,\rho . Note that for a point {\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\notin C , the oracle has multiple choices for separating hyperplanes. We will formalize this choice as saying the oracle has a first-order map \mathcal{G} which determines which separating hyperplane is used to answer the query. We give a formal definition here for feasibility problems (see [ 1 ] for the analogous extension for the first-order information of optimization problems). Definition 1 A first order map \mathcal{G} for \mathcal{I}_{n,d,R,\rho} is a function \mathcal{G}:\mathcal{I}_{n,d,R,\rho}\times(\mathbb{R}^{n}\times\mathbb{R}^{d})\rightarrow\mathbb{R}^{n}\times\mathbb{R}^{d} such that \mathcal{G}(C,\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}})={\mathchoice{\mbox{\boldmath$\displaystyle\bf 0$}}{\mbox{\boldmath$\textstyle\bf 0$}}{\mbox{\boldmath$\scriptstyle\bf 0$}}{\mbox{\boldmath$\scriptscriptstyle\bf 0$}}} if \hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}}\in C ; otherwise, \langle\mathcal{G}(C,\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}}),{\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\rangle<\langle\mathcal{G}(C,\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}}),\hat{{\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}}\rangle for all {\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in C . An oracle \mathcal{O}(\mathcal{Q},\mathcal{G}) using first-order information, with permissible queries \mathcal{Q} and first-order map \mathcal{G} , takes as input a point {\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in\mathbb{R}^{n}\times\mathbb{R}^{d} and a query q\in\mathcal{Q} , which is a function on \mathbb{R}^{n}\times\mathbb{R}^{d} , and returns for an instance C\in\mathcal{I}_{n,d,R,\rho} the answer \mathcal{O}({\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}},q,C)=q(\mathcal{G}(C,{\mathchoice{\mbox{\boldmath$\displaystyle\bf z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})), To summarize: • Without knowing the instance C , based only on the oracle responses thus far, in each step the algorithm defines its query by choosing q from the set of permissible queries \mathcal{Q} (i.e.,

Read the complete text