REVIEW 3 major objections 4 minor 42 references
Information Preserving Line Search via Bayesian Optimization
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Bayesian line search that keeps every evaluation solves more CUTEst problems
desk verdict Promising BO-based line search with real CUTEst results, but the convergence guarantee is only proved for the bracketing phase, not for the GP-driven refinement. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing machinery is the pair of the auxiliary function $\psi(\alpha) = \phi(\alpha) - (\phi(0) + \mu \phi'(0)\alpha)$ and the Moré–Thuente bracket update rules U1–U3: $\psi$'s sign and value at a candidate step certify that a strong-Wolfe step exists in the current interval, and the update rules shrink the interval while preserving that certificate. Around this core, the method conditions a Gaussian process with a Matérn $\nu = 5/2$ kernel on every observed function value and gradient, and uses the LCB acquisition function to propose the next candidate $\alpha$; when the acquisition search stalls, a kernel-density-estimation fallback selects the densest observed step in the interval. The convergence argument (Theorem 2) shows that expanding the initial bracket $[0, \min(1, \alpha_{\max})]$ by a constant factor $c > 1$ terminates in at most $\left\lceil \frac{1}{\alpha_0} \log_c\left(\min(\alpha_b, \alpha_{\max})\right)\right\rceil$ steps, where $\alpha_b$ is the point beyond which the sufficient-decrease condition can no longer hold.
What would settle it
Construct a smooth, bounded-below univariate objective where the LCB acquisition function and its fallback repeatedly select points that fail the Moré–Thuente update conditions, so the bisection fallback is triggered every round; if the line search then exceeds the proven bracket-expansion bound plus the Moré–Thuente iteration count without returning a strong-Wolfe step or $\alpha_{\max}$, the claimed convergence guarantee is false.
Extended reading notes
Core claim
The paper's central claim is that an inexact line search can be driven by Bayesian optimization without losing the convergence guarantee of classical strong-Wolfe line searches. By conditioning a Gaussian process on all observed function values and derivatives and picking the next candidate step with the Lower Confidence Bound acquisition function, the search retains information that interval refinement throws away, and can therefore identify steps that classical bracketing would miss. The reported evidence is that Bayesian GENO converges on 269 of 292 unconstrained and 156 of 163 bound-constrained CUTEst problems, outperforming the cubic-spline GENO, L-BFGS-B, and Ipopt baselines, and after an initial warm-up it matches or beats these baselines in evaluations needed to reach a given distance to the optimum. The authors also provide a proof that the initial interval expansion terminates in finitely many steps, after which Moré–Thuente's bracket updates are used to finish the line search.
Load-bearing premise
The convergence guarantee rests on the assumption that the Moré–Thuente interval-refinement invariant still holds when trial points are chosen by Bayesian optimization and the kernel-density fallback rather than by Moré–Thuente's safeguarded interpolation; the paper proves the initial bracket is found quickly, but does not prove that acquisition-chosen points always preserve the invariant needed for finite termination.
Editorial extensions
If this is right
- If the method works as claimed, line search no longer has to discard intermediate evaluations: every function value and gradient is reused, so a step that classical bracketing would miss becomes reachable.
- The reported CUTEst results imply that the method converges on more problems than the compared solvers, with fewer function evaluations to reach a fixed closeness to the optimum after the initial exploration phase.
- The higher per-evaluation overhead of the Gaussian-process surrogate is acceptable exactly when objective evaluations dominate the cost, which is the regime the method targets.
- Assuming the convergence proof holds, users get a finite-termination strong-Wolfe line search that is also information-efficient, usable inside quasi-Newton solvers for smooth bounded-below objectives.
Reading between the lines
- The paper proves the bracket-expansion bound, but the finite termination of the full line search is inherited from Moré–Thuente; whether arbitrary Bayesian-acquired points preserve the Moré–Thuente bracket invariant is not explicitly proven, so that inheritance is an unstated assumption.
- The comparison against Ipopt and L-BFGS-B changes both the line search and the whole solver, so the clearest evidence for the line-search idea comes from the Cubic GENO comparison, which isolates the line-search component.
- Treating the Gaussian-process noise parameter as measurement noise would let the same algorithm run on stochastic or noisy objectives, though the paper does not test that setting.
- A break-even analysis using the measured overheads in Fig. 3 would tell practitioners how expensive an objective must be before the extra per-step cost pays off.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a Bayesian optimization-based line search that retains all previously evaluated function values and gradients, builds a Gaussian process surrogate with a Matérn kernel, selects trial steps by maximizing the Lower Confidence Bound (LCB) acquisition function, and integrates the resulting line search into the GENO solver. The authors claim the method is guaranteed to converge and demonstrate empirically on 292 unconstrained and 163 bound-constrained CUTEst problems that their Bayesian GENO solver solves more problems and uses fewer function evaluations than several baselines.
Significance. If the convergence guarantee were fully established, this would be a useful contribution: the information-preserving idea is plausible, the empirical evaluation is broad and reproducible (code is provided), and the experimental results are encouraging. However, the current proof only covers the initial interval-expansion phase and does not establish finite termination of the actual refinement loop, which uses BO/LCB and KDE-based trial points. The paper's central theoretical claim is therefore not yet substantiated. The empirical study is a strength, but it cannot replace the missing proof of the advertised guarantee.
major comments (3)
- [Section 3.2 and 3.4] The finite-termination proof does not cover the refinement loop. Theorem 2 (Section 3.4) bounds only the number of expansions needed to find an interval satisfying the Moré-Thuente invariant or reaching αmax. The subsequent sentence, 'Since the interval found ... satisfies the invariant of Moré-Thuente up to reordering, the interval refinement process terminates in a finite number of iterations,' is the only bridge to the full algorithm. But the trial points in the refinement loop are selected by maximizing the LCB acquisition function over a GP posterior, with a KDE fallback, not by Moré-Thuente's safeguarded interpolation. Moré-Thuente's termination proof depends on their specific trial-point selection; no argument is given that arbitrary BO-selected points preserve the U1-U3 interval invariant, nor that forcing a bisection after two non-shrinking refinements yields a strong Wolfe step in finite time. This is the central gap between the theorem and the algorithm.
- [Section 3.3] The implementation contains an exit path that is not covered by the convergence claim. When the conditioning-step threshold is exceeded, the method 'return[s] the step in D ∩ [αmin, αmax] with the best function value.' This returned step is not shown to satisfy the strong Wolfe conditions, and it need not be αmax. The convergence conclusion in Section 3.4 permits only two outcomes: 'a step satisfying the strong Wolfe conditions or αmax.' Unless this threshold-exit path is proven to produce a strong Wolfe step, or the convergence claim is correspondingly weakened, the abstract's statement 'Our approach is guaranteed to converge' is unsupported.
- [Theorem 2, Section 3.4] The iteration-count bound in Theorem 2 is incorrect as written. Starting from α0, the number of updates of the form αu ← c·αu needed to reach at least min(αb, αmax) is ⌈log_c(min(αb, αmax)/α0)⌉, not ⌈(1/α0) log_c(min(αb, αmax))⌉. For example, with α0 = 0.5, αb = 1, and c = 2, the printed formula gives 0 updates, but one update is required before αu ≥ αb and hence ψ(αu) ≥ ψ(αl) is guaranteed. The proof's conclusion that 'we have found an interval' therefore does not follow from the stated iteration count.
minor comments (4)
- [Section 2.1, Corollary 1] The proof of Corollary 1 says 'we rename αl and αu' in the case ψ(αu) < ψ(αl) and ψ′(αu) ≥ 0. This renaming reverses the interval order and makes the condition ψ′(αl)(αu − αl) < 0 fail as written, so Theorem 1 is not directly applicable after renaming. The result is true and can be proved by continuity, but the proof should be corrected.
- [Section 4.1, Eq. (7)] The displayed gradient convergence criterion uses ∥g∥∞ in Eq. (7), but the surrounding text says ∥∇g∥∞. Please standardize the notation.
- [Section 3.3] Several hyperparameters that affect the algorithm are not specified numerically in the text: the LCB exploration coefficient κ, the interval shrink safeguard δ, the BO iteration threshold, and the GP noise variance σ². The code is available, but specifying typical values would improve reproducibility and clarity.
- [Figure 2] The normalization strategy for the function-evaluation plots is underspecified. In particular, it is unclear how problems are handled when a solver never discovers the value f⋆, and whether f⋆ is computed per solver or globally. Please clarify the procedure and state how undefined normalizations are treated.
Circularity Check
No circular derivation: the convergence guarantee rests on an external Moré–Thuente theorem (with a possible applicability gap), and the empirical claims are benchmarked independently on CUTEst.
full rationale
Walking the derivation chain, no step reduces to its own inputs by construction. The initial-interval expansion bound (Theorem 2, Section 3.4) is a genuine analytic bound on the number of interval doublings needed to reach a Wolfe-containing bracket or alpha_max; it does not presuppose the existence of a Wolfe point. The interval-refinement termination claim in Sections 3.2 and 3.4 is justified by citation to Moré and Thuente [25], an external result, not to the authors' own work. One can question whether that external theorem applies when trial points are generated by LCB maximization over a GP posterior rather than by Moré–Thuente's safeguarded interpolation, and whether the evaluation-limit return in Section 3.3 (best point in D) satisfies the Wolfe conditions. But that is a rigor/correctness gap, not circularity: the paper does not define the Wolfe condition in terms of its own BO output, nor does it fit a parameter and then rename it a prediction. The self-citations to GENO [19,21] and to Prusina and Laue [28] are used as solver infrastructure and as a baseline; they are not the load-bearing justification for the paper's convergence or performance claims. The main empirical claim is tested on the independent CUTEst benchmark against external solvers, so the central performance statement is not constructed from the paper's own assumptions. Overall, no circular step is exhibited.
Assumptions & free parameters
free parameters (5)
- LCB exploration coefficient κ =
not reported
- Interval expansion factor c =
not reported
- Interval shrink safeguard δ =
typically 2/3
- BO iteration threshold =
not reported
- GP noise variance σ^2 =
not reported
assumptions (5)
- domain assumption Objective f is continuously differentiable and bounded below on the feasible set.
- domain assumption Function and gradient evaluations are exact and deterministic.
- domain assumption Search direction p is a descent direction.
- standard math Moré-Thuente theorem and interval refinement convergence results.
- standard math Gaussian process posterior formulas and Matérn kernel with ν=5/2.
Cite this review
Pith. "Pith review of Information Preserving Line Search via Bayesian Optimization." pith.science (2026). https://pith.science/paper/TNC2ABXZ
@misc{pith2026250715485,
author = {Pith},
title = {Pith review of: Information Preserving Line Search via Bayesian Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/TNC2ABXZ}},
note = {Machine review of arXiv:2507.15485}
}
read the original abstract
Line search is a fundamental part of iterative optimization methods for unconstrained and bound-constrained optimization problems to determine suitable step lengths that provide sufficient improvement in each iteration. Traditional line search methods are based on iterative interval refinement, where valuable information about function value and gradient is discarded in each iteration. We propose a line search method via Bayesian optimization, preserving and utilizing otherwise discarded information to improve step-length choices. Our approach is guaranteed to converge and shows superior performance compared to state-of-the-art methods based on empirical tests on the challenging unconstrained and bound-constrained optimization problems from the CUTEst test set.
Figures
Reference graph
Works this paper leans on
-
[1]
Pacific Journal of mathematics16(1), 1–3 (1966)
Armijo, L.: Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics16(1), 1–3 (1966)
1966
-
[2]
IMA journal of numerical analysis 8(1), 141–148 (1988)
Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA journal of numerical analysis 8(1), 141–148 (1988)
work page 1988
-
[3]
arXiv preprint arXiv:1012.2599 (2010)
Brochu, E., Cora, V.M., De Freitas, N.: A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv:1012.2599 (2010)
arXiv 2010
-
[4]
In: IEEE Interna- tional Conference on Systems, Man, and Cybernetics
Cox, D., John, S.: A statistical method for global optimization. In: IEEE Interna- tional Conference on Systems, Man, and Cybernetics. pp. 1241–1246 vol.2 (1992)
work page 1992
-
[5]
DennisJr,J.E.,Schnabel,R.B.:Numericalmethodsforunconstrainedoptimization and nonlinear equations. SIAM (1996)
work page 1996
-
[6]
In: Proceedings of the AAAI conference on artificial intelligence
Fiedler, C., Scherer, C.W., Trimpe, S.: Practical and rigorous uncertainty bounds for gaussian process regression. In: Proceedings of the AAAI conference on artificial intelligence. vol. 35, pp. 7439–7447 (2021) 16 R. Labryga et al
work page 2021
-
[7]
Forrester, A., Sobester, A., Keane, A.: Engineering design via surrogate modelling: a practical guide. John Wiley & Sons (2008)
work page 2008
-
[8]
INFORMS journal on Computing21(4), 599–613 (2009)
Frazier, P., Powell, W., Dayanik, S.: The knowledge-gradient policy for correlated normal beliefs. INFORMS journal on Computing21(4), 599–613 (2009)
work page 2009
Show all 42 references
-
[9]
In: Recent advances in optimization and mod- eling of contemporary problems, pp
Frazier, P.I.: Bayesian optimization. In: Recent advances in optimization and mod- eling of contemporary problems, pp. 255–278. Informs (2018)
2018
-
[10]
arXiv preprint arXiv:1807.02811 (2018)
Frazier, P.I.: A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811 (2018)
2018 arXiv
-
[11]
In: International Joint Conference on Artificial Intelligence (IJCAI) (2019)
Giesen, J., Laue, S.: Combining ADMM and the augmented lagrangian method for efficiently handling many constraints. In: International Joint Conference on Artificial Intelligence (IJCAI) (2019)
2019
-
[12]
Computational optimization and applications60, 545–557 (2015)
Gould, N.I., Orban, D., Toint, P.L.: Cutest: a constrained and unconstrained test- ing environment with safe threads for mathematical optimization. Computational optimization and applications60, 545–557 (2015)
2015
-
[13]
Computers & Mathematics with Applications 18(9), 779–795 (1989)
Hager, W.W.: A derivative-based bracketing scheme for univariate minimization and the conjugate gradient method. Computers & Mathematics with Applications 18(9), 779–795 (1989)
1989
-
[14]
Journal of global optimization 79(3), 521–566 (2021)
Jones, D.R., Martins, J.R.: The direct algorithm: 25 years later. Journal of global optimization 79(3), 521–566 (2021)
2021
-
[15]
Journal of optimization Theory and Applications79, 157– 181 (1993)
Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the lipschitz constant. Journal of optimization Theory and Applications79, 157– 181 (1993)
1993
-
[16]
Journal of Global optimization13, 455–492 (1998)
Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. Journal of Global optimization13, 455–492 (1998)
1998
-
[17]
Journal of the Southern African Institute of Mining and Metallurgy 52(6), 119–139 (1951)
Krige, D.G.: A statistical approach to some basic mine valuation problems on the witwatersrand. Journal of the Southern African Institute of Mining and Metallurgy 52(6), 119–139 (1951)
1951
-
[18]
Kushner, H.J.: A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise (1964)
1964
-
[19]
In: Advances in Neural Information Processing Systems
Laue, S., Mitterreiter, M., Giesen, J.: Geno – generic optimization for classical machine learning. In: Advances in Neural Information Processing Systems. vol. 32. Curran Associates, Inc. (2019)
2019
-
[20]
arXiv preprint arXiv:1904.02990 (2022)
Laue, S.: On the equivalence of automatic and symbolic differentiation. arXiv preprint arXiv:1904.02990 (2022)
2022 arXiv
-
[21]
In: Conference on Artificial Intelligence (AAAI) (2022)
Laue, S., Blacher, M., Giesen, J.: Optimization for classical machine learning prob- lems on the GPU. In: Conference on Artificial Intelligence (AAAI) (2022)
2022
-
[22]
Journal of Machine Learning Research18(119), 1–59 (2012)
Mahsereci, M., Henning, P.: Probabilistic line searches for stochastic optimization. Journal of Machine Learning Research18(119), 1–59 (2012)
2012
-
[23]
Journal of Global Optimization4, 347–365 (1994)
Mockus, J.: Application of bayesian approach to numerical methods of global and stochastic optimization. Journal of Global Optimization4, 347–365 (1994)
1994
-
[24]
Journal of optimization theory and applications 70, 157–172 (1991)
Mockus, J.B., Mockus, L.J.: Bayesian approach to global optimization and appli- cation to multiobjective and constrained problems. Journal of optimization theory and applications 70, 157–172 (1991)
1991
-
[25]
ACM Trans
Moré, J.J., Thuente, D.J.: Line search algorithms with guaranteed sufficient de- crease. ACM Trans. Math. Softw.20(3), 286–307 (sep 1994)
1994
-
[26]
Nocedal, J., Wright, S.J.: Numerical optimization (2006)
2006
-
[27]
Optimization and Engineering pp
Papageorgiou, D.J., Kronqvist, J., Kumaran, K.: Linewalker: line search for black box derivative-free optimization and surrogate model construction. Optimization and Engineering pp. 1–65 (2024)
2024
-
[28]
In: Learning and Intelligent Optimization (LION) (2024) Bayesian Line Search 17
Prusina, T., Laue, S.: Efficient line search method based on regression and uncer- tainty quantification. In: Learning and Intelligent Optimization (LION) (2024) Bayesian Line Search 17
2024
-
[29]
Rasmussen,C.E.,Williams,C.K.I.:Gaussianprocessesformachinelearning.Adap- tive computation and machine learning, MIT Press (2006)
2006
-
[30]
John Wiley & Sons (2015)
Scott, D.W.: Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons (2015)
2015
-
[31]
Advances in neural information processing systems25 (2012)
Snoek, J., Larochelle, H., Adams, R.P.: Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems25 (2012)
2012
-
[32]
MIT Press (2012)
Sra, S., Nowozin, S., Wright, S.J.: Optimization for Machine Learning. MIT Press (2012)
2012
-
[33]
arXiv preprint arXiv:0912.3995 (2009)
Srinivas, N., Krause, A., Kakade, S.M., Seeger, M.: Gaussian process optimiza- tion in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995 (2009)
2009 arXiv
-
[34]
IEEE Transactions on Systems, Man, and Cybernetics18(6), 965–977 (1988)
Stuckman, B.: A global search method for optimizing nonlinear systems. IEEE Transactions on Systems, Man, and Cybernetics18(6), 965–977 (1988)
1988
-
[35]
Journal of Statistical Planning and Inference 140(11), 3088–3095 (2010)
Vazquez, E., Bect, J.: Convergence properties of the expected improvement algo- rithm with fixed mean and covariance functions. Journal of Statistical Planning and Inference 140(11), 3088–3095 (2010)
2010
-
[36]
scipy 1.0
Virtanen, P., Gommers, R., Oliphant, T., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., et al.: Fundamental al- gorithms for scientific computing in python and scipy 1.0 contributors. scipy 1.0. Nat. Methods 17, 261–272 (2020)
2020
-
[37]
SIAM Journal on Optimization16(1), 1–31 (2005)
Wächter, A., Biegler, L.T.: Line search filter methods for nonlinear programming: Motivation and global convergence. SIAM Journal on Optimization16(1), 1–31 (2005)
2005
-
[38]
Mathematical program- ming 106, 25–57 (2006)
Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line- search algorithm for large-scale nonlinear programming. Mathematical program- ming 106, 25–57 (2006)
2006
-
[39]
SIAM review11(2), 226–235 (1969)
Wolfe, P.: Convergence conditions for ascent methods. SIAM review11(2), 226–235 (1969)
1969
-
[40]
ii: Some corrections
Wolfe, P.: Convergence conditions for ascent methods. ii: Some corrections. SIAM review 13(2), 185–188 (1971)
1971
-
[41]
Advances in neural information processing systems30 (2017)
Wu, J., Poloczek, M., Wilson, A.G., Frazier, P.: Bayesian optimization with gradi- ents. Advances in neural information processing systems30 (2017)
2017
-
[42]
ACM Transactions on math- ematical software (TOMS)23(4), 550–560 (1997)
Zhu, C., Byrd, R.H., Lu, P., Nocedal, J.: Algorithm 778: L-bfgs-b: Fortran subrou- tines for large-scale bound-constrained optimization. ACM Transactions on math- ematical software (TOMS)23(4), 550–560 (1997)
1997
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.