- 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
-
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.
-
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.
-
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
-
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.
-
On BBOB, the proposed method still falls behind mature optimizers such as Powell, BOBYQA, and CMA-ES. This raises questions about its practical usefulness.
-
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
-
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.
-
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 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.
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.
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:
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.