ArXiv: 2307.16560
🎯 Pitch
Even the foundations of optimization miss something: classic line search algorithms like bisection and golden-section search ignore convexity, yet this paper shows that exploiting it provably doubles or triples convergence speed through refined optimality bounds. For gradient descent, their quasi-exact line search eliminates the notorious parameter sensitivity of backtracking — a single default works universally, while backtracking can catastrophically stall on simple smooth, strongly convex problems.
1. Executive Summary
This paper proposes two principled exact line search algorithms for general convex functions — ∆-Bisection and ∆-Secant — that exploit convexity to accelerate convergence beyond classic quasiconvex methods like bisection and golden-section search. Both algorithms operate on a refined definition of the optimality region ∆ (the provable bounds containing the minimum), with ∆-Bisection using gradient information to reduce the x∗-gap by at least a factor 2 per iteration — always exceeding bisection search’s x-interval halving — while ∆-Secant achieves the same factor-2 reduction every second function query without gradients. Experiments on single-variable convex functions and multivariate gradient descent with a quasi-exact line search (derived from ∆-Secant) demonstrate speedups often exceeding a factor 2 over their quasiconvex counterparts, and the quasi-exact line search provides a convergence guarantee within a factor c/(c+1) of exact line search while remaining robust across a wide parameter range — establishing that backtracking line search, by contrast, suffers catastrophic slowdowns on simple convex functions when its ε parameter is poorly chosen.
2. Context and Motivation
The Core Problem: Exact 1D Minimization of Convex Functions with Rigorous Guarantees
The paper addresses a fundamental algorithmic gap in numerical optimization: how to efficiently find the exact minimum of a general convex function in one dimension with guaranteed bounds on the optimality gap. This problem arises ubiquitously as a subroutine in higher-dimensional optimization — most prominently in selecting step sizes (learning rates) for gradient descent and its variants, where each outer iteration requires solving a 1D line search: minimize over .
The challenge is that these subproblems must be solved repeatedly — once per gradient descent iteration — so any inefficiency in the line search compounds rapidly. For machine learning problems with millions of parameters, a single function or gradient evaluation on the full dataset can be extremely expensive, making query efficiency paramount. Yet the 1D subproblem is often treated as a solved problem in practice, with approximate methods like backtracking used despite known brittleness (Boyd and Vandenberghe, 2004).
The theoretical significance is equally deep. The paper reveals that standard 1D minimization algorithms systematically underutilize convex structure. Bisection search for quasiconvex functions uses only the sign of the gradient — exactly 1 bit of information per query — ignoring the gradient's magnitude, which convex functions make geometrically meaningful through supporting hyperplane inequalities. Similarly, golden-section search for derivative-free quasiconvex minimization maintains an interval known to contain the minimum but never constructs a tighter optimality region from the secant constraints that convexity provides. The paper shows that exploiting this discarded information yields provably faster convergence and, crucially, provides a y∗-gap — an upper bound on — that serves as a rigorous stopping criterion. This gap is almost always infinite for general quasiconvex functions, making principled early termination impossible without convexity.
Why Quasiconvex Methods Leave Performance on the Table
The paper's central insight can be understood through a concrete example illustrated in Figure 1. Consider a convex function where we have evaluated the endpoints and , with . Standard bisection search would query at the midpoint , guaranteeing the -interval containing is halved. However, convexity provides much stronger constraints:
- The tangent at (with slope ) lies below everywhere by convexity, so cannot lie to the left of where this tangent crosses the horizontal line at .
- Similarly, the tangent at (with slope ) provides a right bound .
- Together, these define the x∗-gap — a subinterval of that can be dramatically smaller than the full interval.
In Figure 1, the x∗-gap is roughly [0.2, 1.85] while the full interval is [0.2, 5] — a factor of nearly 3 smaller. A bisection query at would land outside , wasting the query because the gradient sign at that point would only eliminate the region beyond it (which was already known to be suboptimal from the tangent bound). The ∆-Bisection insight is to query at the midpoint of instead, guaranteeing that whichever half of the x∗-gap survives contains the minimum and that the new tangent at the query point further tightens the bounds. The result: the x∗-gap itself is halved (or better) each iteration, not merely the original interval.
The derivative-free ∆-Secant algorithm mirrors this logic using only function evaluations. By maintaining five points around the current lowest point and constructing the optimality region from secant lines — exploiting that convex functions lie below secants between evaluation points and above secants outside their -interval — the algorithm computes an x∗-gap and queries at its midpoint. Theorem 6 proves that five points suffice: additional points provide only redundant constraints.
Where Prior Approaches Fall Short
Bisection search (for gradient-based minimization). The classic bisection method queries at the midpoint of the current -interval and uses to discard the left or right half. Boyd and Vandenberghe (2004) characterize this as optimal for general quasiconvex functions:
"The volume reduction factor is the best it can be: it is always exactly 1/2."
The critical limitation is that bisection discards gradient magnitude. For convex functions, the gradient's value encodes a supporting hyperplane that cuts off additional space beyond what the sign alone provides. Bisection's query point is chosen without reference to these tighter bounds, so it often evaluates the function in regions already provably excluded from containing the minimum. The paper's experiments (Table 1) show ∆-Bisection consistently outperforms bisection, with reduction factors often substantially better than 1/2 — for on , bisection requires 37 iterations while ∆-Bisection requires only 19.
Golden-section search (GSS). For derivative-free quasiconvex minimization, GSS maintains three points bracketing the minimum and reduces the interval by a factor per query. However, GSS is only guaranteed to reduce the full bracketing interval, not necessarily the tighter x∗-gap. Remark 11 demonstrates this concretely for on : after 4 queries, ∆-Secant reduces the x∗-gap below 2, while GSS requires 13 queries to achieve the same precision. The reason is that GSS's query points are determined by golden-ratio spacing in the bracketing interval, irrespective of the secant constraints that convexity provides.
Backtracking line search with Armijo's condition. For practical gradient descent, the dominant approach is backtracking line search (Armijo, 1966; Boyd and Vandenberghe, 2004). Starting from an initial step size, the algorithm repeatedly shrinks the step by a factor until the Armijo condition is satisfied:
where is the "acceptable linearity" parameter. This method has compelling advantages: it's simple, has linear convergence guarantees for strongly convex smooth functions, and terminates quickly in many cases.
However, the paper exposes two catastrophic failure modes that make backtracking fundamentally non-robust:
-
Small causes oscillatory slowdown (Example 15, "Armijo's flying squirrel"). On with , the line search returns a step size that satisfies . The iterates oscillate between symmetric points on opposite branches of the parabola, reducing distance to the origin by only a factor per GD iteration. For , this requires GD iterations vs. 4 for quasi-exact line search (Table 3). The problem is that a small makes the line search accept steps that barely reduce the function value relative to what the gradient magnitude promises, leading to painfully slow progress.
-
Large causes excessive backtracking on highly curved functions (Example 16, "Armijo's snowplow skier"). On , the Armijo condition with large demands that the line search finds a point where the function closely tracks its linear approximation. For , , , this requires over 200 GD iterations and 55,000 function queries — the backtracking repeatedly overshoots acceptable step sizes and must shrink by factors of , cumulatively consuming enormous query budgets. Here, performs far better (Table 3). This creates an irreconcilable tension: no single works well across even simple function classes.
The failure modes illustrate a deeper issue: the Armijo condition is a relative stopping criterion that compares function decrease to gradient magnitude, but the appropriate threshold depends intimately on the function's local curvature — a quantity backtracking does not directly measure. Boyd and Vandenberghe (2004) recommend , but the experiments in Table 3 show that even across three simple functions (, , ), no single performs acceptably — the best choice on one function is disastrous on another.
Exact line search: historically abandoned as too expensive. The paper notes that exact line search — finding the true minimizer of the 1D subproblem — was used historically but abandoned because "people have stopped using exact line searches in favor of backtracking line search due to the former being very expensive" (Boyd and Vandenberghe, 2004). The computational burden comes from solving each 1D subproblem to high precision, which can dominate the cost of the outer iteration. The paper's quasi-exact approach bridges this gap: it terminates when the y∗-gap satisfies , which bounds the suboptimality without requiring full numerical convergence. Theorem 12 shows this loses only a factor in convergence rate compared to true exact search, while the slack captured by allows early termination before numerical precision is reached.
How This Paper Positions Itself
The paper does not propose a new optimization paradigm but rather completes the algorithmic landscape for 1D convex minimization by showing that convexity — long understood as the property enabling efficient higher-dimensional optimization — also enables substantially faster 1D search than the quasiconvex methods currently used. The two algorithms, ∆-Bisection and ∆-Secant, are natural extensions of bisection and golden-section search respectively, differing only in where they query: at the midpoint of the refined optimality region ∆ rather than at the midpoint of the bracketing interval.
The quasi-exact line search positions itself as a replacement for backtracking that is simultaneously more robust (a single parameter works across all experiments) and theoretically grounded (the optimality bound). The paper validates this on both artificial test functions and a 100-dimensional loss landscape (Equation 9, Figure 6), showing quasi-exact search with reliably outperforms backtracking across its entire sweep.
The paper also contributes a conceptual framework — the optimality region ∆ and its associated x∗-gap and y∗-gap — that can be retrofitted onto existing algorithms. Golden-section search can use as a stopping criterion on convex functions even without modifying its query strategy, immediately providing principled termination where previously only heuristic tolerances were available.
3. Technical Approach
3.1 Reader Orientation
This paper develops two algorithms — ∆-Bisection and ∆-Secant — that perform exact 1D minimization of general convex functions by maintaining and shrinking a refined region of possible locations for the minimum (the "optimality region" ∆), rather than just shrinking the original search interval as classic methods do. The system solves the problem of finding with provable bounds on how close you are to the true minimum, and the shape of the solution is: at every iteration, compute the tightest provable bounds on where can be (using gradient tangents or secant lines from previous evaluations), query at the midpoint of that tight region, and use the new information to shrink the bounds further — each query buys at least a factor-2 reduction in the x∗-gap rather than the potentially much looser factor-2 reduction of the original interval.
3.2 Big-Picture Architecture (Diagram in Words)
The system has five conceptual components, shared in spirit across both the gradient-based ∆-Bisection and the derivative-free ∆-Secant:
- Function oracle (
$f$and optionally$f'$) — the black-box convex function to minimize on a user-provided interval$[x_{\text{left}}, x_{\text{right}}]$. For ∆-Bisection, both$f(x)$and$f'(x)$are available; for ∆-Secant, only$f(x)$is available. - Point set
$P_t$(or bracketing pair) — the collection of all evaluated points maintained by the algorithm. For ∆-Bisection, this is exactly two points$p^0_t = (x^0_t, y^0_t)$and$p^1_t = (x^1_t, y^1_t)$with their gradients, representing the current left and right boundaries of the optimality region. For ∆-Secant,$P_t$is a growing set of evaluated points, but Theorem 6 proves that only the five points centered around the current lowest point are non-redundant. - Optimality region constructor
$\Delta(\cdot)$— the core geometric engine. Given the current point set, it computes the polygonal region$\Delta_t$(or$\Delta(P_t)$) that is guaranteed to contain$(x^*, f(x^*))$using convexity constraints. This region is defined by tangents (∆-Bisection) or secants (∆-Secant) acting as lower bounds, and the horizontal line at the lowest known function value$y^{\text{low}}$acting as an upper bound. - Gap extractor — from
$\Delta$, extracts two intervals: the x∗-gap$\Delta_x = [x^-, x^+]$(the projection of$\Delta$onto the x-axis, giving the provable bounds on$x^*$) and the y∗-gap$\Delta_y = [Y, y^{\text{low}}]$(the projection onto the y-axis, giving the provable bounds on how far the current best function value is from the true minimum$y^*$). - Query selector — determines the next evaluation point
$x_q$as the midpoint of the x∗-gap:$x_q = (x^- + x^+)/2$. This is the critical design choice that distinguishes both algorithms from their quasiconvex ancestors (which query at midpoints of the full bracketing interval instead).
The data flow is a tight loop: initial two evaluations at $x_{\text{left}}$ and $x_{\text{right}}$ (plus gradients if available) → compute ∆ and its gaps → if $|\Delta_y| \leq y_{\text{tol}}$, stop and return the best point → otherwise query at $x_q = \text{mid}(\Delta_x)$ → update point set → recompute ∆ → repeat. The quasi-exact line search variant (Section 3.3) wraps this loop inside a dynamic interval-expansion mechanism and replaces the absolute tolerance $y_{\text{tol}}$ with a relative stopping condition comparing the y∗-gap to the observed improvement.
3.3 Roadmap for the Deep Dive
I will explain the technical machinery in the following order, which mirrors how the algorithms build on each other:
- The optimality region for ∆-Bisection (gradient case): How tangents and the horizontal line at
$y^{\text{low}}$define a tightening polygon around the minimum, and how the x∗-gap and y∗-gap are computed from two function+gradient evaluations. - The ∆-Bisection algorithm: The iteration loop, the midpoint-query rule, and the three-case proof (Figures 2–4) for why the x∗-gap is at least halved each iteration.
- The optimality region for ∆-Secant (derivative-free case): How secant lines replace tangents as lower bounds, why five points suffice (Theorem 6), and the geometric definition of
$\Delta(P)$and its gaps. - The ∆-Secant algorithm: How it mirrors ∆-Bisection using only function evaluations, the two-iteration guarantee for halving the x∗-gap (Theorem 10), and the ε-repulsion mechanism for numerical stability.
- Quasi-exact line search: How the y∗-gap enables a relative stopping criterion for step-size selection in gradient descent, the interval-growing mechanism, and the convergence theory (Theorems 12 and 13).
3.4 Detailed, Sentence-Based Technical Breakdown
This is primarily an algorithm design paper whose core idea is that convexity provides geometric constraints (tangent and secant lower bounds) that can be exploited to shrink a provable bounding box around the minimum faster than the original search interval shrinks, and that querying at the midpoint of this tighter box yields convergence guarantees strictly stronger than those of quasiconvex methods.
The Optimality Region for ∆-Bisection: Tangents as Lower Bounds
At any iteration $t$ of ∆-Bisection, the algorithm maintains exactly two evaluated points:
$p^0_t = (x^0_t, y^0_t)$with known gradient$f'(x^0_t)$$p^1_t = (x^1_t, y^1_t)$with known gradient$f'(x^1_t)$
with the invariant that $x^0_t \leq x^1_t$. Define $x^{\text{low}}_t$ as the point with the lower function value and $x^{\text{high}}_t$ as the point with the higher function value:
$y^{\text{low}}_t = \min\{y^0_t, y^1_t\}$is the best known function value$y^{\text{high}}_t = \max\{y^0_t, y^1_t\}$is the worse one
The critical geometric insight is that convexity provides two one-sided linear bounds that the true function must lie above:
- Tangent at
$x^0_t$: Define$f^0_t(x) = f(x^0_t) + (x - x^0_t) f'(x^0_t)$. Since$f$is convex,$f(x) \geq f^0_t(x)$for all$x$— the function lies everywhere above its tangent. - Tangent at
$x^1_t$: Similarly,$f^1_t(x) = f(x^1_t) + (x - x^1_t) f'(x^1_t)$satisfies$f(x) \geq f^1_t(x)$for all$x$.
Additionally, we have the trivial upper bound: $f(x^*) \leq y^{\text{low}}_t$, since $x^*$ is a global minimizer and $y^{\text{low}}_t$ is the function value at some (possibly suboptimal) point.
Combining these three constraints — the two tangent lower bounds and the best-value upper bound — the paper defines the optimality region $\Delta_t$ at iteration $t$:
where $\Delta_t$ is the set of all $(x, y)$ pairs that could possibly be $(x^*, f(x^*))$; $[x^0_t, x^1_t]$ is the known bracket from the two evaluation points; $y \leq y^{\text{low}}_t$ is the upper-bound constraint from the best observed value; and $f^0_t(x) \leq y$ and $f^1_t(x) \leq y$ are the lower-bound constraints from the two tangents.
What it computes: the intersection of two half-planes (above each tangent) with a horizontal ceiling (below $y^{\text{low}}_t$) and vertical walls (between $x^0_t$ and $x^1_t$), producing a polygonal region — either a triangle or a quadrilateral — that is guaranteed to contain the unknown minimum point $(x^*, f(x^*))$.
Why this form: it is the tightest provable bounding box using only first-order convexity information (function values and gradients at two points) with no assumptions about Lipschitz constants, strong convexity, or differentiability beyond the two queried points. Any alternative definition that ignored the tangents would recover the original interval $[x^0_t, x^1_t]$ and the trivial bound $y \leq y^{\text{low}}_t$, which is exactly the information bisection search uses — and would be strictly looser.
From this region, the paper extracts two one-dimensional intervals that quantify the remaining uncertainty:
The x∗-gap $\Delta_x^t$ is the projection of $\Delta_t$ onto the x-axis:
where $x^-_t$ is the leftmost x-coordinate in $\Delta_t$ and $x^+_t$ is the rightmost x-coordinate in $\Delta_t$.
Concretely, these boundaries are the x-values where each tangent crosses the horizontal line at $y^{\text{low}}_t$:
where $x^-_t$ is the intersection of the left tangent $f^0_t$ with the horizontal line at $y^{\text{low}}_t$ — since $f'(x^0_t) \leq 0$ (necessary for the minimum to lie to the right of $x^0_t$), the denominator $-f'(x^0_t)$ is non-negative, and $y^0_t - y^{\text{low}}_t \geq 0$ is how far above the best known value the point at $x^0_t$ sits — and $x^+_t$ is the analogous intersection for the right tangent $f^1_t$ where $f'(x^1_t) \geq 0$, giving $x^+_t \leq x^1_t$.
What it computes: the narrowest x-interval that can be proven, from the two tangent inequalities alone, to contain the true minimizer $x^*$. Note that either $x^0_t = x^-_t$ or $x^1_t = x^+_t$ — the tangent at the lower of the two points is a flat line relative to $y^{\text{low}}_t$, so one boundary coincides with the lower evaluation point.
Why this form: the expressions come directly from solving $f^0_t(x) = y^{\text{low}}_t$ and $f^1_t(x) = y^{\text{low}}_t$ for $x$. The geometric interpretation is that the tangent at the higher point cuts into the interval, pushing the bound inward from that endpoint. The formula works because convexity ensures the tangents never cross above the function, so the true minimum cannot be outside the region where both tangents lie below $y^{\text{low}}_t$.
The y∗-gap $\Delta_y^t$ is the projection onto the y-axis:
where $Y_t$ is the y-coordinate of the intersection point of the two tangents $f^0_t$ and $f^1_t$. Solving $f^0_t(x) = f^1_t(x)$ gives:
where $Y_t$ is the minimum possible value of $f(x^*)$ consistent with the two tangent constraints — it is the highest y-value where both tangent lower bounds are simultaneously active; $y^{\text{low}}_t$ is the best known function value (the upper bound); and $\Delta_y^t$ is the provable optimality gap.
What it computes: the width of this interval $|\Delta_y^t| = y^{\text{low}}_t - Y_t$ is an upper bound on $f(x^{\text{low}}_t) - f(x^*)$ — how much worse the best-evaluated point could be compared to the true minimum. This is what the algorithm uses as the stopping criterion: when $|\Delta_y^t| \leq y_{\text{tol}}$, it is proven that $y^{\text{low}}_t - y^* \leq y_{\text{tol}}$.
Why this form: the intersection point $Y_t$ represents the tightest lower bound on $f(x^*)$ obtainable from two tangent constraints — it is the solution to the small linear system $f^0_t(x) = f^1_t(x)$. The formula emerges from substituting the tangent definitions, collecting terms, and solving for the y-coordinate. Any alternative bound (e.g., using only one tangent) would give a looser (smaller) lower bound and a larger y∗-gap. Crucially, for general quasiconvex functions, the two tangents need not have an intersection above $-\infty$, making $|\Delta_y|$ potentially infinite — this is why bisection search cannot provide a principled stopping criterion while ∆-Bisection can.
The critical geometric fact: $\Delta_t$ is a strict subset of the rectangle $[x^0_t, x^1_t] \times (-\infty, y^{\text{low}}_t]$. The extra constraints from tangents "cut off" two triangular regions — the bottom-left corner (below $f^0_t$ and to the left of the tangent crossing) and the bottom-right corner (below $f^1_t$ and to the right of its crossing). The x∗-gap is the surviving x-interval after these cuts. When the two evaluation points have very different function values and steep gradients, the cuts can be large, making $\Delta_x^t$ dramatically smaller than $[x^0_t, x^1_t]$ — this is the efficiency gain over bisection.
The ∆-Bisection Algorithm: Iteration and Convergence
Algorithm 1 presents the pseudocode. The initialization evaluates $f$ and $f'$ at the two endpoints $x_{\text{left}}$ and $x_{\text{right}}$. A special termination check: if $f'(x_{\text{left}}) \geq 0$ (function is non-decreasing from the left boundary) or $f'(x_{\text{right}}) \leq 0$ (function is non-increasing from the right boundary), then the minimum is at a boundary and $|\Delta_y^0| = 0$ — the algorithm terminates immediately. Otherwise, $f'(x_{\text{left}}) < 0$ and $f'(x_{\text{right}}) > 0$, guaranteeing the minimum lies in the interior.
Query rule. At each iteration $t$, the algorithm computes the x∗-gap boundaries $x^-_t$ and $x^+_t$ using Equation (2), then queries at the midpoint:
This is the fundamental design choice that distinguishes ∆-Bisection from standard bisection search (which would query at $(x^0_t + x^1_t)/2$). Because $\Delta_x^t \subseteq [x^0_t, x^1_t]$, the ∆-Bisection query is always inside the full bracketing interval, and often significantly offset from its center. The query point is chosen to equally split the uncertainty about $x^*$ rather than equally splitting the original interval.
Update rule. After evaluating $f(x^q_t)$ and $f'(x^q_t)$, the new pair $p^0_{t+1}, p^1_{t+1}$ is formed by:
- If
$f'(x^q_t) < 0$, the minimum must be to the right of$x^q_t$, so set$x^0_{t+1} = x^q_t$and$x^1_{t+1} = x^1_t$(discard the left portion). - If
$f'(x^q_t) > 0$, the minimum must be to the left of$x^q_t$, so set$x^0_{t+1} = x^0_t$and$x^1_{t+1} = x^q_t$(discard the right portion).
The case $f'(x^q_t) = 0$ implies $x^q_t$ is an exact stationary point, and the y∗-gap becomes zero.
Termination. The algorithm stops when $|\Delta_y^{t+1}| \leq y_{\text{tol}}$, where $\Delta_y$ is computed via Equation (3). It returns the set of evaluated points; the user can extract the lowest among them as the answer.
Theorem 1 — the convergence guarantee. The theorem states that at each iteration $t \geq 2$, assuming the algorithm has not yet terminated ($\Delta_y^{t+1} > y_{\text{tol}}$), the x∗-gap shrinks by at least a factor of 2:
where $|\Delta_x^t| = x^+_t - x^-_t$ is the width of the x∗-gap at iteration $t$; $y^{\text{low}}_{t+1}$ is the best function value after incorporating the query; $y^q_t = f(x^q_t)$ is the function value at the query point; $z_t = f^{\text{high}}_{t+1}(x^{\text{low}}_{t+1})$ is the value of the tangent at the higher-elevation endpoint evaluated at the x-coordinate of the lower-elevation endpoint — effectively the predicted function value at the best point according to the tangent from the worst point; and $\max\{y^q_t, y^{\text{low}}_t\}$ is the best known value before incorporating $y^q_t$ (pessimistically assuming the query might be worse).
What it computes: the multiplicative factor by which the x∗-gap shrinks in one iteration. Since $y^{\text{low}}_{t+1} \leq y^{\text{low}}_t$ (the best value never increases) and $z_t \leq y^{\text{low}}_{t+1}$ (the tangent at the high point lies below the true function at the low point by convexity), we have $y^{\text{low}}_{t+1} - z_t \leq \max\{y^q_t, y^{\text{low}}_t\} - z_t$, making the ratio at most 1/2.
Why this form: the theorem is not obvious because the naive argument — "we queried at the midpoint of $\Delta_x^t$, so whichever half survives has half the width" — is false: the new tangent at $x^q_t$ can further shrink the surviving interval beyond simple bisection. The precise equality emerges from a case analysis of three possible geometric configurations (Figures 2–4), each of which uses triangle similarity to relate the ratio of interval widths to the ratio of vertical distances between the function values and the tangent intersection.
The three cases of the proof (Figures 2, 3, 4 from the paper). The proof assumes without loss of generality that $y^0_t \leq y^1_t$ (the left evaluation point has the lower value; the symmetric case is handled identically). The three cases are distinguished by the sign of $f'(x^q_t)$ and the relative ordering of $y^q_t$ versus $y^0_t$ and $y^1_t$:
Case 1 (Figure 2): $f'(x^q_t) > 0$ and $y^q_t < y^0_t$. The gradient is positive so the minimum is to the left of $x^q_t$. The query point is lower than the previous best, so $y^{\text{low}}_{t+1} = y^q_t$. The surviving interval is $\Delta_x^{t+1} = [x^-_{t+1}, x^q_t]$ where $x^-_{t+1}$ is determined by the tangent at $x^0_t$ (unchanged) and the horizontal line at $y^q_t$. By similar triangles in the figure, $|\Delta_x^{t+1}| / (\frac{1}{2}|\Delta_x^t|) = (y^q_t - z_t) / (y^0_t - z_t)$, which is less than 1.
Case 2 (Figure 3): $f'(x^q_t) < 0$ and $y^q_t < y^0_t$. The gradient is negative so the minimum is to the right of $x^q_t$. Again $y^{\text{low}}_{t+1} = y^q_t$. The surviving interval is $[x^q_t, x^+_{t+1}]$ with $x^+_{t+1}$ from the tangent at $x^1_t$. The geometry is symmetric to Case 1 with the same ratio.
Case 3 (Figure 4): $f'(x^q_t) > 0$ and $y^0_t < y^q_t < y^1_t$. The gradient is positive (minimum is to the left), but the query point is worse than the previous best — $y^{\text{low}}_{t+1} = y^0_t$ is unchanged. The surviving interval is $[x^0_t, x^+_{t+1}]$ where $x^+_{t+1}$ is determined by the new tangent at $x^q_t$. Because the tangent at $x^q_t$ cuts upward from the right, it intersects the horizontal line at $y^0_t$ at some point $x^+_{t+1} < x^q_t$. The ratio involves $(y^0_t - z_t) / (y^q_t - z_t) < 1$.
The case $f'(x^q_t) < 0$ and $y^q_t > y^0_t$ is excluded by symmetry, and $y^q_t > y^1_t$ is impossible by convexity (a point between $x^0_t$ and $x^1_t$ cannot lie above the higher endpoint).
The key practical insight: the factor 1/2 is a worst-case bound. In practice, the reduction is often much better because:
- The new tangent at
$x^q_t$can cut off additional width beyond the half-interval that the gradient sign discards. - When
$y^q_t \ll y^{\text{low}}_t$(the query point is dramatically better than the previous best), the horizontal line drops significantly, further pushing in both$x^-$and$x^+$. - When one of the original tangents is steep, its intersection with
$y^{\text{low}}$is close to the evaluation point, making$\Delta_x^t$small from the start.
Table 1 validation. The experimental data bears out the theory. For $f(x) = \max\{-x, 2x\}$ on $[-20, 7]$, bisection needs 37 iterations to achieve $y_{\text{tol}} = 10^{-10}$ while ∆-Bisection needs only 19 — the average reduction factor is substantially better than 1/2. For $f(x) = x^4$, the gap is 11 versus 8 iterations. For $f(x) = |x|^{1.1}$, 34 versus 11. These are not marginal improvements; they reflect that the x∗-gap is systematically smaller than the full interval, and querying at its midpoint compounds this advantage geometrically.
The Optimality Region for ∆-Secant: Secants as Lower Bounds
When gradient information is unavailable, the paper constructs an analogous optimality region $\Delta(P)$ using only function evaluations. The geometric principle is the same — convexity provides lower bounds — but the bounding objects are secant lines (lines through two evaluated points) rather than tangents.
The secant lower-bound rule. For any two distinct evaluated points $p_i = (x_i, f(x_i))$ and $p_j = (x_j, f(x_j))$, define the secant line:
where $a_{ij}$ is the slope of the secant through $p_i$ and $p_j$.
The fundamental convexity property used is two-sided relative to the x-interval:
- For
$x \in [x_i, x_j]$(between the two points), convexity implies$f(x) \leq f^{ij}(x)$— the function lies below the secant (the familiar "function lies below chords" property). - For
$x \notin [x_i, x_j]$(outside the interval spanned by the two points), convexity implies$f(x) \geq f^{ij}(x)$— the function lies above the secant extended outward.
This second, "outside" inequality is what provides the lower bounds for the optimality region. If we have evaluation points both to the left and right of the minimum, then secants connecting left-side points to right-side points pass below the minimum's y-coordinate in the region between them? No — the crucial insight is more subtle. Secants connecting a point to the left of $x^*$ and a point to the right of $x^*$: for x-values outside $[x_i, x_j]$, $f(x) \geq f^{ij}(x)$. In particular, for $x = x^*$ which lies inside $[x_i, x_j]$ when $x_i < x^* < x_j$, the first property gives $f(x^*) \leq f^{ij}(x^*)$ — an upper bound, not a lower bound. The lower bounds come from secants where both endpoints are on the same side of $x^*$.
The correct geometry (Figure 5): let the points be ordered $x_0 < x_1 < x_2 < x_3 < x_4$ with $p_2 = p^{\text{low}}$ being the current lowest-evaluated point (presumed closest to the minimum). Then:
- The secant
$f^{01}$connects two points left of the minimum. For$x$to the right of$x_1$(which includes$x^*$),$f(x) \geq f^{01}(x)$— providing a lower bound that slopes upward from the left. - The secant
$f^{34}$connects two points right of the minimum. For$x$to the left of$x_3$(which includes$x^*$),$f(x) \geq f^{34}(x)$— providing a lower bound that slopes upward from the right.
Additionally, $f(x) \leq f^{12}(x)$ for $x \in [x_1, x_2]$ and $f(x) \leq f^{23}(x)$ for $x \in [x_2, x_3]$ provide upper bounds (ceiling constraints) in the regions adjacent to the minimum.
The formal definition of $\Delta(P)$. For a $(f, x_{\text{left}}, x_{\text{right}})$-convex set of points $P$, the paper defines:
where $y^{\text{low}}(P) = \min_{(x,y) \in P} y$ is the lowest observed function value; the first condition restricts $x$ to the convex hull of evaluated points; the second requires $y$ to be at or below the best known value; and the third — the "secant lower-bound condition" — says that for every pair of points $p_i, p_j$, if $x$ is outside the open interval between $x_i$ and $x_j$, then $y$ must be at or above the secant line $f^{ij}(x)$.
What it computes: the intersection of half-planes generated by all secant pairs where $x$ lies outside their span. Geometrically, this produces a polygonal region consisting of at most two triangles (one left of $p_2$, one right of $p_2$) bounded below by the two outer secants $f^{01}$ and $f^{34}$, bounded above by the horizontal line at $y^{\text{low}}(P)$, and bounded at the sides by the innermost secants $f^{12}$ and $f^{23}$ which can cut into the region from above since the function lies below them between $x_1$ and $x_2$ or $x_2$ and $x_3$.
Why this form: it captures all constraints that convexity provides from a set of function evaluations, without requiring any derivative information. The "outside" condition $x \notin (x_i, x_j)$ ensures we only use secants as lower bounds where convexity guarantees $f(x) \geq f^{ij}(x)$ — applying the "inside" inequality $f(x) \leq f^{ij}(x)$ outside the interval would give incorrect (non-lower) bounds and violate the containment guarantee of Theorem 5.
Theorem 5 (correctness). The theorem states that if $P$ is a $(f, x_{\text{left}}, x_{\text{right}})$-convex set of points, then for every global minimizer $x^*$ of $f$ on $[x_{\text{left}}, x_{\text{right}}]$, we have $(x^*, f(x^*)) \in \Delta(P)$. The proof is immediate from the definition: $f(x^*) \leq y^{\text{low}}(P)$ by optimality, and for any $p_i, p_j \in P$ with $x^* \notin (x_i, x_j)$, convexity gives $f(x^*) \geq f^{ij}(x^*)$, so all conditions in Equation (4) are satisfied. The logical structure is identical to the ∆-Bisection case — convexity provides lower bounds, and the best-known value provides the upper bound — but the lower bounds are piecewise-linear through pairs of points rather than linear through a single point+gradient.
Theorem 6 (five points suffice). Let $P$ be a $(f, x_{\text{left}}, x_{\text{right}})$-convex set of points ordered by x-coordinate, with $p_k = p^{\text{low}}(P)$ being the minimum among them, and assume there are at least two points on each side of $p_k$ (indices $k-2, k-1, k, k+1, k+2$). Define $P' = \{p_{k-2}, p_{k-1}, p_k, p_{k+1}, p_{k+2}\}$. Then $\Delta(P') = \Delta(P)$ — points further from the minimum than two steps on either side provide only redundant constraints.
The proof is by elimination: consider a point $p_{k-3}$ to the left of $p_{k-2}$. For any constraint involving $p_{k-3}$ paired with a point $p_i$ where $i \geq k+1$ (right side), the relevant x-values in $\Delta_x(P)$ are already constrained to be inside $[x_{k-1}, x_{k+1}]$, so the $x \notin (x_{k-3}, x_i)$ condition is vacuous for those x-values. For constraints pairing $p_{k-3}$ with $p_i$ where $i \leq k-1$ and $i \neq k-3$, convexity of the secants implies $f^{i, k-3}(x) \leq f^{i, k-1}(x)$ for $x \geq x_{k-1}$, so the $f^{i, k-3}$ constraint is weaker (easier to satisfy) than the $f^{i, k-1}$ constraint already present. Finally, the constraint $f^{k-3, k}$ is made redundant by $f^{k-1, k}$. Thus $p_{k-3}$ can be eliminated without changing $\Delta(P)$. This argument extends recursively to all points beyond $k \pm 2$, establishing that only five centered points are needed.
Why this is important: it means an implementation only needs to store and operate on five points at any time, not the entire history. It also implies that the optimality region's complexity is bounded — it is defined by at most four secant constraints (two outer, two inner) plus the horizontal line, producing a simple polygonal shape.
The x∗-gap and y∗-gap for ∆-Secant. With five points $P = \{p_0, p_1, p_2, p_3, p_4\}$ and $p_2 = p^{\text{low}}$, the gaps are computed analogously to the gradient case:
where $x^-$ is the intersection of the left outer secant $f^{01}$ with the horizontal line at $y_2$ — since $a_{01} < 0$ (the function slopes downward from $p_0$ to $p_1$), $x^- > x_1$ — and $x^+$ is the analogous intersection of the right outer secant $f^{34}$ with $y_2$.
The y∗-gap boundary $\min\{y_{01,23}, y_{12,34}\}$ is more subtle. Here $y_{01,23}$ is the y-coordinate of the intersection of secant $f^{01}$ (left outer) with secant $f^{23}$ (right inner), and $y_{12,34}$ is the intersection of secant $f^{12}$ (left inner) with secant $f^{34}$ (right outer). These two intersection points represent the two possible "vertices" at the bottom of the optimality region — the lowest point that is simultaneously above both lower bounds and below both upper bounds. The minimum of their y-coordinates is the provable lower bound on $f(x^*)$.
What it computes: the same quantities as in the gradient case — an x-interval guaranteed to contain $x^*$ and a y-interval whose width bounds $f(x^{\text{low}}) - f(x^*)$. The key difference is that two intersection points may be candidate lower bounds (the bottom of the left triangle and the bottom of the right triangle in Figure 5), and the lower one (the deeper of the two) is the valid bound — because the function could achieve the minimum in either the left or right triangle of the optimality region.
Why this form: the secant-based computation uses the same geometric principle as the tangent-based one — intersect lower bounds with the horizontal ceiling — but with piecewise-linear rather than linear lower bounds. The intersections $y_{01,23}$ and $y_{12,34}$ use the formula of Equation (1) for line-line intersection from four point coordinates, with the specific pairings chosen because those four secants are the active constraints defining the boundary of $\Delta(P)$ in the five-point case.
Example 7 (four points versus three). Consider $f(x) = |x|$ with $P = \{(-a, a), (\varepsilon, \varepsilon), (1, 1)\}$ and $Q = P \cup \{(-(a+1), a+1)\}$. The y∗-gap with $P$ (three points) is $|\Delta_y(P)| = a + \varepsilon$ — the best lower bound comes from one secant on the right and nothing constraining the left. With $Q$ (four points, adding a second point on the left), $|\Delta_y(Q)| = \varepsilon$ — the left outer secant through $(-(a+1), a+1)$ and $(-a, a)$ provides a much tighter lower bound that brings the y∗-gap down dramatically. This example demonstrates concretely why three points are insufficient (the y∗-gap with three points can be arbitrarily pessimistic) and why four points suffice to capture the secant lower bound on both sides.
Remark 8 (virtual points). When the algorithm starts with only the two boundary evaluations, there are not enough points to form the five-point configuration. The paper describes a virtual-point construction: if $P$ lacks two points to the left or right of $p^{\text{low}}$, add virtual points with the same x-spacing as nearby real points but with y-values set to $\infty$. These virtual points contribute no lower-bound constraints (since $\infty$ cannot serve as a lower bound), so they do not artificially shrink the optimality region. They merely ensure the algorithm has a well-defined five-point structure to compute the gaps from, with $\Delta(P)$ unchanged from the true point set.
The ∆-Secant Algorithm: Derivative-Free Convex Search
Algorithm 2 presents ∆-Secant, which is structurally identical to ∆-Bisection but uses the secant-based optimality region $\Delta(P_t)$ and its associated gaps.
Initialization. The algorithm starts with two boundary evaluations:
At this point $|\Delta_y(P_1)| = \infty$ (with only two points, there is no secant pair on the same side of $p^{\text{low}}$ to provide a lower bound), so the algorithm must perform at least one query before termination is possible.
Query rule. At iteration $t$, compute the x∗-gap boundaries $x^-$ and $x^+$ from Equation (6), then set the query point to the midpoint:
The ε-repulsion mechanism. A subtle numerical issue arises: if $x^{\text{low}}(P_t)$ — the x-coordinate of the lowest-evaluated point — happens to be exactly at $x_m$, then querying there would re-evaluate a known point, providing no new information. More generally, if the lowest point is very close to the midpoint, numerical precision issues can cause the algorithm to make negligible progress. The paper introduces a repulsion step:
if (x_q, ·) ∈ P_t:
x_q = x_m + ε(x^+ - x^-)
else:
x_q = x_m
where $\varepsilon \in (0, 1/2)$ (recommended value: $2^{-7}$). If the exact midpoint has already been evaluated, the query is nudged slightly to the right by a fraction $\varepsilon$ of the x∗-gap width, guaranteeing a new evaluation point distinct from all previous ones. The paper suggests this repulsion should be applied whenever $|x^{\text{low}}(P_t) - \Delta_x(P_t)/2| < \varepsilon$, not just for exact equality, to maintain numerical stability.
Update and five-point maintenance. After evaluating $f(x_q)$, the new point is added to $P_t$. By Theorem 6, only the five points centered around the current minimum need to be retained — all others are geometrically redundant. The bookkeeping is: sort points by x-coordinate, identify the index $k$ of $p^{\text{low}}(P_{t+1})$, keep $p_{k-2}$ through $p_{k+2}$ (with virtual points as needed near boundaries), discard the rest.
Termination. Stop when $|\Delta_y(P_t)| \leq y_{\text{tol}}$, using Equation (6) to compute the y∗-gap.
Remark 9 (saving one query). The paper observes that the very first query can sometimes be avoided at the right boundary. Given initial bounds $x_{\text{left}}$ and $x_{\text{right}}$, after evaluating $f(x_{\text{left}})$, query at $x_q^1 = (x_{\text{left}} + x_{\text{right}})/2$ before evaluating $f(x_{\text{right}})$. If $f(x_{\text{left}}) \leq f(x_q^1)$, then by convexity the function is non-decreasing from $x_{\text{left}}$ to at least $x_q^1$, and the minimum could be at $x_{\text{left}}$ — the rightmost evaluation at $x_{\text{right}}$ provides no additional information because the secant through $(x_{\text{left}}, f(x_{\text{left}}))$ and $(x_q, f(x_q))$ already bounds the function from below on $[x_q, x_{\text{right}}]$. This optimization is never developed into a full algorithm invariant, but it illustrates the information-theoretic principle: three well-chosen points can sometimes render a fourth redundant.
Theorem 10 (∆-Secant convergence). For ∆-Secant with $\varepsilon \to 0$, at any iteration $t$ such that the algorithm does not terminate before $t+2$, the x∗-gap is at least halved every second iteration:
The proof handles the extra iteration (compared to ∆-Bisection's single-iteration guarantee) because the secant-based ∆ region provides weaker per-query information than the tangent-based one. The structure of the proof is:
Case 1: If $y^q_t \geq y^{\text{low}}(P_t)$ — the query point is not an improvement over the current best. Then the sign information (which side of the midpoint contains the minimum based on the shape of the sampled points) allows discarding one half of $\Delta_x(P_t)$, giving $|\Delta_x(P_{t+1})| \leq \frac{1}{2}|\Delta_x(P_t)|$ in a single iteration. This is analogous to the ∆-Bisection situation where the gradient sign directly indicates which side is valid.
Case 2: If $y^q_t \leq y^{\text{low}}(P_t)$ — the query point is an improvement (new lowest point). Now the algorithm has a new $p^{\text{low}}$ at $x_q$, and the x∗-gap is recentered around this point. The subsequent query at $t+1$ will be at the midpoint of the new ∆x. The analysis splits into two subcases:
-
Case 2a: At
$t+1$, the query yields$y^q_{t+1} \geq y^{\text{low}}(P_{t+1}) = y^q_t$(no further improvement). Then by Case 1 logic, iteration$t+1$alone halves the x∗-gap from$t+1$, so$|\Delta_{t+2}| \leq |\Delta_{t+1}|/2$. Since$|\Delta_{t+1}| \leq |\Delta_t|$(adding constraints never expands ∆), we get$|\Delta_{t+2}| \leq |\Delta_t|/2$. -
Case 2b:
$y^q_{t+1} \leq y^q_t$(another improvement). Now the minimum is known to lie in either$[x^-_t, x^q_t]$or$[x^q_t, x^+_t]$based on which side contains$x^q_{t+1}$, and this is reflected in$\Delta(P_{t+2})$. The surviving interval has width at most$\max\{x^q_t - x^-_t, x^+_t - x^q_t\} = |\Delta_t|/2$.
Why the two-iteration guarantee: unlike ∆-Bisection where the gradient at the query point immediately provides both a sign signal and a new tangent (simultaneously halving the interval and tightening bounds), ∆-Secant needs at most one "exploratory" query that improves the best value (Case 2) followed by one query that provides the directional information (Case 1 or 2b) — two queries to achieve what one gradient query accomplishes. This matches the intuition that a function evaluation provides "half" the information of a function-plus-gradient evaluation.
Remark 11 (comparison with golden-section search). GSS reduces its bracketing interval (the distance between the two points bracketing the minimum among three maintained points) by a factor $\phi \approx 1.62$ per query. However, this bracketing interval can be arbitrarily larger than the x∗-gap. The example $f(x) = \sqrt{1 + x^2}$ on $[-1000, 900]$ illustrates this: the function behaves like $|x|$ outside $[-1, 1]$ and like $x^2$ inside. GSS must sequentially shrink the full $[-1000, 900]$ interval using golden-ratio spacing, requiring 13 iterations to reach $\Delta_x$ precision below 2. ∆-Secant, by contrast, uses secant constraints to recognize that points far from the origin provide very strong lower bounds (the secants through $(-1000, \sim 1000)$ and $(-100, \sim 100)$ intersect $y^{\text{low}}$ close to the origin), and reduces the x∗-gap below 2 in only 4 iterations. The crucial difference is that ∆-Secant's query locations are adaptive to the actual function shape via the ∆ bounds, whereas GSS's query locations are fixed by the golden ratio regardless of observed function values.
Table 2 validation. The experiments confirm the theoretical advantage. ∆-Secant consistently outperforms GSS, with the margin varying by function. For $f(x) = \max\{-x, 2x\}$ on $[-20, 7]$, GSS requires 50 queries while ∆-Secant requires only 23. For $f(x) = \max\{x^2, (x-3)^2\}$, the gap is even larger: 60 vs. 18 queries. When counting gradient evaluations as separate queries (two per function+gradient call), ∆-Secant often beats ∆-Bisection as well — for $f(x) = |x|$, ∆-Secant needs 7 queries vs. ∆-Bisection's 6 queries × 2 (function+gradient) = 12 equivalent queries, making the derivative-free method more query-efficient in terms of total oracle calls. This is because a single function evaluation provides a point on the curve, while a gradient provides only the local slope — the former can constrain the optimality region from multiple secant pairs simultaneously, while the latter constrains via exactly one tangent.
Quasi-Exact Line Search for Gradient Descent
The paper's third major component bridges the 1D algorithms to multivariate optimization: using ∆-Secant as a subroutine for selecting step sizes in gradient descent, with a relative stopping criterion that trades off optimality against query count.
The setting. At iteration $k$ of gradient descent on a multivariate function $f: \mathbb{R}^d \to \mathbb{R}$, the current iterate is $x_k$ and the search direction is the negative gradient $-\nabla f(x_k)$. Define the 1D restriction:
where $\tilde{f}(\alpha)$ is the function value when stepping a distance $\alpha$ along the negative gradient direction; the domain $\alpha \geq 0$ ensures we only consider descent steps; and $\tilde{f}$ is convex in $\alpha$ because $f$ is convex and composition with an affine map preserves convexity.
The goal is to find an $\alpha$ that sufficiently reduces $\tilde{f}$ without solving the 1D problem to full numerical precision.
The relative stopping criterion. Instead of terminating when $|\Delta_y(P_t)| \leq y_{\text{tol}}$ for a small absolute tolerance, the quasi-exact line search uses:
where $y^{\text{left}}(P_t) = \tilde{f}(0)$ is the function value at the left boundary (the starting point $\alpha = 0$); $y^{\text{low}}(P_t)$ is the best function value found so far in the search; $|\Delta_y(P_t)|$ is the y∗-gap (an upper bound on $y^{\text{low}} - \tilde{f}(\alpha^*)$); and $c > 0$ is a user-chosen parameter (recommended $c = 1$).
What it computes: the stopping condition says "stop when the improvement we've already achieved $y^{\text{left}} - y^{\text{low}}$ is at least $c$ times the maximum possible remaining improvement $|\Delta_y|$." Equivalently, the remaining possible gain is at most $1/(c+1)$ of the total possible gain — we've captured at least a fraction $c/(c+1)$ of the available decrease.
Why this form: traditional exact line search (run ∆-Secant to numerical precision with $y_{\text{tol}} \approx 10^{-10}$) guarantees near-optimal step sizes but wastes queries on marginal improvements. Backtracking with Armijo's condition makes a relative comparison ($f(x) - f(x - \alpha \nabla f) \geq \varepsilon \alpha \|\nabla f\|^2$) but the comparison is to the gradient norm rather than to the provable optimality gap — Armijo has no lower bound on $f(x^*)$ and thus cannot quantify how close it is to optimal. The quasi-exact criterion uses the y∗-gap to make the relative comparison provably tight: Theorem 12 shows that any $\alpha_c$ satisfying Equation (7) achieves at least $c/(c+1)$ of the maximum possible decrease. Armijo's condition can guarantee a fraction of the gradient-predicted decrease but cannot relate this to the true optimal decrease without additional assumptions (like knowledge of the Lipschitz constant $M$).
The interval-growing mechanism. Algorithm 3 implements quasi_exact_line_search with an outer loop that expands the search interval as needed. The algorithm maintains an interval $[0, x_{\text{right}}]$ and a set of points $P_i$. It starts with $x_{\text{right}} = \alpha_{\text{prev}}$ (the step size from the previous GD iteration, initialized to 1). The key logic:
for i = 0, 1, 2, ...:
x_right = α_prev * 4^i
P'_i = P_i ∪ {(x_right, f̃(x_right))}
P_{i+1} = ∆-Secant_core(f̃, P'_i, stop_when)
if x_low(P_{i+1}) < x_right:
return y_low(P_{i+1})
At each outer iteration $i$, the right boundary is multiplied by 4 relative to the previous iteration. The set $P_i$ from the previous iteration is augmented with the new boundary point, and ∆-Secant is run with the stopping condition. If ∆-Secant returns a minimum not at the right boundary ($x^{\text{low}} < x_{\text{right}}$), the algorithm terminates — the minimum has been found within the current interval. If the minimum is at the right boundary, the function is still decreasing at $x_{\text{right}}$, so the interval is expanded and the search continues.
Why multiply by 4: the factor 4 ensures that the interval expansion is exponential, so at most $O(\log(\alpha^*/\alpha_{\text{prev}}))$ expansions are needed. Using a factor of 2 would require more iterations; a factor of 10 might overshoot dramatically and waste evaluations on unnecessarily large α values. The factor 4 balances these concerns and is not theoretically critical — any constant > 1 would work.
Why reuse previous points: when expanding the interval, all previously evaluated points remain valid and contribute to $\Delta(P)$. The new boundary point $(x_{\text{right}}, \tilde{f}(x_{\text{right}}))$ expands the x-range of $P$ and may provide new secant constraints. This means the computational effort invested in earlier, smaller intervals is never wasted — it continues to constrain the optimality region when the interval expands.
Theorem 12 (quasi-exact optimality bound). Let $\tilde{f}: [0, \infty) \to \mathbb{R}$ be convex, let $\alpha_{\infty} \in \arg\min_{\alpha \geq 0} \tilde{f}(\alpha)$ with $\alpha_{\infty} < \infty$ and $\tilde{f}(\infty) > \tilde{f}(\alpha_{\infty})$ (the function eventually increases), and let $\alpha_c$ be the step size returned by quasi_exact_line_search with parameter $c$. Then:
where $\tilde{f}(0) - \tilde{f}(\alpha_c)$ is the actual decrease achieved; $\tilde{f}(0) - \tilde{f}(\alpha_{\infty})$ is the maximum possible decrease (exact line search optimum); and the ratio $c/(c+1)$ is the fraction of the optimal decrease guaranteed.
What it computes: a worst-case guarantee on how much improvement the quasi-exact line search leaves on the table compared to perfect exact search. For $c = 1$, the guarantee is at least half of the optimal decrease; for $c = 10$, at least 91% of optimal decrease; for $c = 0.1$, at least 9% of optimal decrease.
Why this form: the proof is a direct consequence of the stopping condition and Theorem 5. From Theorem 5, $|\Delta_y(P)| \geq y^{\text{low}} - \tilde{f}(\alpha_{\infty})$ — the y∗-gap upper-bounds the suboptimality. Combining with the stopping condition $\tilde{f}(0) - \tilde{f}(\alpha_c) \geq c |\Delta_y(P)|$ gives:
Adding $c\tilde{f}(0) - c\tilde{f}(\alpha_c)$ to both sides yields the result. The algebraic manipulation reveals that $c$ trades off query budget (larger $c$ means tighter optimization per line search) against convergence speed (captured in Theorem 13).
Theorem 13 (GD convergence with quasi-exact line search). For an $m$-strongly convex and $M$-smooth function $f: \mathbb{R}^d \to \mathbb{R}$, after $k$ iterations of gradient descent with quasi-exact line search:
where $f(x^*) = y^*$ is the global minimum; $m$ is the strong convexity constant (the function curves upward at least as fast as a quadratic with curvature $m$); $M$ is the smoothness constant (the gradient is $M$-Lipschitz, so the function does not curve upward faster than a quadratic with curvature $M$); $m/M \leq 1$ is the inverse condition number; and $c/(c+1)$ is the quasi-exact slack factor.
What it computes: a linear convergence rate — the suboptimality is multiplied by a constant factor $1 - \frac{c}{c+1}\frac{m}{M}$ at each GD iteration. For exact line search ($c = \infty$, giving $c/(c+1) = 1$), the rate is $1 - m/M$, matching the standard textbook guarantee (Boyd and Vandenberghe, 2004). For quasi-exact with $c = 1$, the rate is $1 - \frac{1}{2}\frac{m}{M}$ — at most a factor 2 slower in the number of GD iterations compared to exact search. In exponential form:
Why this form: the proof adapts the standard GD convergence proof with exact line search by replacing the exact optimal decrease $f(x_k) - f(x^{\infty}_k) \geq \|\nabla f(x_k)\|^2 / (2M)$ with the quasi-exact guarantee from Theorem 12, which multiplies this bound by $c/(c+1)$. The strong convexity bound $\|\nabla f(x_k)\|^2 \geq 2m(f(x_k) - f(x^*))$ is unchanged. The combined effect is that quasi-exactness introduces a multiplicative slowdown of $c/(c+1)$ in the linear convergence rate, which is bounded by 1/2 for the recommended $c = 1$ and approaches 1 as $c \to \infty$.
Remark 14 (using initial gradient information). Algorithm 3 can be modified to incorporate the known initial gradient $\tilde{f}'(0) = -\|\nabla f(x_k)\|^2$. By adding two virtual points at $\alpha = -1$ and $\alpha = -2$ with function values $\tilde{f}(0) + \|\nabla f\|^2$ and $\tilde{f}(0) + 2\|\nabla f\|^2$ respectively, the secant through these virtual points has slope $\|\nabla f\|^2$ and provides the same lower bound as the tangent at $\alpha = 0$. This effectively gives ∆-Secant gradient-level information at the left boundary, potentially accelerating convergence on the first few iterations when the left boundary is the most informative point. The paper notes (Appendix B.2) that this should be done by explicitly adding the linear constraint $\tilde{f}(\alpha) \geq \tilde{f}(0) - \alpha \|\nabla f\|^2$ rather than relying on virtual points, for numerical stability.
Table 3 and Figure 6 — experimental comparison with backtracking. The experiments demonstrate the robustness claim:
-
On
$f(x) = 3.95x^2$with$x_0 = 1000$(Example 15, the flying squirrel), backtracking with$\varepsilon = 0.01$requires 754 GD iterations and 3020 total queries, matching quasi-exact with$c = 0.01$(754 iterations, 2265 queries) — both suffer from the same "too-lax stopping" issue. But for$c \geq 0.1$, quasi-exact needs only 4 GD iterations and 25 queries. Backtracking with$\varepsilon = 0.5$also needs only 4 iterations and 25 queries on this function. The problem: no single$\varepsilon$works on all functions. -
On
$f(x) = e^{3x} + e^{-3x}$with$x_0 = 100$(Example 16, the snowplow skier), backtracking with$\varepsilon = 0.5$is catastrophic — 898 GD iterations, 193,817 queries. With$\varepsilon = 0.1$, 229 iterations, 48,266 queries. With$\varepsilon = 0.01$, 13 iterations, 1,376 queries. Quasi-exact with$c = 1$takes 10 iterations, 965 queries; with$c = 0.1$, 44 iterations, 1,090 queries. The quasi-exact performance is stable across$c \in [0.5, 10]$(6–10 GD iterations, ~950–960 queries), while backtracking varies by two orders of magnitude in query count across$\varepsilon \in [0.01, 0.8]$. -
On the 100-dimensional loss function of Equation (9) (Figure 6), quasi-exact with
$c = 0.1, 1, 2$all achieve rapid descent, reaching loss$< 10^{-20}$within ~400–600 total queries. Backtracking with$\varepsilon = 0.01$plateaus early (fails to decrease loss below$\sim 10^{-5}$after hundreds of queries),$\varepsilon = 0.1$stalls even earlier, and$\varepsilon = 0.5$makes essentially no progress. The exponential curvature of Equation (9) triggers the "snowplow skier" failure mode for backtracking.
Why backtracking fails systematically. The Armijo condition $f(x) - f(x - \alpha\nabla f) \geq \varepsilon\alpha\|\nabla f\|^2$ tests whether the actual decrease is at least a fraction $\varepsilon$ of the decrease predicted by the first-order Taylor expansion. On functions where the true decrease is much smaller than the gradient predicts (high curvature, "steep but rapidly flattening"), large $\varepsilon$ makes the condition too demanding — the backtracking shrinks $\alpha$ repeatedly without accepting any step, accumulating queries. On functions where the gradient is small relative to the function value (shallow slopes), small $\varepsilon$ makes the condition too lenient — it accepts tiny steps that barely move the iterate. The quasi-exact criterion $\tilde{f}(0) - y^{\text{low}} \geq c|\Delta_y|$ avoids both failures because $|\Delta_y|$ adapts to the function's actual geometry via the secant constraints — on a highly curved function, the secants quickly tighten ∆ even if the function value hasn't decreased much, making $|\Delta_y|$ small and the stopping condition easy to satisfy. On a flat function, $|\Delta_y|$ remains large until the algorithm has explored far enough to find the upturn, naturally spending more queries where the optimal step size is ambiguous.
Recommendation: use $c = 1$, which balances practical speed (the $c/(c+1)$ slowdown factor is at most 2) with query efficiency (the line search stops well before numerical precision). The experiments show $c=1$ is within a factor of 2 of the best $c$ for every function tested, making it a robust default.
4. Key Insights and Innovations
Innovation 1: The x∗-gap as a Refined Optimization Object — Shrinking the Tightest Provable Bound, Not the Original Interval
The paper's central conceptual move is to change what gets shrunk during line search. Prior 1D minimization algorithms — bisection search, golden-section search — operate on the bracketing interval: the full span $[x_0, x_1]$ of evaluated points known to contain the minimum. Their convergence guarantees are measured in terms of this interval's width, and their query strategies (midpoint for bisection, golden-ratio spacing for GSS) optimize the worst-case reduction of this interval. The field accepted Boyd and Vandenberghe's (2004) characterization that bisection's factor-2 reduction is "the best it can be" for quasiconvex functions.
The reframing is: stop shrinking the original interval and start shrinking the provable optimality region ∆ — the set of $(x, y)$ pairs that are geometrically consistent with all convexity constraints from the evaluated points. The x∗-gap $\Delta_x$ (the projection of ∆ onto the x-axis) is always a subset of the bracketing interval, and on functions with strong curvature or asymmetric values at the boundaries, it can be dramatically smaller — by a factor of 3 or more at the very first iteration, as Figure 1 illustrates for ∆-Bisection. The algorithms then query at the midpoint of this tighter region rather than the midpoint of the original interval.
This is not a tweak to the query rule; it is a fundamental shift in what the algorithm maintains. The optimality region ∆ is a richer object than an interval — it encodes the function's local geometry through tangent or secant intersections, it provides both x-bounds and y-bounds simultaneously, and its shape (triangle, quadrilateral, or two triangles) reflects the asymmetry of the current information. Prior methods treated all points as interchangeable interval endpoints; ∆-Bisection and ∆-Secant treat them as generators of half-plane constraints whose intersection defines the feasible set for $(x^*, f(x^*))$.
The significance is both theoretical and practical. Theoretically, the x∗-gap reduction guarantees in Theorems 1 and 10 are strictly stronger than the interval-reduction guarantees of bisection and GSS: bisection guarantees factor 2 on the full interval, ∆-Bisection guarantees factor 2 on the (smaller) x∗-gap, which implies at least factor 2 on the full interval but often much more. Practically, this transforms line search from an algorithm whose convergence is bottlenecked by the initial interval width to one whose convergence adapts to the function's actual shape — steep slopes and large value differences at the boundaries automatically yield tight initial bounds and fast convergence, as seen in Table 1 where $\max\{-x, 2x\}$ reduces in 19 iterations versus 37 for bisection.
This is a fundamental rather than incremental advance because it redefines the optimization target. It reveals that the quasiconvex methods were not information-theoretically optimal for convex functions — they systematically discarded the magnitude information in gradients and the lower-bound information in secants — and that the discarded information can be captured by a simple geometric construction with no additional oracle queries.
Innovation 2: The y∗-gap as a Principled, Provable Stopping Criterion — Solving the Termination Problem for General Convex Functions
A direct consequence of maintaining the optimality region ∆ is that its y-axis projection $\Delta_y$ provides a provable upper bound on the suboptimality of the current best point: $|\Delta_y| \geq y^{\text{low}} - f(x^*)$. This quantity is computable after every query using only the same convexity constraints that define $\Delta_x$, requiring no Lipschitz constants, strong convexity parameters, or other unknown function properties.
This solves a problem that was previously unsolvable for quasiconvex methods. For general quasiconvex functions, knowing that $x^* \in [x_0, x_1]$ gives no bound on $f(x^{\text{low}}) - f(x^*)$ — the function could plunge arbitrarily deep in the remaining interval with no violation of quasiconvexity. This is why bisection search and golden-section search cannot provide principled termination guarantees: they can bound the x-error but not the y-error. Practitioners either run these algorithms for a fixed number of iterations (risking both premature termination and wasted computation) or stop when the x-interval is small (which provides no guarantee about function value accuracy for ill-conditioned functions).
The y∗-gap changes this. It is finite from the first iteration of ∆-Bisection (as soon as two gradient evaluations at points with opposite-sign slopes are available, the tangent intersection provides a finite lower bound) and becomes finite for ∆-Secant once four points surround the minimum (two on each side, providing secant lower bounds from both directions — Example 7 shows that three points can leave $|\Delta_y| = \infty$ but four suffice). The stopping criterion $|\Delta_y| \leq y_{\text{tol}}$ is then provably correct: when it triggers, $y^{\text{low}} - f(x^*) \leq y_{\text{tol}}$ is guaranteed. Table 2 shows these termination guarantees in action: every algorithm run stops when the y∗-gap reaches $10^{-10}$, and the reported query counts reflect the cost of achieving this guarantee.
This contribution can also be retrofitted onto existing algorithms. The paper notes that golden-section search can compute $|\Delta_y(P_t^{\text{GSS}})|$ using the five-point construction of Equation (6) on the points it already maintains, providing principled termination with zero modification to its query strategy — only the stopping condition changes. The GSS column in Table 2 uses this enhanced termination, so the comparisons are fair (all algorithms stop at the same provable y∗-gap threshold).
The innovation is fundamental in the sense that it fills a recognized gap in the optimization toolbox: how to stop a 1D convex minimization algorithm with rigorous guarantees without knowing strong convexity or smoothness parameters, without requiring the function to be differentiable everywhere, and without additional oracle queries beyond those already performed for the search. It is also what enables the quasi-exact line search of Section 3.3 — without a computable y∗-gap, there is no way to formulate a relative stopping condition with provable optimality bounds.
Innovation 3: Exposing and Diagnosing the Brittleness of Backtracking Line Search Through Convex Counterexamples
The paper provides a sharp diagnostic critique of backtracking line search with Armijo's condition that goes beyond the standard "it works well in practice" narrative. Backtracking is the default line search in virtually all gradient descent implementations — Boyd and Vandenberghe (2004) describe it as the method of choice after exact line search was abandoned as too expensive — and its convergence theory (linear rate for strongly convex smooth functions) is considered settled.
The paper's contribution is not a new claim about backtracking's weaknesses (the flying squirrel oscillatory mode is well-known, and Truong and Nguyen, 2021 studied failure cases), but rather: (1) the systematic isolation of two distinct and opposing failure modes, (2) the demonstration that they force an irreconcilable tradeoff in the single parameter $\varepsilon$, and (3) the provision of simple, closed-form convex functions that trigger each failure mode deterministically.
Specifically:
- Failure Mode 1 — the flying squirrel (Example 15): Small
$\varepsilon$causes slow linear convergence because the Armijo condition accepts steps that barely reduce the function value relative to the gradient's prediction. On$f(x) = ax^2$with carefully chosen$a$, the iterates oscillate between symmetric points with$x_{k+1} = -(1-\varepsilon)x_k$, reducing distance to zero by only a factor$1-\varepsilon$per iteration. This is not a pathological edge case — it occurs precisely when the function's curvature$a$aligns with the backtracking parameters$\tau$and$\varepsilon$as$a = \tau^{-t'}(1-\varepsilon)$, a condition that can easily arise in practice for poorly conditioned quadratics. - Failure Mode 2 — the snowplow skier (Example 16): Large
$\varepsilon$causes catastrophic query explosion because the Armijo condition demands that the line search find a point where the actual decrease tracks the gradient-predicted decrease closely, but on highly curved functions (like exponentials), the function departs from its linear approximation almost immediately. Each backtracking iteration shrinks$\alpha$by$\tau$, but must shrink it many times before the condition is met, and each shrinkage costs a function evaluation. The total query count scales quadratically in the initial distance to the minimum, making large$\varepsilon$unusable on such functions. - The tradeoff: Table 3 shows that no single
$\varepsilon$works across even three simple functions. On$3.95x^2$,$\varepsilon = 0.01$is catastrophic (754 GD iterations) while$\varepsilon = 0.5$is excellent (4 iterations). On$e^{3x} + e^{-3x}$, the ranking is inverted:$\varepsilon = 0.01$requires 13 iterations while$\varepsilon = 0.5$requires 898. The best$\varepsilon$on one function is the worst on the other.
The diagnostic insight is that the Armijo condition compares actual decrease to gradient-predicted decrease — a local, linear quantity — but the appropriate threshold depends on the function's curvature, a global, second-order quantity that backtracking does not measure. Quasi-exact line search avoids this by comparing actual decrease to the provable optimality gap $|\Delta_y|$, which the secant constraints automatically adapt to the function's curvature without needing to know it explicitly. On highly curved functions, the secants tighten rapidly, $|\Delta_y|$ shrinks, and the stopping condition is satisfied early — precisely when further optimization would yield diminishing returns.
This is an incremental contribution in the sense that the individual failure modes were known, but diagnostically fundamental because it reframes the problem: it is not that backtracking needs better parameter tuning (the standard advice of $\varepsilon \in [0.01, 0.3]$), but that the Armijo condition's structure — comparing to gradient magnitude rather than to a provable lower bound — is inherently unable to adapt to curvature variation across functions. The quasi-exact approach solves this by replacing the gradient-based comparator with a curvature-adaptive one, and the experiments validate that this yields robustness across the full parameter range $c \in [0.5, 10]$.
Innovation 4: Unifying Gradient-Based and Derivative-Free Convex Search Under a Single Geometric Principle
The paper reveals a structural duality between ∆-Bisection and ∆-Secant that was previously unrecognized in the optimization literature. Gradient-based methods (bisection) and derivative-free methods (golden-section search) were treated as fundamentally different algorithm classes with incomparable guarantees — bisection guarantees factor-2 x-interval reduction per gradient query, GSS guarantees factor-$\phi$ x-interval reduction per function query, and neither's bound is strictly stronger than the other's.
The unification is: both ∆-Bisection and ∆-Secant maintain the same optimality region ∆ and query at its midpoint; they differ only in how they construct the lower bounds — tangents from single points with gradient information, versus secants from point pairs without gradients. The convergence guarantees are commensurate: ∆-Bisection halves the x∗-gap every one gradient query (Theorem 1), ∆-Secant halves it every two function queries (Theorem 10). The ratio of 1:2 matches the information-theoretic intuition that a gradient query provides twice the information of a function query (it gives both a function value and a local slope, versus just a point on the curve).
This reframing has several consequences:
-
Fair comparison across oracle models. Standard comparisons between bisection (gradient-based) and GSS (derivative-free) are apples-to-oranges because one uses a stronger oracle. The paper introduces the convention of counting a function+gradient query as two queries (Table 2), putting both algorithm families on the same cost model. Under this accounting, ∆-Secant often beats ∆-Bisection — for
$|x|$, ∆-Secant requires 7 function queries while ∆-Bisection requires 6 function+gradient queries (equivalent to 12 oracle calls), because secants from three well-placed function evaluations can constrain ∆ more tightly than two tangents. This is a genuinely surprising result: sometimes derivative-free is more query-efficient than gradient-based, even when gradients are cheap. -
Transfer of principles. The ε-repulsion mechanism from ∆-Secant (Section 3.2.2) — nudging queries away from previously evaluated points to avoid stalling — has a natural gradient-based analog: if the tangent intersection happens to coincide with an evaluated point, the gradient at that point would be zero and the algorithm would terminate anyway. The paper's modular architecture makes such transfers explicit.
-
Unified gap extraction. Both algorithms extract the x∗-gap and y∗-gap from ∆ using the same geometric logic — intersect lower bounds with the horizontal line at
$y^{\text{low}}$for x-bounds, intersect lower bounds with each other for the y-lower-bound — with the only difference being whether the lower bounds are lines through individual points (tangents) or through point pairs (secants). Equation (6) for ∆-Secant is structurally identical to Equations (2) and (3) for ∆-Bisection, with slopes$a_{01}$,$a_{34}$replacing gradients$f'(x^0)$,$f'(x^1)$.
This contribution is fundamental in that it provides a single algorithmic template for 1D convex minimization into which both gradient and derivative-free methods fit as special cases. It suggests natural extensions — for instance, a hybrid method that uses both tangents (where gradients are available) and secants (for robustness when gradients are noisy) simultaneously in the same ∆ computation — that the paper leaves to future work.
Innovation 5: The c/(c+1) Convergence Framework — Decoupling Line Search Precision from Outer Iteration Convergence
The quasi-exact line search (Section 3.3) introduces a theoretical framework that decouples the precision of the 1D line search from the convergence rate of the outer gradient descent iteration. Prior theory for backtracking line search bundles these together: the Armijo parameter $\varepsilon$ and the shrinkage factor $\tau$ simultaneously affect how many backtracking steps are taken (inner loop cost) and the linear convergence rate $1 - 2\tau\varepsilon m/M$ (outer loop speed). This coupling creates the tension documented in Innovation 3 — changing $\varepsilon$ to speed up the inner loop can catastrophically slow the outer loop, and vice versa.
The quasi-exact framework introduces the parameter $c$ that cleanly separates these concerns. Theorem 12 guarantees that any step size satisfying the relative stopping condition $\tilde{f}(0) - y^{\text{low}} \geq c|\Delta_y|$ achieves at least $c/(c+1)$ of the optimal decrease. This guarantee holds regardless of how many queries were needed to satisfy the condition — the inner loop cost is determined by the function's geometry and the value of $c$, but the outer convergence rate is determined purely by $c/(c+1)$. The factor $c/(c+1)$ then appears in the linear convergence rate of Theorem 13 as a multiplicative slowdown compared to exact line search: $1 - \frac{c}{c+1}\frac{m}{M}$ versus $1 - \frac{m}{M}$ for exact search. For $c = 1$, the slowdown is at most a factor of 2 in the number of GD iterations, while the inner loop stops after achieving only half the possible decrease — a substantial computational savings.
This is theoretically novel compared to the backtracking literature. Backtracking's convergence proofs (Boyd and Vandenberghe, 2004, Section 9.3.1) rely on the Armijo condition to bound the decrease per iteration by $f(x_k) - f(x_{k+1}) \geq \varepsilon \alpha \|\nabla f(x_k)\|^2$, then bound $\alpha$ from below using the Lipschitz constant $M$ to get $f(x_k) - f(x_{k+1}) \geq (\varepsilon/M) \|\nabla f(x_k)\|^2$. The final rate depends on $\varepsilon$ directly. The quasi-exact proof replaces this with a bound on $f(x_k) - f(x_{k+1})$ relative to the true optimal decrease, not the gradient-predicted decrease, using Theorem 12 and the y∗-gap. The result is a convergence rate that depends on $c/(c+1)$ — a number close to 1 for any reasonable $c$ — rather than $\varepsilon$, which can be arbitrarily small.
Practically, this means that $c = 1$ is a universally safe default. The experiments in Table 3 and Figure 6 confirm that $c \in [0.5, 10]$ yields consistent performance across all test functions, in stark contrast to backtracking's extreme sensitivity. The theoretical slowdown factor of $c/(c+1) = 1/2$ for $c = 1$ is a small price for eliminating the need to hand-tune a parameter whose optimal value varies by two orders of magnitude across problem instances.
This is a fundamental contribution to the theory of line search methods because it provides the first framework where the inner optimization precision can be chosen based on a single, interpretable parameter with provable, dimension-free bounds on the outer convergence rate, without requiring knowledge of the function's smoothness or strong convexity constants. It also opens the door to adaptive strategies — for instance, increasing $c$ in later GD iterations as the optimum is approached — that the paper mentions but does not develop.
5. Experimental Analysis
Evaluation Methodology
-
Dataset. The experiments span two categories. For the 1D convex minimization algorithms (Tables 1 and 2), the "dataset" is a collection of 11 manually selected convex functions with specified domains — including
|x|,x^2,x^4,max{-x, 2x},sqrt(1 + x^2),x log x - x, and compositions thereof — chosen to exercise different difficulty characteristics (asymmetric minima, boundary minima, piecewise-linear, smooth but non-quadratic, etc.). For the multivariate gradient descent experiments (Table 3, Figure 6), the test functions are3.95x^2(a specific quadratic chosen to trigger Armijo's flying squirrel failure atε = 0.01),e^{3x} + e^{-3x}(a sum of exponentials triggering the snowplow skier failure),x^4 + y^4(a degenerate-minimum function from Truong and Nguyen, 2021), and an artificial 100-dimensional loss function defined in Equation (9) withN = 10,d = 100, random initialization in[-20, 20]^d, and random problem parametersa_{i,j} ∈ [-1, 1]. -
Base model(s). This is an optimization algorithms paper — there are no learned models. The "base algorithm" being augmented is gradient descent (GD) for the multivariate experiments, and the line search subroutines being proposed (∆-Bisection, ∆-Secant) are compared against standard quasiconvex alternatives (bisection search, golden-section search) and backtracking line search with Armijo's condition. The gradient descent variant used in Algorithm 3 (quasi-exact) and Algorithm 4 (backtracking) includes an interval-growing mechanism to handle unbounded domains.
-
Metrics. The primary metric is number of queries (function evaluations only for derivative-free methods; function+gradient evaluations for gradient-based methods, with a function+gradient call counting as two queries for fair comparison, as noted in the Table 2 caption). For the multivariate experiments (Table 3), both GD iterations and total queries are reported, with the loss
f(x_k) - f(x^*)tracked until it drops below10^{-10}. The x-axis in Figure 6 is cumulative function+gradient queries, which the paper notes "is strongly correlated with computation time." A secondary metric is the provable y∗-gap|Δ_y|, which serves as both a termination criterion (algorithms stop when|Δ_y| ≤ y_tol = 10^{-10}for Tables 1–2) and a diagnostic of how quickly each algorithm tightens its optimality bounds. -
Baselines. Four baselines are compared:
- Bisection search (Boyd and Vandenberghe, 2004): gradient-based 1D quasiconvex minimization, queries at the midpoint of the current x-interval, reduces the interval by exactly factor 2 per query.
- Golden-section search (GSS) (classic, as described in Boyd and Vandenberghe, 2004): derivative-free quasiconvex minimization, maintains three bracketing points, reduces the interval by factor
φ ≈ 1.62per query. The paper's version augments GSS with the 5-point y∗-gapΔ_y(P_t)as a stopping criterion — otherwise GSS would have no principled way to terminate on convex functions. - Backtracking line search with Armijo's condition (Armijo, 1966; Boyd and Vandenberghe, 2004): the standard inexact line search for gradient descent, with parameters
τ = 1/2(shrinkage factor) andεvaried across{0.001, 0.01, 0.1, 0.3, 0.5, 0.8}. Algorithm 4 extends the standard backtracking with interval-growing (multiplying the interval by 4 when the returned step is at the boundary), matching the capability of the quasi-exact line search to handle unbounded domains.
-
Generation budget / compute accounting. "Compute" is measured in oracle queries rather than FLOPs or wall-clock time. One function evaluation = 1 query. One function+gradient evaluation = 2 queries (as explicitly stated in the Table 2 caption: "For gradient-based algorithms, a function+gradient query counts as two queries"). This accounting is crucial for fair comparison: ∆-Secant with 7 function queries uses 7 oracle calls, while ∆-Bisection with 4 iterations uses 8 oracle calls (4 function queries + 4 gradient queries), giving ∆-Secant a slight advantage on some functions (e.g.,
|x|where ∆-Secant needs 7 queries vs. ∆-Bisection's4 × 2 = 8equivalent queries). For the GD experiments, total queries include all function and gradient evaluations across all GD iterations and line search inner loops. The stopping tolerance for Tables 1–2 isy_tol = 10^{-10}; for Table 3 and Figure 6, GD runs untilf(x_k) - f(x^*) ≤ 10^{-10}or 2000 total queries (Figure 6). -
Cross-validation / statistical protocol. There is no cross-validation or statistical protocol — this is a deterministic optimization algorithms paper. All functions have known closed forms and known minima, all algorithms are deterministic (the ∆-Secant ε-repulsion uses a fixed
ε = 2^{-7}, and the otherwise-ambiguous tie-breaking whenf'(x_q) = 0terminates the algorithm), and initial conditions (e.g.,x_0 = 1000for the quadratic,x_0 = 100for the exponential sum,(0.1, 15)for the quartic) are fixed per experiment. The 100-dimensional loss function (Equation 9, Figure 6) uses a single random draw of parameters and initialization — the paper describes the figure as illustrating "a typical example" without reporting variance across random seeds. This is a genuine methodological weakness: without multiple random seeds for the high-dimensional experiment, it is unclear whether Figure 6's ordering of algorithms (quasi-exact dominating backtracking) is reliable or an artifact of a favorable random draw.
Main Quantitative Results
1D Convex Minimization: ∆-Bisection vs. Bisection Search (Table 1)
Headline finding. ∆-Bisection consistently requires fewer iterations than bisection search to reduce the provable y∗-gap below 10^{-10}, with improvements ranging from modest to dramatic depending on the function. Across the 11 test functions, ∆-Bisection uses 17% to 76% fewer iterations than bisection, with a typical reduction of roughly a factor 1.5–2.
Function-by-function breakdown (Table 1). The table reports iterations for bisection search and ∆-Bisection (not counting the two initial boundary queries, which are identical for both algorithms):
-
Boundary-minimum functions terminate immediately. For
f(x) = -xon[-20, 7]andf(x) = |x|on[-20, 7], both algorithms take 0 iterations becausef'(x_left) ≥ 0orf'(x_right) ≤ 0makes|Δ_y^0| = 0. This is not a comparison between algorithms but a correctness check on the termination logic. -
Piecewise-linear functions show the largest gains. On
max{-x, 2x}on[-20, 7], bisection requires 37 iterations while ∆-Bisection requires only 19 — a 49% reduction. On the shifted versionmax{-x, 2x}on[-0.01, 100], the gap is 37 vs. 14 (62% reduction). These functions benefit because the tangents at the boundary points have steep slopes, causing the initial x∗-gap to be far smaller than the full interval — ∆-Bisection exploits this immediately, while bisection must slowly chip away at the full[-20, 7]or[-0.01, 100]interval regardless of tangent information. -
Smooth but asymmetric functions also benefit substantially. On
|x|^{1.1}on[-20, 7], bisection takes 34 iterations vs. ∆-Bisection's 11 (68% reduction). Onx^2on[-20, 7], the gap is 20 vs. 12 (40% reduction). Onsqrt(1 + x^2)on[-1000, 900]— a function that behaves like|x|at large magnitudes and likex^2near zero — bisection needs 27 iterations vs. ∆-Bisection's 19 (30% reduction). The wide initial interval makes the x∗-gap advantage pronounced because the tangents at±1000have slopes near±1, intersectingy_lowclose to the origin, while bisection patiently halves the 1900-unit interval. -
Non-quadratic smooth functions see moderate gains. On
x log x - xon[0.001, 20](minimum atx^* = 1), bisection takes 20 iterations vs. ∆-Bisection's 12 (40% reduction). Onx^4on[-20, 7], 11 vs. 8 (27% reduction). On1/x^2 + x^2on[0.001, 100], 23 vs. 18 (22% reduction). The smaller relative gains reflect functions where the initial tangent intersections don't cut off as much of the interval — forx^4, the flatness near zero means the tangents at-20and7have moderate slopes relative to the function's high values, limiting the initial ∆x shrinkage.
Why the variation matters. The fact that ∆-Bisection's advantage ranges from 22% to 76% across these 11 functions demonstrates that the x∗-gap is not uniformly smaller than the full interval by a constant factor — it depends on how much the function's values and slopes at the boundary points reveal about the minimum's location. Functions with large value differences across the interval and steep slopes at the boundaries (piecewise-linear, exponential-like) concentrate the x∗-gap tightly around the minimum early, giving ∆-Bisection a large head start. Functions where both boundary values are similar or the slopes are shallow (quartics near flat regions) keep the x∗-gap closer to the full interval, making ∆-Bisection's advantage more modest.
The "lucky" case. The paper notes that for f(x) = |x|, ∆-Bisection terminates in 4 iterations because "the x∗-gap is reduced to 0 on the second iteration, due to the symmetry of the function." This is a specific instance where the query point lands exactly at the kink (the minimum), the left and right derivatives have opposite signs and infinite magnitude in the limit, and the tangent intersection precisely identifies the minimum. This is not a general property — it's an artifact of the absolute value's perfect symmetry and non-differentiability at the minimum — but it illustrates that ∆-Bisection can terminate in finite iterations on non-smooth functions where bisection would require infinitely many.
1D Convex Minimization: ∆-Secant vs. Golden-Section Search (Table 2)
Headline finding. When counting a function+gradient query as two oracle calls, ∆-Secant (derivative-free) matches or outperforms ∆-Bisection (gradient-based) on 8 of 11 functions, and always substantially outperforms golden-section search (GSS), often by a factor of 2 or more in query count. ∆-Secant's per-query efficiency derives from its adaptive query placement at the midpoint of the x∗-gap, which incorporates secant constraints that GSS ignores.
Query counts (Table 2). The table reports total queries including initial boundary evaluations, with ∆-Bisection counting function+gradient as two queries:
| Function | Domain | ∆-Bisection (queries) | ∆-Secant (queries) | GSS (queries) | Winner (derivative-free vs. gradient) |
|---|---|---|---|---|---|
-x | [-20, 7] | 4 | 3 | 3 | Tie (all detect boundary minimum) |
| ` | x | ` | [-20, 7] | 78 | 7 |
max{-x, 2x} | [-20, 7] | 78 | 23 | 50 | ∆-Secant |
max{-x, 2x} | [-0.01, 100] | 78 | 18 | 52 | ∆-Secant |
| ` | x | ^{1.1}` | [-20, 7] | 72 | 28 |
x^2 | [-20, 7] | 42 | 27 | 33 | ∆-Secant |
sqrt(1 + x^2) | [-1000, 900] | 58 | 23 | 41 | ∆-Secant |
x log x - x | [0.001, 20] | 44 | 23 | 32 | ∆-Secant |
max{x^2, (x-3)^2} | [-5, 55] | 80 | 18 | 60 | ∆-Secant |
max{x^2, (x/2 - 3)^2} | [-5, 55] | 82 | 26 | 58 | ∆-Secant |
x^4 | [-20, 7] | 26 | 18 | 21 | ∆-Secant (marginal) |
1/x^2 + x^2 | [0.001, 100] | 50 | 31 | 36 | ∆-Secant |
Key patterns:
-
∆-Secant dominates GSS on every function. The smallest margin is
x^4(18 vs. 21 queries, a 14% reduction). The largest margins are on the piecewise-linear functions:max{-x, 2x}variants show GSS needing ~50–52 queries while ∆-Secant needs 18–23, a factor of ~2.5× improvement. Onmax{x^2, (x-3)^2}, GSS needs 60 queries vs. ∆-Secant's 18, a factor of >3×. This validates Remark 11's analysis: GSS reduces the full bracketing interval by factor ~1.62 per query, but the x∗-gap can be far smaller, and ∆-Secant's query placement at the midpoint of that tighter region yields dramatically faster convergence. -
∆-Secant often beats ∆-Bisection in total oracle queries. This is the surprising result highlighted in Section 4 (Innovation 4). On
|x|, ∆-Secant requires 7 function queries while ∆-Bisection requires39 iterations × 2 queries/iteration + 2 boundary queries = 80oracle calls (the Table 2 entry of 78 is the total including initial queries). The explanation:|x|has a non-differentiable kink at the minimum, so gradient information at smooth points (away from zero) is misleading — the gradient magnitude near zero doesn't reveal the imminent kink, while secants through points on opposite branches intersect close to the kink. On smooth functions without kinks (e.g.,x^4,x^2), the gradient-based method is more competitive, but ∆-Secant still edges it out (27 vs. 42 forx^2, 18 vs. 26 forx^4) because ensemble secant constraints from multiple function evaluations collectively provide more geometric information than two tangents. -
GSS is closer to ∆-Secant on the smoothest functions. On
x^4(21 vs. 18 queries),x^2(33 vs. 27), and1/x^2 + x^2(36 vs. 31), the gap narrows. These functions have gentle curvature that keeps the x∗-gap close to the bracketing interval initially, so GSS's golden-ratio spacing is not as severely suboptimal. However, ∆-Secant still wins because as soon as the algorithm has placed a few points, the secant constraints begin to tighten ∆x beyond what GSS's fixed spacing achieves.
The gradient-based vs. derivative-free comparison depends on the oracle cost model. If gradient evaluations are cheap (e.g., computed simultaneously with function values via automatic differentiation), counting them as separate queries may overstate ∆-Secant's advantage. The paper's accounting is conservative: it assumes gradients cost as much as function evaluations, which is realistic for finite-difference approximations but pessimistic for AD. If function+gradient counts as a single query, ∆-Bisection would retake the lead on most smooth functions. The paper wisely makes the cost model explicit so practitioners can adjust based on their gradient availability.
Multivariate Gradient Descent: Quasi-Exact vs. Backtracking Line Search (Table 3, Figure 6)
Headline finding. Quasi-exact line search with the default parameter c = 1 achieves competitive or superior performance to the best-tuned backtracking line search on every test function, while being robust across a wide range of c — in stark contrast to backtracking, whose performance varies by orders of magnitude depending on the choice of ε, and for which no single ε works well across all functions.
Table 3 — three functions, fixed tolerance 10^{-10}:
-
On
f(x) = 3.95x^2(quadratic,x_0 = 1000): Quasi-exact withc ∈ [0.1, 1]requires 4 GD iterations and 25 queries. Backtracking withε ∈ [0.1, 0.5]also requires 4 iterations and 25 queries — parity. However, backtracking withε = 0.01requires 754 GD iterations and 3020 queries — a 120× increase in queries. Quasi-exact withc = 0.01also fails similarly (754 iterations, 2265 queries), which is expected because Theorem 12 predicts thatc = 0.01guarantees only ~1% of the optimal decrease, mirroring the too-lenient stopping that plagues the flying squirrel. The critical difference: quasi-exact's failure occurs atc = 0.01(an extreme value far from the recommendedc = 1), while backtracking's failure occurs atε = 0.01, which is within Boyd and Vandenberghe's recommended range[0.01, 0.3]— exactly the values a practitioner might innocently choose. -
On
f(x) = e^{3x} + e^{-3x}(sum of exponentials,x_0 = 100): Quasi-exact withc = 1requires 10 GD iterations and 965 queries. The best backtracking performance is atε = 0.001(10 iterations, 867 queries) — slightly better than quasi-exact in this single instance. However, backtracking degrades catastrophically asεincreases:ε = 0.01needs 13 iterations and 1376 queries;ε = 0.1needs 147 iterations and 31,486 queries;ε = 0.3needs 229 iterations and 48,266 queries;ε = 0.5needs 898 iterations and 193,817 queries (a 200× explosion over the bestε). This is the snowplow skier failure mode: largeεdemands that each step track the linear approximation closely, forcing the backtracking to shrinkαmany times per GD iteration, each shrinkage costing a function evaluation without accepting the step. Quasi-exact withc ∈ [0.5, 10]stays in the narrow band of 6–10 GD iterations and ~950–960 queries — a 2× variation across a 20× parameter range, versus backtracking's 200× variation. -
On
f(x, y) = x^4 + y^4(degenerate minimum at(0,0), initialized at(0.1, 15)): This function has a degenerate (non-isolated) minimum along certain directions, making step size selection challenging. Quasi-exact withc = 0.5requires 5 iterations and 38 queries; withc = 1, 5 iterations and 42 queries. Backtracking withε = 0.1requires 10 iterations and 68 queries — roughly 60% more queries. The paper reports two numbers for backtracking: the parenthetical values (e.g.,(17 655)forε = 0.1) show standard backtracking without the interval-growing modification, which gets stuck with a far too small learning rate — the algorithm fails to escape the flat region near the degenerate minimum because it repeatedly accepts tiny steps that satisfy Armijo's condition locally. The non-parenthetical values use Algorithm 4's interval-growing mechanism to recover, but still lag behind quasi-exact.
Figure 6 — 100-dimensional loss landscape (Equation 9), 2000 query budget:
The figure plots loss (log-scale) against cumulative function+gradient queries for quasi-exact with c ∈ {0.1, 1, 2} and backtracking with ε ∈ {0.01, 0.1, 0.5}. The results are striking:
- Quasi-exact with all three
cvalues achieves rapid descent, reaching loss below10^{-20}within ~400–600 queries. The three quasi-exact curves are nearly indistinguishable, confirming robustness toc. - Backtracking fails to make meaningful progress for
ε ≥ 0.1. Theε = 0.1curve stalls around loss10^{-5}after ~600 queries and never improves. Theε = 0.5curve makes essentially no progress — loss remains above10^{-1}throughout. This is the snowplow skier on a high-dimensional landscape: the exponential terms in Equation (9) create regions of high curvature where the Armijo condition with largeεdemands step sizes too small to move the iterate significantly. - Backtracking with
ε = 0.01initially descends but plateaus around loss10^{-5}after ~600 queries — better than largerεbut still more than 15 orders of magnitude worse than quasi-exact at the same query budget. The plateau suggests a region where the Armijo condition is satisfied for tiny step sizes that don't reduce the loss enough to escape the local flatness, a combined flying-squirrel + snowplow-skier effect in different regions of the parameter space.
The c = 1 default as a universal recommendation. The data supports the paper's claim that "c = 1 to balance practical speed and tight theoretical guarantees" is robust. Across all three functions in Table 3 and the high-dimensional landscape in Figure 6, c = 1 is within a factor of 2 of the best quasi-exact performance and within striking distance of the best-tuned backtracking performance — with the crucial difference that it achieves this without requiring per-function tuning.
Frank-Wolfe Integration (Section 3.5)
The paper only sketches the Frank-Wolfe integration theoretically without experiments. The key theoretical note is that by ensuring the first line search query at FW iteration k is at α = 2/(k+2), the standard O(1/k) convergence proof goes through — the returned point from quasi-exact line search will have a lower function value than the standard step size schedule, preserving the convergence guarantee. The paper does not report FW experiments, so no quantitative results exist to assess. This is arguably a missed opportunity: demonstrating that quasi-exact line search improves FW convergence on a standard benchmark (e.g., Lasso) would have strengthened the practical case.
Ablation Studies and Robustness Checks
PRM aggregation strategy (Appendix E, Figure 13). Not applicable — this is an optimization paper without verifier models.
Virtual points for ∆-Secant initialization (Remark 8, implicit in all ∆-Secant experiments). The five-point optimality region construction requires two points on each side of the current minimum. When the algorithm starts with only the two boundary evaluations, virtual points with y = ∞ at infinitesimally spaced x-coordinates are added to satisfy the five-point structure without adding false constraints. The fact that ∆-Secant works correctly from the first iteration (Table 2 shows it terminating with finite queries on all functions) validates this construction implicitly, but there is no explicit ablation comparing virtual-point initialization against alternative strategies (e.g., querying twice at the boundaries to immediately obtain four real points).
ε-repulsion in ∆-Secant (Algorithm 2, recommended ε = 2^{-7}). The paper mentions the ε-repulsion mechanism to avoid querying at the same point twice when x_low(P_t) lies at the midpoint of Δ_x(P_t), but reports no ablation studying sensitivity to the choice of ε, nor does it report how often the repulsion triggers in practice. This is a gap: if the repulsion triggers frequently, the algorithm's actual query points deviate from the midpoint-of-∆x rule, potentially weakening the factor-2 guarantee (Theorem 10 assumes ε → 0). If it triggers rarely, the parameter choice is irrelevant. The lack of data leaves the practitioner uncertain about whether the default 2^{-7} is universally safe.
Initial gradient usage in quasi-exact line search (Remark 14, Appendix B.2). Remark 14 suggests incorporating the known initial gradient ∇f(x_k) into the quasi-exact line search by adding virtual points or a linear constraint. Appendix B.2 warns that "it is important to keep the line constraint as a function α → f(x) - α‖∇f(x)‖^2 as is done in backtracking line search" rather than relying on virtual points for numerical stability. However, no experiments are reported with this enhancement. This is a significant omission: using the initial gradient would give ∆-Secant gradient-level information at the left boundary, potentially closing the gap with ∆-Bisection on the first few iterations. The fact that Table 3's quasi-exact results do not use initial gradients (the algorithm description in Algorithm 3 does not include Remark 14's enhancement) means the reported numbers represent a lower bound on what quasi-exact could achieve — it may be even faster with initial gradient augmentation.
Saving one query at initialization (Remark 9). The paper notes that querying at the midpoint before evaluating the right boundary can sometimes save a query: if f(x_left) ≤ f(x_mid), then convexity implies f is non-decreasing from x_left to x_mid, and the minimum may be at x_left. This optimization is never implemented in the reported experiments (Table 2 counts include both boundary evaluations for all algorithms) and is mentioned only as an observation. An ablation comparing with and without this optimization would quantify its practical benefit, which is likely small (at most 1 query saved on a subset of functions where the minimum is at a boundary).
GSS with y∗-gap stopping criterion (an implicit ablation). The paper's version of GSS (Table 2) uses the five-point y∗-gap |Δ_y(P_t)| as its stopping criterion rather than the standard approach of stopping when the x-interval is small. This is itself an ablation: it isolates the effect of where GSS queries (golden-ratio spacing) from how GSS decides to stop. The fact that GSS still requires many more queries than ∆-Secant under the same stopping criterion demonstrates that the query placement strategy (adaptive midpoint of ∆x vs. fixed golden-ratio spacing) is the primary driver of ∆-Secant's advantage, not the stopping rule.
Parameter sensitivity of quasi-exact (Table 3, c column for 3.95x^2). The quasi-exact column for 3.95x^2 shows an abrupt transition between c = 0.1 (4 iterations, 25 queries) and c = 0.01 (754 iterations, 2265 queries). This is not a failure of the algorithm per se — Theorem 12 predicts that c = 0.01 guarantees only 1% of the optimal decrease, so the outer GD convergence becomes extremely slow. The important observation is that the threshold for catastrophic slowdown is c ≈ 0.01, whereas the recommended c = 1 is two orders of magnitude above this threshold. For backtracking, the catastrophic threshold is ε ≈ 0.1 (on the exponential sum) while the recommended range [0.01, 0.3] straddles the failure boundary — ε = 0.1 is in the recommended range and fails badly on e^{3x} + e^{-3x}. This validates the paper's robustness claim: quasi-exact's safe range is much wider relative to its recommended default.
Interval-growing mechanism (Algorithms 3 and 4, implicit in Table 3 x^4 + y^4 results). The parenthetical numbers in Table 3 for backtracking on x^4 + y^4 show performance without interval-growing — the standard backtracking line search limited to α ∈ [0, 1] — which is catastrophically slow (thousands of queries at the default 2000 budget). The non-parenthetical numbers use Algorithm 4's interval-growing. Quasi-exact (Algorithm 3) always uses interval-growing. The improvement from adding interval-growing to backtracking (e.g., from 17,655 to 10 queries for ε = 0.3) is dramatic, but even with this enhancement, backtracking still underperforms quasi-exact. This ablation demonstrates that the quasi-exact advantage is not solely due to interval expansion — it's the combination of adaptive query placement and the relative stopping criterion.
Critical Assessment
Claim 1: ∆-Bisection always outperforms bisection, and ∆-Secant substantially outperforms golden-section search.
Strongly supported for the tested functions. Tables 1 and 2 provide exhaustive evidence across 11 functions with diverse characteristics (smooth, non-smooth, symmetric, asymmetric, piecewise-linear, exponential-like, polynomial). ∆-Bisection never requires more iterations than bisection, and ∆-Secant never requires more queries than GSS. The margins vary substantially — from 14% to 76% for ∆-Bisection, from 14% to >3× for ∆-Secant — which is consistent with the theory: the advantage depends on how much tighter the initial x∗-gap is than the full interval, which is function-dependent.
Qualification: the function set is small and hand-selected. Eleven functions, while diverse in shape, do not constitute a systematic benchmark. The functions were chosen by the authors to illustrate the algorithms' behavior, not drawn from a standard test suite. There is no random generation of problem instances, no parameter sweeps over function parameters (e.g., varying the slopes in max{-x, ax}), and no evaluation on "real" line search subproblems drawn from actual higher-dimensional optimization traces. The claim that ∆-Bisection "always" outperforms bisection is strictly true only for the 11 tested functions — a pathological counterexample where the x∗-gap equals the full interval at every iteration would erase the advantage, and such cases may exist (e.g., f(x) = constant + linear on an interval where both boundary values are equal, making the tangents horizontal and providing no interior cut). The paper does not characterize the function class for which the advantage is zero versus large.
Claim 2: The y∗-gap provides a principled stopping criterion with provable bounds.
Strongly supported by construction and validation. The definition of |Δ_y| in Equations (3) and (6) follows directly from convexity, and Theorems 1 and 10 prove that the algorithms reduce it. Tables 1 and 2 demonstrate that all algorithms successfully terminate at |Δ_y| ≤ 10^{-10}, validating that the gap is computable and decreases to zero. The implicit comparison is compelling: GSS without the y∗-gap (standard version) has no way to bound f(x_low) - f(x^*) and must use heuristic tolerances; GSS with the y∗-gap (the paper's version) terminates with a provable guarantee.
Missing: verification that the computed y∗-gap is tight. The paper reports the number of queries to reach |Δ_y| ≤ 10^{-10}, but does not report the actual suboptimality f(x_low) - f(x^*) at termination. On well-behaved functions where the minimum is known analytically, this would be easy to compute and would validate that |Δ_y| is not overly conservative. If |Δ_y| is 10 orders of magnitude larger than the true suboptimality, the stopping criterion is provably correct but practically wasteful — the algorithm could have stopped much earlier. The absence of this comparison leaves open the possibility that the gap is loose on some functions, causing unnecessary queries.
Claim 3: Quasi-exact line search is more robust than backtracking line search — a single parameter c = 1 works across all functions, while backtracking's ε must be tuned per function.
Supported with strong qualitative evidence, but the quantitative comparison could be deeper. Table 3 and Figure 6 convincingly demonstrate that backtracking's performance varies by orders of magnitude across ε values on individual functions, and that no single ε is simultaneously good on 3.95x^2 and e^{3x} + e^{-3x}. Quasi-exact with c ∈ [0.5, 10] keeps the query count within a factor of 2–3 across all functions. This is a genuine robustness advantage.
Caveat 1: Only three low-dimensional and one high-dimensional function are tested. The claim of "universally good" robustness rests on four test functions. The high-dimensional function (Equation 9) is of a specific form (products of softmax-like terms followed by inversion) and uses a single random draw. Without testing on standard optimization benchmarks — logistic regression on MNIST, Lasso on synthetic data, Rosenbrock function — the breadth of the robustness claim is unverified. It is plausible that on some common loss landscapes, quasi-exact's query budget becomes excessive (e.g., if the 1D restriction in the gradient direction is nearly flat, requiring many queries to find the upturn) while backtracking would terminate quickly because the Armijo condition is satisfied immediately.
Caveat 2: The comparison gives backtracking the benefit of interval-growing (Algorithm 4) and searches over ε. The paper tests backtracking with ε from 0.001 to 0.8, essentially giving it an oracle to select the best ε per function in the final comparison. The paper's argument is not "quasi-exact with c = 1 beats the best backtracking on every function" — it's "quasi-exact with c = 1 is always competitive with the best backtracking, and you don't need to find the best ε, which can vary by orders of magnitude." This is a more nuanced and defensible claim.
Caveat 3: The 2000-query budget in Figure 6 may be too tight. The backtracking curves for ε = 0.01 in Figure 6 show a plateau around loss 10^{-5} at 600–800 queries, but the figure cuts off at 1000 queries on the x-axis. It is possible that backtracking would eventually escape the plateau given more queries, while quasi-exact reaches 10^{-20} within the budget. Without running to convergence, we cannot assess whether backtracking's failure at ε = 0.01 is a catastrophic stall or merely a severe slowdown that would eventually recover. The plateau at 10^{-5} for ε = 0.01 after 600 queries without further improvement for 400 queries suggests a genuine stagnation, but the evidence is not conclusive.
Claim 4: The algorithms are "principled" and applicable to "general convex functions."
Supported theoretically, not experimentally. The paper's theorems assume only convexity — no differentiability (for ∆-Secant), no Lipschitz gradients, no strong convexity. The test functions, however, are all either smooth or have a single kink at the minimum. Important classes of convex functions are not tested: functions with many non-differentiable points (e.g., f(x) = ∑ |x - x_i|), functions with "flat" regions where the minimum is a continuum (e.g., max{0, |x| - 1}), and functions where gradient or function evaluations are noisy (finite-precision or stochastic). The paper's claim of applicability to "general convex functions" is a theoretical property of the algorithm design, not an experimental finding. The absence of tests on non-smooth, flat-bottomed, or noisy convex functions leaves a gap between the theoretical guarantee and the demonstrated practical robustness.
Missing experiments that would strengthen the paper:
-
Comparison against Brent's method or other derivative-free 1D optimizers. Brent's method (inverse parabolic interpolation combined with golden-section search) is the de facto standard for 1D minimization in scientific computing (SciPy's
minimize_scalar). It is not guaranteed for general convex functions (it assumes smoothness for the interpolation steps), but it is widely used and fast. A comparison would situate ∆-Secant against practical alternatives, not just GSS. -
Wall-clock timing, not just query counts. The paper assumes that each function or gradient evaluation dominates the algorithm's internal computation. For simple test functions, the overhead of computing ∆ and its gaps may be comparable to evaluation cost, making query counts a poor proxy for runtime. A timing comparison on at least one expensive-to-evaluate function (e.g., a line search where each function evaluation trains a logistic regression model on a subset of data) would validate the practical relevance.
-
Experiments on "real" line search subproblems drawn from gradient descent traces. Rather than hand-picking 1D functions, extract the 1D restrictions
α → f(x_k - α∇f(x_k))from actual GD runs on standard ML problems (logistic regression on MNIST, a small neural network) and compare ∆-Secant against backtracking on these subproblems. This would test the algorithms on function shapes that arise in practice, where the curvature along the gradient direction may have structure not captured by the 11 hand-picked functions. -
Frank-Wolfe experiments. The theoretical integration with FW (Section 3.5) is only sketched. Demonstrating that quasi-exact line search maintains or improves FW's convergence on a standard sparse optimization problem (e.g., Lasso with a nuclear norm constraint) would extend the practical case beyond gradient descent.
-
Sensitivity to the ε-repulsion parameter and virtual-point construction. An ablation showing that ∆-Secant's query count is insensitive to
εacross, say,{2^{-4}, 2^{-7}, 2^{-10}, 2^{-15}}would validate the robustness of the numerical scheme. An ablation on the virtual-point y-values (e.g., using10^{10}vs.∞) would confirm that the gap computation is numerically stable.
Despite these gaps, the experimental evidence for the paper's central algorithmic contributions — ∆-Bisection and ∆-Secant accelerate 1D convex minimization by exploiting convexity beyond what quasiconvex methods achieve — is thorough and convincing on the tested function set. The quasi-exact line search experiments, while limited in breadth, make a compelling qualitative case for robustness that the theoretical analysis (Theorems 12 and 13) backs rigorously. The contrast with backtracking's parameter sensitivity is vividly illustrated and likely to resonate with practitioners who have experienced the frustration of tuning ε.
6. Limitations and Trade-offs
The Cost of Difficulty Estimation Is Not Accounted For in the Efficiency Gains
The assumption or constraint. The quasi-exact line search's stopping criterion depends on the y∗-gap |Δ_y(P)|, which is computed from the five-point optimality region construction using only the evaluated points. The gap computation itself adds negligible overhead — it requires solving small linear systems from at most five points (Theorem 6). However, the interval-growing mechanism in quasi_exact_line_search (Algorithm 3) incurs a hidden cost: when the minimum lies at the right boundary of the current interval [0, x_right], the algorithm must expand the interval by a factor of 4, re-evaluate the right boundary, and re-run ∆-Secant. Each expansion adds at least one function evaluation (at the new boundary) that would not be needed if the initial α_prev or initial x_right were already large enough.
The paper does not account for this expansion cost in a dysfunctional way in Table 3 or Figure 6 because the interval-growing is built into both quasi-exact and the enhanced backtracking (Algorithm 4), so the comparison is fair between them. But the headline query counts in Table 3 do not isolate how many queries were spent on interval expansion versus on the actual line search convergence, and there is no ablation showing performance as a function of the initial α_prev choice. The default α_prev = 1 (Algorithm 3) is arbitrary and may be far from the true optimal step size, triggering multiple expensive expansions.
The consequence. On functions where the optimal step size is much larger than 1 — for instance, if the gradient is very small (flat region) and a large step is needed to escape — the interval expansion loop could dominate the query budget. Each expansion multiplies x_right by 4, so reaching α^* ≈ 4^k requires k boundary evaluations and k re-runs of ∆-Secant. If α^* is unknown and the initial guess is far off, the number of wasted queries grows logarithmically in α^* but with a constant factor that could be substantial (each re-run of ∆-Secant on the expanded interval may partially re-explore territory the algorithm already covered in the previous, smaller interval, because the new wider interval changes the secant constraints and the x∗-gap midpoint).
The paper's convergence theory (Theorems 12 and 13) assumes the line search finds a point satisfying the quasi-exact stopping criterion — it does not model the cost of interval expansion. A practitioner who initializes α_prev poorly on a problem where the optimal step size varies dramatically across GD iterations could experience significantly higher total query counts than Table 3 suggests.
What evidence exists in the paper. The paper provides no direct measurement of this cost. Table 3 reports total queries aggregated over all GD iterations, conflating line search queries, expansion queries, and gradient evaluations at each outer iteration. There is no breakdown of "queries spent on interval expansion" vs. "queries spent on ∆-Secant convergence." The choice of factor 4 for expansion is justified only by a brief comment: "Using a factor of 2 would require more iterations; a factor of 10 might overshoot dramatically" — no experimental sweep over expansion factors is reported.
Mitigation status. The paper suggests reusing the previously found learning rate α_prev from the previous GD iteration (Algorithm 3), which is a sensible heuristic — in practice, the optimal step size tends to change smoothly across GD iterations, so α_prev is usually close to the next α^*. However, on the first iteration or after large gradient changes, this heuristic can fail. The paper does not propose or evaluate a more robust initialization strategy (e.g., predicting α_0 from the gradient norm or Lipschitz estimate). This limitation is unmitigated but partially acknowledged by the reuse heuristic's existence.
Only a Small Set of Hand-Selected Test Functions Are Evaluated
The constraint. Every experimental result in the paper — Tables 1, 2, 3, and Figure 6 — uses test functions that were manually chosen by the authors. The 1D experiments use 11 convex functions with specific domains and parameters. The multivariate experiments use exactly four functions: 3.95x^2 (a carefully chosen quadratic coefficient to trigger the flying squirrel failure at ε = 0.01), e^{3x} + e^{-3x} (chosen to trigger the snowplow skier failure), x^4 + y^4 (a known degenerate-minimum case from Truong and Nguyen, 2021), and the 100-dimensional artificial loss of Equation (9) with a single random draw of parameters. The authors state in Section 3.4:
"We validate on some experiments that our quasi-exact line search is competitive with a well-tuned backtracking line search"
The word "some" accurately reflects the limited scope, but the paper's claims of robustness and universality rest entirely on this narrow empirical base.
The consequence. There is no way to assess whether the observed advantages generalize to the types of convex functions that arise in practical optimization. Several critical gaps:
- No standard ML benchmarks. The paper does not evaluate on logistic regression, Lasso, SVM, or any problem from the convex optimization literature where line searches are routinely used. The 100-dimensional Equation (9) is an artificial construction designed by the authors — it is not drawn from any standard benchmark suite and its properties (products of softmax-like exponentials with random coefficients) may not be representative of typical ML loss landscapes.
- No exploration of function parameter variation. The functions in Tables 1–2 have fixed parameters. We do not know how performance varies with, say, changing the slopes in
max{-x, ax}acrossa ∈ {2, 5, 10, 100}, or changing the exponent in|x|^pforpnear 1, or varying the domain bounds. The factor-2 and factor-3 improvements over GSS and bisection are point estimates on specific function instances — they may not hold across the function class. - Single random seed for Figure 6. The 100-dimensional experiment uses one random draw of the parameters
a_{i,j}and one random initialization ofx_0. Without error bars or multiple seeds, Figure 6's dramatic separation between quasi-exact (rapid descent) and backtracking (stalling) could be an artifact of a particularly favorable or unfavorable random configuration. The paper describes it as "a typical example" but provides no evidence of typicality. - No "real" line search subproblems. The most direct test of practical utility would be to extract the 1D restriction
α → f(x_k - α∇f(x_k))from actual gradient descent traces on standard problems and evaluate the line search algorithms on these subproblems individually. This would reveal whether the curvature patterns that trigger slow convergence for backtracking (flying squirrel, snowplow skier) occur with meaningful frequency in practice, or whether they are pathological constructions that rarely arise outside the authors' chosen examples.
What evidence exists in the paper. The paper itself provides none beyond the chosen functions. The limitation is not discussed in Section 8 (Conclusion) or flagged as a caveat. The experimental section simply presents the results without acknowledging the narrowness of the test set.
Mitigation status. Not addressed. The paper does not claim to have performed an exhaustive empirical evaluation, but neither does it explicitly scope its claims to the tested functions. A reader unfamiliar with optimization benchmarks might reasonably interpret the robustness claims as having been validated across a representative suite of problems, which is not the case. This limitation could be substantially mitigated by even a modest expansion: logistic regression on a few UCI datasets, Lasso on synthetic data, and multiple random seeds for Equation (9) would go a long way.
No Evaluation on Non-Smooth, Flat-Bottomed, or Noisy Convex Functions
The assumption or constraint. The paper's theoretical guarantees (Theorems 1, 5, 10, 12, 13) require only convexity — no differentiability, no Lipschitz smoothness, no strong convexity. The x∗-gap and y∗-gap constructions are geometrically valid for any convex function, including those with kinks, flat regions, or discontinuities in the derivative. The algorithms query the function at specific x-values and use only the returned values (and gradients, for ∆-Bisection) — they make no smoothness assumptions.
However, every function in the experimental evaluation is either smooth or has exactly one kink at the minimum. The 1D test functions include |x| (single kink at the minimum), max{-x, 2x} (kink at the minimum for one variant, elsewhere for the other), and piecewise-quadratic compositions — but all are differentiable almost everywhere, and the non-differentiable points are at or near the minimum, not in regions the algorithm must traverse during search. The multivariate functions (3.95x^2, e^{3x} + e^{-3x}, x^4 + y^4) are all infinitely differentiable. The 100-dimensional Equation (9) is smooth (ratios of exponentials).
Missing from the evaluation are function classes where the convexity-exploiting mechanisms might behave differently:
- Functions with many kinks. Consider
f(x) = ∑_{i=1}^n |x - c_i|— a piecewise-linear convex function with kinks at everyc_i. For ∆-Secant, secant lines through points on different linear segments may provide misleading slope estimates — a secant through two points that straddle a kink has a slope that is an average of the slopes on either side, potentially reducing the tightening of ∆ compared to a smooth interpolation. - Functions with flat bottoms. Consider
f(x) = max{0, |x| - 1}— zero on[-1, 1], linear outside. The minimum is a continuum, sox^*is not a single point. The y∗-gap can reach zero whileΔ_xremains large (the entire flat region is consistent with the constraints), which is correct behavior (the optimality gap is zero since any point in the flat region achievesy^*), but the algorithm may continue querying because the x∗-gap stopping criterion would not be met if the user also demands x-precision. The paper does not discuss how to handle non-unique minima. - Noisy function evaluations. In many practical settings (stochastic gradient descent, finite-precision simulations), function evaluations are corrupted by noise. The paper's algorithms assume exact oracle access —
f(x)andf'(x)return true values. Even small noise could violate the convexity lower-bound constraints: a noisy evaluation slightly below the true function at one point could produce a secant that lies above the function elsewhere, breaking the(x^*, f(x^*)) ∈ Δ(P)guarantee. The paper does not mention noise robustness anywhere.
The consequence. A practitioner deploying these algorithms on a non-smooth, flat-bottomed, or noisy convex function has no experimental guidance about what to expect. The geometric logic of the optimality region construction is sound, but the practical behavior — convergence speed, numerical stability, sensitivity to kink locations relative to query points — is unvalidated. For noisy evaluations, the algorithms may fail catastrophically (returning a point far from the true minimum with a falsely small y∗-gap) because the fundamental invariant (x^*, f(x^*)) ∈ Δ relies on exact convexity, which noise corrupts.
What evidence exists in the paper. None. The paper does not acknowledge this gap. The abstract claims the algorithms work for "general convex functions — including piecewise-linear and max-compositions of convex functions" — the experiments include exactly two piecewise-linear functions (|x| and max{-x, 2x}), both with a single kink at the minimum. No function with multiple kinks, flat regions, or noise is tested.
Mitigation status. Not addressed. The theoretical framework could potentially be extended to handle noise by replacing hard convexity constraints with probabilistic or robust variants (e.g., assuming evaluations are within ε of the true values and widening ∆ accordingly), but this is not explored. The paper does not suggest this as future work. This is a significant practical limitation because many gradient descent applications — especially in machine learning — use stochastic gradients, and the line search must operate on noisy 1D slices.
The Quasi-Exact Convergence Guarantee Depends on Strong Convexity and Smoothness, but the Line Search Itself Does Not Use These Constants
The assumption or constraint. Theorem 13 (the linear convergence guarantee for GD with quasi-exact line search) assumes the multivariate function is m-strongly convex and M-smooth, and the convergence rate explicitly depends on the condition number m/M. However, the quasi-exact line search algorithm itself (Algorithm 3) does not take m or M as inputs — it operates solely on the 1D restriction f̃(α) using only function evaluations (and potentially the initial gradient, per Remark 14, though the experiments don't use this). The line search has no knowledge of the global strong convexity or smoothness constants.
This creates a theory-practice mismatch: the theoretical guarantee that justifies using quasi-exact line search in GD assumes properties the algorithm cannot verify and does not exploit. The convergence rate (1 - (c/(c+1))(m/M))^k is valid only if f is indeed m-strongly convex and M-smooth on the entire domain — conditions that the user must verify independently. If the function is merely convex but not strongly convex (e.g., f(x) = |x|, f(x) = max{0, x}, linear functions, or the degenerate x^4 + y^4 which is not strongly convex near the origin), Theorem 13 provides no convergence rate at all, and GD with any line search could converge arbitrarily slowly.
Moreover, even when strong convexity and smoothness hold, the rate depends on the global condition number m/M. On functions where m/M is tiny (ill-conditioned), the theoretical linear rate may be extremely slow. The quasi-exact framework offers no adaptive mechanism to accelerate convergence on ill-conditioned problems — the c/(c+1) factor multiplies m/M, making bad conditioning worse. Compare this to backtracking, where the Armijo condition with small ε can sometimes yield faster practical convergence on ill-conditioned quadratics than the theoretical rate 1 - 2τεm/M suggests, because the line search may take larger steps than predicted by the worst-case Lipschitz bound (Truong and Nguyen, 2021, discuss adaptive variants).
The consequence. The paper's strongest convergence result (Theorem 13) applies only to a restricted class of functions, while the paper's main selling point — "our algorithms work for general convex functions" — applies to the 1D subproblems but not to the overall GD convergence when the outer function is not strongly convex or smooth. A practitioner using quasi-exact line search on a general convex function (e.g., Lasso, which is convex but not strongly convex without regularization) has no convergence rate guarantee from this paper, despite the line search itself being provably efficient on each 1D subproblem. The outer iteration could stall or converge sublinearly, and the paper provides no diagnostics for this situation.
What evidence exists in the paper. Table 3 includes x^4 + y^4 — a function that is not strongly convex at the origin (the Hessian is zero). The quasi-exact line search still works (5 GD iterations, 42 queries) and outperforms backtracking, but Theorem 13 does not apply. The paper does not highlight this discrepancy or discuss the gap between the theoretical guarantee's scope and the experiments' scope. The convergence proof for quasi-exact line search in Theorem 13 is presented as a key result, but the experiments demonstrating its practical value include functions outside its formal domain of validity without comment.
Mitigation status. Not addressed. The paper does not discuss how to extend the convergence theory to general convex functions (e.g., sublinear O(1/k) rates) or how to adapt the line search to exploit local strong convexity when it exists. The Frank-Wolfe sketch (Section 3.5) hints at a O(1/k) convergence guarantee for general convex smooth functions, but no theorem is stated or proved — it's only a remark that "the O(1/k) convergence proof of Frank-Wolfe with a quasi-exact line search goes through straightforwardly." A formal theorem and proof for the Frank-Wolfe case, and a discussion of what guarantees exist (and don't exist) for GD on non-strongly-convex functions, would substantially strengthen the paper's claims to generality.
The Derivative-Free Guarantee Is a Factor-2 Reduction Every Two Queries — Matching the Information-Theoretic Limit but Potentially Slow in Absolute Terms
The constraint. Theorem 10 guarantees that ∆-Secant reduces the x∗-gap by at least a factor of 2 every second function query. This matches the information-theoretic expectation that a function query provides half the information of a gradient query (which gives factor 2 every query in ∆-Bisection). However, "factor 2 every two queries" is equivalent to a factor of √2 ≈ 1.41 per query on average — which is slower than golden-section search's factor of φ ≈ 1.62 per query on the full interval. The paper rightly emphasizes that comparing these factors is misleading because the x∗-gap can be far smaller than the full interval. But on functions where the x∗-gap is not substantially smaller than the full interval — because the boundary values are similar, the slopes are shallow, or the function is nearly symmetric — the per-query reduction of the x∗-gap is close to √2, while GSS is reducing the full interval by φ per query. In such regimes, GSS could theoretically overtake ∆-Secant.
The paper's experiments (Table 2) show ∆-Secant always beating GSS, but this is on the 11 chosen functions. The theoretical worst case for ∆-Secant — where the x∗-gap equals the full interval and the midpoint query provides no additional tightening beyond what the sign of the comparison gives — would exhibit a √2 per-query reduction, strictly worse than GSS's φ. The paper does not characterize when this worst case occurs or bound how close to it typical functions are.
The consequence. In the worst case (or near-worst case), ∆-Secant could require more queries than GSS to achieve the same x∗-gap reduction. Because the x∗-gap and the full interval coincide, the two algorithms are shrinking the same quantity, and GSS does it faster per query. A practitioner who does not know a priori whether their function will exhibit tight x∗-gaps might prefer GSS for its guaranteed φ reduction (a known, dimension-free constant) over ∆-Secant's guaranteed √2 reduction (which comes with the caveat that it applies to a potentially smaller region, but that region might not be smaller in practice). The paper's recommendation to use ∆-Secant over GSS is an empirical claim based on 11 functions, not a theoretical dominance result.
What evidence exists in the paper. Table 2 provides some indirect evidence of the gap. On f(x) = x^4 on [-20, 7], ∆-Secant and GSS are closest (18 vs. 21 queries) — a 14% advantage for ∆-Secant. The x^4 function is relatively flat near the origin and symmetric, making the x∗-gap close to the full interval initially. On functions where the x∗-gap is much smaller (piecewise-linear with asymmetric slopes, e.g., max{-x, 2x} on [-0.01, 100]), the gap is huge (18 vs. 52 queries, a 65% advantage). This pattern is consistent with the theory: ∆-Secant's advantage is proportional to how much smaller the initial x∗-gap is than the bracketing interval. However, the paper does not quantify this relationship or provide a diagnostic for predicting when ∆-Secant will substantially outperform GSS.
Mitigation status. Not addressed. The paper does not discuss the worst-case behavior of ∆-Secant relative to GSS. The theoretical comparison in Remark 11 is entirely favorable to ∆-Secant (focusing on the sqrt(1 + x^2) example where the x∗-gap is small), without acknowledging that the φ > √2 factor means GSS is asymptotically faster per query on the quantity it measures. A balanced discussion of the tradeoff — ∆-Secant adapts to tight x∗-gaps but has a weaker worst-case per-query reduction factor than GSS — would help practitioners choose between them based on their expectations about function shape. This limitation is fundamental to the algorithm's design: the midpoint query rule achieves factor 2 every two queries by splitting the x∗-gap, which is optimal in an information-theoretic sense for the worst-case convex function, but it does not match GSS's φ factor on the quantity GSS optimizes.
No Discussion of Numerical Stability or Precision Requirements for Secant Intersection Computations
The constraint. The y∗-gap computation for ∆-Secant (Equation 6) requires computing the minimum of two line-line intersection y-coordinates: y_{01,23} and y_{12,34}. These intersections are computed from four points using Equation (1) or the numerically stabilized variant described in Appendix B.1. The stabilized formula iterates the intersection calculation twice (computing x_c, then re-evaluating at x_c and computing again) and takes y_c = min{f^{12}(x_c), f^{34}(x_c)} conservatively.
However, when the four points are nearly collinear — as happens when the algorithm has converged close to the minimum and the function is nearly linear between adjacent evaluation points — the secant slopes a_{01}, a_{12}, a_{23}, a_{34} become nearly equal, and the denominator a_{kl} - a_{ij} in Equation (1) approaches zero. In finite-precision arithmetic, this produces catastrophic cancellation: the computed intersection point can be arbitrarily far from the true intersection, potentially placing the estimated y∗-gap below zero or orders of magnitude above the true value. A falsely small |Δ_y| could cause premature termination (the algorithm thinks it has found the minimum to tolerance when it hasn't), while a falsely large |Δ_y| could cause the algorithm to continue querying indefinitely.
The paper acknowledges the numerical sensitivity in Appendix B.1 — "Some numerical stability care needs to be taken when implementing the line-line intersection function" — and provides the stabilized formula, but reports no experiments on the numerical behavior of this computation.
The consequence. On functions where the minimum lies in a region of near-linearity (e.g., x^2 near x=0, x^4 near x=0, or any smooth function evaluated at points very close together after many iterations), the line-line intersection computation may become numerically unreliable. The algorithm could:
- Terminate prematurely with an incorrect answer (if the intersection calculation underestimates
|Δ_y|). - Loop infinitely or require excessive queries (if
|Δ_y|oscillates due to numerical noise and never drops below the tolerance). - Produce a y∗-gap that is not a true upper bound — violating the
(x^*, f(x^*)) ∈ Δguarantee — if the conservativemincorrection in Appendix B.1 is insufficient to compensate for cancellation errors.
The paper's experiments terminate at y_tol = 10^{-10}, which is close to double-precision machine epsilon for functions with values near unity. This is an aggressive tolerance that pushes against the limits of the intersection formula's numerical stability, yet no analysis of the actual numerical error in the intersection computation is provided.
What evidence exists in the paper. None. The only mention of numerical stability is Appendix B.1, which describes the stabilized formula without evaluating its accuracy on test cases. The paper does not report:
- The actual value of
|Δ_y|at termination vs. the true suboptimalityf(x_low) - f(x^*)(which would reveal systematic underestimation). - The condition number of the line-line intersection computation (ratio of secant slope differences to their magnitudes) at the final iterations.
- The effect of varying
y_tolon query count and solution accuracy (e.g.,y_tol ∈ {10^{-6}, 10^{-8}, 10^{-10}, 10^{-12}, 10^{-14}}) — does query count scale as expected, or does it explode near machine precision?
Mitigation status. The paper provides the double-iteration stabilization formula (Appendix B.1) and the conservative min correction, which are sensible heuristics, but does not prove or experimentally validate their reliability at the tolerances used. The ε-repulsion mechanism (ε = 2^{-7}) in ∆-Secant helps prevent queries that are so close together that secant slopes become ill-conditioned, but 2^{-7} ≈ 0.008 of the x∗-gap width is not necessarily enough separation to guarantee numerical stability when the x∗-gap itself is very small. A more robust implementation might dynamically increase ε or switch to a gradient-based method (if gradients are available) when points become too clustered, but this is not proposed. The paper's claim that the algorithms are "principled" and suitable for "exact" minimization must be qualified by the reality that finite-precision arithmetic will eventually limit the achievable precision of the y∗-gap, and the paper provides no characterization of this limit.
7. Implications and Future Directions
How This Work Changes the Landscape
This paper causes a reconceptualization of what a 1D line search algorithm should shrink. Prior to this work, the dominant framework — codified in standard textbooks (Boyd and Vandenberghe, 2004) — treated bisection search's factor-2 interval reduction as optimal for gradient-based quasiconvex minimization and golden-section search's factor-φ reduction as optimal for derivative-free quasiconvex minimization. The optimization field had implicitly accepted that convexity's benefits are fully captured by the ability to perform these searches (since convex functions are quasiconvex), and that any remaining structure — gradient magnitudes, secant constraints connecting multiple function evaluations — was irrelevant to the 1D case.
This paper demonstrates that this acceptance was premature. The x∗-gap Δ_x — the provable bounds on x^* derived from tangent or secant intersections — is the correct optimization target, not the original bracketing interval. The shift is not a tweak to query placement but a change in the algorithm's maintained state: from "I know x^* lies in [x_0, x_1]" to "I know x^* lies in [x^-, x^+] where x^- and x^+ are computed from the specific geometric constraints that convexity provides." This richer state enables both faster convergence (the x∗-gap shrinks faster because it starts smaller and can tighten by more than a factor 2 per query — see the factor-3 reduction in Figure 1) and principled termination (the y∗-gap provides an optimality certificate unavailable to quasiconvex methods).
The field impact is best characterized as a methodological correction rather than a paradigm shift. The algorithms — ∆-Bisection and ∆-Secant — are structurally identical to their quasiconvex ancestors (query at a midpoint, use the result to shrink a region), differing only in which midpoint they query. The correction is that the optimal midpoint for convex functions is not the midpoint of the bracketing interval but the midpoint of the provable optimality region — and that this region is computable from exactly the same oracle queries that bisection and GSS already perform, requiring no additional function evaluations or stronger assumptions. This means the improvement is "free" in terms of oracle access and assumptions, making it an unambiguous advance over the prior state of the art for 1D convex minimization.
The resolution of a long-standing practical contradiction is equally significant. The optimization community had bifurcated: exact line search was theoretically ideal but "too expensive" (Boyd and Vandenberghe, 2004), while backtracking line search with Armijo's condition was fast but brittle — practitioners knew it could stall on ill-conditioned problems but had no systematic alternative. This paper dissolves the tradeoff by showing that a quasi-exact line search (using the y∗-gap as a relative stopping criterion) is simultaneously:
- Provably close to exact. Theorem 13 shows the convergence rate slowdown is at most
c/(c+1)— a factor of 2 for the recommendedc = 1— compared to true exact line search, which is negligible in practice. - Empirically fast. Table 3 shows quasi-exact with
c = 1matches or beats the best-tuned backtracking on every test function, while using a default parameter that requires no per-function tuning. - Robust where backtracking fails. The two failure modes — the flying squirrel (oscillatory slowdown at small
ε) and the snowplow skier (query explosion at largeε) — are eliminated because the quasi-exact stopping condition compares achieved improvement to the provable optimality gap|Δ_y|rather than to the gradient-predicted decrease. The y∗-gap adapts to the function's curvature automatically through the secant constraints, without needing Lipschitz constants or strong convexity parameters.
This reframes the line search design problem: instead of asking "what fraction of the gradient-predicted decrease should I demand?" (the Armijo ε question, which depends on unknown curvature), the quasi-exact framework asks "what fraction of the provable remaining improvement can I leave on the table?" (the c question, which has a clear, curvature-independent answer: c = 1 is always safe). The diagnostic contribution is that Armijo's condition is structurally misaligned with convex optimization — it uses local gradient information to set a global threshold, whereas the y∗-gap uses global convexity constraints to set a local threshold that is automatically curvature-appropriate.
The work also makes several research directions more attractive:
- Adaptive line search termination. The
cparameter could be increased as gradient descent converges (exploiting the diminishing returns of exact line search far from the optimum) or adapted based on observed problem conditioning. Thec/(c+1)framework provides the theoretical scaffolding for such schemes. - Verifier-guided optimization. The y∗-gap is a form of verifier — it certifies suboptimality without knowing the true minimum — and this paper shows that such verifiers can be constructed from only convexity and function evaluations. This connects conceptually to recent work on process reward models in LLM reasoning, where learned verifiers guide search, though the mechanisms are entirely different.
- Hybrid secant-tangent methods. The paper studies ∆-Bisection (tangents only) and ∆-Secant (secants only) separately, but the optimality region framework naturally accommodates both simultaneously. A hybrid method using tangents where gradients are cheap and secants elsewhere could dominate both pure approaches, especially when gradients are available but noisy.
Several research directions become less attractive in light of this work:
- Designing more sophisticated quasiconvex 1D search algorithms. The paper shows that the quasiconvex formulation is fundamentally information-limited — it discards gradient magnitudes and secant constraints. Any algorithm that only uses the quasiconvex property (ordinal comparisons of function values, gradient signs) will be dominated by one that exploits convexity, making quasiconvex-specific research for 1D problems less impactful.
- Fine-tuning backtracking's
εparameter on a per-problem basis. The paper demonstrates thatεmust vary by two orders of magnitude across simple functions (0.001 for exponentials, 0.5 for quadratics). A hyperparameter optimization loop forεis strictly worse than using quasi-exact withc = 1, which achieves competitive performance without tuning. - Developing "exact" line searches that run to full numerical precision. The quasi-exact framework shows that the
c/(c+1)slack allows dramatic computational savings (stopping when only half the possible improvement remains, forc = 1) with a bounded impact on outer-loop convergence. Pushing to|Δ_y| ≈ 10^{-10}is unnecessary for gradient descent step size selection.
Follow-Up Research This Work Enables
1. A systematic empirical comparison on "real" line search subproblems extracted from standard ML benchmarks.
The paper's experiments use 11 hand-selected 1D functions and 4 hand-selected multivariate functions. The open question is: do the curvature patterns that trigger catastrophic backtracking failure (flying squirrel, snowplow skier) occur with meaningful frequency in practical optimization, or are they pathological edge cases? A strong follow-up would instrument gradient descent on standard convex ML problems — logistic regression on MNIST or CIFAR-10 (with linear model), Lasso on synthetic sparse recovery, SVM on UCI datasets — and log every 1D restriction α → f(x_k - α∇f(x_k)) encountered during optimization. For each subproblem, run ∆-Secant, GSS, and backtracking (at multiple ε values) to convergence, and measure: (a) what fraction of subproblems trigger Armijo failure modes (oscillatory step sizes, excessive backtracking iterations), (b) the actual curvature (ratio of actual decrease to gradient-predicted decrease) at the step sizes chosen by each method, and (c) the total query count for each method aggregated across all GD iterations to reach a fixed suboptimality. This would transform the paper's existence proof ("backtracking can fail") into a frequency estimate ("backtracking fails on X% of real line search subproblems"), which is what practitioners need to decide whether to switch.
2. Hybrid secant-tangent optimality regions: what is the value of one gradient query when function evaluations dominate?
The paper studies ∆-Bisection (uses all available gradients) and ∆-Secant (uses no gradients) but never a mixed strategy where, say, the first query at the midpoint of Δ_x includes a gradient, and subsequent queries are function-only. Section 3.2's observation that "querying the gradient at x_low(P_t), if available, would be even better" (Algorithm 2 footnote) suggests a natural hybrid: use the initial gradient at α = 0 in the quasi-exact line search (Remark 14 suggests this but provides no experiments), and possibly compute one additional gradient at the midpoint of the initial Δ_x to immediately obtain a tangent lower bound on both sides of the minimum. The concrete question: how many gradient queries are worth their cost (in terms of function-query equivalents) for typical convex functions? A follow-up would implement a parameterized hybrid where the user specifies a cost ratio ρ (gradient query cost / function query cost), and the algorithm dynamically decides whether to request a gradient at each query point based on the expected reduction in |Δ_x| per unit cost. The baseline comparison would sweep ρ ∈ {1, 2, 5, 10, 100} and measure total oracle cost (in function-query equivalents) to reach |Δ_y| ≤ 10^{-8} on the 11 test functions and the extracted ML subproblems from direction 1. This would produce practical guidance: "if gradients cost less than X function evaluations, use the hybrid; otherwise use pure ∆-Secant."
3. Verifying the tightness of the y∗-gap: when does the algorithm dramatically overestimate suboptimality?
The y∗-gap |Δ_y| is a provable upper bound on y_low - f(x^*), but it may be loose — the true suboptimality could be orders of magnitude smaller than |Δ_y| suggests. If so, the algorithm wastes queries shrinking a gap that is already effectively zero. The paper never reports the true suboptimality at termination because all test functions have known minima — this would be trivial to compute and report. A follow-up should instrument ∆-Secant and ∆-Bisection on a diverse set of convex functions (including the 11 from the paper plus randomly generated piecewise-linear, quadratic, and exponential functions with varying condition numbers) and log at each iteration both |Δ_y| and the true y_low - f(x^*). The key metric is the gap ratio R = |Δ_y| / (y_low - f(x^*)) — values near 1 indicate the gap is tight (the lower bound is accurate); values ≫ 1 indicate looseness. This would answer: (a) is the gap ratio typically O(1), O(10), or O(100)? (b) does the ratio shrink, grow, or stay constant as the algorithm converges? (c) on which function classes is the gap loose, and can the algorithm detect this and adapt (e.g., by placing queries to specifically tighten the lower bound rather than halving the x∗-gap)? If R ≈ 1 on most functions, the stopping criterion is near-optimal; if R ≫ 1, then a modified algorithm that targets gap tightness rather than x∗-gap reduction could terminate substantially earlier.
4. Robustness to evaluation noise: can the optimality region be "fattened" to maintain probabilistic guarantees?
The paper's theory and experiments assume exact function and gradient evaluations. In stochastic optimization (the dominant paradigm in machine learning), every evaluation is corrupted by noise: f̂(x) = f(x) + ε, f̂'(x) = f'(x) + δ. Noise breaks the convexity lower-bound guarantees — a noisy point below the true function can produce a secant that crosses above the function elsewhere, potentially excluding the true minimum from Δ(P). A natural extension is to widen the optimality region based on a known noise bound: if |ε| ≤ σ and |δ| ≤ σ', then the tangent constraint f(x) ≥ f(x_0) + f'(x_0)(x - x_0) becomes f(x) ≥ f̂(x_0) + f̂'(x_0)(x - x_0) - σ - σ'|x - x_0| — a "fattened" tangent that lies below the true function with high probability. The x∗-gap and y∗-gap would expand by O(σ, σ'), and the algorithm would terminate when the expanded gap is small relative to the noise level. The concrete experiment: take the 11 test functions, add Gaussian noise with σ ∈ {10^{-2}, 10^{-4}, 10^{-6}}, and measure (a) whether the fattened ∆ still contains the true (x^*, f(x^*)) on >95% of runs, (b) the query count scaling with 1/σ, and (c) whether the algorithm correctly identifies when it has reached the noise floor (where further queries cannot reduce the gap below the noise level). This would extend the paper's applicability to the setting where line search is most needed — stochastic gradient descent — and would clarify whether the optimality region framework degrades gracefully or catastrophically under noise.
5. Frank-Wolfe with quasi-exact line search: experimental validation on sparse optimization benchmarks.
Section 3.5 sketches the integration with Frank-Wolfe (FW) but provides zero experiments. The FW setting is particularly interesting because: (a) the line search domain is always [0, 1] (no interval expansion needed), removing one source of query overhead; (b) FW's O(1/k) convergence rate for general convex smooth functions is complementary to GD's linear rate for strongly convex functions, testing the quasi-exact framework in a regime where Theorem 13 does not apply; (c) the standard FW step size schedule 2/(k+2) is known to be conservative — a quasi-exact line search could take larger steps early and smaller steps late, potentially improving the constant in the O(1/k) rate. The concrete experiment: run FW with (i) standard 2/(k+2) step size, (ii) exact line search (∆-Secant to |Δ_y| ≤ 10^{-10}), (iii) quasi-exact line search with c = 1, and (iv) Armijo backtracking, on standard FW benchmarks: Lasso with a simplex constraint, matrix completion with a nuclear norm constraint, and a quadratic program over a polytope. Measure: primal gap f(x_k) - f(x^*) vs. iteration count (for asymptotic rate) and vs. total query count (for practical efficiency). This would validate or refute the theoretical claim that quasi-exact line search "goes through straightforwardly" for FW, and would quantify the practical improvement over the standard step size schedule — is it a 2× speedup, a 10× speedup, or negligible?
6. Can the y∗-gap serve as a diagnostic for detecting non-convexity?
The paper's algorithms assume convexity — if the function is non-convex, the tangent and secant lower-bound constraints may be violated, and Δ(P) may not contain the global minimum. However, a violation of the optimality region invariant is detectable: if a new function evaluation at x_q produces a point (x_q, f(x_q)) that lies below a previously constructed secant lower bound (violating f(x_q) ≥ f^{ij}(x_q) for some x_q outside [x_i, x_j]), this is a certificate of non-convexity. The algorithm could flag this and either (a) widen the optimality region to accommodate the violation (since the previous lower bound was invalid), (b) switch to a non-convex search strategy, or (c) terminate with a warning. The concrete experiment: construct non-convex test functions by adding a negative Gaussian bump to convex functions (f(x) = x^2 - A exp(-(x - μ)^2 / (2σ^2))), run ∆-Secant, and measure (i) what fraction of non-convexity violations are detected before the algorithm converges to a local minimum (as opposed to the global minimum), (ii) the false-positive rate on purely convex functions (does numerical noise ever create spurious violation signals?), and (iii) whether the violation-detection mechanism can be used to construct a convexity test — a procedure that, with high probability, either finds an approximate global minimum or outputs a certificate that the function is not convex on the given interval. This would extend ∆-Secant from an algorithm for known-convex functions to a tool that can operate safely on functions of unknown convexity status.
Practical Applications and Downstream Use Cases
1. Automatic step size selection in large-scale logistic regression and generalized linear models.
In production ML pipelines — particularly for advertising, recommendation, and risk modeling — logistic regression with millions of parameters is routinely trained using gradient descent or coordinate descent. Each gradient evaluation requires a pass over the full dataset (or a large minibatch), making query efficiency paramount. Current practice typically uses backtracking line search with a hand-tuned ε (often 0.1 or 0.01), which the paper shows is vulnerable to both the flying squirrel failure (small ε on well-conditioned problems causing oscillatory progress) and the snowplow skier failure (large ε on poorly-conditioned problems causing excessive line search queries). By replacing backtracking with quasi-exact line search (c = 1), a practitioner eliminates the need for ε tuning entirely. The paper's Table 3 shows that on 3.95x^2 (a proxy for a well-conditioned convex problem), quasi-exact matches the best backtracking (4 GD iterations, 25 queries), while on e^{3x} + e^{-3x} (a proxy for an ill-conditioned problem with high curvature), quasi-exact requires 10 iterations and 965 queries vs. backtracking's 193,817 queries at ε = 0.5 — a 200× query reduction from switching the line search algorithm. Even against backtracking's best ε on that function (ε = 0.001, requiring 867 queries), quasi-exact is within 11% — and the practitioner doesn't need to find that ε. The implementation cost is low: Algorithm 3 with c = 1 and α_prev reuse (tracking the previous step size, which is natural in GD) can be dropped into any existing gradient descent codebase as a replacement for the backtracking loop.
2. Derivative-free hyperparameter tuning for convex validation metrics.
Many hyperparameter optimization problems involve minimizing a convex validation metric (e.g., held-out log-loss) as a function of a scalar hyperparameter (e.g., L2 regularization strength λ). The validation metric is typically expensive to evaluate (requiring full model retraining), and gradients with respect to the hyperparameter are unavailable. Current practice often uses grid search, Bayesian optimization, or golden-section search. Grid search is query-inefficient; Bayesian optimization is overkill for 1D convex problems and requires tuning its own hyperparameters. GSS with a fixed number of iterations is the most principled quasiconvex method, but it terminates heuristically — "stop when the interval is smaller than δ" — with no guarantee on how close the validation metric is to its minimum. ∆-Secant with the y∗-gap stopping criterion (|Δ_y| ≤ y_tol) provides both: (a) deterministic convergence with a factor-2 x∗-gap reduction every two queries (faster than GSS's φ ≈ 1.62 on the bracketing interval whenever the x∗-gap is tighter, which Table 2 shows is typical — 23 vs. 50 queries on max{-x, 2x}), and (b) a provable guarantee that the returned λ achieves validation loss within y_tol of optimal (unlike GSS's heuristic interval-based stopping). The five-point optimality region construction requires only that the validation loss is convex in λ — a property that holds for many learning problems (e.g., the validation loss of ridge regression is convex in λ on a log scale). For a practitioner running 100 hyperparameter sweeps per week, the consistent 2–3× query reduction over GSS translates directly to reduced compute cost and faster experimentation cycles.
3. Line search for simulation-based optimization with expensive function evaluations.
In scientific computing and engineering design, optimization problems often involve a convex objective that requires running an expensive simulation (finite element analysis, computational fluid dynamics, molecular dynamics) to evaluate f(x). These simulations may take minutes to hours per evaluation, making query counts the dominant cost — a line search requiring 50 vs. 20 evaluations represents a difference of hours or days of wall-clock time. The paper's ∆-Secant algorithm is particularly well-suited to this regime because:
- No gradient requirement. Simulations rarely provide gradients (automatic differentiation through complex physics solvers is often infeasible), making derivative-free methods necessary.
- The y∗-gap provides a rigorous termination certificate. In safety-critical engineering optimization (e.g., optimizing airfoil shape subject to lift/drag constraints), knowing that the design is within
y_tolof optimal — rather than just "the search interval is small" — has regulatory implications. The y∗-gap is a verifiable bound that can be included in certification documentation. - Adaptive query placement reduces risk of wasted evaluations. GSS's fixed golden-ratio queries might evaluate the simulation at points far from the minimum (especially when the initial bracket is wide but the function's shape already localizes the minimum, as in the
sqrt(1+x^2)example where ∆-Secant reachesΔ_x < 2in 4 queries vs. GSS's 13). For a simulation costing 9000 per line search.
The paper's Table 2 indicates that across diverse convex functions, ∆-Secant consistently reduces queries by 30–70% compared to GSS — on a 50-evaluation GSS budget, this means 15–35 evaluations saved per line search, or thousands of dollars in simulation cost for expensive models. The implementation requires only the function evaluations the simulation already provides, with no changes to the simulation itself.
4. Enabling exact line search in resource-constrained on-device optimization.
On-device ML — running gradient descent on a smartphone or embedded system to personalize a model — faces severe constraints: limited CPU cycles, battery budget, and (often) no automatic differentiation framework capable of computing gradients through the full model. The paper's finding that ∆-Secant (derivative-free) often beats ∆-Bisection (gradient-based) in total oracle queries — for |x|, 7 function queries vs. 6 function+gradient queries (equivalent to 12 oracle calls) — has direct implications for this setting. If computing a gradient costs roughly the same as a function evaluation (common in finite-difference approximations or systems without AD), the derivative-free method is not just a fallback when gradients are unavailable — it is the more efficient choice for many convex subproblems. A mobile keyboard learning to predict next-word probabilities from user typing patterns could use ∆-Secant for the line search in SGD, with each function evaluation being a forward pass through a small language model and the convexity of the 1D restriction α → f(x_k - α∇f(x_k)) guaranteed by the convexity of the outer loss (e.g., logistic loss on a linear model). The c = 1 quasi-exact variant would further reduce the per-iteration query budget (typically 3–8 evaluations per line search based on the paper's data) while maintaining the convergence rate guarantee of Theorem 13. The key practical advantage over backtracking is robustness without tuning: on-device deployment means no ML engineer is present to tune ε for each new model version or user distribution — a default that works across problem instances is essential, and the paper's experimental sweep of c ∈ [0.5, 10] showing consistent performance across all test functions provides exactly this.
When to Prefer This Method
The paper explicitly positions its algorithms against named alternatives — bisection search, golden-section search, and backtracking line search — and provides clear conditions under which each proposed method should be preferred. The decision rules emerge directly from the theoretical guarantees and experimental results:
-
Prefer ∆-Bisection over bisection search when: (1) the function is known to be convex (not just quasiconvex), (2) gradient evaluations are available and their cost is comparable to or less than function evaluations, and (3) the initial interval boundaries have different function values and/or steep gradients — the advantage over bisection is proportional to how much smaller the initial x∗-gap is than the bracketing interval. If the function is nearly symmetric with similar boundary values (making
Δ_x ≈ [x_0, x_1]initially), the advantage narrows but is never negative — ∆-Bisection is never worse than bisection because querying at the midpoint of a region that equals the full interval is identical to bisection. The gradient-based y∗-gap also provides immediate termination certificates (unlike bisection), so always prefer ∆-Bisection over bisection for convex functions when gradients are available — there is no downside. -
Prefer ∆-Secant over golden-section search when: (1) the function is known to be convex, (2) gradient evaluations are unavailable or too expensive (cost ratio > 1), and (3) the function's shape is expected to produce a tight x∗-gap — in particular, when the boundary values differ significantly or the function has steep slopes near the boundaries. Table 2 shows ∆-Secant always outperforms GSS on the tested functions, with margins from 14% to >3×. However, the paper's theoretical analysis reveals a caveat: ∆-Secant's worst-case per-query reduction is
√2 ≈ 1.41on the x∗-gap (factor 2 every two queries), while GSS guaranteesφ ≈ 1.62on the bracketing interval. If the x∗-gap equals the bracketing interval (no tightening from secant constraints), ∆-Secant is asymptotically slower per query. Prefer GSS only if you have strong reason to believe the x∗-gap will remain approximately equal to the bracketing interval throughout the search (e.g., evaluating a nearly-flat convex function with similar boundary values) — in all other regimes, ∆-Secant's adaptive placement at the midpoint of the tighter region dominates. -
Prefer ∆-Secant over ∆-Bisection when: gradient evaluations are expensive relative to function evaluations. The paper's accounting in Table 2 (function+gradient = 2 queries) shows ∆-Secant beating ∆-Bisection on 11 of 12 function cases in total oracle queries. The magnitude of the advantage depends on the function: for
|x|, ∆-Secant uses 7 queries vs. ∆-Bisection's 78 equivalent queries (a 11× advantage); forx^4, 18 vs. 26 (a 1.4× advantage). Prefer ∆-Bisection only if gradients are essentially free (e.g., computed via automatic differentiation with no additional computational cost), in which case ∆-Bisection's single-query factor-2 guarantee dominates ∆-Secant's two-query factor-2 guarantee. -
Prefer quasi-exact line search (
c = 1) over backtracking line search when: (1) the function is convex, (2) you want a single default parameter that works across problem instances without per-function tuning, and (3) you can tolerate a factor-c/(c+1)slowdown in outer-loop convergence (factor 2 forc = 1) compared to true exact line search — a cost that is almost always dwarfed by the query savings from early termination. The paper's evidence strongly suggests always preferring quasi-exact over backtracking for convex problems: Table 3 shows backtracking's query count varies by 200× acrossεvalues on the same function, while quasi-exact varies by 2× acrosscvalues — andc = 1is always competitive with the bestεon every function, whileε = 0.1(a commonly recommended value) is catastrophic one^{3x} + e^{-3x}. The only scenario where backtracking might be preferred is if (a) the function is not known to be convex (backtracking's Armijo condition does not require convexity, only smoothness, while quasi-exact's y∗-gap computation assumes convexity and may produce invalid bounds on non-convex functions), or (b) the line search budget is extremely tight and the problem-specific bestεis known from prior experience — but the paper's diagnostic (Examples 15–16) shows that even this knowledge may not transfer across problem instances. For general convex optimization with unknown curvature, quasi-exact line search withc = 1is the safer default.
