Pith. sign in

REVIEW 5 minor 253 references

Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read The OGD+Projection algorithm for constrained online convex optimization must incur cumulative constraint violation Ω(T^{(d-1)/(2d)}).

desk verdict First algorithm-specific CCV lower bound for OGD+Projection; clean packing construction that matches the known O(√T) upper bound for large d. read the letter →

arxiv 2607.10808 v1 pith:C4YBYFDQ submitted 2026-07-12 cs.LG

Haricharan Balasundaram , Karthick Krishna Mahendran , Rahul Vaze This is my paper · ORCID
classification cs.LG
keywords constrainedonlineconvexoptimizationcumulativeconstraintviolationOGD+Projectionlowerboundnestedfeasiblesetssphericalpackingstaticregret
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

In constrained online convex optimization a learner picks a point each round before seeing a convex loss and a convex constraint. The best-known practical method, OGD+Projection, first takes a gradient step on the latest loss then projects onto the latest nested feasible set. Earlier work proved that this method keeps static regret O(√T) while keeping cumulative constraint violation (CCV) at most O(T^{1/3}) in two dimensions and O(√T) in any dimension. The present paper shows that the same algorithm is forced to suffer CCV at least Ω(T^{(d-1)/(2d)}) on a carefully constructed family of nested spherical caps. The construction packs many well-separated directions on concentric spheres, rotates successive layers so that consecutive points stay close, and designs losses that drag the algorithm along that path; each new half-space then produces a fixed-size violation. The lower bound is the first of its kind and demonstrates that the existing upper-bound analyses are essentially tight for this algorithm.

What carries the argument

An ordered packing of unit vectors on the sphere S^{d-1} whose angular separation is at least ρ yet consecutive angles are at most A_d ρ, with cardinality Ω(ρ^{-(d-1)}). Scaled and rotated copies of this packing on concentric spheres of slowly shrinking radii produce nested half-space constraints that force a positive projection distance at each of Ω(T^{(d+1)/(2d)}) phase heads.

What would settle it

Exhibit either a packing whose consecutive angular gaps force the inter-point distance to exceed the available OGD budget for every packing constant, or an explicit input sequence on which OGD+Projection's realized CCV is o(T^{(d-1)/(2d)}).

Watch

Extended reading notes

Core claim

There exists an instance of constrained online convex optimization of diameter 2D and Lipschitz constant G such that the OGD+Projection algorithm incurs cumulative constraint violation Ω(T^{(d-1)/(2d)}). The same instance keeps the usual O(√T) regret bound, so the algorithm cannot simultaneously achieve sub-√T CCV for every dimension.

Load-bearing premise

The packing density can be made small enough that the total step-size budget inside each phase is still large enough to travel the short distance between successive points without exceeding the Lipschitz bound.

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

0 major / 5 minor

Summary. The paper proves the first lower bound on cumulative constraint violation (CCV) for the OGD+Projection algorithm of Vaze and Sinha (2025) in constrained online convex optimization (COCO). After the learner plays x_t, convex losses f_t and constraints g_t are revealed; the goal is simultaneous static regret and CCV control relative to a fixed feasible benchmark. The authors construct an explicit adversarial instance on nested concentric spheres of radii r_m = 1 - (m-1)/(2M) with M = T^{1/d}. Using an inductive packing of unit vectors (Theorem 2) that are ρ-separated with local angular steps O(ρ) and cardinality Ω(ρ^{-(d-1)}), they place half-space constraints tangent to successive spheres and linear losses that force the algorithm along a trajectory of P = Θ(T^{(d+1)/(2d)}) phase heads. Each phase head incurs a projection distance Ω(T^{-1/d}), yielding CCV = Ω(T^{(d-1)/(2d)}) while the diameter and Lipschitz constants remain O(1). The packing constants A_d = 2^{d-1} and c_d = π^{d-1}/2^{d^{2}} are fully explicit.

Significance. The result is the first nontrivial lower bound for any algorithm in the COCO literature that matches the geometry-aware OGD+Projection method currently holding the best simultaneous regret/CCV upper bounds (O(√T) regret and O(T^{1/3}) CCV for d=2, O(√T) CCV for general d). It shows that the existing upper-bound analyses are not fundamentally loose and that dimension dependence is unavoidable for this algorithm. The construction is fully constructive, with machine-checkable inductive packing constants and an explicit forced trajectory; no free parameters are recovered after the fact. This supplies a concrete benchmark for future algorithms that might improve the CCV exponent.

minor comments (5)
  1. In the abstract and introduction the upper-bound citations (Balasundaram et al. 2026, Sarkar and Sinha 2026) appear as arXiv preprints; once they are published the bibliographic entries should be updated for archival permanence.
  2. Figure 2 caption states M=2 and D/(2M)=D/4, which is correct, but the figure itself is dense; a short sentence in the caption clarifying that only the first-layer half-space H_1^{(1)} is drawn would improve readability.
  3. Equation (51) uses the lower bound ∑ η_t ≥ 2(Δ-1)D/√T; a parenthetical remark that the same asymptotic holds for the exact harmonic sum would remove any residual doubt about the Ω notation.
  4. The constant B_d introduced after (50) is never given an explicit expression; stating B_d = A_d + 1 (or any convenient upper bound) would make the dependence on the packing constant fully transparent.
  5. Typographical: after (12) the symbol “˜ c_d” is written both with and without the tilde; consistent notation would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: explicit adversarial construction yields the CCV lower bound without definitional reduction or load-bearing self-citation of the target claim.

full rationale

The paper proves Theorem 1 by constructing an explicit COCO instance (nested concentric spheres, angularly packed unit vectors from the self-contained inductive packing of Theorem 2, tangent half-spaces, and linear losses that force the OGD+Projection trajectory along the ordered points Z). Every quantitative step (projection distance D/(2M) at each of the P = Θ(T^{(d+1)/(2d)}) phase heads, existence of γ_t ∈ [0,G] covering ℓ_p after shrinking the free packing constant c̃_d, and the final summation giving Ω(T^{(d-1)/(2d)})) is derived from the geometry and the algorithm definition written out in (3). Self-citations supply only the algorithm name and prior upper bounds; they are not used to justify any step of the lower-bound argument. No quantity is defined in terms of the claimed exponent, no parameter is fitted to data and then re-predicted, and the packing constants A_d, c_d are obtained by a direct induction that does not presuppose the CCV bound. The derivation is therefore self-contained and free of circularity.

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

The claim rests on standard convex-analysis facts (projection onto nested convex sets, Lipschitz linear losses, OGD step-size schedule) plus the classical feasibility assumption of COCO and an explicit geometric packing whose constants are derived, not fitted. No physical constants or data-driven free parameters appear. The only tunable quantities are the packing constants A_d, c_d and the sufficiently-small c̃_d needed to keep the forced steps inside the Lipschitz budget; they are chosen once for all T and do not depend on data.

free parameters (2)
  • c̃_d (packing truncation constant)
    Chosen small enough so that the required step lengths ℓ_p remain inside the reachable interval [0,o_T] generated by γ_t≤G; asymptotic only, not fitted to data.
  • A_d, c_d (packing constants)
    Explicitly constructed by induction (A_d=2^{d-1}, c_d=π^{d-1}/2^{d^2}); not free in the fitting sense but are paper-specific constants that control the final Ω notation.
assumptions (4)
  • domain assumption Feasibility assumption: the intersection X* of all constraint sets is nonempty.
    Standard COCO hypothesis stated in the introduction; used to guarantee a well-defined static benchmark.
  • domain assumption Losses and constraints are convex and G-Lipschitz; action set has diameter 2D.
    Classical OCO regularity; used for step-size η_t=2D/(G√t) and for the definition g_t=G·dist(·,S_t).
  • standard math Projection onto a closed convex set is non-expansive and unique; halfspace projection has closed form.
    Used throughout the trajectory argument (Propositions 4–8).
  • ad hoc to paper On the unit sphere there exist ordered ρ-separated packings with local angular steps O(ρ) and cardinality Ω(ρ^{-(d-1)}).
    Proved as Theorem 2 by induction; the existence statement is load-bearing for the phase count P.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)." pith.science (2026). https://pith.science/paper/C4YBYFDQ

@misc{pith2026260710808,
  author       = {Pith},
  title        = {Pith review of: Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C4YBYFDQ}},
  note         = {Machine review of arXiv:2607.10808}
}
abstract

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action $x_t \in \mathcal{X} \subset \mathbb{R}^d$, a convex loss function $f_t$ and a convex constraint function $g_t$ that drives the constraint $g_t(x)\le 0$ are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions $f_t$ and $g_t$ for all $t$ ahead of time, and chooses a static optimal action that is feasible with respect to all $g_t(x)\le 0$. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of $O(\sqrt{T})$ and CCV of $O(T^{1/3})$ for $d=2$ [Balasundaram et al., 2026], and simultaneous regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T})$ for any $d$ [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is $\Omega (T^{\frac{d-1}{2d}})$. This is the first such lower bound result.

Figures

Figures reproduced from arXiv: 2607.10808 by the authors.

Figure 1
Figure 1. The tangent hyperplane H (m) i to Cm+1 at y cuts from Cm a spherical cap centered at x. The points s− and s+ are the two intersection points in the displayed cross-section, and the half-angle of the cap is ϑm. Our lower bound instance is such that the corresponding constraint set shown for this vector is a hyperplane which is tangent to Cm+1 at y and contains the origin. The value of ρ is selected so that this const… view at source ↗
Figure 2
Figure 2. Nested construction in d = 2 with M = 2, showing the cap removal and projection associated with z (1) 1 . Note the rotation of the vectors in the second layer to ensure that z (1) 6 and z (2) 1 are directly below each other. Constraint sets. We next define the constraint sets. Recall that the constraint sets are given by Gt = {x ∈ X : gt(x) ≤ 0} and St = Gt ∩ St−1 for 1 ≤ t ≤ T, where we take S0 = X . Note that the … view at source ↗
Figure 3
Figure 3. Actions played during the first phase from [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Base construction on S 1 with six equally spaced directions for d = 2. Note that N2(ρ) is even, by construction. The construction is depicted in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Induction from k = 2 to k = 3. The embedded equatorial vectors Λ3(v1),Λ3(v2),Λ3(v3) determine longitudes M1,M2,M3, which are populated by points uℓ,1, uℓ,2, uℓ,3 with polar angles π/4 ≤ αℓ ≤ 3π/4. Formal construction for general k. For k ≥ 3, set η = 2ρ. Since ρ ≤ π/4,…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

253 extracted references · 13 linked inside Pith

  1. [1]

    1966 , publisher=

    Convexity , author=. 1966 , publisher=

    1966

  2. [2]

    Breaking the O(

    Haricharan Balasundaram and Karthick Krishna Mahendran and Rahul Vaze , year=. Breaking the O(. 2603.20671 , archivePrefix=

    arXiv

  3. [3]

    2026 , eprint=

    Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction , author=. 2026 , eprint=

    2026

  4. [4]

    2016 , eprint=

    A Simple Proof of Cauchy's Surface Area Formula , author=. 2016 , eprint=

    2016

  5. [5]

    The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

    Optimal Algorithms for Online Convex Optimization with Adversarial Constraints , author=. The Thirty-eighth Annual Conference on Neural Information Processing Systems , year=

  6. [6]

    Rahul Vaze and Abhishek Sinha , year=. O(. 2502.05019 , archivePrefix=

    arXiv

  7. [7]

    2025 , publisher =

    Vershynin, Roman , title =. 2025 , publisher =

    2025

  8. [8]

    Geometriae Dedicata , volume=

    Maximum length of steepest descent curves for quasi-convex functions , author=. Geometriae Dedicata , volume=. 1991 , publisher=

    1991

Show all 253 references
  1. [9]

    CoRR , volume =

    Elad Hazan , title =. CoRR , volume =. 2019 , url =. 1909.05207 , timestamp =

    2019 arXiv

  2. [10]

    Proceedings of Thirty Fifth Conference on Learning Theory , pages =

    Realizable Learning is All You Need , author =. Proceedings of Thirty Fifth Conference on Learning Theory , pages =. 2022 , volume =

    2022

  3. [11]

    GitHub repository , howpublished =

    Abhishek Sinha , title =. GitHub repository , howpublished =. 2024 , publisher =

    2024

  4. [12]

    Proceedings of the National Academy of Sciences , volume=

    Reconciling modern machine-learning practice and the classical bias--variance trade-off , author=. Proceedings of the National Academy of Sciences , volume=. 2019 , publisher=

    2019

  5. [13]

    Expert systems with applications , volume=

    Learned lessons in credit card fraud detection from a practitioner perspective , author=. Expert systems with applications , volume=. 2014 , note =

    2014

  6. [14]

    A low complexity algorithm with O(

    Yu, Hao and Neely, Michael J , journal=. A low complexity algorithm with O(

  7. [15]

    On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization , year=

    Vaze, Rahul , booktitle=. On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization , year=

  8. [16]

    IEEE Transactions on automatic control , volume=

    Online convex optimization with time-varying constraints and bandit feedback , author=. IEEE Transactions on automatic control , volume=. 2018 , publisher=

    2018

  9. [17]

    IEEE Internet of Things Journal , volume=

    Bandit convex optimization for scalable and dynamic IoT management , author=. IEEE Internet of Things Journal , volume=. 2018 , publisher=

    2018

  10. [18]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Nested convex bodies are chaseable , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  11. [19]

    Proceedings of the Symposium on the Mathematical Theory of Automata , volume=

    On convergence proofs on perceptrons , author=. Proceedings of the Symposium on the Mathematical Theory of Automata , volume=. 1962 , organization=

    1962

  12. [20]

    Journal of optimization theory and applications , volume=

    Subgradient methods for saddle-point problems , author=. Journal of optimization theory and applications , volume=. 2009 , publisher=

    2009

  13. [21]

    IEEE Transactions on Automatic Control , year=

    Regret and cumulative constraint violation analysis for distributed online constrained convex optimization , author=. IEEE Transactions on Automatic Control , year=

  14. [22]

    Nature , volume=

    Dense reinforcement learning for safety validation of autonomous vehicles , author=. Nature , volume=. 2023 , publisher=

    2023

  15. [23]

    Optimization for machine learning , pages=

    The convex optimization approach to regret minimization , author=. Optimization for machine learning , pages=. 2012 , publisher=

    2012

  16. [24]

    1967 , publisher=

    Convex polytopes , author=. 1967 , publisher=

    1967

  17. [25]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    A nearly-linear bound for chasing nested convex bodies , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  18. [26]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Chasing nested convex bodies nearly optimally , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  19. [27]

    IEEE INFOCOM 2019-IEEE Conference on Computer Communications , pages=

    Learning to Cache With No Regrets , author=. IEEE INFOCOM 2019-IEEE Conference on Computer Communications , pages=. 2019 , organization=

    2019

  20. [28]

    2012 , publisher=

    The Borel-Cantelli Lemma , author=. 2012 , publisher=

    2012

  21. [29]

    Kingma and Jimmy Ba , editor =

    Diederik P. Kingma and Jimmy Ba , editor =. Adam:. 3rd International Conference on Learning Representations,. 2015 , url =

    2015

  22. [30]

    2008 , publisher=

    Control techniques for complex networks , author=. 2008 , publisher=

    2008

  23. [31]

    , author=

    Adaptive subgradient methods for online learning and stochastic optimization. , author=. Journal of machine learning research , volume=

  24. [32]

    International Conference on Machine Learning , pages=

    Regret and cumulative constraint violation analysis for online convex optimization with long term constraints , author=. International Conference on Machine Learning , pages=. 2021 , organization=

    2021

  25. [33]

    arXiv preprint arXiv:1706.05098 , year=

    An overview of multi-task learning in deep neural networks , author=. arXiv preprint arXiv:1706.05098 , year=

    arXiv

  26. [34]

    2015 , publisher=

    Random processes for engineers , author=. 2015 , publisher=

    2015

  27. [35]

    Advances in Neural Information Processing Systems , volume=

    Online convex optimization with hard constraints: Towards the best of two worlds and beyond , author=. Advances in Neural Information Processing Systems , volume=

  28. [36]

    Advances in Neural Information Processing Systems , volume=

    Adaptive smoothed online multi-task learning , author=. Advances in Neural Information Processing Systems , volume=

  29. [37]

    International Conference on Computational Learning Theory , pages=

    Online multitask learning , author=. International Conference on Computational Learning Theory , pages=. 2006 , organization=

    2006

  30. [38]

    Rockafellar, R. Tyrrel. Convex Analysis

  31. [39]

    Electronic colloquium on computational complexity (ECCC) , volume=

    Adaptive algorithms for online decision problems , author=. Electronic colloquium on computational complexity (ECCC) , volume=

  32. [40]

    Artificial Intelligence and Statistics , pages=

    Improved strongly adaptive online learning using coin betting , author=. Artificial Intelligence and Statistics , pages=. 2017 , organization=

    2017

  33. [41]

    Theoretical Computer Science , volume=

    Scale-free online learning , author=. Theoretical Computer Science , volume=. 2018 , publisher=

    2018

  34. [42]

    International Conference on Machine Learning , pages=

    A simple yet universal strategy for online convex optimization , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    2022

  35. [43]

    Machine learning , volume=

    Regret bounded by gradual variation for online convex optimization , author=. Machine learning , volume=. 2014 , publisher=

    2014

  36. [44]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  37. [45]

    International Conference on Machine Learning , pages=

    Adaptive regret of convex and smooth functions , author=. International Conference on Machine Learning , pages=. 2019 , organization=

    2019

  38. [46]

    International Conference on Machine Learning , pages=

    Cautious regret minimization: Online optimization with long-term budget constraints , author=. International Conference on Machine Learning , pages=. 2019 , organization=

    2019

  39. [47]

    Proceedings of the 36th International Conference on Machine Learning , pages =

    Cautious Regret Minimization: Online Optimization with Long-Term Budget Constraints , author =. Proceedings of the 36th International Conference on Machine Learning , pages =. 2019 , editor =

    2019

  40. [48]

    2003 , publisher=

    Applied probability and queues , author=. 2003 , publisher=

    2003

  41. [49]

    The Journal of Machine Learning Research , volume=

    Trading regret for efficiency: online convex optimization with long term constraints , author=. The Journal of Machine Learning Research , volume=. 2012 , publisher=

    2012

  42. [50]

    International Conference on Machine Learning , pages=

    Safety-aware algorithms for adversarial contextual bandit , author=. International Conference on Machine Learning , pages=. 2017 , organization=

    2017

  43. [51]

    Proceedings of the 34th International Conference on Machine Learning , pages =

    Safety-Aware Algorithms for Adversarial Contextual Bandit , author =. Proceedings of the 34th International Conference on Machine Learning , pages =. 2017 , editor =

    2017

  44. [52]

    ACM SIGMETRICS Performance Evaluation Review , volume=

    Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints , author=. ACM SIGMETRICS Performance Evaluation Review , volume=. 2022 , publisher=

    2022

  45. [53]

    arXiv preprint arXiv:2306.00149 , year=

    Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition , author=. arXiv preprint arXiv:2306.00149 , year=

    arXiv

  46. [54]

    A Low Complexity Algorithm with O (

    Yu, Hao and Neely, Michael J , journal=. A Low Complexity Algorithm with O (

  47. [55]

    29th IEEE Conference on Decision and Control , pages=

    Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks , author=. 29th IEEE Conference on Decision and Control , pages=. 1990 , organization=

    1990

  48. [56]

    IEEE Transactions on Communications , volume=

    Achieving 100\ author=. IEEE Transactions on Communications , volume=. 1999 , publisher=

    1999

  49. [57]

    1992 , publisher=

    Integral inequalities and applications , author=. 1992 , publisher=

    1992

  50. [58]

    arXiv preprint arXiv:1702.04783 , year=

    Online convex optimization with time-varying constraints , author=. arXiv preprint arXiv:1702.04783 , year=

    arXiv

  51. [59]

    , author=

    Online Learning with Sample Path Constraints. , author=. Journal of Machine Learning Research , volume=

  52. [60]

    Advances in Neural Information Processing Systems , volume=

    Online convex optimization with stochastic constraints , author=. Advances in Neural Information Processing Systems , volume=

  53. [61]

    International Conference on Machine Learning , pages=

    Adaptive algorithms for online convex optimization with long-term constraints , author=. International Conference on Machine Learning , pages=. 2016 , organization=

    2016

  54. [62]

    Advances in Neural Information Processing Systems , volume=

    Online convex optimization for cumulative constraints , author=. Advances in Neural Information Processing Systems , volume=

  55. [63]

    2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt) , pages=

    On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization , author=. 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt) , pages=. 2022 , organization=

    2022

  56. [64]

    Advances in neural information processing systems , volume=

    Adaptive online gradient descent , author=. Advances in neural information processing systems , volume=

  57. [65]

    Advances in Neural Information Processing Systems , volume=

    Queue Up Your Regrets: Achieving the Dynamic Capacity Region of Multiplayer Bandits , author=. Advances in Neural Information Processing Systems , volume=

  58. [66]

    Sinha, Abhishek , booktitle=. Bandit. 2024 , organization=

    2024

  59. [67]

    Mathematical Proceedings of the Cambridge Philosophical Society , volume=

    The theory of queues with a single server , author=. Mathematical Proceedings of the Cambridge Philosophical Society , volume=. 1952 , organization=

    1952

  60. [68]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Achieving Counterfactual Fairness for Causal Bandit , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  61. [69]

    Advances in Neural Information Processing Systems , volume=

    Fair algorithms for multi-agent multi-armed bandits , author=. Advances in Neural Information Processing Systems , volume=

  62. [70]

    Advances in neural information processing systems , volume=

    Metric-free individual fairness in online learning , author=. Advances in neural information processing systems , volume=

  63. [71]

    Advances in neural information processing systems , volume=

    Online learning with an unknown fairness metric , author=. Advances in neural information processing systems , volume=

  64. [72]

    1953 , publisher=

    Stochastic processes , author=. 1953 , publisher=

    1953

  65. [73]

    A sharp inequality for sub-martingales and stopping-times , author=. Ast

  66. [74]

    Foundations and Trends

    Regret analysis of stochastic and nonstochastic multi-armed bandit problems , author=. Foundations and Trends. 2012 , publisher=

    2012

  67. [75]

    Abhishek Sinha and Rahul Vaze , year=. Beyond. 2505.06709 , archivePrefix=

  68. [76]

    , booktitle=

    Hsu, Wei-Kang and Xu, Jiaming and Lin, Xiaojun and Bell, Mark R. , booktitle=. Integrating Online Learning and Adaptive Control in Queueing Systems with Uncertain Payoffs , year=

  69. [77]

    Communications of the ACM , volume=

    Discrimination in online ad delivery , author=. Communications of the ACM , volume=. 2013 , publisher=

    2013

  70. [78]

    Proceedings of the conference on fairness, accountability, and transparency , pages=

    Controlling polarization in personalization: An algorithmic framework , author=. Proceedings of the conference on fairness, accountability, and transparency , pages=

  71. [79]

    IEEE INFOCOM 2018-IEEE Conference on Computer Communications , pages=

    An online learning approach to network application optimization with guarantee , author=. IEEE INFOCOM 2018-IEEE Conference on Computer Communications , pages=. 2018 , organization=

    2018

  72. [80]

    IEEE Transactions on Network Science and Engineering , volume=

    Combinatorial sleeping bandits with fairness constraints , author=. IEEE Transactions on Network Science and Engineering , volume=. 2019 , publisher=

    2019

  73. [81]

    Proceedings of the 2020 ACM/IEEE International Conference on Human-Robot Interaction , pages=

    Multi-armed bandits with fairness constraints for distributing resources to human teammates , author=. Proceedings of the 2020 ACM/IEEE International Conference on Human-Robot Interaction , pages=

    2020

  74. [82]

    2004 , publisher=

    Convex optimization , author=. 2004 , publisher=

    2004

  75. [83]

    CVX: Matlab software for disciplined convex programming , author=

  76. [84]

    Proceedings of the 24th International Conference on Artificial Intelligence , pages =

    Xia, Yingce and Li, Haifang and Qin, Tao and Yu, Nenghai and Liu, Tie-Yan , title =. Proceedings of the 24th International Conference on Artificial Intelligence , pages =. 2015 , isbn =

    2015

  77. [85]

    Advances in Neural Information Processing Systems , volume=

    Spectral filtering for general linear dynamical systems , author=. Advances in Neural Information Processing Systems , volume=

  78. [86]

    Advances in Neural Information Processing Systems , volume=

    Learning linear dynamical systems via spectral filtering , author=. Advances in Neural Information Processing Systems , volume=

  79. [87]

    2020 , publisher=

    Bandit algorithms , author=. 2020 , publisher=

    2020

  80. [88]

    1995 , publisher=

    Stochastic processes , author=. 1995 , publisher=

    1995

  81. [89]

    arXiv preprint arXiv:1309.1541 , year=

    Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application , author=. arXiv preprint arXiv:1309.1541 , year=

    arXiv

  82. [90]

    Journal of Machine Learning Research , volume=

    Adaptation to the Range in K--Armed Bandits , author=. Journal of Machine Learning Research , volume=

  83. [91]

    International Conference on Algorithmic Learning Theory , pages=

    Scale-free adversarial multi armed bandits , author=. International Conference on Algorithmic Learning Theory , pages=. 2022 , organization=

    2022

  84. [92]

    The Journal of Machine Learning Research , volume=

    Achieving fairness in the stochastic multi-armed bandit problem , author=. The Journal of Machine Learning Research , volume=. 2021 , publisher=

    2021

  85. [93]

    Conference on Learning Theory , pages=

    Second-order quantile methods for experts and combinatorial games , author=. Conference on Learning Theory , pages=. 2015 , organization=

    2015

  86. [94]

    Journal of the ACM (JACM) , volume=

    Bandits with knapsacks , author=. Journal of the ACM (JACM) , volume=. 2018 , publisher=

    2018

  87. [95]

    Journal of the ACM , volume=

    Adversarial bandits with knapsacks , author=. Journal of the ACM , volume=. 2022 , publisher=

    2022

  88. [96]

    Operations research , volume=

    On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation , author=. Operations research , volume=. 2005 , publisher=

    2005

  89. [97]

    Journal of the ACM (JACM) , volume=

    Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data , author=. Journal of the ACM (JACM) , volume=. 2005 , publisher=

    2005

  90. [98]

    Synthesis Lectures on Communication Networks , volume=

    Stochastic network optimization with application to communication and queueing systems , author=. Synthesis Lectures on Communication Networks , volume=. 2010 , publisher=

    2010

  91. [99]

    arXiv preprint arXiv:2303.01745 , year=

    Queue Scheduling with Adversarial Bandit Learning , author=. arXiv preprint arXiv:2303.01745 , year=

    arXiv

  92. [100]

    Bandit Learning for Proportionally Fair Allocations , author=

  93. [101]

    Talebi, Mohammad Sadegh and Proutiere, Alexandre , title =. Proc. ACM Meas. Anal. Comput. Syst. , month =. 2018 , issue_date =. doi:10.1145/3224431 , abstract =

    2018 doi

  94. [102]

    Conference on Uncertainty in Artificial Intelligence , pages=

    Fair contextual multi-armed bandits: Theory and experiments , author=. Conference on Uncertainty in Artificial Intelligence , pages=. 2020 , organization=

    2020

  95. [103]

    arXiv preprint arXiv:2303.06396 , year=

    No-regret Algorithms for Fair Resource Allocation , author=. arXiv preprint arXiv:2303.06396 , year=

    arXiv

  96. [104]

    IEEE INFOCOM 2019-IEEE Conference on Computer Communications , pages=

    Satisfying network slicing constraints via 5G MAC scheduling , author=. IEEE INFOCOM 2019-IEEE Conference on Computer Communications , pages=. 2019 , organization=

    2019

  97. [105]

    Advances in neural information processing systems , volume=

    Fairness in learning: Classic and contextual bandits , author=. Advances in neural information processing systems , volume=

  98. [106]

    2010 , publisher=

    An axiomatic theory of fairness in network resource allocation , author=. 2010 , publisher=

    2010

  99. [107]

    IEEE/ACM Transactions on networking , volume=

    A unified framework for max-min and min-max fairness with applications , author=. IEEE/ACM Transactions on networking , volume=. 2007 , publisher=

    2007

  100. [108]

    European transactions on Telecommunications , volume=

    Charging and rate control for elastic traffic , author=. European transactions on Telecommunications , volume=. 1997 , publisher=

    1997

  101. [109]

    Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA , volume=

    A quantitative measure of fairness and discrimination , author=. Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA , volume=

  102. [110]

    Proceedings of the 3rd Innovations in Theoretical Computer Science Conference , pages =

    Dwork, Cynthia and Hardt, Moritz and Pitassi, Toniann and Reingold, Omer and Zemel, Richard , title =. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference , pages =. 2012 , isbn =. doi:10.1145/2090236.2090255 , abstract =

    2012 doi

  103. [111]

    Altman and K

    E. Altman and K. Avrachenkov and A. Garnaev , keywords =. Fair resource allocation in wireless networks in the presence of a jammer , journal =. 2010 , note =. doi:https://doi.org/10.1016/j.peva.2009.08.002 , url =

    2010 doi

  104. [112]

    and Burch, C

    Blum, A. and Burch, C. and Kalai, A. , booktitle=. Finely-competitive paging , year=

  105. [113]

    Proceedings of the tenth annual conference on Computational learning theory , pages=

    On-line learning and the metrical task system problem , author=. Proceedings of the tenth annual conference on Computational learning theory , pages=

  106. [114]

    International Conference on Machine Learning , pages=

    Online learning with imperfect hints , author=. International Conference on Machine Learning , pages=. 2020 , organization=

    2020

  107. [115]

    Proceedings of the 24th Annual Conference on Learning Theory , pages=

    Online learning: Beyond regret , author=. Proceedings of the 24th Annual Conference on Learning Theory , pages=. 2011 , organization=

    2011

  108. [116]

    IEEE Communications Surveys & Tutorials , volume=

    Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial , author=. IEEE Communications Surveys & Tutorials , volume=. 2008 , publisher=

    2008

  109. [117]

    MIT Technology Review , year=

    Facebook’s ad-serving algorithm discriminates by gender and race , author=. MIT Technology Review , year=

  110. [118]

    , author=

    Online Learning for Global Cost Functions. , author=. COLT , year=

  111. [119]

    , title =

    Patil, Vishakha and Ghalme, Ganesh and Nair, Vineet and Narahari, Y. , title =. J. Mach. Learn. Res. , month =. 2021 , issue_date =

    2021

  112. [120]

    IEEE/ACM Transactions on networking , volume=

    Fair end-to-end window-based congestion control , author=. IEEE/ACM Transactions on networking , volume=. 2000 , publisher=

    2000

  113. [121]

    IEEE/ACM Transactions on Networking , volume=

    Birkhoff’s decomposition revisited: Sparse scheduling for high-speed circuit switches , author=. IEEE/ACM Transactions on Networking , volume=. 2021 , publisher=

    2021

  114. [122]

    Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=

    Enabling Long-term Fairness in Dynamic Resource Allocation , author=. Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=. 2022 , publisher=

    2022

  115. [123]

    Management Science , volume=

    On the efficiency-fairness trade-off , author=. Management Science , volume=. 2012 , publisher=

    2012

  116. [124]

    Wang, Zhiyuan and Ye, Jiancheng and Lin, Dong and Lui, John C. S. , title =. Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing , pages =. 2022 , isbn =. doi:10.1145/3492866.3...

    2022 doi

  117. [125]

    2012 , publisher=

    Lectures on polytopes , author=. 2012 , publisher=

    2012

  118. [126]

    Proceedings of the 23rd international conference on world wide web , pages=

    Online dating recommendations: matching markets and learning preferences , author=. Proceedings of the 23rd international conference on world wide web , pages=

  119. [127]

    2013 , publisher=

    Concentration inequalities: A nonasymptotic theory of independence , author=. 2013 , publisher=

    2013

  120. [128]

    Advances in Neural Information Processing Systems , volume=

    Dynamic regret of convex and smooth functions , author=. Advances in Neural Information Processing Systems , volume=

  121. [129]

    Conference on Learning Theory , pages=

    Online optimization with gradual variations , author=. Conference on Learning Theory , pages=. 2012 , organization=

    2012

  122. [130]

    Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies

    Optimal utility based multi-user throughput allocation subject to throughput constraints , author=. Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. , volume=. 2005 , organization=

    2005

  123. [131]

    Journal of the ACM (JACM) , volume=

    Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time , author=. Journal of the ACM (JACM) , volume=. 2004 , publisher=

    2004

  124. [132]

    Proceedings of the 20th international conference on machine learning (icml-03) , pages=

    Online convex programming and generalized infinitesimal gradient ascent , author=. Proceedings of the 20th international conference on machine learning (icml-03) , pages=

  125. [133]

    2006 , publisher=

    Prediction, learning, and games , author=. 2006 , publisher=

    2006

  126. [134]

    Advances in Neural Information Processing Systems , volume=

    Online learning for adversaries with memory: price of past mistakes , author=. Advances in Neural Information Processing Systems , volume=

  127. [135]

    International Conference on Artificial Intelligence and Statistics , pages=

    k-experts-Online Policies and Fundamental Limits , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2022 , organization=

    2022

  128. [136]

    Advances in Neural Information Processing Systems , volume=

    LeadCache: Regret-Optimal Caching in Networks , author=. Advances in Neural Information Processing Systems , volume=

  129. [137]

    Advances in Neural Information Processing Systems , volume=

    Improved algorithms for online submodular maximization via first-order regret bounds , author=. Advances in Neural Information Processing Systems , volume=

  130. [138]

    arXiv preprint arXiv:1407.1082 , year=

    Online submodular maximization under a matroid constraint with application to learning assignments , author=. arXiv preprint arXiv:1407.1082 , year=

    arXiv

  131. [139]

    Proceedings of the 25th international conference on Machine learning , pages=

    Learning diverse rankings with multi-armed bandits , author=. Proceedings of the 25th international conference on Machine learning , pages=

  132. [140]

    Mathematical programming , volume=

    An analysis of approximations for maximizing submodular set functions—I , author=. Mathematical programming , volume=. 1978 , publisher=

    1978

  133. [141]

    2017 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) , pages=

    Alpha fair coded caching , author=. 2017 15th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) , pages=. 2017 , organization=

    2017

  134. [142]

    Online Caching with Optimal Switching Regret , year=

    Mukhopadhyay, Samrat and Sinha, Abhishek , booktitle=. Online Caching with Optimal Switching Regret , year=

  135. [143]

    Conference on Learning Theory , pages=

    Faster projection-free online learning , author=. Conference on Learning Theory , pages=. 2020 , organization=

    2020

  136. [144]

    SIAM Journal on Computing , volume=

    Optimal prediction for prefetching in the worst case , author=. SIAM Journal on Computing , volume=. 1998 , publisher=

    1998

  137. [145]

    The Annals of Mathematical Statistics , volume=

    On the theory of systematic sampling, II , author=. The Annals of Mathematical Statistics , volume=. 1949 , publisher=

    1949

  138. [146]

    Journal of the ACM (JACM) , volume=

    Optimal prefetching via data compression , author=. Journal of the ACM (JACM) , volume=. 1996 , publisher=

    1996

  139. [147]

    Mathematics of Operations Research , volume=

    Efficient online linear optimization with approximation algorithms , author=. Mathematics of Operations Research , volume=. 2021 , publisher=

    2021

  140. [148]

    arXiv preprint arXiv:1804.07837 , year=

    Online improper learning with an approximation oracle , author=. arXiv preprint arXiv:1804.07837 , year=

    arXiv

  141. [149]

    SIAM Journal on Computing , volume=

    Playing games with approximation algorithms , author=. SIAM Journal on Computing , volume=. 2009 , publisher=

    2009

  142. [150]

    International Conference on Algorithmic Learning Theory , pages=

    Combinatorial online prediction via metarounding , author=. International Conference on Algorithmic Learning Theory , pages=. 2013 , organization=

    2013

  143. [151]

    Journal of Computer and System Sciences , volume=

    Efficient algorithms for online decision problems , author=. Journal of Computer and System Sciences , volume=. 2005 , publisher=

    2005

  144. [152]

    , author=

    Hedging Structured Concepts. , author=. COLT , pages=. 2010 , organization=

    2010

  145. [153]

    Journal of Algorithms , volume=

    Competitive paging algorithms , author=. Journal of Algorithms , volume=. 1991 , publisher=

    1991

  146. [154]

    ACM SIGMETRICS Performance Evaluation Review , volume=

    Spatial multi-LRU caching for wireless networks with coverage overlaps , author=. ACM SIGMETRICS Performance Evaluation Review , volume=. 2016 , publisher=

    2016

  147. [155]

    and Sun, Jennifer , title =

    Nygren, Erik and Sitaraman, Ramesh K. and Sun, Jennifer , title =. SIGOPS Oper. Syst. Rev. , month = aug, pages =. 2010 , issue_date =. doi:10.1145/1842733.1842736 , abstract =

    2010 doi

  148. [156]

    Journal of the ACM (JACM) , volume=

    Principles of optimal page replacement , author=. Journal of the ACM (JACM) , volume=. 1971 , publisher=

    1971

  149. [157]

    2018 , journal =

    Berger, Daniel S , title =. 2018 , journal =

    2018

  150. [158]

    2019 , publisher=

    Probability: theory and examples , author=. 2019 , publisher=

    2019

  151. [159]

    , author=

    Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm. , author=. COLT , pages=. 2010 , organization=

    2010

  152. [160]

    IEEE Transactions on Information Theory , volume=

    Random-walk perturbations for online combinatorial optimization , author=. IEEE Transactions on Information Theory , volume=. 2015 , publisher=

    2015

  153. [161]

    Information and computation , volume=

    The weighted majority algorithm , author=. Information and computation , volume=. 1994 , publisher=

    1994

  154. [162]

    Journal of computer and system sciences , volume=

    A decision-theoretic generalization of on-line learning and an application to boosting , author=. Journal of computer and system sciences , volume=. 1997 , publisher=

    1997

  155. [163]

    Contributions to the Theory of Games , volume=

    Approximation to Bayes risk in repeated play , author=. Contributions to the Theory of Games , volume=

  156. [164]

    Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=

    Practical bounds on optimal caching with variable object sizes , author=. Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=. 2018 , publisher=

    2018

  157. [165]

    arXiv preprint arXiv:2208.06414 , year=

    Optimistic No-regret Algorithms for Discrete Caching , author=. arXiv preprint arXiv:2208.06414 , year=

    arXiv

  158. [166]

    2020 , volume =

    Foundations and Trends® in Communications and Information Theory , title =. 2020 , volume =. doi:10.1561/0100000104 , issn =

    2020 doi

  159. [167]

    Conference on Learning Theory , pages=

    Online linear optimization via smoothing , author=. Conference on Learning Theory , pages=

  160. [168]

    Analysis of Perturbation Techniques in Online Learning , author=

  161. [169]

    Perturbations, Optimization, and Statistics , pages=

    Perturbation techniques in online learning and optimization , author=. Perturbations, Optimization, and Statistics , pages=. 2016 , publisher=

    2016

  162. [170]

    IEEE Journal on Selected Areas in Communications , volume=

    The role of caching in future communication systems and networks , author=. IEEE Journal on Selected Areas in Communications , volume=. 2018 , publisher=

    2018

  163. [171]

    Algorithmic Learning Theory , pages=

    Competitive ratio vs regret minimization: achieving the best of both worlds , author=. Algorithmic Learning Theory , pages=

  164. [172]

    Geographical analysis , volume=

    The maximal covering problem with some negative weights , author=. Geographical analysis , volume=. 2009 , publisher=

    2009

  165. [173]

    Computers & Operations Research , volume=

    The minimum weighted covering location problem with distance constraints , author=. Computers & Operations Research , volume=. 2008 , publisher=

    2008

  166. [174]

    Journal of Combinatorial Optimization , volume=

    Pipage rounding: A new method of constructing algorithms with proven performance guarantee , author=. Journal of Combinatorial Optimization , volume=. 2004 , publisher=

    2004

  167. [175]

    Annals of the Institute of Statistical Mathematics , volume=

    Stochastic ordering of multivariate normal distributions , author=. Annals of the Institute of Statistical Mathematics , volume=. 2001 , publisher=

    2001

  168. [176]

    2009 , publisher=

    Random fields and geometry , author=. 2009 , publisher=

    2009

  169. [177]

    Algorithmic Learning Theory , pages=

    Online non-convex learning: Following the perturbed leader is optimal , author=. Algorithmic Learning Theory , pages=

  170. [178]

    2020 , issue_date =

    Bhattacharjee, Rajarshi and Banerjee, Subhankar and Sinha, Abhishek , title =. 2020 , issue_date =. doi:10.1145/3392143 , journal =

    2020 doi

  171. [179]

    1995 , publisher=

    Randomized algorithms , author=. 1995 , publisher=

    1995

  172. [180]

    arXiv preprint arXiv:1912.13213 , year=

    A modern introduction to online learning , author=. arXiv preprint arXiv:1912.13213 , year=

    1912 arXiv

  173. [181]

    mathematical Programming , volume=

    A method for globally minimizing concave functions over convex sets , author=. mathematical Programming , volume=. 1981 , publisher=

    1981

  174. [182]

    1952 , publisher=

    Inequalities , author=. 1952 , publisher=

    1952

  175. [183]

    Graduate texts in mathematics , volume=

    Graph theory 3rd ed , author=. Graduate texts in mathematics , volume=

  176. [184]

    David Chappell & Associates White Paper , year=

    Introducing the windows azure platform , author=. David Chappell & Associates White Paper , year=

  177. [185]

    2019 , publisher=

    High-dimensional statistics: A non-asymptotic viewpoint , author=. 2019 , publisher=

    2019

  178. [186]

    2007 , publisher=

    Concentration inequalities and model selection , author=. 2007 , publisher=

    2007

  179. [187]

    Amazon Web Services , pages=

    Overview of amazon web services , author=. Amazon Web Services , pages=

  180. [188]

    International Conference on Machine Learning , pages=

    Following the perturbed leader for online structured learning , author=. International Conference on Machine Learning , pages=

  181. [189]

    2017 , publisher=

    Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis , author=. 2017 , publisher=

    2017

  182. [190]

    IETF Request For Comments , year=

    RaptorQ forward error correction scheme for object delivery--rfc 6330 , author=. IETF Request For Comments , year=

  183. [191]

    Proceedings of the joint international conference on Measurement and modeling of computer systems , pages=

    The output of a cache under the independent reference model: where did the locality of reference go? , author=. Proceedings of the joint international conference on Measurement and modeling of computer systems , pages=

  184. [192]

    1996 , publisher=

    Competitive online algorithms , author=. 1996 , publisher=

    1996

  185. [193]

    M. A. IEEE Communications Magazine , title=. 2016 , volume=. doi:10.1109/MCOM.2016.7537173 , ISSN=

    2016 doi

  186. [194]

    IEEE Transactions on Information Theory , title=

    M. IEEE Transactions on Information Theory , title=. 2016 , volume=. doi:10.1109/TIT.2015.2504556 , ISSN=

    2016 doi

  187. [195]

    Universal Caching , year=

    Joshi, Ativ and Sinha, Abhishek , booktitle=. Universal Caching , year=

  188. [196]

    2015 IEEE 16th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) , title=

    M. 2015 IEEE 16th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) , title=. 2015 , volume=. doi:10.1109/SPAWC.2015.7227127 , ISSN=

    2015 doi

  189. [197]

    IEEE Transactions on Information Theory , volume=

    Fundamental limits of caching , author=. IEEE Transactions on Information Theory , volume=. 2014 , publisher=

    2014

  190. [198]

    Ieee Infocom , volume=

    Web caching and Zipf-like distributions: Evidence and implications , author=. Ieee Infocom , volume=. 1999 , organization=

    1999

  191. [199]

    D. N. 2000 IEEE International Conference on Multimedia and Expo. ICME2000. Proceedings. Latest Advances in the Fast Changing World of Multimedia (Cat. No.00TH8532) , title=. 2000 , volume=. doi:10.1109/ICME.2000.871464 , ISSN=

    2000 doi

  192. [200]

    , author=

    On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies. , author=. SIGMETRICS , volume=. 1999 , organization=

    1999

  193. [201]

    Acm transactions on interactive intelligent systems (tiis) , volume=

    The movielens datasets: History and context , author=. Acm transactions on interactive intelligent systems (tiis) , volume=. 2015 , publisher=

    2015

  194. [202]

    MovieLens 25M Dataset , howpublished =

  195. [203]

    ACM SIGCOMM Computer Communication Review , volume=

    Open connect everywhere: A glimpse at the internet ecosystem through the lens of the netflix cdn , author=. ACM SIGCOMM Computer Communication Review , volume=. 2018 , publisher=

    2018

  196. [204]

    Journal of the ACM (JACM) , volume=

    Expected length of the longest probe sequence in hash code searching , author=. Journal of the ACM (JACM) , volume=. 1981 , publisher=

    1981

  197. [205]

    1996 , school=

    The Power of Two Choices in Randomized Load Balancing , author=. 1996 , school=

    1996

  198. [206]

    IEEE Transactions on Parallel and Distributed Systems , volume=

    The power of two choices in randomized load balancing , author=. IEEE Transactions on Parallel and Distributed Systems , volume=. 2001 , publisher=

    2001

  199. [207]

    1990 , publisher=

    An approximate analysis of the LRU and FIFO buffer replacement schemes , author=. 1990 , publisher=

    1990

  200. [208]

    IEEE Transactions on Parallel and Distributed Systems , volume=

    rStream: resilient and optimal peer-to-peer streaming with rateless codes , author=. IEEE Transactions on Parallel and Distributed Systems , volume=. 2007 , publisher=

    2007

  201. [209]

    In Proceedings of the Nineteenth Annual Conference on Computational Learning Theory , year =

    Jacob Abernethy and Alexander Rakhlin , title =. In Proceedings of the Nineteenth Annual Conference on Computational Learning Theory , year =

  202. [210]

    Machine Learning , volume=

    Logarithmic regret algorithms for online convex optimization , author=. Machine Learning , volume=. 2007 , publisher=

    2007

  203. [211]

    ACM SIGCOMM Computer Communication Review , volume=

    Temporal locality in today's content caching: why it matters and how to model it , author=. ACM SIGCOMM Computer Communication Review , volume=. 2013 , publisher=

    2013

  204. [212]

    IEEE Transactions on Multimedia , volume=

    Unravelling the impact of temporal and geographical locality in content caching systems , author=. IEEE Transactions on Multimedia , volume=. 2015 , publisher=

    2015

  205. [213]

    ACM SIGMETRICS Performance Evaluation Review , volume=

    Learning to rank: Regret lower bounds and efficient algorithms , author=. ACM SIGMETRICS Performance Evaluation Review , volume=. 2015 , publisher=

    2015

  206. [214]

    Artificial Intelligence and Statistics , pages=

    Tight regret bounds for stochastic combinatorial semi-bandits , author=. Artificial Intelligence and Statistics , pages=

  207. [215]

    Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages=

    Regret bounds for Gaussian process bandit problems , author=. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages=

  208. [216]

    Artificial intelligence and statistics , pages=

    Further optimal regret bounds for thompson sampling , author=. Artificial intelligence and statistics , pages=

  209. [217]

    Lipschitz Bandits: Regret Lower Bound and Optimal Algorithms , booktitle =

    Stefan Magureanu and Richard Combes and Alexandre Prouti. Lipschitz Bandits: Regret Lower Bound and Optimal Algorithms , booktitle =. 2014 , crossref =

    2014

  210. [218]

    The Journal of Machine Learning Research , volume=

    Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization , author=. The Journal of Machine Learning Research , volume=. 2014 , publisher=

    2014

  211. [219]

    International Conference on Machine Learning , pages=

    Strongly adaptive online learning , author=. International Conference on Machine Learning , pages=

  212. [220]

    2006 , publisher=

    Efficient algorithms for online convex optimization and their applications , author=. 2006 , publisher=

    2006

  213. [221]

    Proceedings of the Workshop on Virtual Reality and Augmented Reality Network , pages=

    VR/AR immersive communication: Caching, edge computing, and transmission trade-offs , author=. Proceedings of the Workshop on Virtual Reality and Augmented Reality Network , pages=. 2017 , organization=

    2017

  214. [222]

    Discrete Applied Mathematics , volume=

    Birthday paradox, coupon collectors, caching algorithms and self-organizing search , author=. Discrete Applied Mathematics , volume=. 1992 , publisher=

    1992

  215. [223]

    ACM SIGMETRICS Performance Evaluation Review , volume=

    Characterizing the miss sequence of the LRU cache , author=. ACM SIGMETRICS Performance Evaluation Review , volume=. 2008 , publisher=

    2008

  216. [224]

    IEEE/ACM Transactions on Networking (TON) , volume=

    Online coded caching , author=. IEEE/ACM Transactions on Networking (TON) , volume=. 2016 , publisher=

    2016

  217. [225]

    IEEE Transactions on Knowledge and data Engineering , volume=

    Caching on the world wide web , author=. IEEE Transactions on Knowledge and data Engineering , volume=. 1999 , publisher=

    1999

  218. [226]

    Information processing letters , volume=

    A short proof of optimality for the MIN cache replacement algorithm , author=. Information processing letters , volume=. 2007 , publisher=

    2007

  219. [227]

    IEEE Transactions on Information Theory , volume=

    Femtocaching: Wireless content delivery through distributed caching helpers , author=. IEEE Transactions on Information Theory , volume=. 2013 , publisher=

    2013

  220. [228]

    ACM SIGOPS Operating Systems Review , volume=

    The akamai network: a platform for high-performance internet applications , author=. ACM SIGOPS Operating Systems Review , volume=. 2010 , publisher=

    2010

  221. [229]

    Available in: http://aws

    Amazon web services , author=. Available in: http://aws. amazon. com/es/ec2/(November 2012) , year=

    2012

  222. [230]

    2006 , publisher=

    Operating system principles , author=. 2006 , publisher=

    2006

  223. [231]

    1997 , publisher=

    Introduction to linear optimization , author=. 1997 , publisher=

    1997

  224. [232]

    1964 , publisher=

    Principles of mathematical analysis , author=. 1964 , publisher=

    1964

  225. [233]

    2015 , publisher=

    Convex optimization algorithms , author=. 2015 , publisher=

    2015

  226. [234]

    IEEE Internet of Things Journal , year=

    Joint Caching and Routing in Congestible Networks of Arbitrary Topology , author=. IEEE Internet of Things Journal , year=

  227. [235]

    Optimal strategies and minimax lower bounds for online convex games , author=

  228. [236]

    IEEE Transactions on Wireless Communications , volume=

    Optimizing MDS coded caching in wireless networks with device-to-device communication , author=. IEEE Transactions on Wireless Communications , volume=. 2018 , publisher=

    2018

  229. [237]

    IEEE/ACM Transactions on Networking (TON) , volume=

    Raptor codes , author=. IEEE/ACM Transactions on Networking (TON) , volume=. 2006 , publisher=

    2006

  230. [238]

    The American Mathematical Monthly , volume=

    Mean deviation of the binomial distribution , author=. The American Mathematical Monthly , volume=. 1945 , publisher=

    1945

  231. [239]

    The American mathematical monthly , volume=

    A remark on Stirling's formula , author=. The American mathematical monthly , volume=. 1955 , publisher=

    1955

  232. [240]

    URL: https://web

    Drift Method: from Stochastic Networks to Machine Learning , author=. URL: https://web. stanford. edu/\

  233. [241]

    2004 , publisher=

    The probabilistic method , author=. 2004 , publisher=

    2004

  234. [242]

    , author=

    The hadoop distributed file system. , author=. MSST , volume=

  235. [243]

    IEEE transactions on information theory , volume=

    Network coding for distributed storage systems , author=. IEEE transactions on information theory , volume=. 2010 , publisher=

    2010

  236. [244]

    Foundations and Trends

    Online learning and online convex optimization , author=. Foundations and Trends. 2012 , publisher=

    2012

  237. [245]

    D. H. 2011 IEEE International Symposium on Multimedia , title=. 2011 , volume=. doi:10.1109/ISM.2011.53 , ISSN=

    2011 doi

  238. [246]

    2008 , month=may # " 27", publisher=

    Multi-resolution video coding and decoding , author=. 2008 , month=may # " 27", publisher=

    2008

  239. [247]

    Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

    Randomized competitive algorithms for generalized caching , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=. 2008 , organization=

    2008

  240. [248]

    2013 , month=mar # " 12", publisher=

    Multiple bit rate video encoding using variable bit rate and dynamic resolution for adaptive video streaming , author=. 2013 , month=mar # " 12", publisher=

    2013

  241. [249]

    International Workshop on Randomization and Approximation Techniques in Computer Science , pages=

    ``Balls into bins"— A simple and tight analysis , author=. International Workshop on Randomization and Approximation Techniques in Computer Science , pages=. 1998 , organization=

    1998

  242. [250]

    The Annals of Probability , pages=

    Distribution inequalities for the binomial law , author=. The Annals of Probability , pages=. 1977 , publisher=

    1977

  243. [251]

    arXiv preprint arXiv:1111.6554 , year=

    On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands , author=. arXiv preprint arXiv:1111.6554 , year=

    arXiv

  244. [252]

    Statistics & Probability Letters , volume=

    A sharp estimate of the binomial mean absolute deviation with applications , author=. Statistics & Probability Letters , volume=. 2013 , publisher=

    2013

  245. [253]

    , AUTHOR =

    Expectation of square root of binomial r.v. , AUTHOR =. https://mathoverflow.net/q/121424 , URL =

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.