Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911247959588864 |
|---|---|
| author | Basu, Amitabh Kerger, Phillip Molinaro, Marco |
| author_facet | Basu, Amitabh Kerger, Phillip Molinaro, Marco |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02082 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization Basu, Amitabh Kerger, Phillip Molinaro, Marco Optimization and Control 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. |
| title | Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.02082 |