Introduces asymmetric (b_t, s_t) price tuples for trading prophets and gives online algorithms achieving constant competitive ratios for unit capacity and 1 - Θ(log B0/√B0) for general capacity under i.i.d. arrivals.
The Nonstochastic Multiarmed Bandit Problem
14 Pith papers cite this work, alongside 2,252 external citations. Polarity classification is still indexing.
14
Pith papers citing it
2,252
external citations · OpenAlex
citation-role summary
background 2
method 1
citation-polarity summary
representative citing papers
Derives first lower bound on γ_t for mean-based algorithms in unknown-horizon bandit settings, proposes two new algorithms, and shows some are also no-regret.
Repetition rate mismatch between small-scale proxies and target budgets is the main reason data mixture experiments do not scale; a subsampling procedure that equalizes repetition rates recovers optimal mixtures from 1/16-scale experiments.
LOSCAR-SGD combines local updates, sparse model averaging, and communication-computation overlap with a delay-corrected merge rule, providing convergence rates for smooth non-convex objectives under worker heterogeneity.
Ringmaster LMO extends delay-thresholding from ASGD to LMO-based momentum updates, providing convergence guarantees under (L0, L1)-smoothness and time-complexity bounds that recover optimal rates in the Euclidean case.
Spectral bandits achieve scalable regret in graph-structured recommendation by using an effective dimension to learn good policies from few node evaluations.
In bandit-feedback zero-sum games, uncoupled algorithms achieve last-iterate Nash convergence at the optimal rate of O(T^{-1/4}).
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
Rescaled ASGD recovers convergence to the true global objective by rescaling worker stepsizes proportional to computation times, matching the known time lower bound in the leading term under non-convex smoothness and bounded heterogeneity.
Two strategies are introduced for transmission over unknown binary erasure channels: a two-phase method achieving O(T^{2/3}) regret with one query and a windowing method achieving O(sqrt(T)) regret with O(log T) queries.
Polynomial samples learn dual pricing and polynomial queries learn near-optimal anonymous pricing for online resource allocation with heterogeneous agents.
CHRONOS is a three-layer system for evolving data marketplaces that applies neural-ODE temporal decay, changepoint-aware Shapley valuation, and EXP3-IX private coordination to achieve 0.937 recall, 2.74 qps, 161 ms latency, and epsilon 4.25 at delta 10^-6.
Rennala MVR improves time complexity over Rennala SGD for smooth nonconvex stochastic optimization in heterogeneous parallel systems under a mean-squared smoothness assumption.
A survey that taxonomizes data mixing strategies for LLM pretraining into static rule-based, learning-based, and dynamic adaptive families while highlighting transferability challenges and evaluation gaps.
citing papers explorer
-
Asymmetric Trading Prophets
Introduces asymmetric (b_t, s_t) price tuples for trading prophets and gives online algorithms achieving constant competitive ratios for unit capacity and 1 - Θ(log B0/√B0) for general capacity under i.i.d. arrivals.
-
Mean-based algorithms: A lower bound and regret
Derives first lower bound on γ_t for mean-based algorithms in unknown-horizon bandit settings, proposes two new algorithms, and shows some are also no-regret.
-
Repetition Mismatch: Why Data Mixture Experiments Don't Scale and How to Fix Them
Repetition rate mismatch between small-scale proxies and target budgets is the main reason data mixture experiments do not scale; a subsampling procedure that equalizes repetition rates recovers optimal mixtures from 1/16-scale experiments.
-
LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging
LOSCAR-SGD combines local updates, sparse model averaging, and communication-computation overlap with a delay-corrected merge rule, providing convergence rates for smooth non-convex objectives under worker heterogeneity.
-
Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method
Ringmaster LMO extends delay-thresholding from ASGD to LMO-based momentum updates, providing convergence guarantees under (L0, L1)-smoothness and time-complexity bounds that recover optimal rates in the Euclidean case.
-
Spectral bandits
Spectral bandits achieve scalable regret in graph-structured recommendation by using an effective dimension to learn good policies from few node evaluations.
-
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
In bandit-feedback zero-sum games, uncoupled algorithms achieve last-iterate Nash convergence at the optimal rate of O(T^{-1/4}).
-
Offline Local Search for Online Stochastic Bandits
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
-
Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity
Rescaled ASGD recovers convergence to the true global objective by rescaling worker stepsizes proportional to computation times, matching the known time lower bound in the leading term under non-convex smoothness and bounded heterogeneity.
-
Learning to Transmit Over Unknown Erasure Channels with Empirical Erasure Rate Feedback
Two strategies are introduced for transmission over unknown binary erasure channels: a two-phase method achieving O(T^{2/3}) regret with one query and a windowing method achieving O(sqrt(T)) regret with O(log T) queries.
-
Learning Anonymous Pricing for Online Resource Allocation
Polynomial samples learn dual pricing and polynomial queries learn near-optimal anonymous pricing for online resource allocation with heterogeneous agents.
-
CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces
CHRONOS is a three-layer system for evolving data marketplaces that applies neural-ODE temporal decay, changepoint-aware Shapley valuation, and EXP3-IX private coordination to achieve 0.937 recall, 2.74 qps, 161 ms latency, and epsilon 4.25 at delta 10^-6.
-
Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
Rennala MVR improves time complexity over Rennala SGD for smooth nonconvex stochastic optimization in heterogeneous parallel systems under a mean-squared smoothness assumption.
-
Data Mixing for Large Language Models Pretraining: A Survey and Outlook
A survey that taxonomizes data mixing strategies for LLM pretraining into static rule-based, learning-based, and dynamic adaptive families while highlighting transferability challenges and evaluation gaps.