4 papers
Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values
Phillip Kerger
We study the deterministic query complexity of minimizing a convex Lipschitz function over a -dimensional Euclidean ball using only exact function values. At accuracy $Θ(d^{-1/2…
Tight Lower Bounds for Binary First-Order Oracles for Convex Optimization
Amitabh Basu, Phillip Kerger, Marco Molinaro
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 inform…
A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles
Phillip Kerger, Marco Molinaro, Hongyi Jiang +1
Given any algorithm for convex optimization that uses exact first-order information (i.e., function values and subgradients), we show how to use such an algorithm to solve the prob…
Information Complexity of Mixed-integer Convex Optimization
Amitabh Basu, Hongyi Jiang, Phillip Kerger +1
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,…