惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

博客园 - Franky
Microsoft Azure Blog
Microsoft Azure Blog
阮一峰的网络日志
阮一峰的网络日志
宝玉的分享
宝玉的分享
量子位
N
Netflix TechBlog - Medium
M
MIT News - Artificial intelligence
GbyAI
GbyAI
Apple Machine Learning Research
Apple Machine Learning Research
博客园_首页
博客园 - 叶小钗
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
酷 壳 – CoolShell
酷 壳 – CoolShell
T
Tailwind CSS Blog
Y
Y Combinator Blog
L
LangChain Blog
The Cloudflare Blog
T
The Blog of Author Tim Ferriss
U
Unit 42
Martin Fowler
Martin Fowler
aimingoo的专栏
aimingoo的专栏
G
Google Developers Blog
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
月光博客
月光博客

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Online Lower Bounds via Duality
Yossi Azar, Ilan Reuven Cohen, Alan Roytman · 2016-04-07 · via cs.DS updates on arXiv.org

In this paper, we exploit linear programming duality in the online setting (i.e., where input arrives on the fly) from the unique perspective of designing lower bounds on the competitive ratio. In particular, we provide a general technique for obtaining online deterministic and randomized lower bounds (i.e., hardness results) on the competitive ratio for a wide variety of problems. We show the usefulness of our approach by providing new, tight lower bounds for three diverse online problems. The three problems we show tight lower bounds for are the Vector Bin Packing problem, Ad-auctions (and various online matching problems), and the Capital Investment problem. Our methods are sufficiently general that they can also be used to reconstruct existing lower bounds. Our techniques are in stark contrast to previous works, which exploit linear programming duality to obtain positive results, often via the useful primal-dual scheme. We design a general recipe with the opposite aim of obtaining negative results via duality. The general idea behind our approach is to construct a primal linear program based on a collection of input sequences, where the objective function corresponds to optimizing the competitive ratio. We then obtain the corresponding dual linear program and provide a feasible solution, where the objective function yields a lower bound on the competitive ratio. Online lower bounds are often achieved by adapting the input sequence according to an online algorithm's behavior and doing an appropriate ad hoc case analysis. Using our unifying techniques, we simultaneously combine these cases into one linear program and achieve online lower bounds via a more robust analysis. We are confident that our framework can be successfully applied to produce many more lower bounds for a wide array of online problems.