Efficient algorithm for unknown linear systems with convex costs.
problem Controlling an unknown linear system with stochastic convex costs.
method Optimism in the Face of Uncertainty paradigm.
result Achieves optimal regret-rate.
On-device research index
arXiv research
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “unknown costs”
New method optimizes costly functions with unknown costs and budget constraints.
problem Optimizing functions with unknown and heterogeneous evaluation costs under a budget constraint.
method Budgeted multi-step expected improvement acquisition function.
result Our method outperforms existing approaches in various synthetic and real problems.
Study one-shot strategic classification under unknown costs, improving worst-case accuracy.
problem Learning robust decision rules in strategic settings with unknown user costs.
method Formal study of one-shot strategic classification, framing as a minimax problem, designing efficient algorithms for full-batch and stochastic settings.
result Proves efficient algorithms converge to minimax solution, revealing dual norm regularization's value.
Paper tackles unknown variances in best-arm identification.
problem Identifying the best arm with unknown variances in Gaussian distributions.
method Two approaches: empirical variance plugging or adapting transportation costs.
result The impact of unknown variances is small on sample complexity.
Study on scheduling jobs with unknown types, achieving sublinear excess cost.
problem Optimizing job scheduling with unknown job types and varying durations.
method Design of algorithms for non-preemptive and preemptive scenarios, proving lower bounds.
result Preemptive algorithms can significantly outperform non-preemptive ones when job types have distinct durations.
We develop asymptotically optimal policies for the multi armed bandit (MAB), problem, under a cost constraint. This model is applicable in situations where each sample (or activation) from a population (bandit) incurs a known bandit dependent cost. Successive samples from each population are iid random variables with u…
New model considers varying costs in learning, outperforming existing methods.
problem Learning with varying costs in machine learning models.
method Introduces ε-frugal learning that considers both known and unknown costs.
result ε-frugal learners outperform learners with known costs and random sampling.
Study schedules jobs with unknown holding costs to minimize expected cumulative cost.
problem Minimizing expected cumulative holding costs of jobs with unknown parameters.
method Learning-based rule scheduling with a preemption phase.
result Achieves near-optimal performance guarantees with nearly matching regret bounds.
In real-world scenarios, different features have different acquisition costs at test-time which necessitates cost-aware methods to optimize the cost and performance trade-off. This paper introduces a novel and scalable approach for cost-aware feature acquisition at test-time. The method incrementally asks for features …
Paper develops PAC-Bayes bounds for unknown linear systems.
problem Learning controllers for unknown stochastic linear discrete-time systems.
method PAC-Bayes framework for data-dependent high probability bounds.
result Proposes efficient learning algorithms with theoretical guarantees.
Meta-learning control algorithm with finite-time guarantees for unknown systems.
problem Online control of unknown linear systems with constraints.
method Provable regret guarantees for an iterative control algorithm.
result Regret bounds of for controller cost and constraint violation.
Constrained Markov Decision Processes are a class of stochastic decision problems in which the decision maker must select a policy that satisfies auxiliary cost constraints. This paper extends upper confidence reinforcement learning for settings in which the reward function and the constraints, described by cost functi…
Safe linear bandits over unknown polytopes avoid safety violations and suboptimal actions.
problem Online approach to linear programming with unknown constraints and risks.
method Doubly-optimistic strategy (DOSS) for safe linear bandits over polytopes.
result DOSS achieves tight bounds on efficacy regret and safety violations.
Optimizes costs in uncertain Markov systems using risk filters.
problem Optimizing costs in systems with model uncertainty and unknown parameters.
method Risk filters and Bellman principle of optimality applied to Bayesian framework.
result Derives the Bellman principle for non-standard risk-averse control problems.
New algorithm clusters Gaussian mixtures with unknown covariance efficiently.
problem Clustering data from a mixture of Gaussians with unknown covariance.
method Developed an efficient spectral algorithm based on a Max-Cut integer program.
result Achieves optimal misclassification rate with quadratic sample size.
AI agent learns to handle unknown unknown states in reinforcement learning.
problem Handling unexpected, previously unseen states in reinforcement learning.
method Proposes EMDP-GA model with NIVE approach to expand value functions.
result Asymptotically consistent regret and comparable computational complexity.
Ergodic Annealingcs.AI
New method uses reinforcement learning to improve Simulated Annealing.
problem Optimization problems with unknown cost functions.
method Replaces Metropolis engine with Macau Algorithm.
result Effective heuristic for unknown cost functions.
New trade-off found in bandit problems with unknown range.
problem Stochastic bandit problems with unknown range.
method Exhibit a strategy achieving new trade-off between distribution-dependent and distribution-free regret bounds.
result Achieves the rates for regret indicated by the new trade-off.
Learning robot controllers by minimizing a black-box objective cost using Bayesian optimization (BO) can be time-consuming and challenging. It is very often the case that some roll-outs result in failure behaviors, causing premature experiment detention. In such cases, the designer is forced to decide on heuristic cost…
We consider the problem of controlling an unknown linear dynamical system in the presence of (nonstochastic) adversarial perturbations and adversarial convex loss functions. In contrast to classical control, the a priori determination of an optimal controller here is hindered by the latter's dependence on the yet unkno…
Study strategic dynamic pricing for buyers with unknown manipulation costs.
problem Strategic buyers manipulate their features to get lower prices, hindering profit maximization.
method Proposes a strategic dynamic pricing policy that incorporates strategic behavior and binary response data.
result Achieves sublinear regret bound of compared to linear regret of non-strategic policies.
In query learning, the goal is to identify an unknown object while minimizing the number of "yes" or "no" questions (queries) posed about that object. A well-studied algorithm for query learning is known as generalized binary search (GBS). We show that GBS is a greedy algorithm to optimize the expected number of querie…
Optimal control in changing systems without strong convexity assumptions.
problem Adversarial changes in convex costs for unknown linear systems.
method Non-convex lower confidence bounds and computationally-efficient regret minimization.
result Achieves -regret rate, optimal compared to best stabilizing controller.
New algorithms for planning with adversarial changes in costs.
problem Planning with adversarial changes in costs over time.
method Developed algorithms for adversarial SSP with high probability regret bounds.
result Obtained sub-linear regret bounds for adversarial SSP.
This paper concerns the problem of learning control policies for an unknown linear dynamical system to minimize a quadratic cost function. We present a method, based on convex optimization, that accomplishes this task robustly: i.e., we minimize the worst-case cost, accounting for system uncertainty given the observed …
MetaCaDI learns causal graphs and unknown interventions from few data instances.
problem Discovering causal mechanisms in systems with high data costs and unknown interventions.
method MetaCaDI is a Bayesian meta-learning framework that optimizes for rapid adaptation to new intervention targets.
result MetaCaDI significantly outperforms state-of-the-art methods in causal graph recovery and intervention target prediction.
We present a generic framework for trading off fidelity and cost in computing stochastic gradients when the costs of acquiring stochastic gradients of different quality are not known a priori. We consider a mini-batch oracle that distributes a limited query budget over a number of stochastic gradients and aggregates th…
In the context of stochastic continuum-armed bandits, we present an algorithm that adapts to the unknown smoothness of the objective function. We exhibit and compute a polynomial cost of adaptation to the H{ö}lder regularity for regret minimization. To do this, we first reconsider the recent lower bound of Locatelli an…
The paper analyzes the statistical cost of tuning kernel hyperparameters in robust regression.
problem Finding the best interpolant from a class of kernels with unknown hyperparameters under adversarial noise.
method Finite-sample guarantees, subsampling guarantee for linear regression, ε-net argument for discretizing kernel parameterizations.
result Hyperparameter optimization increases sample complexity by just a logarithmic factor, compared to known parameters.
Bayesian optimization with cost-awareness using Gittins index.
problem Optimizing unknown functions with limited data evaluations and costs.
method Developed a connection between cost-aware Bayesian optimization and the Pandora's Box problem, using the Gittins index as an acquisition function.
result The Gittins index-based acquisition function performs well in cost-aware Bayesian optimization, especially in high dimensions.
Incentive-aware recommender system for online platforms.
problem Myopic agents exploit optimal arms, not exploring alternatives.
method Model as multi-agent bandit problem, incentivizes exploration.
result Asymptotically optimal performance with ex-post fairness.
Algorithm reduces control regret for unknown systems.
problem Minimizing control regret for unknown linear systems.
method Novel geometric exploration strategy and polynomial-time algorithms.
result First polynomial-time algorithms with optimal regret bounds.
New algorithm achieves data-dependent regret bounds in MDPs with unknown transitions.
problem Achieving best-of-both-worlds guarantees with data-dependent regret bounds in MDPs with unknown transitions.
method Optimistic follow-the-regularized-leader algorithm with new optimistic Q-function estimators and transition bonus.
result First-order, second-order, and path-length bounds with polylog(T) regret in the stochastic regime.
New algorithm reduces online learning error for unknown feature distributions.
problem Oracle-efficient hybrid online learning with unknown feature and label distributions.
method Computational efficient online predictor using ERM oracle for finite-VC and fat-shattering classes.
result Oracle-efficient sublinear regret bounds for hybrid online learning with unknown feature generation.
Paper tackles online control of linear systems with unbounded noise.
problem Online control of linear systems under unbounded noise with unknown convex cost functions.
method Developed an algorithm achieving high-probability regret under unbounded noise, and established regret bound for strongly convex costs and sub-Gaussian noise.
result Achieved high-probability regret under unbounded noise, and regret bound for specific noise and cost conditions.
New algorithm reduces online hyperparameter optimization costs.
problem High cost of evaluating validation examples in online HPO.
method Modeling online HPO as a time-varying Bayesian optimization problem, proposing a costly feedback setting.
result Cost-efficient GP-UCB algorithm reaches human expert-level performance.
Study Nash competition among dealers quoting prices to clients with unknown trading motives.
problem Adverse selection and inventory costs in dealer-client interactions.
method Analyzes one-shot Nash competition with unknown client type and inventory constraints.
result Unique symmetric Nash equilibrium exists and can be characterized by a nonlinear ODE.
Optimizing Basis Function Selection in Constructive Wavelet Neural Networks and Its Applicationscs.LG
A new WNN framework selects wavelet bases for efficient learning.
problem Challenges in constructing accurate wavelet bases and high computational costs in WNN.
method Introduces a constructive WNN that selects initial bases and trains functions by introducing new bases for predefined accuracy while reducing computational costs.
result Significantly improves computational efficiency through a frequency estimator and wavelet-basis increase mechanism.
A new UCB policy improves reward-cost ratio estimation in budgeted MAB.
problem Maximizing reward-cost ratio under budget constraints.
method ω-UCB policy with asymmetric confidence intervals.
result Logarithmic regret and superior performance in various settings.
The paper develops a method to learn robust decision policies from observational data, reducing high-cost outcomes.
problem Learning safe decision policies from observational data with high-risk outcomes.
method Develops a method to learn policies that reduce high-cost outcomes, valid under finite samples and uneven feature overlap.
result Validates the method with real and synthetic data, providing statistical bounds on decision costs.
Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairnessstat.ML
New method reduces total cost constraints in CBwK to sqrt(T) with fairness application.
problem Maximize rewards while adhering to total cost constraints in CBwK.
method Dual strategy based on projected-gradient-descent updates.
result Total cost constraints reduced to sqrt(T) with poly-logarithmic terms.
Gradient descent solves rank-one matrix estimation problem with detailed time evolution analysis.
problem Estimating a rank-one symmetric matrix corrupted by noise.
method Gradient descent on a sphere, using local versions of the semi-circle law.
result Explicit formulas for the time evolution of the estimator and cost function, revealing phase transitions.
Imbalanced data with a skewed class distribution are common in many real-world applications. Deep Belief Network (DBN) is a machine learning technique that is effective in classification tasks. However, conventional DBN does not work well for imbalanced data classification because it assumes equal costs for each class.…
Study tests feasibility of linear programs with bandit feedback.
problem Testing feasibility of unknown linear programs with bandit feedback.
method Developed a novel test based on low-regret algorithms and a nonasymptotic law of iterated logarithms.
result Proved that the test is reliable and adapts to the signal level, with mean sample costs scaling as \( \widetilde{O}(d^2/Γ^2) \).
New study reveals a polynomial penalty for adapting to unknown margin parameters in batched nonparametric bandits.
problem Adapting to an unknown margin parameter in batched nonparametric bandits.
method Introduces the regret inflation criterion and develops RoBIN algorithm to achieve optimal regret inflation.
result The optimal regret inflation grows polynomially with the horizon T, characterized by a convex optimization problem.
The paper develops a method to learn navigation costs from expert demonstrations in partially observable environments.
problem Learning navigation costs from expert demonstrations in partially observable environments.
method Develops a cost function representation composed of a probabilistic occupancy encoder and a cost encoder, optimized by differentiating the error between demonstrated controls and a control policy computed from the cost encoder.
result The method outperforms baseline IRL algorithms in robot navigation tasks, improving both training and test-time efficiency.
COF algorithm minimizes cost in multi-armed bandits with known costs and reward constraints.
problem Minimizing cost while meeting a minimum reward requirement in uncertain environments.
method COF algorithm that intelligently combines samples from all arms to gauge feasibility and minimize cost.
result COF achieves instance-dependent upper bounds on cumulative cost and quality regret.
People Mover's Distance: Class level geometry using fast pairwise data adaptive transportation costsstat.ML
We address the problem of defining a network graph on a large collection of classes. Each class is comprised of a collection of data points, sampled in a non i.i.d. way, from some unknown underlying distribution. The application we consider in this paper is a large scale high dimensional survey of people living in the …