Imagen de Portada

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Xu, Haoran, Shen, Owen, Glynn, Peter, Ye, Yinyu, Jaillet, Patrick
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms Machine Learning
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Two-Layer Framework for Joint Online Configuration Selection and Admission Control
por: Shen, Owen, et al.
Publicado: (2026)

Online Resource Allocation with Convex-set Machine-Learned Advice
por: Golrezaei, Negin, et al.
Publicado: (2023)

Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
por: Oki, Taihei, et al.
Publicado: (2026)

Towards Optimal Differentially Private Regret Bounds in Linear MDPs
por: Sahu, Sharan
Publicado: (2025)

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
por: John, Philips George, et al.
Publicado: (2024)

Online Linear Programming with Replenishment
por: Chen, Yuze, et al.
Publicado: (2026)

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
por: Ye, Zichun, et al.
Publicado: (2025)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
por: Braverman, Vladimir, et al.
Publicado: (2024)

Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
por: Su, Yuexin, et al.
Publicado: (2025)

Solving Linear Programs with Fast Online Learning Algorithms
por: Gao, Wenzhi, et al.
Publicado: (2021)

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
por: Harada, Tsubasa, et al.
Publicado: (2025)

Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
por: Tarzanagh, Davoud Ataee, et al.
Publicado: (2022)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
por: Sakaue, Shinsaku, et al.
Publicado: (2026)

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
por: Ye, Zichun, et al.
Publicado: (2025)

$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
por: Vaze, Rahul, et al.
Publicado: (2025)

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
por: He, Yuchen, et al.
Publicado: (2024)

Improved Bounds for Online Facility Location with Predictions
por: Fotakis, Dimitris, et al.
Publicado: (2021)

Infrequent Resolving Algorithm for Online Linear Programming
por: Li, Guokai, et al.
Publicado: (2024)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
por: Koh, Zhuan Khye, et al.
Publicado: (2024)

Finite Sample Bounds for Learning with Score Matching
por: Smedira, Devin, et al.
Publicado: (2026)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
por: Woodruff, David P., et al.
Publicado: (2023)

Near-optimal Swap Regret Minimization for Convex Losses
por: Hu, Lunjia, et al.
Publicado: (2026)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
por: Maity, Binita, et al.
Publicado: (2024)

Perfect $L_p$ Sampling with Polylogarithmic Update Time
por: Swartworth, William, et al.
Publicado: (2025)

Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm
por: Davoodi, Mansoor, et al.
Publicado: (2025)

Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy
por: Wu, Ruihan, et al.
Publicado: (2025)

Polylogarithmic Approximation for Robust s-t Path
por: Li, Shi, et al.
Publicado: (2023)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
por: Kalavas, Andreas, et al.
Publicado: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
por: Kalavas, Andreas, et al.
Publicado: (2025)

Non-Stationary Online Resource Allocation: Learning from a Single Sample
por: Feng, Yiding, et al.
Publicado: (2026)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
por: Mangoubi, Oren, et al.
Publicado: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
por: Agarwal, Arpit, et al.
Publicado: (2024)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
por: Jiang, Yonggang, et al.
Publicado: (2025)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
por: Oki, Taihei, et al.
Publicado: (2024)

Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
por: Chenakkod, Shabarish, et al.
Publicado: (2025)

Single-Sample and Robust Online Resource Allocation
por: Ghuge, Rohan, et al.
Publicado: (2025)

Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming
por: Chen, Yilun, et al.
Publicado: (2025)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
por: Hu, Hang, et al.
Publicado: (2022)

Sample-Adaptivity Tradeoff in On-Demand Sampling
por: Haghtalab, Nika, et al.
Publicado: (2025)

Memory Reallocation with Polylogarithmic Overhead
por: Jin, Ce
Publicado: (2026)