The work is more an exploration of an oracle model for optimization rather than designing new algorithms. While the results are not practical, the work largely answers the question of what is possible with the chosen oracle model. The paper in the end provides a 'target' complexity so that other researchers may design more practical methods which match the theoretical bounds of this work. The reviewers unanimously agree that the work should be accepted. The authors' rebuttal also helped clarify some concerns and ultimately increased the overall score of the work.