Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values

Phillip Kerger

REVIEW 1 major objections 3 minor 2 cited by

Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values

T0 review · 1 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Minimizing a convex function from exact values alone requires ~d^2 evaluations, closing a 30-year gap with gradient queries.

desk verdict A credible near-quadratic lower bound for deterministic exact-value convex optimization that closes a gap from 1996; the central proof looks sound and deserves full refereeing. read the letter →

arxiv 2607.13335 v1 pith:ARGMFHHC submitted 2026-07-14 math.OC cs.CC

Phillip Kerger This is my paper · ORCID

classification math.OCcs.CC MSC 90C2590C60

keywords zeroth-orderoracleconvexoptimizationcomplexitynonsmoothlowerboundexactfunctionvaluesmixed-integerderivative-free

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper settles a long-standing question in deterministic derivative-free convex optimization: how many exact function evaluations are needed to minimize a convex, 1-Lipschitz function over the unit ball to accuracy Θ(d^{-1/2})? The answer is Θ~(d^2), up to logarithmic factors. This closes the gap between the old Ω(d) lower bound and the O(d^2 log^2 d) upper bound from 1996. The proof introduces an adversarial oracle that maintains a Cartesian product of uncertainty sets for the rows of a max-affine hard family, showing that after T queries many rows retain enough volume. It also lifts the bound to mixed-integer convex optimization, giving Θ~(2^n d^2) for n binary variables and d continuous ones.

What carries the argument

The load-bearing mechanism is the exact resisting oracle built from a Cartesian product invariant. The adversary maintains compact convex uncertainty sets P_i ⊆ τB^m for each row of the max-affine objective; every selection of one vector from each set reproduces the entire exact transcript. A query is answered by a quantile level that either reduces one row's dimension by one (informative update) or truncates all rows by halfspaces removing at most a 1/(4m) fraction of their intrinsic volume (noninformative update). This limits total damage after T queries to s ≤ T dimension reductions and log-volume loss O(T log m), so up to T = Θ(m^2/log m) many rows retain both high dimension and volume r

What would settle it

Construct a deterministic value-only algorithm for the max-affine family of Section 3 that reaches error 10^{-7}/√d in o(d^2/log d) queries, or exhibit a single admissible query whose exact response on some transcript leaves a constant fraction of several row uncertainty sets' intrinsic volume eliminated — either would break the key per-query tradeoff (Proposition 10) and invalidate the lower bound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4: for every sufficiently large dimension d, any deterministic algorithm using only exact function values needs at least c d^2 / log(d+1) queries to guarantee error ε0/√d, with ε0 = 10^{-7}; combined with the known value-only method, the complexity is Θ~(d^2). The hard functions are maxima of m = d/2 linear functions f_W(x,z) = max_i (a x_i + ⟨w_i,z⟩). The lower bound works by an exact resisting oracle: after each query the adversary keeps a product of convex uncertainty sets for the rows, consistent with the entire transcript; an informative query slices one row to a codimension-one section while shrinking every other row's volume by at most a 1/(4m) fraction. A

Load-bearing premise

The adversary can answer every exact-value query by collapsing exactly one row's uncertainty set to a codimension-one slice while shrinking every other row by at most a 1/(4m) volume fraction; if a single exact value could destroy a constant fraction of volume of many rows at once (for instance by encoding a full subgradient), the aggregate-width argument would fail and the d^2 lower bound would no longer follow.

Editorial extensions

If this is right

The polynomial separation between exact values and full first-order information is now proven: at accuracy Θ(d^{-1/2}), value-only complexity is Θ~(d^2) while first-order complexity is Θ(d).
The same near-quadratic lower bound holds for every fixed polynomially smaller accuracy d^{-α} with α > 1/2 (Corollary 5).
Mixed-integer convex optimization with n binary variables and d continuous variables requires Θ~(2^n d^2) exact-value queries, even when fractional queries in the continuous coordinates are allowed.
The hard instances are explicit maxima of d/2 linear functions, so the lower bound applies to the entire class of convex 1-Lipschitz functions.
Any exact-value algorithm, however adaptive, discontinuous, or memory-rich, fails below the bound; this rules out transcript-compression or bit-counting escapes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The adversary's product invariant shows that exact real numbers can be treated without assigning a finite bit-content to a response; similar 'volume-slicing' adversaries may yield tight lower bounds for other partial oracles (comparison, bit-limited, or noisy values).
A natural next question is whether randomized algorithms can beat the d^2 barrier; the present resisting oracle is tied to a fixed deterministic transcript and the paper notes it does not yield a hard distribution, so randomization remains genuinely open.
The manuscript reports that machine-based formal verification covers only a coarser accuracy variant (d^{-3}), not the headline d^{-1/2} theorem; the main proof relies on classical convex-geometry results that have not been machine-checked, which is a place where a subtle gap could hide.
If a single exact function value could be shown to encode a subgradient or to shrink many rows at once, the lower bound would collapse; testing small-dimensional extreme cases of the per-query tradeoff could reveal whether the adversary's chosen response is optimal.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline result is real: this paper closes the oracle-complexity gap for deterministic exact-value minimization on nonsmooth convex functions, giving Ω(d²/log d) at ε = 10⁻⁷/√d and matching Protasov's upper bound up to log factors. That is a genuine polynomial separation between value-only and full first-order oracles, and I don't think there's a load-bearing flaw in the continuous lower bound.

The hard family (max of d/2 linear functions), the Cartesian-product uncertainty invariant, and the aggregate-width plus barycentric-separation argument are all new and well constructed. I checked the adversary's per-query tradeoff carefully, since it's the load-bearing step: a single exact value can cut at most one row down by a dimension, and every other row loses only its upper 1/(4m)-quantile cap. That is exactly what Proposition 10 claims, and the volume accounting in (25)–(28) is consistent. Lemma 13 and Lemma 14 hold up. The stress-test concern about one value destroying many rows simultaneously does not land.

The soft spots are presentational, not mathematical. First, §1.4 says the proof is formally verified in Lean, but Appendix A correctly discloses that this only covers the earlier d⁻³-accuracy version, not the headline d⁻¹/² theorem. The main theorem is not machine-checked. That's fine, but the opening section should not oversell it. Second, Corollary 2 leans on the self-cited transfer theorem [15, Thm 7]. The result is published, but the application does not verify every hypothesis—specifically whether the Lipschitz parameter M can depend on d. That needs a careful check before the mixed-integer claim is accepted at face value. Third, in §4 the sentence about the Lipschitz constant of g_W is compressed: the conclusion (g_W is 1-Lipschitz) is correct once you account for the 1/2 factor, but the derivation as written skips a step.

This paper is for anyone working on information-based complexity, oracle complexity, or derivative-free optimization. The proof is intricate and deserves a serious referee who can spend time on the adversary argument. I'm skeptical by default of AI-assisted proofs, but here the human verification seems real: the details are explicit, the constants check out, and the transfer theorem is cited rather than re-proved. I'd bring it to my reading group, and I'd cite it if I write on zeroth-order complexity.

Recommendation: send it to peer review. The referee should focus on the mixed-integer transfer theorem's hypotheses and on making the scope of the Lean verification precise in the final version.

Referee Report

1 major / 3 minor

Summary. The paper studies deterministic query complexity of minimizing a convex 1-Lipschitz function over the Euclidean ball using only exact function values. Theorem 4 gives a lower bound of Ω(d²/log d) at accuracy ε₀/√d, matching Protasov's upper bound O(d² log² d) up to logarithmic factors and thereby closing a gap dating back to 1996. The proof constructs a max-of-linear hard family f_W(x,z)=max_i{a x_i+⟨w_i,z⟩}, an adversary that maintains a Cartesian product of row uncertainty sets, and a per-query tradeoff: each informative query reduces one row's dimension and removes at most α=1/(4m) of the intrinsic volume from every other row. A volume/dimension budget shows that after O(m²/log m) queries many rows remain high-dimensional with large normalized volume; Urysohn's inequality yields a common wide direction; and taking opposite extremes in that direction produces two transcript-consistent functions whose minimizers are separated by a constant. Corollary 2 lifts the result to mixed-integer convex optimization via a published transfer theorem, giving Θ~(2ⁿ d²) complexity.

Significance. If the proof is read with the norm-scale correction noted below, this is a substantial contribution. It establishes the first polynomial separation between deterministic exact-value and full first-order oracles on nonsmooth convex functions, and it settles the dimension dependence in the value-only model at d^{-1/2} accuracy up to logarithms. The adversary argument is self-contained and transparent, and it carefully avoids assigning finite bit content to exact real answers. The Lean formalization of the initial d^{-3}-accuracy lower bound is a useful partial machine check, though it does not cover the main d^{-1/2} refinement. I also verified the per-query tradeoff that was flagged as the weakest assumption: unselected rows are truncated only by caps above their own α-quantile, so no single exact value can destroy a constant fraction of many rows simultaneously. The main mathematical structure is sound; the issues are concentrated in a repeated normalization typo and an overstrong formal-verification claim.

major comments (1)

[§3.4, Lemma 14; Eq. (11); Eq. (38)] There is a norm-scale inconsistency in a load-bearing step. Lemma 8's proof establishes a/√m ≤ ||p_W||₂ ≤ (a/√m)√(1+Γ^{-2}), but Eq. (11), the definition of r₀ in Lemma 14, and Eq. (38) all print r₀ = a√m. With the printed value, τ/(5r₀) = 1/(5Γm), so the RHS of the Lemma 14 display is not a positive constant and the claimed separation ||p̂₊−p̂₋||₂ > 1/600 does not follow for large m. Replacing r₀ by a/√m gives τ/(5r₀) = 1/(5Γ), and the stated inequality is valid. Because Lemma 14 provides the constant minimizer separation used in the final gap computation, this correction is load-bearing and must appear in the published version.

minor comments (3)

[§1.4 / Appendix A] The statement that the paper provides 'formal verification of the proof of the Ω~(d²) lower bound' is stronger than what Appendix A discloses: the Lean development covers the initial d^{-3}-accuracy construction, not the d^{-1/2} refinement that is the main theorem. Please qualify the §1.4 claim to match Appendix A.
[§3.1, §3.4] After the norm-scale correction, r₀ should be consistently written as a/√m. The repeated appearance of 'a√m' in (11), Lemma 14, and (38) is likely a copy-paste error, but as printed it prevents a reader from verifying the central separation argument.
[§4] The proof of Corollary 2 says 'one exact query to f_W simulates one exact query to g_W'. This is correct, but it may be worth spelling out that the simulation also requires knowing r = max{1, ||q||₂}, which is available to the algorithm from the query point alone.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central continuous lower bound is proved from explicit adversarial invariants and standard convex-geometry facts; the mixed-integer lift uses a published transfer theorem rather than a restatement of the target.

full rationale

The derivation chain is self-contained and does not reduce to its own inputs. The lower bound in Theorem 4 is established by an explicit adversarial construction: row uncertainty sets P_i, the quantile slicing Lemma 9, the exact product invariant and dimension/volume bounds of Proposition 10, the volume budget (24)-(28), the aggregate-width Lemma 13, and the projection-separation Lemma 14. Each of these is proved from standard external facts (Urysohn's inequality, Euclidean ball-volume ratios, Gaussian projection identities), and no parameter is fitted to data: a=1/2, Gamma=100, eta=1/100 are proof constants adjusted only to satisfy inequalities. The final two-function indistinguishability argument follows from the rectangular invariant, so the claimed lower bound is not assumed as an input. The mixed-integer Corollary 2 applies the transfer theorem of Basu, Jiang, Kerger, and Molinaro [15, Theorem 7], a published result with stated hypotheses that do not include the target lower bound; although this citation shares an author, it functions as a genuine external reduction rather than a circular restatement. The paper itself flags a verification-coverage limitation in Appendix A: the Lean formal verification covers the d^{-3} variant, while the main theorem is at d^{-1/2}; this is an honest scope disclosure, not a circularity. Overall, no load-bearing step is self-definitional, no fitted quantity is relabeled as a prediction, and no conclusion is forced by an unverified self-citation chain.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central continuous proof is self-contained; its only external inputs are standard convex-geometry facts (Urysohn's inequality, Gaussian projections, ball-volume ratios) and the hand-chosen constants listed. The matching upper bound imports Protasov's result, and the mixed-integer corollary imports the authors' own transfer theorem. No data are fitted anywhere.

free parameters (4)

a (slope of x_i terms in the hard family) = 1/2
Chosen by hand; the Lipschitz bound requires a² + τ² < 1, and the final accuracy constant ε0 depends on it. Not fitted to data.
Γ (radius normalization: row box τB^m with τ = a/(Γ√m)) = 100
Chosen large enough for Lemma 14's separation bound and the final constant; a proof constant, not a fitted parameter.
η (query-budget fraction in Lemma 12) = 1/100
Sets the m/2 good-rows threshold and makes 16η/(1-4η) = 1/6; hand-chosen to make the volume/width argument work.
ε0 (accuracy constant in Theorem 4) = 10^{-7}
Derived from the constants above: the final gap is > 10^{-7}/√d. The theorem's guarantee holds with this value; not fitted to data.

assumptions (5)

standard math Urysohn's inequality: for a k-dimensional convex body P, the mean directional width is at least 2 (vol_k(P)/κ_k)^{1/k}.
Invoked in Lemma 13 to convert volume radius into aggregate directional width; cited to Schneider [19, Eq. (7.21), p. 382].
standard math Gaussian projection facts: for θ uniform on S^{m-1}, the projection onto a k-dimensional subspace has a radial component R with E[R] ≥ E[R²] = k/m, and the projected direction is uniform and independent of R.
Used in Lemma 13's projection argument to lower-bound the expectation of the aggregate width.
domain assumption Protasov's deterministic exact-value upper bound: O(d² log(d+1) log(1/δ)) evaluations for relative error δ.
External 1996 result [11]; supplies the matching upper bound in Theorem 1 and the mixed-integer upper bound. The exact hypotheses and absolute-error conversion are not proved in this paper.
domain assumption Basu–Jiang–Kerger–Molinaro transfer theorem (Theorem 15 here, [15, Thm 7]).
Self-cited prior work; the mixed-integer lower bound (Corollary 2) is obtained by applying this theorem to the prepared continuous family. Neither the statement nor the proof is reproduced.
domain assumption Model assumption: exact real-valued oracle responses; algorithms may use unlimited computation and memory and discontinuous decision rules.
Definition 1; the lower bound applies only in this model. The paper notes that finite-precision or bounded-memory analogues would require different arguments.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values." pith.science (2026). https://pith.science/paper/ARGMFHHC

@misc{pith2026260713335,
  author       = {Pith},
  title        = {Pith review of: Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ARGMFHHC}},
  note         = {Machine review of arXiv:2607.13335}
}

abstract

We study the deterministic query complexity of minimizing a convex Lipschitz function over a $d$-dimensional Euclidean ball using only exact function values. At accuracy $\Theta(d^{-1/2})$, the previously applicable lower bound was $\Omega(d)$, inherited from the stronger full first-order oracle, while an upper bound from Protasov's value-only method requires $O(d^2\log^2 d)$ evaluations. By providing a lower bound of $\Omega(\,\frac{d^2}{\log(d+1)})$ on the oracle complexity in this setting, we thereby close this gap dating back to 1996, up to polylogarithmic factors. Furthermore, we are able to lift this result to the mixed-integer setting: Mixed-integer convex optimization with $d$ continuous and $n$ discrete variables using function values requires $\tilde{\Omega}(d^2\cdot 2^n)$ queries.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A Domain-Specific Harness for End-to-End Automation of Optimization Research
math.OC 2026-08 conditional novelty 7.0 of 10 full

An automated pipeline proposes, proves, and machine-checks two optimization results: a new O(1/N^4) gradient-norm method with lemniscate-constant bound, and an analytic ITEM-f with accelerated linear contraction.
Convergence rates for pivoted QR and LU
math.NA 2026-07 accept novelty 7.0 of 10

Under approximate greedy pivoting, pivoted QR/LU residuals are bounded by the geometric mean of leading singular values, yielding algebraic and geometric convergence rates for matrices and bivariate functions.

Reference graph

Works this paper leans on

19 extracted references · 6 canonical work pages · cited by 2 Pith papers

[1]

MPS-SIAM Series on Optimization, vol

Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization, vol. 8. Society for Indus- trial and Applied Mathematics, Philadelphia (2009). https://doi.org/10.1137/1. 9780898718768

doi:10.1137/1 2009
[2]

IEEE Transactions on Information Theory61(5), 2788–2806 (2015) https://doi.org/10

Duchi, J.C., Jordan, M.I., Wainwright, M.J., Wibisono, A.: Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory61(5), 2788–2806 (2015) https://doi.org/10. 1109/TIT.2015.2409256

arXiv 2015
[3]

In: Proceedings of the 26th Annual Conference on Learning Theory

Shamir, O.: On the complexity of bandit and derivative-free stochastic con- vex optimization. In: Proceedings of the 26th Annual Conference on Learning Theory. Proceedings of Machine Learning Research, vol. 30, pp. 3–24 (2013). https://proceedings.mlr.press/v30/Shamir13.html 24

2013
[4]

Journal of Machine Learning Research18(52), 1–11 (2017)

Shamir, O.: An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research18(52), 1–11 (2017)

2017
[5]

John Wiley & Sons, New York (1983)

Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, New York (1983)

1983
[6]

Foundations and Trends in Machine Learning8(3–4), 231–357 (2015) https://doi.org/10.1561/ 2200000050

Bubeck, S.: Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning8(3–4), 231–357 (2015) https://doi.org/10.1561/ 2200000050

2015
[7]

In: Advances in Neural Information Processing Systems, vol

Bubeck, S., Jiang, Q., Lee, Y.T., Li, Y., Sidford, A.: Complexity of highly parallel non-smooth convex optimization. In: Advances in Neural Information Processing Systems, vol. 32, pp. 13900–13909 (2019)

2019
[8]

In: Proceedings of the Thirty-Second Confer- ence on Learning Theory

Woodworth, B., Srebro, N.: Open problem: The oracle complexity of convex optimization with limited memory. In: Proceedings of the Thirty-Second Confer- ence on Learning Theory. Proceedings of Machine Learning Research, vol. 99, pp. 3202–3210 (2019).https://proceedings.mlr.press/v99/woodworth19a.html

2019

Show all 19 references

[9]

Journal of the ACM71(6), 41–14137 (2024) https: //doi.org/10.1145/3689208

Marsden, A., Sharan, V., Sidford, A., Valiant, G.: Efficient convex optimization requires superlinear memory. Journal of the ACM71(6), 41–14137 (2024) https: //doi.org/10.1145/3689208

2024 doi
[10]

Mathematics of Operations Research50(4), 2941–2971 (2024) https://doi.org/ 10.1287/moor.2023.0208

Blanchard, M., Zhang, J., Jaillet, P.: Quadratic memory is necessary for optimal query complexity in convex optimization: Center of mass is pareto optimal. Mathematics of Operations Research50(4), 2941–2971 (2024) https://doi.org/ 10.1287/moor.2023.0208 . Published online 20 N...

2024
[11]

Mathematical Notes59(1), 69–74 (1996) https: //doi.org/10.1007/BF02312467

Protasov, V.Y.: Algorithms for approximate calculation of the minimum of a convex function from its values. Mathematical Notes59(1), 69–74 (1996) https: //doi.org/10.1007/BF02312467

1996 doi
[12]

Mathematical Programming 169(2), 337–375 (2018) https://doi.org/10.1007/s10107-017-1137-4

Cartis, C., Scheinberg, K.: Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Mathematical Programming 169(2), 337–375 (2018) https://doi.org/10.1007/s10107-017-1137-4

2018 doi
[13]

Mathematical Pro- gramming207(1–2), 55–106 (2024) https://doi.org/10.1007/s10107-023-01999-5

Cao, L., Berahas, A.S., Scheinberg, K.: First- and second-order high probability complexity bounds for trust-region methods with noisy oracles. Mathematical Pro- gramming207(1–2), 55–106 (2024) https://doi.org/10.1007/s10107-023-01999-5

2024 doi
[14]

https://doi.org/10

Basu, A., Kerger, P., Molinaro, M.: Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization (2025). https://doi.org/10. 48550/arXiv.2511.02082 . https://arxiv.org/abs/2511.02082 25

2025 doi arXiv
[15]

Mathematical Programming210(1), 3–45 (2025) https://doi.org/10.1007/s10107-024-02099-8

Basu, A., Jiang, H., Kerger, P., Molinaro, M.: Information complexity of mixed- integer convex optimization. Mathematical Programming210(1), 3–45 (2025) https://doi.org/10.1007/s10107-024-02099-8

2025 doi
[16]

OpenAI-hosted manuscript (2026)

OpenAI: A Proof of the Cycle Double Cover Conjecture. OpenAI-hosted manuscript (2026). https://cdn.openai.com/pdf/ 04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf Accessed 2026-07-14

2026
[17]

A Proof of the Cycle Double Cover Conjecture

OpenAI: Prompt Used for “A Proof of the Cycle Double Cover Conjecture”. OpenAI-hosted methodological document (2026). https://cdn.openai.com/pdf/ 04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_prompt.pdf Accessed 2026-07-14

2026
[18]

Revised 19 January 2026 (2025)

Jang, U., Ryu, E.K.: Point Convergence of Nesterov’s Accelerated Gradient Method: An AI-Assisted Proof. Revised 19 January 2026 (2025). https://doi.org/ 10.48550/arXiv.2510.23513 . https://arxiv.org/abs/2510.23513

2026 doi
[19]

nonsmooth convex optimization

Schneider, R.: Convex Bodies: The Brunn–Minkowski Theory, 2nd edn. Encyclo- pedia of Mathematics and its Applications, vol. 151. Cambridge University Press, Cambridge (2014). https://doi.org/10.1017/CBO9781139003858 26 A AI usage and methodology Section A.1 gives the full prom...

2014 doi

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

MPS-SIAM Series on Optimization, vol

Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization, vol. 8. Society for Indus- trial and Applied Mathematics, Philadelphia (2009). https://doi.org/10.1137/1. 9780898718768

doi:10.1137/1 2009

[2] [2]

IEEE Transactions on Information Theory61(5), 2788–2806 (2015) https://doi.org/10

Duchi, J.C., Jordan, M.I., Wainwright, M.J., Wibisono, A.: Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory61(5), 2788–2806 (2015) https://doi.org/10. 1109/TIT.2015.2409256

arXiv 2015

[3] [3]

In: Proceedings of the 26th Annual Conference on Learning Theory

Shamir, O.: On the complexity of bandit and derivative-free stochastic con- vex optimization. In: Proceedings of the 26th Annual Conference on Learning Theory. Proceedings of Machine Learning Research, vol. 30, pp. 3–24 (2013). https://proceedings.mlr.press/v30/Shamir13.html 24

2013

[4] [4]

Journal of Machine Learning Research18(52), 1–11 (2017)

Shamir, O.: An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research18(52), 1–11 (2017)

2017

[5] [5]

John Wiley & Sons, New York (1983)

Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, New York (1983)

1983

[6] [6]

Foundations and Trends in Machine Learning8(3–4), 231–357 (2015) https://doi.org/10.1561/ 2200000050

Bubeck, S.: Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning8(3–4), 231–357 (2015) https://doi.org/10.1561/ 2200000050

2015

[7] [7]

In: Advances in Neural Information Processing Systems, vol

Bubeck, S., Jiang, Q., Lee, Y.T., Li, Y., Sidford, A.: Complexity of highly parallel non-smooth convex optimization. In: Advances in Neural Information Processing Systems, vol. 32, pp. 13900–13909 (2019)

2019

[8] [8]

In: Proceedings of the Thirty-Second Confer- ence on Learning Theory

Woodworth, B., Srebro, N.: Open problem: The oracle complexity of convex optimization with limited memory. In: Proceedings of the Thirty-Second Confer- ence on Learning Theory. Proceedings of Machine Learning Research, vol. 99, pp. 3202–3210 (2019).https://proceedings.mlr.press/v99/woodworth19a.html

2019