acceptodds
Under review as a conference paper at ICLR 2027

Learning to Search Beyond Lines

Abstract

We study derivative-free nonconvex optimization through reusable conditional responses rather than isolated search directions. Building on the conditional restrictions of convolutional optimization with convex kernels and power lifting, we construct search paths from approximate conditional minimizers. Ideally these paths are conjugate curves: on quadratic objectives they reduce to the conjugate lines of Powell's parallel-subspace construction, and elsewhere they follow the curved valley floor. In one scalar instantiation, power lifting and convolution with a convex kernel give a convex surrogate for nonlocal proposals. We couple this construction to adaptive sampling and error-aware reuse of previously sampled profiles, separating surrogate accuracy from improvement in the original objective. Under explicit regularity assumptions, we derive approximation bounds for profile reuse, evaluation guarantees for safeguarded one-dimensional search, query bounds that charge response learning together with path search, and an exact price for straightening a curved response, and show that on flat curved valleys segment-descending line searches need unboundedly many steps, at a sharp rate, where a conjugate-curve search in an aligned chart needs a constant number of evaluations. Controlled experiments isolate the effects of path construction, convexification, and reuse under matched budgets; on structured curved valleys, curved paths need less than half the evaluations of secant paths that estimate conjugate lines. At larger budgets on the standard COCO/BBOB suite, affine responses beat straight search within the same algorithm, with no resolved further gain from curvature; in value-only training of a diagonal linear network, conditional responses beat straight coordinate search at large budgets in the flattest valleys created by weight decay. The resulting framework connects nonlocal path search with reusable function information while accounting for the cost of acquiring and maintaining that information.

Primary area:
optimization
Keywords:
derivative-free optimization, nonconvex optimization, nonlinear path search, convolutional convexification

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ENMGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies derivative-free optimization by extending Powell's conjugate lines to curved search paths which can be used agian. The authors analyze the approximation errors and evaluation costs, and test the method on synthetic problems, BBOB benchmarks, and neural network training. The results show that curved paths work well on structured curved valleys, but show little additional improvement over affine paths on the other benchmarks.

Critical strengths
  1. The paper explores using learned curved search paths to overcome the limitations of traditional line search in nonconvex optimization. The idea is well motivated, especially for problems with narrow, curved valleys.

  2. The connection between Powell's conjugate lines and conjugate curves is interesting. The paper also provides theoretical analysis of curve approximation errors, function evaluation costs, and when curved search can outperform straight-line search.

  3. The authors consider not only how to construct curved paths, but also the cost of learning them and the reuse of previous function evaluations. The experiments are fairly systematic and transparent, showing how these components contribute to performance on different problems.

Critical weaknesses
  1. Although curved search performs well on specially designed curved valleys, it shows little additional benefit over affine methods on the standard BBOB benchmarks and neural network training tasks.

  2. On BBOB, the proposed method still falls behind mature optimizers such as Powell, BOBYQA, and CMA-ES. This raises questions about its practical usefulness.

  3. The main theoretical results rely on specific function structures, known regularity bounds, and suitable search coordinates. These conditions may be difficult to satisfy in practical black-box optimization, so it is unclear how well the theoretical advantages carry over to more general problems.

Questions for authors
  1. On BBOB, Curved and Affine show almost the same performance, and both are worse than established methods like Powell, BOBYQA and CMA-ES. I wonder why adding curvature does not help much in these tests. Also, is the gap with these optimizers mainly due to implementation and parameter tuning, or is it more about the limitation of the method itself? I think this is important to understand how useful the proposed method can be in practice.

  2. The theoretical results rely on several assumptions, such as known regularity bounds and suitable search coordinates. But in the actual black-box setting, the search paths are learned from limited function evaluations. Could the authors clarify which theoretical guarantees still hold for the actual algorithm?

3 comments

Thank you for a clear review and two precise questions. We answer them directly; the general response gives the overview.

Q1, part 1: why does curvature not help on BBOB? The curved and affine controls buy the same three paid anchors and the same path-search budget, so the tie is not explained by extra acquisition cost. A fixed-chart diagnostic (general response, part 3) separates the remaining explanations. On 96 BBOB and 380 network charts, the responses are clearly curved, the network anchors are exact (BBOB anchors err more on multimodal functions), and curves fit the responses better. The better fit does not consistently turn into decrease; the local 25-call scalar search on often multimodal profiles is a plausible limitation. We can also show when curvature pays. Scaling the curvature of the hidden response by α in the structured family, curve and secant cost the same at α = 0, and the curve is cheaper for every α above 0 with both kernels. Its cost does not change with α, while the secant's certified response loss grows as α², as Proposition 2 predicts. In the network, curves gain 0.08 [0.02, 0.12] in mean log₁₀ gap over affine responses in the flattest valleys at 1000d, with no broad aggregate advantage.

Q1, part 2: implementation or method? Both contribute, and we can quantify only part of it.

  • One controller choice is measured. The frozen controller stops only at poll radius 10⁻¹², so at 1000d it restarts 0.5–0.6 times per run against 5.1–12.0 for Powell, PRAXIS, and BOBYQA. A radius floor of 10⁻⁴ (Powell's xtol) improves the mean log₁₀ gap by 0.11–0.12, but Powell and restart CMA-ES remain significantly ahead (Section 6.4). This choice accounts for part of the gap, not all of it.
  • A second constant is measured. In a new sensitivity study (60,480 runs, all 24 functions, 200d), the initial poll radius matters, while σ and the scalar caps change the fraction of targets by at most 0.013 pooled over dimensions (more in 2D). Raising the initial radius from 1 to 4 lifts the curved controller from 0.325 to 0.351 of the targets, against 0.363 for Powell and 0.371 for BOBYQA (Table 4). This single grid point, not a tuned setting, closes more than half of the gap at this budget, and the effect persists at 1000d.
  • The controller is minimal. It keeps no direction set across cycles, as Powell does, and builds no quadratic model, as BOBYQA does. A development controller that also admits learned response slopes as directions reaches 0.454 of the targets at 1000d, against 0.406 for the frozen instance and 0.504 for Powell (Table 4); this comparison is descriptive.
  • Learning has a structural cost. Each history chart costs up to 52 evaluations (27 for anchors, 25 for the path search). Below about 50d this cost is not repaid; at 10d the three geometries give identical results in 2,118 of 2,160 runs, because the budget ends before a chart matters.
  • Other factors are not separated: chart selection, response errors, and the rest of the search strategy.

The flat-valley study in the general response (follow-up 3) gives a direct example of how much implementation matters. A single rule, the size of the navigation window, decides between failing in every valley-floor run and reaching 10⁻⁸ in 16/16 runs at A/μ = 10⁴ in 2D to 40D, where BOBYQA, CMA-ES, and Powell mostly fail. Within BBOB's matched controller, conditional responses improve on straight search by 0.20–0.36 in mean log₁₀ gap at 200–1000d; closing the remaining gap to mature solvers on generic functions is open work.

Q2: which guarantees hold for the actual algorithm? The table in the general response states this result by result. In short:

  • Holds: every evaluation is charged, the returned point is the best actually evaluated, a history-chart cycle costs at most 27d+52 evaluations, and the curvature identity, Eq. (4), describes each smooth segment of its fitted paths.
  • Holds only for an idealized version: Proposition S7 gives subsequence stationarity under exact arithmetic, unlimited iterations, completed polls, and no positive radius floor; the finite-budget code receives no stationarity certificate.
  • Not inherited: Theorem 5 and the chart certificates, which need a supplied chart, valid bounds, and their structural assumptions.

The theory is still informative for the actual algorithm: it names the conditions under which learning a response pays, namely enough accuracy of the response and its slope, a response inside the navigation domain, and a straightening loss that is large compared with the reduced decrease. The tolerance follow-up confirms the first condition: matching the tolerances to the target lets the curve reach 10⁻⁶ in 192/192 runs, against 115/192 for the tangent.

Thank you for your rebuttal. I have read and acknowledged your responses.

Thank you for reading our responses. One new result bears directly on your Q1, so we flag it here; the details are in the final general update posted today.

  • Testing the explanation we gave in Q1, part 1. We suggested that the local 25-call path search might be why curves tie with affine responses, and we tested it. On the network with new seeds, conditional responses again beat straight search (95 against 61 of 128 runs reach gap 10⁻⁸ at 1000d) and curves stay level with affine responses; spending part of the path budget on grid probes does not help, and on 15 new BBOB instances (233,280 runs) neither a 60-call search nor a near-exhaustive scan of each path changes the curve–affine tie. The diagnostics point instead to the chart and the response model, and replacing the chart module repairs the failures (next point). What limits curvature on BBOB remains open.
  • When curvature pays. With paid Brent anchors instead of exact ones and up to 100D, the curve reaches relative 10⁻⁸ in 128/128 runs at A/μ = 10⁸, against 0/128 for the matched affine response and 64/128 for analytic-gradient BFGS. On coupled valleys, where the submitted controller fails, replacing only the chart module by paid discovery of the coupled coordinates gives 384/384 runs within 300d, against 192/384 for BFGS; at A/μ = 10⁴ BFGS remains cheaper.

If these points answer your Q1, we would be grateful if you took them into account in your final assessment.

Reviewer_V4rpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies optimization using only function values by learning conditional minimizer responses and searching along the resulting paths. The framework connects Powell’s conjugate directions to curved search trajectories, accounts for the evaluations needed to learn responses, and provides guarantees for approximation errors, scalar search, and information reuse. Experiments demonstrate substantial benefits on structured curved valleys, while affine responses capture most of the observed gains on standard benchmarks and in diagonal linear network training.

Critical strengths
  1. The connection between conjugate directions and conditional minimizer curves is intuitive, and the analysis explains when curvature can improve search.
  2. The complexity analysis explicitly charges for learning and refining responses, making the guarantees more informative.
  3. The controlled experiments isolate the effects of path geometry, scalar proposals, and reuse under matched evaluation budgets.
Critical weaknesses
  1. The benefits of curvature are mainly demonstrated on structured problems, with no clear aggregate advantage over affine responses on the other tasks.
  2. The strongest guarantees require supplied charts and regularity bounds whose availability in general applications remains unclear.
  3. The response acquisition theorem differs from the practical implementation, whose stationarity guarantee relies on the coordinate poll.
  4. The COCP proposals offer inconsistent benefits over BB and DIRECT, leaving their practical role somewhat unclear.
  5. Tangents reach the stricter target more often than curves under the reported budget, and this reversal deserves a clearer explanation.
Questions for authors

Please refer to weaknesses.

2 comments

Thank you for a precise review. Your summary matches our intent, and your five points are the questions we most needed to answer. The general response gives the overview; here are the details.

W1: curvature pays mainly on structured problems. We agree that curved responses show no broad aggregate advantage over affine responses on BBOB or in the network. In the network, curves are ahead by 0.08 [0.02, 0.12] in mean log₁₀ gap at c = 0.003 and 1000d, and behind by 0.02 [0.002, 0.05] at 100d (Supplement S8). The question is when curvature is worth its cost. Proposition 2 says that a straight path pays a loss growing like h⁴‖s*″‖² at step length h, where s*″ is the curvature of the ideal response. We tested this in a controlled follow-up, scaling the curvature of the hidden response by α ∈ {0, 0.1, 0.3, 1, 1.5} in two settings (32 new seeds, 1024 evaluations):

  • at α = 0, curve and secant cost the same (2D with both kernels, 8D with BB; 8D with COCP differs by 1.4 evaluations);
  • for every α above 0, the curve is cheaper with both kernels; at α = 1 the COCP savings are 89 [69, 113] evaluations in 2D and 552 [537, 566] in 8D;
  • the curve's cost does not change with α (about 38 evaluations in 2D, 231–251 in 8D), while the secant's certified response loss grows as α²: its ratio to α² stays at 1.81–1.89 in 2D and 0.46–0.48 in 8D.

The secant's total cost is not monotone in α (it is higher at α = 0.1 than at 0.3), so the squared-curvature law governs the response loss, not the whole adaptive cost. Why, then, no aggregate gain on BBOB and the network? A fixed-chart diagnostic (general response, part 3) rules out nearly affine responses, and in the network also anchor error. On 380 network and 96 BBOB charts, the responses are clearly curved (median deviation from a line of 0.11 and 0.19 of the window), and the network anchors are exact to rounding. Curves fit the responses better, but the better fit does not consistently turn into decrease; the local 25-call scalar search on often multimodal path profiles is a plausible limitation. On flat valleys, where this step works, the curve succeeds in 48/48 runs where the matched affine response succeeds in none.

W2: supplied charts and bounds. The three instances receive different information: the certified instance receives charts and valid bounds, the network instance receives factor pairs from the architecture, and the black-box instance builds charts from its history without bounds. The certificates and Theorem 5 require the supplied information, and discovering suitable charts automatically remains open. What the theory contributes beyond the certified setting is a list of measurable conditions that decide whether a learned response pays: the accuracy of the response and of its slope, the response staying inside the navigation domain, and the straightening loss compared with the reduced decrease. The follow-ups test three of them: tolerance matching, response curvature, and the response domain. Widening only the navigation window turned the empirical controller from 0/16 to 16/16 successes on flat valleys, where mature solvers mostly fail (general response, follow-up 3).

W3: the acquisition theorem and the implementation. Theorem 5 is an exact-arithmetic construction with golden-section anchors, under the assumptions listed in the general response. The black-box instance uses nine-call Brent anchors and does not inherit its bound. Its safeguard result, Proposition S7, concerns an idealized search-and-poll policy (exact arithmetic, unlimited iterations, completed polls, no positive radius floor). Under those conditions a subsequence of unsuccessful poll centers satisfies ‖∇F(y)‖ ≤ √d (L/2 + σ) δ → 0, whatever the proposed paths. The finite-budget code, with its 10⁻¹² radius floor, keeps its best evaluated point but receives no stationarity certificate. This follows the search-and-poll design of pattern search (Kolda et al., 2003): proposals may be heuristic, and the safeguard does not depend on them. The revision states these scopes explicitly (table in the general response).

W4: role of COCP relative to BB and DIRECT. We agree that COCP is not uniformly better. Under valid tight bounds BB is cheaper: 204.29 against 236.98 capped first-hit evaluations at 10⁻⁴ in the submitted study, and 425 against 491 at 10⁻⁶ in the new tolerance study (paired difference 65 [60, 71]). On multimodal one-dimensional profiles without curvature bounds, COCP proposals improve on a matched bisection control by 0.16–0.35 in mean log₁₀ gap at 8–64 evaluations, while DIRECT is stronger from 32 evaluations on (Section 6.2). The geometric results hold with either kernel: curves beat secants by 279.58 evaluations with COCP and 247.87 with BB (Table 2), and the curvature sweep shows the same pattern with both kernels. The revision presents COCP as one interchangeable proposal kernel with a limited low-budget role, not as a component on which the other results depend.

W5: tangents reach the stricter target more often. The reversal is real: in the submitted study the tangent reaches 10⁻⁶ in 54/192 runs and the curve in 22/192 (1024 evaluations), all in the uncoupled 2D settings. Both the response/path tolerances (10⁻⁴) and an eight-sweep cap had been set for the primary 10⁻⁴ target, so we separated them in a 2 × 2 follow-up: tolerances 10⁻⁴ versus ε/(4r) with ε = 10⁻⁶ and r = d/2 blocks, crossed with the sweep cap (8 versus the full budget). It uses the same six settings, 32 new seeds per setting, all five strategies, and budgets 1024 and 4096, with the other local caps and the refinement depth fixed.

10⁻⁶ successes (of 192)Original tol., 1024Tight tol., 1024Tight tol., 4096
COCP curve27160192
COCP tangent5573115
COCP secant173281
BB curve14162192
  • At the original budget with tight tolerances, the capped first-hit costs are 353 (curve) and 798 (tangent) evaluations; the paired difference is −445.00 [−465.21, −422.43]. The 32 remaining curve misses all occur in the sine 8D setting.
  • At 4096 evaluations the capped costs are 490.58, 2379.02, and 3017.85 for curve, tangent, and secant; curve minus tangent is −1888.44 [−1991.06, −1778.53].
  • Raising the sweep cap changes no first-hit outcome in any of the 3,840 matched pairs, at 10⁻⁴, 10⁻⁶, or 10⁻⁸.

The joint tolerance setting therefore accounts for the reversal at the target it is matched to; the design does not separate the response tolerance from the path tolerance. At 10⁻⁸, two orders below the matched tolerance, the curve leads at 1024 evaluations (81 against 66 successes) and the tangent at 4096 (104 against 88). This is consistent with the same mechanism, and we do not claim superiority at every accuracy. These are observed target hits, not global certificates. The revision adds a paragraph to Section 6.1 and the full tables to an appendix, and keeps the submitted cohort's results unchanged.

We would be grateful to know whether these answers address your concerns, especially W1 and W5.

Reviewer_zmzEOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper approaches nonconvex optimization by offering an affine "local best path" oracle to the optimizer, which can be queried at a cost which is charged to the overall training computational budget. The best path is estimated from past points that the loss function was evaluated at; this enables the optimizer to perform a line search along the (possibly curved) best path, as opposed to only doing line searches along line trajectories in the original parameter search space. They present analyses of their optimizer and evaluate it in experiments.

Critical strengths

The paper attacks an interesting and intuitive geometric direction, that of descent through curved valleys; furthermore, I believe from past literature that these valleys exist in deep learning optimization.

The paper provides thorough theoretical analysis of the benefit of this curve following, including examples to help the reader follow.

Critical weaknesses

This paper is not well self-contained. The introduction should be understandable to the average reader, but instead it relies heavily on terms such as "Powell’s parallel-subspace construction", "chart certificates", "Hessian-conjugate" without minimal explanations of what they are or why they are desirable.

The paper leaves definition of several notations to the reader, including (most crucially) C.

Algorithm 1 is insufficiently specific; see question 5 below about line 226.

The paper lacks explanations on how delta, sigma, and the "sufficient decrease" threshold on line 232 are chosen, or alternatively - how difficult it was to find them computationally and how robust they are to error or optimization scenario change. It also lacks an ablation study evaluating their importance.

The mechanism for computing a "response" is unclear, as well as what exactly is reused and how, as well as the mechanism for determining the price paid by the optimizer for each response evaluation.

The paper compares their optimizer against various obscure optimizers and Powell's method, but not against standard popular optimizers like Adam, SGD, Muon, etc. They also failed to demonstrate the practical value of the optimization scenarios they presented; in other words, it is unclear when a loss function similar to those the proposed optimizer is evaluated on in the paper would show up outside of this paper's evaluation section.

Questions for authors
  1. Line 149: What is meant by "F is in C^2"? You already defined F as the loss function, i.e. a function from the search space to the real line. Furthermore, please define all of your notations, including C (is it a matrix, since we're multiplying s by it on line 142? A search space, since F belongs to it? A vector, since it's in a span on line 143?); it would help to define a notational system (e.g. all upper cases are matrices, all lower cases are scalars unless they have a line over them, in which case they are vectors...) and remain consistent to it.

  2. Line 150: What is "the implicit theorem"? Why does it give those equations? Why is it valuable for C and gamma* to be Hessian-conjugate?

  3. What is a "conditional minimizer"? What are "Brent searches/anchors"?

  4. Line 196: what are y_i? What are those "blocks" you refer to? And it looks like you have a self-referencing definition there - the definition of F depends on e_i which depends on p_i, which in turn is defined as a response - which, if I understand correctly, depends on F (depicting a valley in F). What are those "baselines" you refer to?

  5. Line 226: How do you select a chart? Does selecting a chart refer to selecting a and C? How robust is your algorithm to poor chart selection? This seems like a critical and central element of your algorthm, and it is not present in the paper.

  6. Line 227: How do you "Acquire paid conditional anchors and fit a feasible response P"?

  7. Line 232: What is an "unsuccessful poll"?

  8. How well does P match s? How much of an effect does that have on the optimization?

  9. Line 410: Why are you calling that model a "network"? It seems to me to be a simple least squares system-of-linear-equations problem alongside a weight decay (that I have never seen before and does not match the weight decay penalties usually used in machine learning regularization).

  10. What are COCP? BB? The paper keeps bringing them up as well as using them as baselines, but they are not explained in the paper.

  11. Under what circumstances (that can be decided before optimization begins and much computational cost has been sunk into the optimization effort) should one use the proposed optimizer instead of more standard choices like gradient descent?

4 comments

Thank you for the detailed questions. We agree that the paper was too compact for a general reader, and your list has served as our checklist. The revised PDF (changes in blue) opens Section 3 with a setting-and-notation paragraph that defines C2,CC^2, C, the conditional minimizer, anchors, and Brent searches; it also defines Hessian conjugacy, COCP, and the poll where they first appear. We answer in your numbering.

Setting (also W6). The method observes only function values; no gradients are used (derivative-free, or zeroth-order, optimization). This is why the baselines are Powell's method, BOBYQA, PRAXIS, and CMA-ES, the standard solvers in this setting, rather than SGD, Adam, or Muon, which require gradients.

Q1 (line 149) and W2: notation. "F∈C2F \in C^2" means that F is twice continuously differentiable; C2C^2 is a class of functions, not a search space. In the chart Φ(t, s) = x + ta + Cs:

  • x∈Rdx\in\mathbb{R}^d is the current point and a∈Rda \in \mathbb{R}^d is the baseline direction;
  • C∈Rd×mC \in \mathbb{R}^{d×m} is a matrix whose m columns are the navigation directions;
  • t∈Rt\in\mathbb{R} is the scalar baseline coordinate and s ∈ ℝᵐ collects the navigation coordinates;
  • span{a, C} is the span of a and the columns of C.

We write q(t, s) = F(x + ta + Cs). Subscripts on q denote partial derivatives, for example qₛ = ∂q/∂s and qₛₛ = ∂²q/∂s². In the black-box instance m = 1, so C is a single vector and s a scalar.

Q2 (line 150): the implicit function theorem and conjugacy. This is the implicit function theorem of calculus. Suppose that for each t the conditional minimizer s*(t) is unique and interior and that qₛₛ is positive definite there. Then s* is differentiable, and differentiating the identity qₛ(t, s*(t)) = 0 in t gives qₛₜ + qₛₛ s*′(t) = 0, the first part of Eq. (2). For the affine chart, qₛₛ = Cᵀ∇²F C and qₛₜ = Cᵀ∇²F a, so Cᵀ∇²F (a + C s*′) = 0, that is, Cᵀ∇²F γ*′ = 0. Two vectors u and v are Hessian-conjugate when uᵀ∇²F v = 0. This is useful for three reasons.

  1. Moving along γ* keeps the navigation coordinates optimal, so the path follows the valley floor instead of climbing its walls.
  2. Along γ*, the curvature in t drops from qₜₜ to the Schur complement qₜₜ − qₜₛ qₛₛ⁻¹ qₛₜ (Eq. (3)), so in a narrow valley much longer steps are possible than along a coordinate.
  3. For a strictly convex quadratic F, this is the parallel-subspace property behind Powell's method (Prop. 1): the minimizers over two parallel subspaces differ by a direction conjugate to them. Exact line searches along d mutually conjugate directions minimize such a quadratic in d steps, and later searches do not undo earlier ones. Our paths are the curved generalization of these lines.

A "chart certificate" (Prop. 3) is a verifiable lower bound on the minimum of F within a chart, so the gap between the best value found and that minimum has a verifiable upper bound.

Q3: conditional minimizer, Brent searches, anchors. The conditional minimizer s*(t) minimizes F(x + ta + Cs) over s for a fixed t; it gives the best navigation coordinates for each value of the baseline coordinate. For example, for the valley A(s − t²)² + μ(1 − t)² with the chart along t and s, it is s*(t) = t², the valley floor. Brent's method is the classical derivative-free one-dimensional minimizer that combines golden-section steps with parabolic interpolation (Brent, 1973; the default of SciPy's minimize_scalar). A "Brent search" is one run of it on a bounded interval with a cap on evaluations. An anchor is a baseline value tₖ at which we pay for such a search over s to estimate s*(tₖ).

Q4 (line 196): the structured family. Eq. (5) is a synthetic test family. Its variables come in r blocks; block i has one baseline coordinate yᵢ and one navigation coordinate zᵢ. The functions pᵢ are fixed by the experimenter (quadratic or sinusoidal, drawn from the instance seed), and eᵢ = zᵢ − pᵢ(yᵢ) − λyᵢ₋₁ measures how far zᵢ is from the valley floor. Since ψ(e) ≥ e² and ψ(0) = 0, the best zᵢ for given y is pᵢ(yᵢ) + λyᵢ₋₁. There is no circularity: the pᵢ are fixed first and F is built from them. The optimizer never sees pᵢ; it learns this relation from evaluations of F, which lets us measure response errors exactly (Q8). A "baseline" is the coordinate along which a chart moves (here yᵢ).

Q5 (line 226) and W3: choosing a chart. Yes, choosing a chart means choosing a and C, together with the ranges of t and s. Each instance has its own rule.

  • Black-box instance (BBOB): each cycle first sweeps the coordinates with bounded Brent searches. a is the displacement of this sweep and C is the previous cycle's displacement made orthogonal to a (a coordinate direction if that is degenerate). The range of t has radius min(8, max(δ, ‖a‖)), and that of s has radius δ.
  • Certified instance (structured family): the charts are supplied, one per baseline coordinate, containing every navigator that coordinate affects.
  • Network: each chart pairs uᵢ with vᵢ.

A poor chart cannot lower the best value found, because every evaluated point is kept, and one history chart costs at most 52 evaluations beyond the sweep and the poll. Repeatedly poor charts do waste budget, and the paper gives no guarantee that the history rule finds good charts. On BBOB at 200–1000d, history charts improve on the straight control, which uses no response.

Q6 (line 227): anchors and the fitted response. At t ∈ {−r, 0, r}, with r the radius above, a Brent search of at most 9 evaluations over s, with t fixed, returns an anchor response. The affine and curved responses use the same three anchors. The curved response is the quadratic through all three; the affine response passes through the center anchor with the slope of the secant between the outer two. "Feasible" means that the path stays in the range of s: the affine path is restricted to its feasible interval, and a curve that leaves the range is replaced by a piecewise interpolant. The response stays frozen during the subsequent search, which evaluates F itself along the path.

Q7 (line 232): unsuccessful poll; W4: δ, σ, and the threshold. A cycle is successful when it lowers F by at least σδ². After a successful cycle, δ is multiplied by 1.5 (up to 8) if some improving coordinate step had length at least 0.8δ, and kept otherwise. If the cycle falls short, a poll evaluates y ± δeᵢ around its fixed best point y. The poll succeeds as soon as one candidate improves F(y) by at least σδ². It is unsuccessful when all 2d candidates have been checked without such an improvement, and then δ is halved. This is standard pattern-search terminology (Kolda et al., 2003). The prototype starts with δ = 1 and uses σ = 10⁻⁴, with caps of 25 evaluations per path search and 9 per anchor. These values were fixed during development on pilot instances and frozen before the confirmation runs on new instances; the same values serve all functions, dimensions, and budgets.

Sensitivity (new). Following your question, we varied each constant on its own on all 24 BBOB functions in 2–40D (15 instances, 200d, 60,480 runs, protocol frozen before the run). Pooled over all functions and dimensions, changing σ to 10⁻⁶ or 10⁻², the path-search cap to 15 or 40, the anchor cap to 5 or 15, or the expansion factor to 2 changes the fraction of COCO targets reached by at most 0.013 for every geometry. The pooled figure hides a low-dimensional exception. In 2D, an anchor cap of 5 lowers attainment by about 0.07 (intervals excluding zero), and σ = 10⁻² raises the curve's by 0.03. At 200d, from 3D upward, none of these changes exceeds 0.02. The initial radius matters, mostly in 2–5D: pooled, δ = 0.25 lowers attainment by 0.04–0.06 and δ = 4 raises it by 0.02–0.03, so our default δ = 1 is conservative for the COCO domain [−5, 5]ᵈ. Our prediction of insensitivity therefore held for the pooled effects of σ, the caps, and the expansion factor, but failed for the initial radius and for 2D. Affine responses keep a lower mean log₁₀ gap than straight search under every setting (by 0.04–0.23; intervals exclude zero in four of eight settings), and the curve–affine difference stays unresolved under all. The default runs reproduce Table 4 (0.325, 0.328, and 0.309 for curve, affine, and straight). A second cohort at 1000d in 2–20D (50,400 runs) gives the same picture: observed pooled changes of at most 0.018 (with exceptions in 2D and 3D), the affine advantage over straight search resolved under all eight settings, and an initial-radius effect that remains material, with no resolved change between the two budgets.

W5: cost and reuse. Every new function evaluation costs one unit of the budget, whatever its purpose. A history-chart cycle costs at most 27d+52 evaluations: at most 25d for the sweep, 27 for the anchors, 25 for the path search, and 2d for the poll. Reuse takes two forms. The black-box instance retrieves identical points already evaluated from a cache and selects directions from past displacements. The certified instance also transports cached value intervals to a changed problem under stated drift bounds, Eq. (9), charging every refresh. This cuts the total cost of certifying a changing problem by 27–69% relative to keeping only the previous solution and its certificate (Section 6.1).

Q8: how well P matches s*. Position accuracy alone is not enough: the conjugacy defect of a fitted path depends on both the error P − s* and its slope. On the structured family, where s* is known, the median certified response-loss bound at the first refinement level is about 9 × 10⁻⁶ for curves and 1.38 for secants. Secants need 15.6 interval splits per run against 3.3, and on average 279.58 [260.89, 300.81] more evaluations to reach 10⁻⁴ (Table 2). These compare complete strategies, not position error alone. In the network, exact parabolic anchors make the three anchor positions exact, but not the fitted response between them.

Q9 (line 410): why "network", and the weight decay. "Diagonal linear network" is the standard name in the literature on implicit bias (Woodworth et al., 2020) for the two-layer linear model x ↦ vᵀ diag(u) x = ⟨u ⊙ v, x⟩, whose first layer is diagonal. The penalty (λ/2)(‖u‖² + ‖v‖²) is ordinary L2 weight decay on all parameters θ = (u, v), the penalty behind the update θ ← θ − η(∇L(θ) + λθ). Prediction is linear in w = u ⊙ v, but optimization is over the factors, and the objective is nonconvex in (u, v). Rescaling (uᵢ, vᵢ) to (cuᵢ, vᵢ/c) leaves the data term unchanged, so its minimizers form curved valleys uᵢvᵢ = wᵢ, and weight decay tilts each valley toward |uᵢ| = |vᵢ|. The minimum equals the Lasso optimum (Hoff, 2017), which we certify numerically to within 1.8 × 10⁻¹⁴, so optimality gaps can be measured. The experiment is a controlled value-only study of this mechanism, not a claim about training deep networks.

Q10: COCP and BB. Both are scalar kernels, one-dimensional search routines inside our method; they can serve both in the anchor searches and in the search along a frozen path. The chart rule and the response model are separate choices. COCP (convolutional optimization with convex kernels and power lifting; Lu, 2025) proposes the minimizer of the convex surrogate K(z) = ∫ |z − u| exp(−βf(u)) du, a weighted median, as a nonlocal candidate. BB is a branch-and-bound search that samples the cell whose valid quadratic lower bound, Eq. (6), is lowest. The baselines are Powell, PRAXIS, BOBYQA, CMA-ES, coordinate Brent, Nelder–Mead, and DIRECT.

W6: standard optimizers and practical value. SGD, Adam, and Muon use gradients, which our information model excludes. Their value-only counterparts estimate gradients from differences of function values (zeroth-order SGD, Ghadimi and Lan, 2013; ZO-AdaMM, Chen et al., 2019; MeZO, Malladi et al., 2023). We have not compared against them, and we make no claim against gradient-based training. Value-only problems arise with simulators, non-differentiable pipelines, hyperparameter tuning, and fine-tuning by forward passes (MeZO). Curved valleys of the kind we study arise from factorized parameters with weight decay (u ⊙ v as in Section 6.3, or low-rank factors) and from separable nonlinear least squares (Golub and Pereyra, 1973), whose conditional elimination motivates the paper.

Q11: when to use the method. We cannot offer a test that decides in advance, for an arbitrary objective, that this method beats BOBYQA or Powell. The conditions under which it is worth trying are:

  1. only function values are available; with reliable gradients, a gradient method is the natural choice;
  2. some coordinates compensate for one another, for example factor pairs or coupled blocks, so that a chart can be supplied or learned;
  3. the budget is at least a few hundred evaluations per dimension: affine responses repaid their acquisition cost on BBOB from 200d and in the network at 1000d, but not at 10–50d.

The clearest case is a flat curved valley. There, Theorem A.16 shows that gradient descent with step sizes below 2/L, and any line search whose accepted segments stay in the current sublevel set, needs a number of steps that grows with the flatness. In our follow-up (general response, item 3), the controller reached 10⁻⁸ in 16/16 runs from 2D to 40D at A/μ = 10⁴, where BOBYQA, CMA-ES, and Powell mostly failed. On generic benchmarks we currently recommend BOBYQA, Powell, or CMA-ES, which lead on BBOB.

If any concern about correctness remains after these clarifications, we would be glad to address it specifically.

Comments on the paper

4 comments
AuthorsOpenReview ↗

General response and three points for clarification

We thank the reviewers. V4rp and ENMG identify what we regard as the paper's core: the link between conjugate directions and conditional-minimizer curves, and an analysis that charges for learning the response instead of treating it as a free oracle. zmzE finds descent through curved valleys an interesting direction and asks for a more self-contained presentation. We want to make the following points clear to facilitate the reviewers' reassessment.

Aim and present scope. Gradient, Newton-type, and direction-set methods all move along straight segments built from local information. Our aim is a search primitive beyond this line paradigm: the search follows learned conditional responses instead. Theorem A.16 makes the limitation precise. On flat curved valleys, every method whose accepted segments stay in the current sublevel set needs a number of iterations growing like (A/μ)^(1/4), whatever information it uses; this class includes gradient descent with step sizes below 2/L and exact line searches along any adaptively chosen directions. A conjugate-curve search in an aligned chart needs a constant number of evaluations. Follow-up 3 below shows this separation in practice against mature solvers. The present controller does not yet lead mature solvers on generic benchmarks such as BBOB, and we report this openly.

What the paper establishes. Within a supplied chart, Theorem 5 bounds the total number of queries needed to learn a conditional response and to search along it, so the benefit of following a valley is weighed against the cost of finding it. Under its stated assumptions (one navigator, the residual model q = b(t) + κψ(s − p(t)), strictly unimodal conditional profiles with an interior margin, exact values), acquisition keeps a factor (KR²/ε)^(1/6) for general smooth responses, and only a logarithmic dependence on the transverse stiffness K when the response is quadratic. The theorem does not pay for discovering a chart, and it is not a bound for the nine-call Brent anchors of the black-box instance. Matched controls under equal budgets then separate three effects: learning a response, bending it, and the scalar proposal rule.

Follow-up experiments. Each uses new seeds and a protocol frozen before its confirmation run; all outcomes are reported, with 95% paired seed-cluster bootstrap intervals (no multiplicity correction).

  1. High-accuracy reversal (V4rp, W5). Matching the response and path tolerances to the 10⁻⁶ target, with everything else fixed, raises curve successes from 27/192 to 160/192 at the original budget of 1024 evaluations, against 55/192 to 73/192 for the tangent. The paired difference in capped first-hit cost is −445 evaluations [−465, −422]. At 4096 evaluations the curve reaches 192/192, the tangent 115/192, and the secant 81/192. Allowing more sweeps changes no first-hit outcome in any of the 3,840 matched pairs.
  2. Response-curvature sweep (V4rp, W1; ENMG, Q1). We scale the curvature of the hidden response by α ∈ {0, 0.1, 0.3, 1, 1.5}. At α = 0, curve and secant cost the same; for every α above 0 the curve is cheaper in both settings and with both kernels, with intervals excluding zero. The curve's cost does not change with α, while the secant's certified response loss grows in proportion to α².
  3. Flat curved valleys against mature solvers (ENMG). We compared the empirical pair-chart controller with Powell, BOBYQA, and CMA-ES on flat valleys in 2D, 10D, and 40D, with only the coordinate pairing supplied. It first failed: from valley-floor starts it reached the relative target 10⁻⁸ in 0 of 180 runs, against 16 for Powell and 63 for BOBYQA. The trajectories show why: the navigation window equalled the poll radius, so the exact conditional minimizer, several units away, was clipped and the fitted response degenerated into a line; the response left its domain, violating the interior-margin assumption of Theorem 5. A follow-up designed after this result, frozen and run on new seeds, enlarged only this window. At A/μ = 10⁴ from valley-floor starts, the curve then reached 10⁻⁸ in 16/16 runs in each dimension, with mean costs of 194, 1,178, and 25,542 evaluations (2D, 10D, 40D). BOBYQA reached it in 16, 3, and 0 of 16 runs, CMA-ES in 6, 0, and 0, and Powell in none. The curve also beat affine responses in every dimension (paired differences −260 [−301, −216], −1,229 [−1,382, −1,032], and −2,377 [−2,701, −2,005] evaluations). The anchors use exact conditional parabolas, which this valley family admits. Part 3 of this response reports the flattest case, A/μ = 10⁸, and a fixed-chart diagnostic. The original negative result stays reported unchanged.

Setting. The method observes only function values (derivative-free, or zeroth-order, optimization). Every evaluation, including those spent on learning responses, is charged to one budget.

Which result applies to which instance (V4rp, W2–W3; ENMG, Q2). The certified instance receives charts and valid bounds; the network instance receives factor pairs from the architecture; the black-box instance on BBOB builds charts from its search history and receives no bounds.

ResultAssumptionsBlack-box instance
Eq. (2): the ideal response is Hessian-conjugate to the navigatorssmooth F, unique interior conditional minimizer, qₛₛ positive definiteDescribes the ideal response; a fitted path satisfies it only approximately
Eq. (4): curvature of a fitted path = Schur term + conjugacy defect + residual accelerationpath and F twice differentiable, qₛₛ invertibleAn identity on each smooth segment of any fitted path
Prop. 2: cost of straighteningconstant Q and quadratic ideal response; locally up to O(h⁵)Explains when bending can pay; not a bound for an arbitrary fit
Props. 3–4, Thm. 5: certificates and query boundssupplied chart and valid bounds (Thm. 5: also the assumptions listed in part 1 of this response)Not inherited; no certificate is claimed for black-box runs
Prop. S7: subsequence stationarityidealized search-and-poll policy: exact arithmetic, unlimited iterations, completed polls, no positive radius floor; F bounded below with Lipschitz gradientThe finite-budget code (radius floor 10⁻¹²) keeps its best evaluated point but receives no stationarity certificate
Thm. A.16: lower bound for line searches whose accepted segments stay in the current sublevel setthe method class (a, b); an aligned chart (c)The lower bound concerns that class only; the 13-evaluation construction needs the aligned chart

Revision. We have uploaded a revised PDF. Changes are marked in blue, and the main text stays within ten pages:

  1. Section 3 opens with a setting-and-notation paragraph; Brent searches, anchors, the poll, COCP, and BB are defined where they first appear.
  2. Section 4 states the exact rules of the black-box instance: poll success and failure, the radius update, and the constants and how they were fixed.
  3. Section 5 restates Proposition S7 for the idealized policy, and Table 6 (Appendix A.12) repeats the table above.
  4. Section 6.1 adds the target-matched tolerances, Section 6.4 the fixed-chart diagnostic and the sensitivity study, and a new Section 6.5 with Table 5 reports the flat-valley study. Appendix A.13–A.14 give all follow-up results, including those that did not support our expectations.
  5. Abstract (also updated in the submission form): after "curved paths need less than half the evaluations of secant paths that estimate conjugate lines" we added the clause "and on flat curved valleys a learned curve reaches the target where the matched affine response and Powell, BOBYQA, and CMA-ES do not". The rest of the abstract and the title are unchanged. The introduction and conclusion state the aim and the conditions under which bending pays; the paper makes no claim of a general-purpose solver advantage.

Flattest valleys, and a fixed-chart diagnostic. Both studies below were designed after the results in part 1, used new seeds, and froze their protocols before the confirmation runs. Every variant is reported, and the earlier negative results stay unchanged.

1. Flat valleys at A/μ = 10⁸. With only the window enlarged, no method, ours included, reached even 10⁻² from valley-floor starts at this flatness. The trajectories show why: the controller built a pair chart only after its coordinate sweep had moved that pair, and on such a flat floor the sweep barely moves, so the chart was skipped. A second follow-up let the supplied pair chart run even when the sweep had not moved (window ×8, forcing constant scaled by the paid initial value; 16 seeds per dimension).

  • Curve: 16/16 at 10⁻⁸ in 2D, 10D, and 40D, with mean costs of 139, 802, and 3,431 evaluations. These runs also meet a joint criterion on the distance along the valley, so the target is not met just by returning to the floor.
  • Affine response, identical settings and information: 0/48 at 10⁻⁸ (it reaches 10⁻² in 42/48). Curve minus affine: −1,861, −9,198, and −36,569 evaluations, with intervals within ±60.
  • Powell, BOBYQA, and CMA-ES: 0/48 at 10⁻⁸; only Powell reaches 10⁻², in 5 of 16 runs in 2D.

The matched comparison isolates bending: the same pairs, anchors, window, safeguards, and budget, differing only in whether the response is a line or a curve. This is the separation of Theorem A.16 observed in practice. The scope is limited: the three controller changes were made after seeing the failures; the pairing is supplied; the anchors use exact conditional parabolas; and the valleys are separable, up to 40D. From box starts at this flatness, relative attainment is high for every method (42–48 of 48) but can precede substantial progress along the valley, so those runs carry little information.

2. Fixed-chart diagnostic (V4rp, W1; ENMG, Q1). We froze one base point, direction, and window per chart. Charts were fixed in advance from cycles 0 and 4 of new runs: 380 network charts, and 96 BBOB charts from f8, f9, f10, f12, f15, and f20 in 5D and 20D. On each chart we compared the paid anchors, the affine and curved paths, and a reference response (analytic for the network, a refined grid for BBOB); diagnostic evaluations were charged separately.

  • Network: the paid anchors match the analytic response to rounding (median position error 1.6 × 10⁻¹⁶ of the window). The conditional responses are clearly curved, with a median RMS deviation from the best line of 0.11 of the window. Curves fit the response better on all 8 problems. Yet the best value found along a single chart favored the affine path on 4 problems and the curve on 1, with 3 unresolved. In 232 of 380 charts, the conditional profile has at least two local minima.
  • BBOB: the median deviation from a line is 0.19 of the window. The nine-call Brent anchors err by a median of 0.0026 of the window, more on multimodal functions. Curves fit better, while the single-chart gains vary by function.

What this changes. The tie between curved and affine responses on BBOB and the network is not explained by nearly affine responses, and in the network not by anchor error. A better response fit does not consistently turn into greater decrease within the budget; the local 25-call scalar search on often multimodal profiles is a plausible limitation. On flat valleys, once the response domain and chart activation are right, bending decides the outcome (48/48 against 0/48). Nonlocal scalar kernels along curved paths are a natural next step that we have not tested. The revised PDF reports the flat-valley study in Section 6.5 and both studies in full in Appendix A.13.

AuthorsOpenReview ↗

Final update: harder conditions, a modular repair, and a tested explanation

To help the final assessment, we summarize the additional experiments; protocols and full results are in Sections 6.3–6.5 and Appendices A.15–A.16 of the revised PDF (in blue). Every protocol was frozen by file hash before running on new seeds or instances, and every method and negative outcome is reported.

1. The flat-valley advantage survives harder conditions. We replaced the exact conditional parabolas by paid Brent searches, added 100D, and started some runs off the valley floor (15,616 runs). On quadratic and quartic transverse valleys the curve reaches relative 10⁻⁸ in 256/256 runs each, the matched affine response in 128/256. At flatness 10⁸ the curve succeeds in 128/128, affine in 0/128, and analytic-gradient BFGS in 64/128. In 100D at flatness 10⁸ the curve first hits the target after 10,494 function values and BFGS after 23,140 calls, each gradient counted as one call; at flatness 10⁴ BFGS needs only 1,603.

2. Where the submitted controller fails, and why. With supplied pairs alone, the curve fails on coupled valleys (0/192, even at 10⁻²) and mostly under unknown rotations (29/256). Diagnostics trace the coupling failure to a missing navigation direction and the sine and cubic losses to the error of the three-point response model; misses of the scalar search are not the main cause.

3. Each repair changes one module. Charts, responses, and scalar search are separate modules (Proposition 3). On coupled valleys we changed only the chart: given the pairs, paid queries identify which coordinates must move together (40 evaluations in 10D, 460 in 40D), and the three-anchor quadratic response is kept. In a confirmation on 16 new seeds (10D and 40D, flatness 10⁴ and 10⁸, two starts), on the 256 coupled cases the curve reaches relative 10⁻⁸ within 300d evaluations, discovery included, in 256/256 runs; the matched affine response reaches 0/256, the curve with the supplied pairs alone 0/256, BOBYQA and finite-difference L-BFGS 0/256, and analytic-gradient BFGS 128/256. Given 3000d, BFGS solves 383/384, so the gain is in cost: at flatness 10⁸ BFGS needs 3.7 to 13 times the curve's evaluations, while at 10⁴ it is 1.5 to 4.7 times cheaper. Every completed discovery recovered the coupling exactly. On sine and cubic profiles we changed only the response: a nine-anchor piecewise-quadratic response succeeds in 384/384 runs at 1000d, as does a piecewise-linear one on the same grid, at 521 against 880 evaluations per dimension; BFGS remains cheaper there, and unknown rotations remain unsolved. These are new instances of the framework, not the submitted algorithm, and carry no new certificate; the discovery cost grows quadratically with dimension.

4. Testing the explanation we offered. In part 3 of the general response we suggested that the local 25-call path search might be why curves tie with affine responses. We tested this. On the network with 16 new seeds, conditional responses again beat straight search: 95 against 61 of 128 runs reach gap 10⁻⁸ at 1000d, and 118 against 91 at 3000d; curves stay level with affine responses (93 and 117 of 128 for affine), and value-only BOBYQA and finite-difference L-BFGS reach 128/128; Table 12 also covers Adam, ZO-SGD, and ZO-Adam. Spending 9 of the 25 path calls on grid probes does not help (95 and 111), and in 530 diagnosed path searches, searching the same path more completely would never have improved the incumbent by 1% of the gap. The diagnostics point instead to the chart and the response model, which point 3 repairs on the valleys. On BBOB (15 new instances, 233,280 runs, protocol fixed in advance; Appendix A.16) the answer is the same: a 60-call search or a near-exhaustive 33-probe scan of each path leaves the curve–affine difference unchanged (interactions within 0.005 of zero), so path search is not the cause there either.

5. Standard BBOB on new instances. On all 24 functions in 2–40D, 15 new instances, and budgets up to 3000d (194,400 runs), curved and matched affine responses stay within noise of each other, apart from a small curve deficit at 100d. BOBYQA, Powell, PRAXIS, and finite-difference L-BFGS stay ahead at every budget, and BIPOP-CMA-ES at 10d and from 300d on, as the paper states (Appendix A.16).

In short, where the theory says bending pays, a learned curve with an adequate chart beats affine responses and mature value-only solvers and, at high flatness, needs fewer calls than analytic-gradient BFGS. The coupling and profile failures were each repaired by replacing a single module. Making chart discovery a general-purpose component is the next step.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.