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

Amitabh Basu, Phillip Kerger, Marco MolinaroarXiv 2025 · DOI · arXiv

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. We demonstrate that under such oracles, the complexity is quadratic in the number of continuous decision variables ($d$), a result previously unknown even for continuous convex optimization. These bounds are tight (up to a logarithmic term) and matched by discretized cutting-plane methods, revealing that standard bit-representation is essentially optimal for solving constrained convex optimization problems.

Introduction

In classical optimization theory, algorithms are typically analyzed under the assumption of a "first-order oracle" that returns exact gradients or perfect separating hyperplanes. However, digital computers operate using finite precision. This discrepancy between theoretical models and computational reality leads to the study of information complexity: the minimum number of bits required to find an $\epsilon$-approximate solution to an optimization problem.

Recent research from Johns Hopkins, UC Berkeley, and Microsoft Research addresses a long-standing gap in this field. By establishing new, tight lower bounds, the authors prove that the quadratic dependence on the number of variables is a fundamental limit, confirming that standard discretized methods are information-theoretically optimal.

The Information Complexity Gap

The central challenge in this domain has been the discrepancy between known upper and lower bounds for the number of bits required to solve constrained convex problems:

  • Upper Bounds: Standard algorithms, such as discretized cutting-plane methods, require approximately $O(d^2)$ bits of information, where $d$ is the number of continuous variables.
  • Lower Bounds: Previous theoretical limits only established a requirement of $\Omega(d)$ bits.

This research investigates whether more "clever" algorithms could potentially solve these problems using fewer than $d^2$ bits or if the quadratic bottleneck is an inherent property of convex optimization.

Oracle Models

The authors evaluate complexity under two specific bit-wise oracles:

  1. Bit Oracle: This oracle returns individual bits of the coordinates of a gradient or a normal vector of a separating hyperplane.
  2. Inner Product Oracle: This oracle returns only the sign (positive or negative) of the inner product between a query vector and the gradient or normal vector. This is often considered a "weaker" or more restricted source of information.

Methodology: Adversarial Oracle Construction

To establish the lower bounds, the authors employ an adversarial construction. In this framework, the oracle does not commit to a specific convex set at the start of the algorithm. Instead, it maintains a "candidate pool" of all sets consistent with the answers provided so far.

As the algorithm queries the oracle, the adversary provides responses that keep the pool of possible solutions as large and geometrically "spread out" as possible. The authors mathematically prove that if an algorithm makes fewer than $\Omega(d^2)$ queries, the oracle can always identify two disjoint sets that both satisfy all previous responses. Consequently, the algorithm cannot distinguish between these two potential solutions, making it impossible to guarantee an $\epsilon$-accurate result.

Main Results

The paper provides two primary theorems establishing the new lower bounds for information complexity ($icomp$):

Theorem 1: Bit Oracle Complexity

For a problem with $d$ continuous variables and $n$ integer variables, the number of queries required is at least: $$\Omega\left(2^n d^2 \log \frac{R}{\rho}\right)$$

Theorem 2: Inner Product Oracle Complexity

A similar quadratic bound holds for the inner product oracle: $$\Omega\left(2^n d^2 \left(1 + \frac{1}{\log d}\right) \log \frac{R}{\rho}\right)$$

These bounds are "tight," meaning they match the performance of existing discretized cutting-plane algorithms within small logarithmic factors.

Implications for Mixed-Integer Programming

A significant contribution of this work is the extension to mixed-integer convex optimization. By using a "lifting" technique, the authors show that the complexity scales exponentially with the number of discrete dimensions ($2^n$), while maintaining the quadratic dependence on continuous dimensions ($d^2$). This proves that the continuous-variable bottleneck persists and compounds in the presence of integer constraints.

This result provides a theoretical justification for the common practice of rounding gradients to a fixed precision. It suggests that more sophisticated bit-querying strategies are unlikely to yield significant improvements in efficiency, as the "naive" discretization is already near-optimal.

Conclusion and Future Work

This research provides a definitive lower bound for the bit-wise complexity of constrained convex optimization. While it settles the question for feasibility and constrained problems, several avenues for future research remain:

  • Unconstrained Optimization: The authors conjecture that a similar $d^2$ bound applies to unconstrained optimization for Lipschitz continuous functions, though this remains to be proven.
  • Zeroth-Order Oracles: It is yet to be determined if a similar quadratic bottleneck exists for oracles that only provide function values ($f(x)$) without derivative information.
  • Refining Logarithmic Factors: Future work may focus on closing the remaining polylogarithmic gaps between the established lower bounds and current upper bounds.

Summary updated

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.
BibTeX
@misc{basu2025tight,
  author = {Amitabh Basu and Phillip Kerger and Marco Molinaro},
  title = {{Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization}},
  year = {2025},
  eprint = {2511.02082},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.02082},
  howpublished = {arXiv},
}

Loading related content...

Figure