Pith. sign in

REVIEW 76 major objections 32 minor 1 cited by

On Tradeoffs in Learning-Augmented Algorithms

T0 review · 76 major / 32 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper shows that in line search, one-max search, and ski rental, the standard learning-augmented objectives cannot be optimized simultaneously, and it quantifies the resulting tradeoffs.

desk verdict Extends brittleness to line search and one-max search with sound randomized smoothing, but the ski-rental average-cost tradeoff is a bound under a specific side-correctness model, not a universal distributional result. read the letter →

arxiv 2501.12770 v1 pith:IMGYQCT6 submitted 2025-01-22 cs.DS cs.AIcs.LG

Ziyad Benomar , Vianney Perchet This is my paper · ORCID
classification cs.DScs.AIcs.LG MSC 68W2768W40
keywords learning-augmentedalgorithmsconsistencyrobustnesssmoothnessaverage-caseperformanceskirentallinesearchone-max
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that learning-augmented algorithms—online algorithms that receive a possibly wrong prediction—cannot be judged by consistency and robustness alone. For line search, one-max search, and ski rental, it proves that smoothness (graceful degradation as prediction error grows) is a separate objective that often conflicts with consistency, and that in ski rental average performance under a stochastic prediction model conflicts with smoothness. A sympathetic reader would care because several known Pareto-optimal algorithms are brittle: an arbitrarily small prediction error snaps the competitive ratio from the consistency bound to the robustness bound, leaving only the pessimistic guarantee. The paper's remedy is to randomize the prediction or the acceptance threshold with a tunable parameter $\rho$, and it identifies exactly which pairs of objectives trade off.

What carries the argument

The load-bearing device is a one-parameter randomization of the prediction or threshold around a Pareto-optimal deterministic algorithm. For line search, the prediction $y$ is multiplied by $(1+\rho\xi)$, where $\xi$ has tail $1/(1+t)^2$, so small positive perturbations are common and large ones are rare; this smooths the discontinuity at $y=x$ while preserving robustness. For one-max search, when $y$ lies in $[1/r,\theta]$, the acceptance threshold is $e^{-\rho U}/r$ with $U$ uniform, interpolating between the brittle threshold $1/r$ and lower thresholds, with the factor $(1-e^{-\rho})/\rho$ as the cost. For ski rental, the buy time when $y<b$ is $(1+\rho(1/\lambda-1))b$, a convex combination of buying at $b$ ($\rho=0$) and at $b/\lambda$ ($\rho=1$); consistency and robustness depend only on $\lambda$, while smoothness improves and average cost worsens as $\rho$ grows. The average-case analysis uses the side-correctness probability $Q=\Pr(\mathbf{1}_{y\ge b}=\mathbf{1}_{x\ge b})$ to split the expected cost into the cases where the prediction points toward renting or buying.

What would settle it

Fix $\lambda$ and a concrete distribution for $x$ and $y$ with $\Pr(\mathbf{1}_{y\ge b}=\mathbf{1}_{x\ge b})=Q$, for example $x$ uniform on $[b,2b]$ and $y$ on the same side of $b$ with probability $Q$. Compute the exact expected cost of $ASR_{\lambda,\rho}$ as a function of $\rho$. If for some $Q$ and $\lambda$ the expected ratio $E_y[ASR_{\lambda,\rho}(x,y)]/\min(x,b)$ decreases when $\rho$ increases, the paper's claim that increasing $\rho$ degrades average cost would be disproved, since Theorem 4.2 only proves monotonicity of an upper bound.

Watch

Extended reading notes

Core claim

For the Pareto-optimal line-search algorithm $ALS_b$, the paper proves brittleness: with a perfect or slightly too-small prediction the ratio $ALS_b(x,y)/|x|$ is near $(b+1)/(b-1)$, but for $y$ just below $x$ it jumps to $1+2b^2/(b-1)$. Randomizing the prediction as $\tilde y=(1+\rho\xi)y$ with tail $\Pr(\xi\ge t)=1/(1+t)^2$ gives a smoothness bound whose slope improves with $\rho$ for $y<x$, while consistency degrades by an additive $2\rho/(b-1)$ and robustness is unchanged. For one-max search, the Pareto-optimal algorithm of Sun et al. is brittle when the prediction $y$ is just above $1/r$, and randomizing the acceptance threshold to $e^{-\rho U}/r$ in that region replaces the abrupt drop by a smooth degradation, at the cost of multiplying consistency and robustness by $(1-e^{-\rho})/\rho$. For ski rental, the algorithm $ASR_{\lambda,\rho}$ buys at time $\lambda b$ if $y\ge b$ and at $(1+\rho(1/\lambda-1))b$ if $y<b$; its consistency and robustness are Pareto-optimal for every $\rho$, its smoothness factor improves with $\rho$, and under the assumption that prediction and true season length are on the same side of $b$ with probability $Q\ge 1/2$, its expected cost is bounded by a quantity that is non-decreasing in $\rho$. Thus for fixed $\lambda$ the consistency-robustness pair is fixed, and $\rho$ traces a smoothness-versus-average-cost tradeoff.

Load-bearing premise

The ski-rental average-cost tradeoff rests on the assumption that the prediction and the true season length fall on the same side of the buying threshold $b$ with probability at least $Q\in[1/2,1]$, and that $Q$ is known to the algorithm designer.

Editorial extensions

If this is right

  • The line-search and one-max algorithms admit a consistency-smoothness tradeoff governed by $\rho$, with robustness unchanged for line search and degraded by at most $(1-e^{-\rho})/\rho$ for one-max search.
  • For ski rental, the Pareto-optimal consistency-robustness frontier can be attained at any smoothness level, so smoothness is not forced by the frontier.
  • Under the side-correctness assumption with probability $Q$, choosing $\rho=0$ is optimal for average cost, and with the tuned $\lambda^*$ the ski-rental bound improves on the earlier bound and can fall below 2, the deterministic worst-case ratio.
  • An algorithm designer can therefore set $\lambda$ to fix consistency and robustness and then use $\rho$ as a separate dial between smoothness and expected cost.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same randomization trick could be exported to other online problems with brittle Pareto-optimal algorithms; one-way trading is the natural next test, and the randomized-threshold construction for one-max search suggests a template.
  • The side-correctness model is binary; a natural extension is to exploit the full conditional distribution of prediction error, which would likely tighten the average-cost bounds and could reveal cases where exact expected cost is not monotone in $\rho$.
  • The paper's monotonicity statement for average cost is about the upper bound in Theorem 4.2; whether the exact expected cost of $ASR_{\lambda,\rho}$ is monotone in $\rho$ for every distribution satisfying the side-correctness model is left open, and can be checked by exact computation on simple distributions.
  • The two-parameter family suggests a multi-objective view of learning-augmented design in which consistency and robustness are settled at one layer and smoothness and average performance at another; formalizing that as a general framework is an implicit next step.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

76 major / 32 minor

Summary. The paper studies tradeoffs among consistency, robustness, smoothness, and average-case performance in learning-augmented algorithms. For line search, it shows that the Pareto-optimal algorithm of Angelopoulos is brittle and that randomizing the prediction with a heavy-tailed multiplier y~ = (1+rho xi)y yields a consistency-smoothness tradeoff governed by rho. For one-max search, it similarly shows brittleness of the Pareto-optimal threshold algorithm of Sun et al. and proposes a randomized threshold that trades consistency and robustness for smoothness. For ski rental, it introduces a two-parameter algorithm ASR_{lambda,rho} that, for every lambda and rho, maintains the known Pareto-optimal consistency-robustness pair, with rho controlling smoothness; under a side-correctness model Pr(1_{y>=b}=1_{x>=b})>=Q, it gives an upper bound on the worst-case expected ratio and claims a smoothness-versus-average-cost tradeoff. Theorems 2.3, 3.4, 4.1, and 4.2 are proved with explicit algebra, and numerical experiments illustrate the claimed tradeoffs.

Significance. If the claims are taken as stated, the paper makes a useful conceptual point: the design space for learning-augmented algorithms can exhibit at least two independent tradeoffs rather than only the consistency-robustness curve. The randomized smoothing mechanisms for line search and one-max search are concrete and the bounds are explicit and internally consistent in the positive-rho regime. The ski-rental algorithm also gives a clean demonstration that consistency and robustness can be held fixed while smoothness is adjusted. The main caveat is that the advertised average-cost-smoothness tradeoff in Section 4 is proved only for a worst-case-over-x upper bound on the expected ratio, not for a distribution-dependent expected cost; the paper should either redefine 'average performance' in that worst-case sense or prove the stronger statement. With that revision, the contribution would be a solid addition to the learning-augmented algorithms literature.

major comments (76)
  1. [§2, Theorem 2.3; §3, Theorem 3.4; §4, Theorem 4.1] The claim that 'increasing rho enhances the smoothness, it degrades the average cost' is not established for the distribution-dependent expected cost. Theorem 4.2 bounds, for each fixed x, E_y[ASR_{lambda,rho}(x,y)]/min(x,b) and shows that this upper bound is non-decreasing in rho; Corollary 4.2.1 then chooses rho=0 to minimize that upper bound. However, the true expected cost for a fixed x>=b is Q(1+lambda)b + (1-Q)[x 1{x<beta b} + (1+beta)b 1{x>=beta b}], where beta=1+rho(1/lambda-1). As rho increases, beta increases and the term x 1{x<beta b} can switch from (1+beta)b to x, which is a decrease; for example, with lambda=0.5, b=10, x=15, the expectation at rho=0.5 is larger than at rho=0.6. Thus the actual expected cost under a fixed distribution over x is not necessarily monotone in rho. The text's phrasing 'rho=0 is the optimal choice for achieving the best average-case performance' is therefore only valid for the particular worst-case-over-x upper bound, not for average-case cost as usually understood. Please either define 'average performance' explicitly as the worst-case over x of the expected ratio, or supply a distribution-dependent monotonicity result.
  2. [§3, Proposition 3.3] The parameter ranges include rho=0 while the displayed smoothness bounds contain factors of 1/rho. In Theorem 2.3 the bound for y<x is 4(b+1)/rho * eta/x; in Theorem 3.4 the y in [1/r,theta] case is ((1-e^{-rho})/rho)c - ((c-r)/rho)*eta/p*; in Theorem 4.1 the smoothness term is ((1+lambda)/rho)*eta/min(x,b). For rho=0 these expressions are undefined, and the proofs explicitly divide by rho, e.g., in Theorem 2.3 at the substitution s=(1/rho)(x/y-1) and in Theorem 4.1 at (beta-lambda)/(beta-1)=(1+lambda)/rho. Since the text also describes rho=0 as the baseline unrandomized algorithm, the theorems should be restated with rho>0 and the boundary rho=0 handled separately (or via limits). This is a formal flaw in the main statements, though local to the parameter boundary.
  3. [§4, Theorem 4.2, proof, x<b case] The condition delta <= epsilon/r does not imply |p1 - 1/r| <= epsilon p1 as claimed. Since p1 = 1/r - delta, the requirement is delta <= epsilon(1/r - delta), equivalently delta <= epsilon/(r(1+epsilon)). The proof still works after this correction, but the displayed condition is wrong.
  4. [§1.2, description of Sun et al.] In the case x<b, the two bullet points both say 'if x < lambda b'; the second bullet should be 'if x >= lambda b'. This is a typographical slip in the proof, not a substantive error.
  5. [Figure 2, caption] The sentence 'the authors prove that the levels of consistency and smoothness of AOM_lambda are Pareto-optimal' should read 'consistency and robustness'; smoothness is exactly what the paper later shows is missing.
  6. [References] The caption refers to 'Corollary 4.3', but the corollary under discussion is numbered Corollary 4.2.1.
  7. [§2 and §5, line search experiments] The reference to 'Chlkedowski' and the name 'Tomasz .Zolna' appear to contain typos; likely 'Chledowski' and 'Zolna' are intended.
  8. [§5, one-max search experiments] Figure 3 reports rho=5 although Theorem 2.3 restricts rho to [0,1]; the algorithm is well-defined for all rho>0, so either the theorem's range or the experiment caption should be adjusted for consistency.
  9. [§2, proof of Theorem 2.3] The experiment writes the prediction as y = p* + epsilon with epsilon ~ U[-sigma,sigma], but the theoretical analysis in Theorem 3.4 distinguishes the cases y < 1/c, 1/c <= y < 1/r, and y >= 1/r; for large sigma the prediction can fall outside [1,theta], which is outside the stated domain of the theorem. Please clarify how such predictions are handled.
  10. [§4, Corollary 4.2.1] The proof of the y>=x case derives the slightly stronger bound (b-1+2rho)/(b-1) + 2(1+rho)/(b-1)*eta/x, while the theorem states (b+1+2rho)/(b-1) for the constant term; the stronger bound is correct, so the discrepancy is harmless but may confuse readers.
  11. [§4, Theorem 4.2] The choice of lambda* depends on Q, and the paper states that Q is assumed known. If Q is misspecified or unknown, the average-case guarantee is not actionable; this should be stated more prominently, as it limits the practical interpretation of the average-case result.
  12. [§2, Lemma 2.1] The theorem states the assumption as Pr(1_{y>=b}=1_{x>=b}) >= Q, but the proof begins 'assume that Pr(...)=Q' and then argues the bound is non-increasing in Q. That step is correct, but the proof should explicitly say why the inequality version follows from the equality case, since the displayed equations in the proof use equality throughout.
  13. [§4, Theorem 4.1, proof] The lemma's statement 'j = ceil(ln(x/y)/(2 ln b)) in Z' should specify that the equality of the bracketing 1 <= y/x b^{2j} < b^2 holds for all real x,y>0; this is true, but the notation 'in Z' is redundant and the proof would benefit from a brief explanation of why the bracketing holds.
  14. [§5, ski-rental experiments] In the robustness case y>=b, the bullet for lambda b <= x < b writes (1+lambda)b <= (1+1/lambda)x; this is correct because lambda b <= x implies (1+lambda)b <= (1+lambda)/lambda * x, which is (1+1/lambda)x, but the derivation is not shown and may look abrupt.
  15. [§1.1, contributions] Figure 6 uses x ~ U[1,4b] and y selected 'arbitrarily' on the same side with probability Q; the theoretical result of Theorem 4.2 does not require a specific distribution of y on each side, only the side-correctness probability, so the experiment is consistent, but the word 'arbitrarily' could be clarified to mean 'drawn from some conditional distribution that satisfies the Q constraint'.
  16. [§1.2, related work] The contributions paragraph says the line-search and one-max algorithms yield a tradeoff 'governed by a parameter rho >= 0', but the formal theorems restrict rho to [0,1] (Theorem 2.3) or rho >= 0 (Theorem 3.4) with the boundary issue noted above. The introduction should be aligned with the precise parameter ranges in the theorems.
  17. [§1, Definition 1.1] The reference to 'Benomar and Perchet, 2024' is listed for non-clairvoyant scheduling, but the paper is also cited for the querying model; please verify that the citation in the related-work paragraph is the intended one.
  18. [§1, notation] The definition of brittleness quantifies over x,y with |x-y|<=epsilon x, but for x=0 the condition is trivial; since the problems assume x>=1 or x in [L,U], this is not an issue, but the domain of x should be stated in the definition.
  19. [§2, paragraph after Theorem 2.3] The notation ALG(x,y) is used both for the objective value of the algorithm and for the cost or payoff, depending on whether the problem is minimization (line search, ski rental) or maximization (one-max). This is standard but should be explicitly noted when introducing the definitions of consistency and robustness.
  20. [§3, Theorem 3.4, statement] The sentence 'For rho = 0, the algorithm is identical to that of Angelopoulos et al. [2019] and has optimal levels of consistency and smoothness' is misleading: at rho=0 the algorithm is identical and hence is brittle, so it cannot have 'optimal smoothness' in any meaningful sense. The text later clarifies that rho>0 improves smoothness, but this sentence should be phrased to avoid implying a smoothness guarantee at rho=0.
  21. [§4, Theorem 4.2, statement] The robustness bound in Theorem 3.4 for y in [1/r,theta] is ((1-e^{-rho})/rho) r, which tends to r as rho -> 0, matching the original robustness. This is fine, but the smoothness bound for that case tends to -infinity as rho -> 0? In fact the coefficient ((c-r)/rho) blows up, so the theorem's statement at rho=0 is not meaningful; this is part of the boundary issue already raised.
  22. [§4, paragraph 'Smoothness and Average-Cost Tradeoff'] The theorem's upper bound is a maximum of two expressions, one depending on rho for x>=b and one independent of rho for x<b. The non-decreasing property in rho is immediate, but the paper does not discuss whether the bound is tight. A tightness discussion would strengthen the tradeoff claim, since monotonicity of a possibly loose upper bound does not by itself prove that the actual worst-case expected ratio degrades with rho.
  23. [§5, Figure 3] The phrase 'Theorems 4.1 and 4.2 imply that, for a fixed lambda, the levels of consistency and robustness are constant, while the smoothness and average cost can be further adjusted using rho' should be qualified: Theorem 4.2 provides an upper bound, not an exact characterization, so 'the average cost can be adjusted' is only a statement about the bound unless a matching lower bound is proved.
  24. [§5, Figure 5] Figure 3's x-axis is labeled 'Prediction y in [x/b^2, b^2 x]' and the curves are averages over 10^5 trials; the paper does not state whether the standard deviation bars are shown or omitted. The caption should specify whether error bars are plotted.
  25. [§1, abstract] Figure 5 plots the empirical worst-case ratio supx in (0,5b] ASR_{lambda,rho}(x,y)/min(x,b) for y=x+epsilon, but Theorem 4.1's smoothness bound is for fixed x,y with eta=|x-y|; the experiment takes a supremum over x, which is not exactly the same as the theorem's bound. Please clarify the connection between the plotted quantity and the theorem.
  26. [§2, line search, after Definition 1.1] The abstract says 'in some settings, this comes at the expense of smoothness' but the paper shows that in line search and one-max search, randomization can restore smoothness at the expense of consistency, and in ski rental smoothness is adjustable for fixed consistency/robustness. The abstract's phrasing is broad; a more precise summary of the tradeoff directions would help the reader.
  27. [§3, one-max, after Proposition 3.3] The paper defines brittleness using a supremum over prediction error |x-y|<=epsilon x. In Proposition 2.2, the proof considers y in [max{x/b^2,(1-epsilon)x}, x), which is a valid subset; the argument 'taking y arbitrarily close to x' is correct because the condition y>= (1-epsilon)x is satisfied for y close to x. The proof is fine, but the role of epsilon could be made slightly more explicit.
  28. [§4, proof of Theorem 4.1] The discussion after Proposition 3.3 says 'the ratio AOM_lambda(p,y)/p* is larger than c for p*>=1/r, but it drops immediately to r for p*<1/r' — here 'larger' should be 'better' or 'greater than c' is ambiguous because the competitive ratio is maximized; a lower ratio is worse. Please choose clearer wording.
  29. [§4, proof of Theorem 4.2] In the consistency/smoothness case y>=b, the subcase x>=b gives ASR = (1+lambda)b = (1+lambda) min(x,b), which is correct; the next subcase 'lambda b <= x < b' uses (1+lambda)y <= (1+lambda) min(x,b) + (1+lambda)eta, which is also correct since y<=x+eta. The proof is sound but could be condensed.
  30. [§5, experiments, line search] In the x>=b case, the proof writes 'with probability Q: y>=b and ASR=(1+lambda)b'; this assumes the algorithm buys at time lambda b and then rents until b? For x>=b, the cost is lambda b + b = (1+lambda)b, which is correct. The notation is fine but the case distinction is slightly dense.
  31. [§5, experiments, one-max] The experiment fixes b=2.5 and x=100, while the theoretical results in Section 2 are scale-invariant because the algorithm's turn points scale with b; this should be stated so that the reader understands why these particular values are representative.
  32. [§5, experiments, ski rental] The experiment for one-max search uses lambda=0.1 and theta=5; the corresponding c and r values are not given, which makes the consistency and robustness values in Figure 4 hard to interpret. Please provide the numerical values of c(0.1) and r(0.1) or add them to the caption.
  33. [§1, contributions] The ski-rental experiment in Figure 5 sets lambda=0.5 and plots 'worst-case ratio sup_{x in (0,5b]}', but the theoretical smoothness bound in Theorem 4.1 is for all x>0; the experiment's restriction to x<=5b is not stated in the theorem. Please explain why the finite range is sufficient or adjust the comparison.
  34. [§1.1, contributions] The contributions paragraph promises 'a tight analysis' of the ski-rental algorithm, but the paper only proves upper bounds in Theorems 4.1 and 4.2 and does not establish matching lower bounds for consistency, robustness, smoothness, or average cost. The word 'tight' should be replaced by 'explicit' or 'precise' unless matching lower bounds are added.
  35. [§2, Theorem 2.3] The contribution list says 'we show that this brittleness can be mitigated by introducing randomness into the predictions' for line search; this is accurate, but the result is a high-probability or expectation bound, not a per-instance smoothness bound. The distinction between expectation and almost-sure guarantees should be stated in the contributions section.
  36. [§3, Theorem 3.4] The theorem's robustness statement 'we have with probability 1 that ALS_b(x,y~)/x <= 1+2b^2/(b-1)' is a worst-case guarantee over all predictions, including the randomized one; this is correct because the deterministic algorithm is rho-independent in robustness. However, if y is drawn from a distribution, the phrase 'with probability 1' could be confused with probability over y; please specify that the probability is over xi only.
  37. [§4, Theorem 4.1] The theorem's lower bounds are expectations over U, but the algorithm AOM_{lambda,rho} is randomized only through U when y in [1/r,theta]. The consistency/smoothness bounds for y in [1,1/r) are deterministic, which is fine, but the notation E_U in the theorem statement should be defined before the display.
  38. [§4, Theorem 4.1, statement] The notation 'min(x,b) = min(x,b)' appears in the proof; this is redundant and should be removed.
  39. [§4, Corollary 4.2.1, proof] The theorem's upper bound uses the min of two expressions. In the smoothness term, the coefficient ((1+lambda)/rho) becomes infinite as rho -> 0, so the theorem is only meaningful for rho>0. This is connected to the major boundary issue; please decide whether rho=0 is allowed and adjust the statement accordingly.
  40. [§4, Theorem 4.2, statement] In the proof of Corollary 4.2.1, the line '1 + 1-Q/λ' in the maximum should be '1 + (1-Q)/λ'; the current typesetting is ambiguous. Please fix the parentheses in the displayed formulas.
  41. [§1, contributions] The assumption Pr(1_{y>=b}=1_{x>=b}) >= Q is placed in the theorem statement but the proof assumes equality and then argues the bound is decreasing in Q. This is mathematically correct, but the notation should clearly indicate that the probability is over y conditional on x, which is the intended interpretation.
  42. [§2, line search] The paper says 'we demonstrate that certain problems involve multiple tradeoffs', but the line search and one-max results are for randomized algorithms, while the ski rental result is for a deterministic algorithm with randomized decision? ASR is deterministic. The breadth of the claim is fine, but the final sentence of the contributions should mention the randomized versus deterministic distinction.
  43. [§3, one-max] The line search section assumes x>0 without loss of generality and then considers y in R. The randomization y~=(1+rho xi)y preserves the sign of y; if y<0, the algorithm's initial direction is negative, and the analysis should still work by symmetry, but this is not stated. Please add a short note on the sign symmetry.
  44. [§4, average-case model] The competitive ratio for maximization is defined as a lower bound ALG(p)/p*, so 'consistency' and 'robustness' are also lower bounds on the payoff ratio. This is nonstandard but clearly stated; still, the paper should avoid saying 'consistency c' and 'robustness r' without reminding the reader that larger c and r are better in this section, in contrast to the minimization problems.
  45. [§4, Corollary 4.2.1] The average-case model assumes the decision-maker knows Q, the probability that the prediction is on the correct side of b. The paper compares its bound to Benomar and Perchet [2023] under the same model, which is appropriate. However, the practical relevance of the model could be discussed more: how would a decision-maker obtain Q?
  46. [§5, experiments] The expression for lambda* is complicated; a short derivation of the quadratic step would help. The current proof skips the algebra from the equivalence to the quadratic, which some readers may find abrupt.
  47. [§5, Figure 6] The numerical experiments report averages over 10^5 independent trials but do not provide standard deviations or confidence intervals except for line search, where they say 'average and standard deviation are computed'. Figure 4 and Figure 6 do not mention error bars. Please state whether error bars are included or why they are omitted.
  48. [§4, Theorem 4.2] In Figure 6, the empirical setup draws x ~ U[1,4b] and then places y on the same side with probability Q, but the theorem of Theorem 4.2 is worst-case over x. The empirical plot therefore shows an average over x, not the worst-case over x; since the theoretical bound is worst-case, the figure does not directly validate the theorem's tightness. Please clarify the relationship.
  49. [§2, Theorem 2.3, robustness] The theorem's upper bound is stated for all x>0, but the proof for x>=b uses the bound x < beta b and x >= beta b; when x=beta b exactly, the two cases give the same value, so the inequality is fine. The paper should not need to address equalities, but the current proof's strict inequalities are slightly imprecise; they can be made non-strict.
  50. [§3, Theorem 3.4, robustness] The almost-sure robustness bound in Theorem 2.3 is independent of rho and of the prediction distribution; this is a strong property and should be highlighted as a strength of the randomized approach.
  51. [§4, Theorem 4.1, smoothness] The robustness bound ((1-e^{-rho})/rho)r in Theorem 3.4 degrades as rho increases, which is a concrete price for smoothness. This tradeoff is clearly stated and is one of the paper's more valuable findings.
  52. [§4, paragraph 'Smoothness and Average-Cost Tradeoff'] The smoothness factor ((1+lambda)/rho) in Theorem 4.1 is decreasing in rho, which formalizes the intuition that buying earlier (small rho) makes the algorithm more brittle. The paper's explanation of this tradeoff is concise and correct for fixed x,y.
  53. [§1, abstract] The tradeoff paragraph also says 'minimizing the average cost necessitates selecting lambda optimally', but the optimal lambda in Corollary 4.2.1 depends on Q; if Q is not known, a robust choice of lambda might be preferable. A brief discussion of the sensitivity to Q would strengthen the practical interpretation.
  54. [§4, Theorem 4.1] The abstract's final sentence 'we demonstrate that certain problems involve multiple tradeoffs' is supported mainly by the ski-rental section, where consistency and robustness are held constant and smoothness changes with rho; the line search and one-max sections show tradeoffs between consistency and smoothness, which are also multi-dimensional. The abstract is accurate, though it could mention that the average-case result is conditional on a side-correctness model.
  55. [§2, Lemma 2.1] Theorem 4.1's consistency and robustness bounds are stated jointly as a min of two terms, but the consistency part (1+lambda) and robustness part (1+1/lambda) are the known Pareto-optimal pair for ski rental. The paper should explicitly note that these are the same as in Purohit et al. [2018] and Wei and Zhang [2020], which it does; the novelty is the smoothness parametrization by rho.
  56. [§3, Lemma 3.2] The expression in Lemma 2.1 has an o(1/x) term, but the proof actually gives explicit lower and upper bounds. The o(1/x) notation is unnecessary and slightly obscures the exact bound; the explicit inequalities are stronger and should be stated directly.
  57. [§3, Proposition 3.3] In Lemma 3.2, the final bound contains the factor max(1,c/lambda), which is somewhat unexpected; the proof's derivation is correct but readers may want a brief comment on why the max appears, namely the two subcases p* >= Phi and p* < Phi.
  58. [§4, Theorem 4.2, upper bound] Proposition 3.3 shows brittleness for the deterministic AOM_lambda; the proof's instance has p1 = 1/r - delta and p2 = 1, which is a valid price sequence only if 1/r - delta >= 1; the condition delta <= 1/r - 1 ensures this. The proof is clear.
  59. [§5, Figure 4] The theorem's upper bound max(2+(1/lambda-1)((1-Q)rho-Qlambda), 1+(1-Q)/lambda) is not symmetric in the two cases; the first term corresponds to x>=b and the second to x<b. It would be helpful to label these cases in the statement or right after the display.
  60. [§1.1, contributions] Figure 4 shows 'Empirical ratio' versus 'sigma in [1,theta]', but the prediction error in the one-max experiment is eta = |p* - y| = |epsilon|, whose maximum in the worst case is sigma; the axis label should state whether the horizontal axis is the max error or the noise scale sigma.
  61. [§2, Theorem 2.3, statement] The contributions list says 'we prove that the Pareto-optimal tradeoff between consistency and robustness can be achieved with different levels of smoothness' for ski rental; this is exactly Theorem 4.1 and is a clean, complete contribution. The average-case result, however, is as noted conditional on the worst-case interpretation.
  62. [§3, Theorem 3.4, statement] The theorem's bound has a piecewise form with different coefficients for y>=x and y<x; the y<x coefficient contains 1/rho, so the bound is not defined at rho=0. The paper's later claim that 'For rho=0, the algorithm is identical to that of Angelopoulos et al. [2019] and has optimal levels of consistency and smoothness' contradicts the theorem's parameter range. This is a concrete instance of the boundary issue.
  63. [§4, Theorem 4.2, statement] The theorem's consistency/smoothness bound for y in [1,1/c) has coefficient c-(c*eta)/p*; for eta=0 this equals c, which is the consistency value. For y in [1/c,1/r) the coefficient is c-(1-lambda)max(1,c/lambda)c*eta/p*, which also reduces to c at eta=0. These are consistent with the unrandomized algorithm.
  64. [§4, Corollary 4.2.1] The theorem's average-case bound is a worst-case guarantee over x of the expected ratio; such a guarantee is standard in the learning-augmented literature, but the paper should use the term 'worst-case expected ratio' or 'average prediction, worst-case instance' to avoid confusion with a Bayesian average over x.
  65. [§5, experiments] Corollary 4.2.1's bound is independent of rho because it sets rho=0, but the smoothness bound then blows up. This highlights the exact tradeoff the paper wants to make, but it also shows that the average-case optimal point rho=0 is the least smooth point, which is worth stating explicitly as the formal tradeoff.
  66. [§1, related work] The experiments for the three problems are simple and do not compare against baselines other than the unrandomized algorithm. Adding a comparison with the known Pareto-optimal algorithm would help validate the practical relevance of the tradeoffs.
  67. [§5, Figure 1] The paper cites several works on average-case performance of learning-augmented algorithms, but the connection to the worst-case-over-x expected ratio used in Theorem 4.2 is not always clear. A short paragraph explaining how the paper's average-case notion relates to Dütting et al., Gupta et al., and Benomar and Perchet would improve context.
  68. [§2, Figure 1] Figure 1 plots the mapping y -> ALS_b(x,y)/x for x arbitrary large and y in [x/b^2,b^2 x]; the discontinuity at y=x is the visual representation of brittleness. The figure is helpful, but the axis labels do not show the numerical values; a unit label or axis scale would make it more informative.
  69. [§5, Figure 3] The caption of Figure 1 says 'b−2x x b2x', which is garbled; it should be 'y ranges from x/b^2 to b^2 x'. Please fix the typesetting.
  70. [§5, Figure 4] Figure 3's legend shows rho=0.05, rho=0.5, rho=5.0, but Theorem 2.3 restricts rho to [0,1]; please clarify whether the theorem can be extended to rho>1 with the same proof or whether the experiment uses an out-of-range value.
  71. [§4, Theorem 4.2, proof] In the one-max experiment, the paper says the worst-case payoff is Phi if p* >= Phi and 1 otherwise, and that this is asymptotically achieved by a specific price sequence. This is a reasonable empirical proxy, but the statement 'asymptotically achieved' should be justified or cited, since the actual payoff of the algorithm when p*<Phi is the last price, which may be larger than 1 depending on the sequence.
  72. [§4, Theorem 4.2, bound comparison] In the proof of Theorem 4.2, the case x<b with probability 1-Q (i.e., y>=b) has two subcases: if x<lambda b the cost is x, and if x>=lambda b the cost is (1+lambda)b. The proof writes 'if x<lambda b' twice, but the second branch should be 'if x>=lambda b'; this is already noted in the major comments, but the typesetting also makes the displayed inequality hard to read.
  73. [§2, line search, randomization] The paper says the bound of Corollary 4.2.1 is better than the bound of Benomar and Perchet [2023], as shown in Figure 2. The improvement is plausible, but since the two papers use different algorithm parameterizations and the comparison is only of upper bounds, the statement 'better' should be qualified as 'better upper bound'.
  74. [§3, one-max, randomization] The choice of the tail distribution Pr(xi>=t)=1/(1+t)^2 is presumably selected to make the expectation integrals tractable; the paper does not discuss whether other distributions yield similar tradeoffs. This is not a flaw, but a sentence motivating the choice would help.
  75. [§1, contributions] The one-max randomization uses U~U[0,1] and threshold e^{-rho U}/r. This is a natural geometric randomization, but the paper does not compare it to other possible randomized thresholds; such a comparison is unnecessary for the paper's claims.
  76. [§4, main] Overall, the paper is clearly written and the main proofs are checkable. The major issues are the boundary rho=0 and the interpretation of the average-cost tradeoff; both are fixable with a careful revision.
minor comments (32)
  1. [§3, Theorem 3.4, statement] The theorem states 'rho in [0,1]' but the proof divides by rho; this should be corrected to 'rho in (0,1]' or the rho=0 case should be handled separately.
  2. [§4, Theorem 4.1, statement] The theorem states 'rho >= 0', but the y in [1/r,theta] bound uses ((c-r)/rho); the statement should specify rho>0 for that case.
  3. [§3, Proposition 3.3] The theorem states 'rho in [0,1]' before Algorithm 1 and then uses ((1+lambda)/rho) in the bound; please clarify the allowed values of rho.
  4. [§4, Theorem 4.2, proof] The condition on delta should be delta <= epsilon/(r(1+epsilon)) rather than delta <= epsilon/r; this is a minor correction that does not affect the proof's conclusion.
  5. [§1.2, related work] In the x<b case, the second bullet point should say 'if x >= lambda b' instead of repeating 'if x < lambda b'.
  6. [Figure 2, caption] The description of Sun et al. says 'consistency and smoothness' but should say 'consistency and robustness'.
  7. [References] The caption references Corollary 4.3, but the corollary is numbered 4.2.1.
  8. [§2, line search experiments] Several reference names appear garbled: 'Chlkedowski' and 'Tomasz .Zolna' should be checked and corrected.
  9. [§1, Definition 1.1] Figure 3 uses rho=5, which is outside the stated range of Theorem 2.3; either extend the theorem or adjust the experiment.
  10. [§5, Figure 1] The domain of x in Definition 1.1 is not specified; in the problems studied x is positive and bounded away from 0, so please state this in the definition.
  11. [§5, Figure 5] The caption of Figure 1 is garbled: 'b−2x x b2x' should be 'y in [x/b^2, b^2 x]'.
  12. [§4, Corollary 4.2.1] The caption of Figure 5 says 'worst-case ratio supx in (0,5b]', but the theoretical bound is for all x>0; please explain the finite range.
  13. [§2, Lemma 2.1] The displayed bound in the proof has '1 + 1-Q/λ' which is ambiguous; it should be '1 + (1-Q)/λ'.
  14. [§4, Theorem 4.1, proof] The o(1/x) notation is unnecessary because the proof gives explicit lower and upper bounds; using the explicit bounds would be cleaner.
  15. [§3, Lemma 3.2] The line 'min(x,b) = min(x,b)' should be removed.
  16. [§2, Theorem 2.3, proof] The appearance of the factor max(1,c/lambda) in the final bound could use a short explanatory sentence, as it arises from taking a minimum of two subcases.
  17. [§4, Theorem 4.2, statement] The proof derives a slightly stronger constant (b-1+2rho)/(b-1) for y>=x; the displayed theorem uses (b+1+2rho)/(b-1). The stronger bound is correct, so the discrepancy is harmless but should be noted to avoid confusion.
  18. [§5, Figure 6] The proof assumes Pr(...)=Q and then argues the bound is increasing in Q? Actually the bound is non-increasing in Q, so the inequality version follows; this should be stated explicitly in the proof.
  19. [§1.1, contributions] The experiment averages over x, but the theorem is a worst-case bound over x; the figure should be described as an empirical average, not a validation of the worst-case bound.
  20. [§5, one-max experiments] The word 'tight' in the descriptions of the line search and ski-rental analyses is not supported by matching lower bounds; consider using 'explicit' or 'precise' instead.
  21. [§4, paragraph 'Smoothness and Average-Cost Tradeoff'] The text says 'p* + epsilon with epsilon ~ U[-sigma,sigma]', but the theorem assumes y in [1,theta]; predictions outside this range should be clipped or the theorem extended.
  22. [§5, experiments] The phrase 'Theorems 4.1 and 4.2 imply that ... the average cost can be further adjusted using rho' should be tempered to 'the worst-case expected ratio is bounded by a non-decreasing function of rho'.
  23. [§3, Theorem 3.4, statement] The experiments do not report standard deviations for Figures 4 and 6; please state whether error bars are omitted or are too small to be visible.
  24. [§2, line search] The expectation E_U in the theorem statement should be defined before the display, as U is introduced later.
  25. [§3, one-max] The sign symmetry for negative predictions y is not discussed; a one-sentence note would clarify the domain of the theorem.
  26. [§4, Theorem 4.2, proof] The paper should remind the reader that for this maximization problem higher consistency and robustness values are better, unlike the minimization problems.
  27. [§4, Theorem 4.1] The strict inequalities in the case distinctions (x<beta b and x>=beta b) are fine, but the equality case x=beta b belongs to the second branch; the proof is still correct.
  28. [§5, Figure 3] The smoothness coefficient ((1+lambda)/rho) is decreasing in rho, which is the basis of the smoothness-average tradeoff when combined with Theorem 4.2; stating this explicitly would help the reader.
  29. [§5, Figure 4] The caption of Figure 3 should specify whether the plotted curves include error bars; the text mentions standard deviation but the figure caption does not.
  30. [§2, Theorem 2.3, robustness] The horizontal axis in Figure 4 is labeled 'sigma in [1,theta]', but in the text sigma is the noise scale; the axis label should be 'noise scale sigma' or 'max error sigma'.
  31. [§1, abstract] The robustness guarantee in Theorem 2.3 is stated 'with probability 1'; this is a strength of the approach and should be highlighted in the contributions section.
  32. [§4, main] The abstract's mention of 'multiple tradeoffs' is supported, but the average-case tradeoff is conditional on the side-correctness model; including this condition in the abstract would be more precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the tradeoff bounds are derived from explicit parameters and assumptions, not fitted or self-justified.

full rationale

The paper's load-bearing results are proved from explicit definitions and assumptions rather than from its own conclusions. In line search (Theorem 2.3) and one-max search (Theorem 3.4), the algorithms are deterministic functions of parameters b, lambda, rho and of explicit randomizations; the consistency, robustness, and smoothness bounds are proven directly via Lemmas 2.1, 3.1, 3.2, 3.5, and 3.6. In ski rental, Theorem 4.1 proves consistency, robustness, and smoothness for ASR_lambda_rho by case analysis on x relative to b and beta, and Theorem 4.2 proves an upper bound on E_y[ASR]/min(x,b) under the explicit side-correctness assumption Pr(1_{y>=b}=1_{x>=b}) >= Q. No parameter is fitted to data, and no claimed prediction is an input by construction: rho, lambda, b, and Q are explicit design choices or assumption variables. The self-citations to Benomar and Perchet [2023] supply the average-case model and a comparison baseline, but the proofs here do not import those cited theorems as load-bearing steps; the Q assumption is restated and used conditionally. The only caveat is that the claim that increasing rho degrades the average cost is established for the worst-case upper bound of Theorem 4.2, not for every possible distribution of x; this is a scope or correctness concern rather than a circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The mathematical results are parameterized by explicit design choices b, lambda, rho and by the distributional assumption Q. No constants are fit to data, and the paper introduces no new physical or ontological entities. The main external input is the assumed Pareto-optimality of the two base algorithms cited from prior work.

free parameters (3)
  • b = >=2
    Line search hyperparameter inherited from Angelopoulos's Pareto-optimal algorithm; controls consistency (b+1)/(b-1) and robustness 1+2b^2/(b-1). It is an input, not fitted.
  • lambda = in [0,1]
    Consistency-robustness knob for one-max (via Sun et al.) and ski-rental (inherited from Purohit et al.).
  • rho = in [0,1]
    New smoothness parameter introduced by the paper for line search, one-max search, and ski rental. The tradeoff analyses treat it as a free design knob.
assumptions (4)
  • domain assumption Pareto-optimality of the base algorithms ALS_b (Angelopoulos 2023) and AOM_lambda (Sun et al. 2021) is taken as given.
    The paper's narrative of deviating from Pareto-optimal algorithms relies on these prior results; the proofs are cited, not reproduced.
  • domain assumption Performance of randomized algorithms is measured in expectation over internal randomness, while robustness is required almost surely.
    Standard in competitive analysis of randomized algorithms; used implicitly in Theorems 2.3 and 3.4.
  • domain assumption In ski-rental, the prediction y's side relative to b is correct with probability at least Q.
    Stated before Theorem 4.2; this is a modeling assumption on the prediction distribution, not derived from first principles.
  • standard math Standard calculus and tail-integral identities for expectations of nonnegative random variables are used in the proofs.
    For example, E[X] = integral of Pr(X >= t) dt and algebraic inequalities such as 1/(1+u) >= 1-u are invoked without proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Tradeoffs in Learning-Augmented Algorithms." pith.science (2026). https://pith.science/paper/IMGYQCT6

@misc{pith2026250112770,
  author       = {Pith},
  title        = {Pith review of: On Tradeoffs in Learning-Augmented Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IMGYQCT6}},
  note         = {Machine review of arXiv:2501.12770}
}
read the original abstract

The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key properties: consistency, robustness, and smoothness. In scenarios where distributional information about predictions is available, a strong expected performance is required. Typically, the design of these algorithms involves a natural tradeoff between consistency and robustness, and previous works aimed to achieve Pareto-optimal tradeoffs for specific problems. However, in some settings, this comes at the expense of smoothness. This paper demonstrates that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance.

Figures

Figures reproduced from arXiv: 2501.12770 by the authors.

Figure 1
Figure 1. The mapping y 7→ A LS b (x, y)/x for x arbitrary large and y ∈ [ x b 2 , b2x]. . Proof. By definition of j, we have 1 ≤ b 2jy/x < b2 , and recalling that y = b ky /γy, we obtain b ky+2j−2 γy < x ≤ b ky+2j γy . Using these inequalities, we deduce that the algorithm finds the target at iteration ky + 2j. Indeed, as y > 0, at iteration ky + 2j − 2, the searcher travels along the positive branch until reaching the posit… view at source ↗
Figure 2
Figure 2. Upper bound on the competitive ratio of A SR λ,ρ with λ, ρ as in Corollary 4.2.1, and with λ, ρ as in Lemma 2.2 of Benomar and Perchet [2023]. Proof. For all Q ∈ [ 1 2 , 1] and ρ ∈ [0, 1], the upper bound of Theorem 4.2 is non-decreasing with respect to ρ, hence the optimal choice of ρ is 0. With ρ = 0, let us examine for which value of λ the two terms in the maximum of the upper bound in Theorem 4.2 are equal. We h… view at source ↗
Figure 4
Figure 4. Consistency-smoothness tradeoff of Algorithm A OM λ,ρ for ρ ∈ {0, 0.5, 1}. the upper bound established in Theorem 4.2. However, the decision-maker may opt to deviate from this value to achieve a better level of consistency or robustness, depending on the specific use case. Furthermore, Theorems 4.1 and 4.2 imply that, for a fixed λ ∈ [0, 1], the levels of consistency and robustness of A SR λ,ρ are constant, while th… view at source ↗
Figures from the paper (1 more)
Figure 6
Figure 6. Figure 6: Average-case performance of A SR λ,ρ when 1y≥b = 1x≥b with probability Q its impact on the average performance of A SR λ,ρ, under the assumption that the prediction lies on the same side of b as the true value of the number of snow days x with probability Q. In both ex…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search

    cs.DS 2025-02 accept novelty 8.0 of 10

    The paper constructs a deterministic one-max-search algorithm that simultaneously achieves the best possible consistency-robustness trade-off and the best possible smoothness for prediction errors, for both multiplica...

Reference graph

Works this paper leans on

41 extracted references · 32 canonical work pages · cited by 1 Pith paper

  1. [1]

    Online search with a hint

    Spyros Angelopoulos. Online search with a hint. Information and Computation, 295: 0 105091, 2023

    work page 2023

  2. [2]

    Online Computation with Untrusted Advice

    Spyros Angelopoulos, Christoph D \"u rr, Shendan Jin, Shahin Kamali, and Marc Renault. Online computation with untrusted advice. arXiv preprint arXiv:1905.05655, 2019

    work page Pith review arXiv 1905

  3. [3]

    Overcoming brittleness in pareto-optimal learning-augmented algorithms

    Spyros Angelopoulos, Christoph D \"u rr, Alex Elenter, and Yanni Lefki. Overcoming brittleness in pareto-optimal learning-augmented algorithms. arXiv preprint arXiv:2408.04122, 2024 a

    arXiv 2024

  4. [4]

    Search games with predictions

    Spyros Angelopoulos, Thomas Lidbetter, and Konstantinos Panagiotou. Search games with predictions. arXiv preprint arXiv:2401.01149, 2024 b

    arXiv 2024

  5. [5]

    Learning-augmented dynamic power management with multiple states via new ski rental bounds

    Antonios Antoniadis, Christian Coester, Marek Eli \'a s, Adam Polak, and Bertrand Simon. Learning-augmented dynamic power management with multiple states via new ski rental bounds. Advances in Neural Information Processing Systems, 34: 0 16714--16726, 2021

    work page 2021

  6. [6]

    Paging with succinct predictions

    Antonios Antoniadis, Joan Boyar, Marek Eli \'a s, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S Larsen, Adam Polak, and Bertrand Simon. Paging with succinct predictions. In International Conference on Machine Learning, pages 952--968. PMLR, 2023 a

    work page 2023

  7. [7]

    Online metric algorithms with untrusted predictions

    Antonios Antoniadis, Christian Coester, Marek Eli \'a s , Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Transactions on Algorithms, 19 0 (2): 0 1--34, 2023 b

    work page 2023

  8. [8]

    Worst-case running times for average-case algorithms

    Luis Antunes and Lance Fortnow. Worst-case running times for average-case algorithms. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 298--303. IEEE, 2009

    work page 2009

Show all 41 references
  1. [9]

    Searching in the plane

    Ricardo A Baezayates, Joseph C Culberson, and Gregory JE Rawlins. Searching in the plane. Information and computation, 106 0 (2): 0 234--252, 1993

    1993

  2. [10]

    The primal-dual method for learning augmented algorithms

    Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33: 0 20083--20094, 2020

    2020

  3. [11]

    On the linear search problem

    Anatole Beck. On the linear search problem. Israel Journal of Mathematics, 2 0 (4): 0 221--228, 1964

    1964

  4. [12]

    Yet more on the linear search problem

    Anatole Beck and Donald J Newman. Yet more on the linear search problem. Israel journal of mathematics, 8 0 (4): 0 419--429, 1970

    1970

  5. [13]

    Learning-augmented priority queues

    Ziyad Benomar and Christian Coester. Learning-augmented priority queues. arXiv preprint arXiv:2406.04793, 2024

    2024 arXiv

  6. [14]

    Advice querying under budget constraint for online algorithms

    Ziyad Benomar and Vianney Perchet. Advice querying under budget constraint for online algorithms. In Thirty-seventh Conference on Neural Information Processing Systems, 2023

    2023

  7. [15]

    Non-clairvoyant scheduling with partial predictions

    Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Forty-first International Conference on Machine Learning, 2024

    2024

  8. [16]

    Robust learning-augmented caching: An experimental study

    Jakub Ch l k e dowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz .Z o l na. Robust learning-augmented caching: An experimental study. In International Conference on Machine Learning, pages 1920--1930. PMLR, 2021

    1920

  9. [17]

    Average case-worst case tradeoffs for evacuating 2 robots from the disk in the face-to-face model

    Huda Chuangpishit, Konstantinos Georgiou, and Preeti Sharma. Average case-worst case tradeoffs for evacuating 2 robots from the disk in the face-to-face model. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Roboti...

    2018

  10. [18]

    Max-cut with -accurate predictions

    Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. Max-cut with -accurate predictions. arXiv preprint arXiv:2402.18263, 2024

    2024 arXiv

  11. [19]

    Learning online algorithms with distributional advice

    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference on Machine Learning, pages 2687--2696. PMLR, 2021

    2021

  12. [20]

    Secretaries with advice

    Paul D \"u tting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 409--429, 2021

    2021

  13. [21]

    Optimal search and one-way trading online algorithms

    Ran El-Yaniv, Amos Fiat, Richard M Karp, and Gordon Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 30: 0 101--139, 2001

    2001

  14. [22]

    Online algorithms for rent-or-buy with expert advice

    Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pages 2319--2327. PMLR, 2019

    2019

  15. [23]

    Augmenting online algorithms with -accurate predictions

    Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, and Kevin Sun. Augmenting online algorithms with -accurate predictions. Advances in neural information processing systems, 35: 0 2115--2127, 2022

    2022

  16. [24]

    On the complexity of algorithms with predictions for dynamic graph problems

    Monika Henzinger, Barna Saha, Martin P Seybold, and Christopher Ye. On the complexity of algorithms with predictions for dynamic graph problems. arXiv preprint arXiv:2307.16771, 2023

    2023 arXiv

  17. [25]

    Competitive snoopy caching

    Anna R Karlin, Mark S Manasse, Larry Rudolph, and Daniel D Sleator. Competitive snoopy caching. Algorithmica, 3: 0 79--119, 1988

    1988

  18. [26]

    Karlin, Mark S

    Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica, 11 0 (6): 0 542--571, 1994

    1994

  19. [27]

    The case for learned index structures

    Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pages 489--504, 2018

    2018

  20. [28]

    Minimalistic predictions to schedule jobs with online precedence constraints

    Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schl \"o ter. Minimalistic predictions to schedule jobs with online precedence constraints. In International Conference on Machine Learning, pages 18563--18583. PMLR, 2023

    2023

  21. [29]

    Learning augmented binary search trees

    Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, pages 13431--13440. PMLR, 2022

    2022

  22. [30]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3296--3305. PMLR, 2018

    2018

  23. [31]

    On preemption and learning in stochastic scheduling

    Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet. On preemption and learning in stochastic scheduling. In International Conference on Machine Learning, pages 24478--24516. PMLR, 2023

    2023

  24. [32]

    Lattices that admit logarithmic worst-case to average-case connection factors

    Chris Peikert and Alon Rosen. Lattices that admit logarithmic worst-case to average-case connection factors. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 478--487, 2007

    2007

  25. [33]

    Improving online algorithms via ml predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018

    2018

  26. [34]

    Robustness between the worst and average case

    Leslie Rice, Anna Bair, Huan Zhang, and J Zico Kolter. Robustness between the worst and average case. Advances in Neural Information Processing Systems, 34: 0 27840--27851, 2021

    2021

  27. [35]

    Probabilistically robust learning: Balancing average and worst-case performance

    Alexander Robey, Luiz Chamon, George J Pappas, and Hamed Hassani. Probabilistically robust learning: Balancing average and worst-case performance. In International Conference on Machine Learning, pages 18667--18686. PMLR, 2022

    2022

  28. [36]

    Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis

    Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An. Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. arXiv preprint arXiv:2302.06832, 2023

    2023 arXiv

  29. [37]

    Pareto-optimal learning-augmented algorithms for online conversion problems

    Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. Pareto-optimal learning-augmented algorithms for online conversion problems. Advances in Neural Information Processing Systems, 34: 0 10339--10350, 2021

    2021

  30. [38]

    Worst-case versus average case complexity of ray-shooting

    L \'a szl \'o Szirmay-Kalos and G \'a bor M \'a rton. Worst-case versus average case complexity of ray-shooting. Computing, 61 0 (2): 0 103--131, 1998

    1998

  31. [39]

    Optimal robustness-consistency trade-offs for learning-augmented online algorithms

    Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. Advances in Neural Information Processing Systems, 33: 0 8042--8053, 2020

    2020

  32. [40]

    Worst-case and average-case approximations by simple randomized search heuristics

    Carsten Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Annual Symposium on Theoretical Aspects of Computer Science, pages 44--56. Springer, 2005

    2005

  33. [41]

    Robust learning-augmented dictionaries

    Ali Zeynali, Shahin Kamali, and Mohammad Hajiesmaili. Robust learning-augmented dictionaries. In Forty-first International Conference on Machine Learning

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.