Learning to Search Beyond Lines

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.