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:
- Bit Oracle: This oracle returns individual bits of the coordinates of a gradient or a normal vector of a separating hyperplane.
- 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