A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
The paper optimizes A/B tests by balancing lift and cost in large-scale settings.
problem Balancing lift and cost in A/B tests for large-scale experimentation.
method Empirical Bayes approach using a greedy knapsack algorithm to rank experiments based on lift-to-cost ratio, incorporating local false discovery rate (lfdr).
result The proposed method maximizes expected profit while controlling false discovery rate, demonstrating superior performance in large-scale settings.
Study optimal policies under budget and coverage constraints.
problem Optimal policy learning with budget and coverage constraints.
method Combination of knapsack structure, affine threshold rule, linear programming relaxation, Greedy-Lagrangian (GLC), and rank-and-cut (RC) algorithms.
result GLC closely approximates the optimal solution and achieves near-optimal performance in finite samples; RC is approximately optimal under certain conditions.
A typical viral marketing model identifies influential users in a social network to maximize a single product adoption assuming unlimited user attention, campaign budgets, and time. In reality, multiple products need campaigns, users have limited attention, convincing users incurs costs, and advertisers have limited bu…
The typical algorithmic problem in viral marketing aims to identify a set of influential users in a social network, who, when convinced to adopt a product, shall influence other users in the network and trigger a large cascade of adoptions. However, the host (the owner of an online social platform) often faces more con…
We consider a contextual version of multi-armed bandit problem with global knapsack constraints. In each round, the outcome of pulling an arm is a scalar reward and a resource consumption vector, both dependent on the context, and the global knapsack constraints require the total consumption for each resource to be bel…
We present a new Bitcoin coin selection algorithm, "coin selection with leverage", which aims to improve upon cost savings than that of standard knapsack like approaches. Parameters to the new algorithm are available to be tuned at the users discretion to address other goals of coin selection. Our approach naturally fi…
0-1 knapsack is of fundamental importance in computer science, business, operations research, etc. In this paper, we present a deep learning technique-based method to solve large-scale 0-1 knapsack problems where the number of products (items) is large and/or the values of products are not necessarily predetermined but…
We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of nume…
We present a new approach for studying the problem of optimal hedging of a European option in a finite and complete discrete-time market model. We consider partial hedging strategies that maximize the success probability or minimize the expected shortfall under a cost constraint and show that these problems can be trea…
A cost-effective approach to label acquisition using active learning markets.
problem Improving model fitting and training for predictive analytics.
method Formalizing market clearing as an optimisation problem, integrating budget constraints and improvement thresholds, using two active learning strategies with distinct pricing mechanisms.
result Superior performance with fewer labels acquired compared to conventional methods.
A new pruning method improves neural network efficiency and accuracy.
problem Optimizing neural network efficiency and accuracy through pruning.
method Formulated as a Knapsack Problem, the method optimizes trade-off between neuron importance and computational cost. Channels are pruned while maintaining network structure, and fine-tuned using inner knowledge distillation from parent network.
result State-of-the-art pruning results on ImageNet, CIFAR-10, and CIFAR-100.
Improves bandits with knapsacks guarantees for partially stochastic workloads.
problem Improves guarantees for Bandits with Knapsacks (BwK) with partially stochastic workloads.
method Defines Approximately Stationary BwK, explores algorithms with smooth competitive ratios transitioning between stochastic and adversarial cases.
result Offers competitive ratios that smoothly transition between the best possible guarantees in stochastic and adversarial cases, especially beneficial when budget is small.
The stochastic knapsack has been used as a model in wide ranging applications from dynamic resource allocation to admission control in telecommunication. In recent years, a variation of the model has become a basic tool in studying problems that arise in revenue management and dynamic/flexible pricing; and it is in thi…
The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science, and engineering, practitioners will often fix a family of parameterized algorithms and then optimize those parameters to obtain good perfo…
This paper studies the impact of limited switches on resource-constrained dynamic pricing with demand learning. We focus on the classical price-based blind network revenue management problem and extend our results to the bandits with knapsacks problem. In both settings, a decision maker faces stochastic and distributio…
We consider the linear contextual bandit problem with resource consumption, in addition to reward generation. In each round, the outcome of pulling an arm is a reward as well as a vector of resource consumptions. The expected values of these outcomes depend linearly on the context of that arm. The budget/capacity const…
This paper investigates the adversarial Bandits with Knapsack (BwK) online learning problem, where a player repeatedly chooses to perform an action, pays the corresponding cost, and receives a reward associated with the action. The player is constrained by the maximum budget B that can be spent to perform actions, an…
Neural Index Policy for multi-action bandits with heterogeneous budgets.
problem Real-world settings often involve multiple interventions with heterogeneous costs and constraints, breaking classical assumptions.
method Introduces a Neural Index Policy (NIP) that learns to assign budget-aware indices to arm-action pairs using a neural network and differentiable knapsack layer.
result Empirically achieves near-optimal performance while strictly enforcing heterogeneous budgets and scaling to hundreds of arms.
We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We show that the widely used bisection approach is Info-Greedy for a family of k-sparse signals b…
This paper is a follow up to the previous author's paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there three the most popular in nonlinear approximation in Banach…
This paper proposes and evaluates the k-greedy equivalence search algorithm (KES) for learning Bayesian networks (BNs) from complete data. The main characteristic of KES is that it allows a trade-off between greediness and randomness, thus exploring different good local optima. When greediness is set at maximum, KES co…
We study the online saddle point problem, an online learning problem where at each iteration a pair of actions need to be chosen without knowledge of the current and future (convex-concave) payoff functions. The objective is to minimize the gap between the cumulative payoffs and the saddle point value of the aggregate …
Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work \cite{efroni2018beyond}, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analy…