Pith. sign in

REVIEW 3 major objections 4 minor 35 references

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

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read One-max-search can be Pareto-optimal and smooth at once, and a single threshold rule achieves both.

desk verdict First deterministic Pareto-optimal and smooth one-max-search algorithm; the core results hold, but the multiplicative optimality claim needs precise scoping. read the letter →

arxiv 2502.05720 v1 pith:OIFYQ3YO submitted 2025-02-08 cs.DS cs.AI

Ziyad Benomar , Lorenzo Croissant , Vianney Perchet , Spyros Angelopoulos This is my paper · ORCID
classification cs.DScs.AI MSC 68W2768W40
keywords one-maxsearchlearning-augmentedalgorithmscompetitiveanalysisParetooptimalitysmoothnessconsistency-robustnesstrade-offoptimaltransportpredictionerror
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

The paper asks whether one-max-search — the online problem of irrevocably accepting one price from a revealed sequence in $[1,\theta]$ — can have a deterministic algorithm that is simultaneously Pareto-optimal in the consistency–robustness trade-off and smooth in the prediction error. Its answer is yes: among all threshold rules with a fixed robustness $r$, the threshold $\Phi^1_r(y)=\max(r\theta,\varphi_r(y))$ maximizes smoothness, and for a large range of $r$ no Pareto-optimal rule can improve on its power-law exponent in the multiplicative error $E$. Under the standard additive error, the same rule attains the best possible smoothness constant for every robustness value, giving what the paper calls a triple Pareto front. The smoothness bounds also extend to stochastic settings in which prices and predictions are random, with an optimal-transport formulation that isolates the role of the coupling between them.

What carries the argument

The central objects are single-threshold rules $A_\Phi$ that accept the first price at least $\Phi(y)$, where $y$ is a prediction of the maximum price $p^*$, and the associated multiplicative error $E(p^*,y)=\min(p^*/y, y/p^*)$. Theorem 3.1 pins down the class $\mathcal{P}_r$ of all thresholds that give robustness $r$ and consistency $1/(r\theta)$: for every $z \in [1,\theta]$, $r\theta \le \Phi(z) \le 1/r$, and for $z \in [r\theta,\theta]$, $z/(r\theta) \le \Phi(z) \le z$. The paper interpolates within this class by a parameter $\rho \in [0,1]$; $\rho=0$ is the earlier Pareto-optimal threshold, while $\rho=1$ gives $\Phi^1_r(y)=\max(r\theta,\varphi_r(y))$, whose graph has minimal maximal slope. Smoothness is quantified by the exponent $s$ of $E$ in the performance lower bound, and the analysis shows the exponent is controlled by the largest slope of the threshold, so the minimal-slope member yields the best smoothness. The matching lower bound (Theorem 3.3) is forced by the constraints $\Phi(r\theta)=r\theta$ and $\Phi(\theta)=1/r$ on adversarial instances, from which $u \ge \ln\theta/\ln(r\theta)-2$ follows.

What would settle it

For fixed $\theta$ and $r \in [\theta^{-1},\theta^{-2/3}]$, consider a threshold $\Phi \in \mathcal{P}_r$ other than $\Phi^1_r$ and compute the worst-case ratio $\inf_{p,y} A_\Phi(p,y)/p^*$ on the adversarial sequences $I_n(q)$ in the limit $n \to \infty$; if any such $\Phi$ satisfies the bound with exponent $u < \ln\theta/\ln(r\theta) - 2$, Theorem 3.3 fails. A single explicit instance on which another Pareto-optimal threshold dominates $A^1_r$ uniformly in $E$ would refute the multiplicative part of the triple-front claim.

Watch

Extended reading notes

Core claim

One-max-search with predictions admits a deterministic, Pareto-optimal, and smooth algorithm, contrary to what earlier brittleness results might suggest. For any fixed robustness $r \in [\theta^{-1},\theta^{-1/2}]$ and consistency $1/(r\theta)$, the paper characterizes all Pareto-optimal thresholds (Theorem 3.1) and shows that the particular threshold $\Phi^1_r(y)=\max(r\theta,\varphi_r(y))$ yields the smoothness guarantee $A^1_r(p,y)/p^* \ge \max(r, (1/(r\theta)) E(p^*,y)^s)$ with $s = \max(1, \ln\theta/\ln(r\theta) - 2)$ and $E(p^*,y)=\min(p^*/y, y/p^*)$ (Theorem 3.2). Theorem 3.3 proves that any Pareto-optimal algorithm must have exponent $u \ge \ln\theta/\ln(r\theta)-2$, so $A^1_r$ is optimal on this front for $r \le \theta^{-2/3}$. For additive error $\eta=|p^*-y|$, Theorem 3.4 gives the exact optimal slope $\beta^*$ for all $r$, so $A^1_r$ attains the triple Pareto-optimal front. The same smoothness transfers to stochastic one-max-search via Jensen's inequality, and the resulting expected bound is minimized over couplings of $(P^*,Y)$, connecting the analysis to optimal transport.

Load-bearing premise

The optimality of the smoothness guarantees is relative to the chosen error measures — the power-law exponent in $E$ for multiplicative error and the linear slope in $\eta$ for additive error — so a different definition of smoothness could make some other Pareto-optimal algorithm look smoother.

Editorial extensions

If this is right

  • For every robustness $r \le \theta^{-2/3}$, the deterministic algorithm $A^1_r$ is simultaneously Pareto-optimal and optimally smooth among Pareto-optimal algorithms, measured by the multiplicative error $E$.
  • For additive prediction error, $A^1_r$ achieves the best achievable smoothness constant $\beta^*$ for all $r \in [\theta^{-1},\theta^{-1/2}]$, completing a triple Pareto front.
  • Under the $\lambda$-trust parametrization, the bound becomes $\theta^{-\lambda/2} E^{\max(1,2/\lambda-2)}$ alongside consistency $\theta^{-\lambda/2}$ and robustness $\theta^{-(1-\lambda/2)}$, making the guarantees easy to instantiate.
  • In the stochastic setting, the same algorithm satisfies $\mathbb{E}[A^1_r]/\mathbb{E}[P^*] \ge \max(r, (1/(r\theta))\, \mathbb{E}[P^* E(P^*,Y)^s]/\mathbb{E}[P^*])$, with a coupling-dependent term that an optimal transport dual can lower-bound using only marginal distributions.
  • Randomisation is not needed for smoothness: a deterministic threshold within the Pareto-optimal class already degrades gracefully, and it does so without losing worst-case guarantees.

Reading between the lines

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

  • The same maximal-slope design principle could produce Pareto-optimal smooth algorithms for related online selection problems, such as k-search or one-way trading with divisible orders, where brittleness has been observed.
  • The optimal-transport formulation suggests a new way to measure prediction quality: the cost $p^* E(p^*,y)^s$ is asymmetric and algorithm-specific, unlike symmetric Wasserstein distances, so predictions could be optimised for this cost rather than for raw accuracy.
  • The gap for $r \in (\theta^{-2/3}, \theta^{-1/2}]$, where $A^1_r$ is smooth but not proven optimal, is a natural target: the true optimal exponent in that range may be smaller than the one the paper establishes.
  • If smoothness is assessed by other error functionals, the triple-front claim may not transfer; refining the definition of smoothness is a modelling choice that would need to be re-examined for each new metric.
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

3 major / 4 minor

Summary. The paper studies learning-augmented one-max search, in which a trader observes a sequence of prices in [1, θ] and must irrevocably accept one, with access to a prediction y of the maximum price p*. The authors characterize the set of thresholds that yield Pareto-optimal consistency-robustness trade-offs (Theorem 3.1), and then introduce a parametric family of deterministic threshold algorithms A^ρ_r that interpolates between the brittle Pareto-optimal algorithm of Sun et al. (ρ=0) and a smooth variant (ρ=1). They prove smoothness bounds for both multiplicative and additive prediction error (Theorems 3.2 and 3.4) and give a lower bound on the achievable smoothness exponent for algorithms whose guarantee has a pure power-law form (Theorem 3.3). The paper further develops a stochastic analysis in which prices and predictions are random, deriving expectation bounds that depend on the coupling of (P*, Y), and connects the resulting minimization to an optimal transport problem. Numerical experiments on synthetic worst-case instances and Bitcoin data illustrate that A^1_r degrades more gracefully than A^0_r as prediction error increases.

Significance. The central contribution is a deterministic learning-augmented algorithm for one-max-search that is simultaneously Pareto-optimal with respect to consistency and robustness and smooth with respect to prediction error. This addresses a real gap: the previous Pareto-optimal algorithm is brittle, and existing smooth algorithms are either randomized or sacrifice Pareto optimality. The proofs are detailed and mostly self-contained, and the stochastic extension via couplings and optimal transport is a novel and suggestive direction. The experimental section is useful and consistent with the theory. The main caveat is that the optimality claims are established only within restricted families of smoothness bounds (power-law for multiplicative error, linear for additive error), not for all continuous monotone smoothness functions; this does not invalidate the deterministic construction but requires the claims to be scoped precisely.

major comments (3)
  1. [§3, Eq. (2)] The definition of Φ^ρ_r in Eq. (2) is not the linear interpolation described in the text and used in the proofs. At y = 1/r the third branch evaluates to φr(1/r) + (1/r - φr(1/r))/(ρ(1-r)) · 1/(r²θ), which is not equal to φr(1/r) in general. The correct interpolation, which appears in Corollary B.2 and is used throughout Appendix B, is Φ^ρ_r(y) = φr(y) + (1/r - φr(y))/(ρ(θ - 1/r)) · (y - 1/r) for y ∈ [1/r, 1/r + ρ(θ - 1/r)]. Since A^ρ_r is the paper's main algorithmic object, Eq. (2) must be corrected; as written, a reader cannot reconstruct the algorithm.
  2. [§3.1, Theorem 3.3 and following paragraph] The optimality claim for multiplicative error is proven only within the family of bounds of the exact form max{r, (1/rθ)E^u} in Eq. (5). The proof in Appendix B.3 evaluates the bound at a single error value E0 = 1/(rθ), where Pareto-optimality already forces the ratio to be approximately r; it does not rule out a Pareto-optimal algorithm whose smoothness guarantee is a different monotone function of E, e.g. f(E) = (1/rθ)E^k g(E) with g(1) = g(1/(rθ)) = 1 and g(E) > 1 for intermediate E, that is strictly better than a pure power law. The statements that A^1_r 'attains the triple Pareto-optimal front' and that 'no Pareto-optimal algorithm can guarantee better smoothness' are therefore broader than what the theorem establishes. The same caveat applies to Theorem 3.4, whose lower bound in Appendix D.2 assumes the linear form in Eq. (6). The authors should either prove a lower bound over all continuous monotone smoothness functions or explicitly restrict the optimality claims to power-law (resp. linear) smoothness bounds.
  3. [§3.1, Theorem 3.3 and Appendix B.3] Theorem 3.3 states 'Let A be any algorithm', but the proof assumes A is deterministic: it invokes the equivalence between any deterministic algorithm and a threshold algorithm on the In(q) instances. The paper's later phrase 'among all deterministic algorithms' is correct, but the theorem statement itself is not, and the possibility of randomized algorithms achieving better smoothness is left open. This is a scope error in a central statement; it does not affect the deterministic construction A^1_r, but the theorem and surrounding claims should be made unambiguous.
minor comments (4)
  1. [§2, Theorem 3.1] The phrase 'For any fixed of robustness r' contains a typo; it should read 'For any fixed robustness level r'.
  2. [§4.1, Lemma 4.1] The proof says 'Apply Jensen's inequality to Theorem 3.2', but the displayed inequality follows directly by linearity of expectation from A ≥ p* · max{r, (1/rθ)E^s}; Jensen is not needed. The proof should cite the actual argument, since Lemma 4.1 underpins the stochastic section.
  3. [Appendix B.2, proof of Theorem 3.2, Case 4] The text 'Now if p* < 1/y' appears to be a typo; the subsequent argument concerns p* < Φ^ρ_r(y) = 1/r. Please correct this to 'p* < 1/r'.
  4. [§3.1, Theorems 3.2 and 3.3] The expressions involve ln(rθ), which is undefined at r = θ^{-1} (since rθ = 1). The theorems state no explicit range for r, while the proofs assume rθ > 1. The paper should state that r ranges over (θ^{-1}, θ^{-1/2}] (or discuss the boundary case separately), to avoid division by zero in the exponents.

Circularity Check

0 steps flagged · score 1.0 of 10

No meaningful circularity: the central bounds are proven from explicit adversary constructions and matching case analysis; self-citations are motivational only, and the flagged concerns (power-law scope of Theorem 3.3, deterministic-only proof) are scope or proof gaps, not circular reductions.

full rationale

The paper's derivation chain is self-contained and none of its central claims reduces to its own inputs. Theorem 3.1 proves both inclusions of the Pareto-optimal threshold set P_r using the adversary family I_n(q) (Appendix B.1). Theorem 3.2 derives the smoothness bound case-by-case (Appendix B.2) from Lemma B.1 and Corollary B.2; the exponent s_rho is solved from the inequality max_z Phi^rho_r(z)^{s+1}/z^s <= rtheta, not fitted to any quantity the theorem later 'predicts'. Theorem 3.3 is a genuine adversarial lower bound: assuming the power-law guarantee form (Eq. 5), it evaluates the instance (y = theta, q = 1/((1+epsilon)r)) and obtains u >= ln theta/ln(rtheta) - 2 by taking epsilon -> 0; the matching upper bound of A^1_r is verified over the whole error range and is separately tight at the same adversary point by construction of the threshold. Theorem 3.4 is likewise a two-sided matching bound (Lemmas D.2 and D.3) with explicit adversary instances; no parameter is estimated from data. The only self-citations (Benomar and Perchet 2025) motivate the brittleness question and supply the Appendix D.3 comparison; they never appear in a proof, and the paper independently reproduces the brittleness of Sun et al.'s rho = 0 algorithm through s_rho -> infinity in Theorem 3.2. No uniqueness theorem is imported from the authors' prior work: the Pareto front Eq. (1) is the external result of Sun et al. 2021, and its threshold characterization is proved inside this paper. Two flagged concerns are scope limitations rather than circularity. First, Theorem 3.3 quantifies only over guarantees of the exact form max{r, (1/rtheta)E^u} and its proof evaluates the bound at a single error value, so a strictly smoother non-power-law guarantee at intermediate errors is not excluded; the headline 'triple Pareto-optimal front' (Section 3.1) is broader than the proved statements. Second, Theorem 3.3 is stated for 'any algorithm' while its proof begins 'Let A be a deterministic algorithm'; the paper's headline claims are confined to deterministic algorithms, so this gap does not threaten the central construction. Neither concern exhibits an equation equal to its own input or a fitted parameter renamed as a prediction.

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

No free parameters are fitted to data; all algorithm parameters are explicit design choices. The paper introduces no new physical or mathematical entities beyond the algorithm and its analyses.

assumptions (3)
  • domain assumption The price sequence and prediction are confined to [1, θ] with known θ.
    Used throughout the problem definition and all theorems; required for bounded competitive ratio.
  • domain assumption Any deterministic algorithm is equivalent to a threshold algorithm on the instance family {In(q)}.
    Stated in Appendix B and used to derive necessary conditions for Pareto-optimal thresholds (Theorem 3.1) and lower bounds (Theorem 3.3, Lemma D.3).
  • standard math Optimal transport duality holds for the cost c(p*,y)=p* E(p*,y)^s.
    Invoked in Appendix C.2 to prove Proposition 4.7, following Villani's conditions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search." pith.science (2026). https://pith.science/paper/OIFYQ3YO

@misc{pith2026250205720,
  author       = {Pith},
  title        = {Pith review of: Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OIFYQ3YO}},
  note         = {Machine review of arXiv:2502.05720}
}
read the original abstract

One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. The problem has been studied both in probabilistic and in worst-case settings, notably through competitive analysis, and more recently in learning-augmented settings in which the trader has access to a prediction on the sequence. However, existing approaches either lack smoothness, or do not achieve optimal worst-case guarantees: they do not attain the best possible trade-off between the consistency and the robustness of the algorithm. We close this gap by presenting the first algorithm that simultaneously achieves both of these important objectives. Furthermore, we show how to leverage the obtained smoothness to provide an analysis of one-max search in stochastic learning-augmented settings which capture randomness in both the observed prices and the prediction.

Figures

Figures reproduced from arXiv: 2502.05720 by the authors.

Figure 1
Figure 1. The set Pr of Theorem 3.1 is depicted shaded. A threshold Φ is r-robust and 1/rθ-consistent if and only if its graph lies in this shaded area. 1 rθ 1/r 1 r +ρ(θ − 1 r ) θ Prediction y ∈ [1,θ] rθ ϕr( 1 r) 1/r Threshold Φ ρ r (y) ρ = 0 ρ ∈ (0,1) ρ = 1 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 4
Figure 4. Comparison of A 1 r and A 0 r on the Bitcoin price dataset. Proposition 4.7. The family {A 1 r}r satisfies E[A 1 r (P ∗ , Y )] E[P∗] ≥ 1 rθ Z θ 1 2 1 p ∗1+s dF ∗ (p ∗ )+Z θ θ 1 2 p ∗1−s dF ∗ (p ∗ ) E[P∗] . Moreover, the RHS is the infimum over G of Eq. (14). Proposition 4.7 once more highlights the asymmetry of the problem through different contributions of the regions above and below √ θ, which is the threshold tha… view at source ↗
Figure 5
Figure 5. Numerical quadrature of Proposition C.5 for [PITH_FULL_IMAGE:figures/full_fig_p025_5.png] view at source ↗
Figures from the paper (2 more)
Figure 6
Figure 6. Figure 6: Performance of A ρ r with ρ ∈ {0, 0.5, 1}. One can observe that the bounds of Corollary D.5 represent the supremum version of the transport problem associated with W1 (see below). The supremum is expected due to the additive nature of the analysis, which makes the erro…
Figure 7
Figure 7. Figure 7: Comparison of A 1 r and A 0 r on the Bitcoin price dataset with λ = 0.2. 0.0 0.2 0.4 0.6 0.8 1.0 α ∈ [0,1] r 0.35 0.4 1/rθ Empirical ratio ρ = 0 ρ = 1 [PITH_FULL_IMAGE:figures/full_fig_p032_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 34 canonical work pages

  1. [1]

    Online facility location with multiple advice

    Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. Advances in neural information processing systems, 34: 0 4661--4673, 2021

    work page 2021

  2. [2]

    Online search with a hint

    Spyros Angelopoulos. Online search with a hint. Inf. Comput., 295 0 (Part B ): 0 105091, 2023

    work page 2023

  3. [3]

    Online search with best-price and query-based predictions

    Spyros Angelopoulos, Shahin Kamali, and Dehou Zhang. Online search with best-price and query-based predictions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, pages 9652--9660. AAAI Press, 2022

    work page 2022

  4. [4]

    Contract scheduling with distributional and multiple advice

    Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, and Bertrand Simon. Contract scheduling with distributional and multiple advice. In Kate Larson, editor, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24 , pages 3652--3660. International Joint Conferences on Artificial Intelligence Organization, 8 2...

    work page 2024

  5. [5]

    Secretary and online matching problems with machine learned advice

    Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33: 0 7933--7944, 2020

    work page 2020

  6. [6]

    Online graph algorithms with predictions

    Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 35--66. SIAM, 2022

    work page 2022

  7. [7]

    Sorting with predictions

    Xingjian Bai and Christian Coester. Sorting with predictions. Advances in Neural Information Processing Systems, 36: 0 26563--26584, 2023

    work page 2023

  8. [8]

    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

    work page 2020

Show all 35 references
  1. [9]

    Learning-augmented priority queues

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

    2024 arXiv

  2. [10]

    On tradeoffs in learning-augmented algorithms, January 2025

    Ziyad Benomar and Vianney Perchet. On tradeoffs in learning-augmented algorithms, January 2025. URL https://arxiv.org/abs/2501.12770. arXiv:2501.12770 [cs]

    2025 arXiv

  3. [11]

    Online computation and competitive analysis

    Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. C ambridge university press, 2005

    2005

  4. [12]

    Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems

    Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. In AISTATS , volume 206 of Proceedings of Machine Learning Research, pages 9377--9399. PMLR , 2023

    2023

  5. [13]

    Financial modelling with jump processes

    Rama Cont and Peter Tankov. Financial modelling with jump processes. Chapman & Hall / CRC financial mathematics series. Chapman & Hall/CRC, Boca Raton, Fla, 2004. ISBN 978-1-58488-413-2

    2004

  6. [14]

    Binary Search with Distributional Predictions , November 2024

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Aidin Niaparast, and Sergei Vassilvitskii. Binary Search with Distributional Predictions , November 2024. URL http://arxiv.org/abs/2411.16030. arXiv:2411.16030 [cs]

    2024 arXiv

  7. [15]

    Optimal Execution : A Review

    Ryan Donnelly. Optimal Execution : A Review . Applied Mathematical Finance, 29 0 (3): 0 181--212, May 2022. ISSN 1350-486X, 1466-4313

    2022

  8. [16]

    Secretaries with advice

    Paul D \"u tting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. Mathematics of Operations Research, 49 0 (2): 0 856--879, 2024

    2024

  9. [17]

    Competitive solutions for online financial problems

    Ran El-Yaniv. Competitive solutions for online financial problems. ACM Computing Surveys, 30 0 (1): 0 28--69, March 1998. ISSN 0360-0300

    1998

  10. [18]

    Overcoming brittleness in pareto-optimal learning augmented algorithms

    Alex Elenter, Spyros Angelopoulos, Christoph D \"u rr, and Yanni Lefki. Overcoming brittleness in pareto-optimal learning augmented algorithms. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  11. [19]

    Online algorithms for rent-or-buy with expert advice

    Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, ICML , volume 97 of Proceedings of Machine Learning Research, pages 2319--2327. PMLR , 2019

    2019

  12. [20]

    Online knapsack with frequency predictions

    Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. Advances in Neural Information Processing Systems, 34: 0 2733--2743, 2021

    2021

  13. [21]

    Online scheduling via learned weights

    Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859--1877. SIAM, 2020

    2020

  14. [22]

    Russell Lee, Bo Sun, Mohammad Hajiesmaili, and John C. S. Lui. Online search with predictions: Pareto-optimal algorithm and its applications in energy markets. In The 15th ACM International Conference on Future and Sustainable Energy Systems, e-Energy 2024, Singapore, June 4-7...

    2024

  15. [23]

    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

  16. [24]

    Repository of works on algorithms with predictions

    Alexander Lindermayr and Nicole Megow. Repository of works on algorithms with predictions. https://algorithms-with-predictions.github.io, 2025. Accessed: 2025-01-01

    2025

  17. [25]

    Optimal algorithms for k-search with application in option pricing

    Julian Lorenz, Konstantinos Panagiotou, and Angelika Steger. Optimal algorithms for k-search with application in option pricing. Algorithmica, 55 0 (2): 0 311--328, 2009

    2009

  18. [26]

    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

  19. [27]

    Robert C. Merton. Optimum consumption and portfolio rules in a continuous-time model. In W.T. Ziemba and R.G. Vickson, editors, Stochastic Optimization Models in Finance, pages 621--661. Academic Press, 1975

    1975

  20. [28]

    Online algorithms for conversion problems: a survey

    Esther Mohr, Iftikhar Ahmad, and G \"u nter Schmidt. Online algorithms for conversion problems: a survey. Surveys in Operations Research and Management Science, 19 0 (2): 0 87--104, 2014

    2014

  21. [29]

    Improving online algorithms via ML predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems, volume 31, pages 9661--9670, 2018

    2018

  22. [30]

    Optimal adaptive price search

    Donald B Rosenfield and Roy D Shapiro. Optimal adaptive price search. Journal of Economic Theory, 25 0 (1): 0 1--20, 1981

    1981

  23. [31]

    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 . In Advances in Neural Information Processing Systems , volume 34, pages 10339--10350. Curran Associates, Inc., 2021

    2021

  24. [32]

    Online algorithms with uncertainty-quantified predictions

    Bo Sun, Jerry Huang, Nicolas Christianson, Mohammad Hajiesmaili, Adam Wierman, and Raouf Boutaba. Online algorithms with uncertainty-quantified predictions. In Forty-first International Conference on Machine Learning, ICML , 2024

    2024

  25. [33]

    Optimal Transport , volume 338 of Grundlehren der mathematischen Wissenschaften

    Cédric Villani. Optimal Transport , volume 338 of Grundlehren der mathematischen Wissenschaften . Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. doi:10.1007/978-3-540-71050-9

    2009 doi

  26. [34]

    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. In Proceedings of the 33rd Conference on Neural Information Processing Systems ( NeurIPS ) , 2020

    2020

  27. [35]

    Robust learning-augmented dictionaries

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

    2024

Pith tools

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