arXiv research

Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.

New algorithm learns efficiently with a simple 'yes/no' oracle.

Three new oracle-efficient algorithms for private synthetic data release.

Oracle-efficient algorithms for online learning with smoothed and hint-adversaries.

New algorithms adapt to friendly environments in online learning.

GPE algorithm optimizes nonparametric contextual bandits with efficient regret bounds.

We develop theory for using heuristics to solve computationally hard problems in differential privacy. Heuristic approaches have enjoyed tremendous success in machine learning, for which performance can be empirically evaluated. However, privacy guarantees cannot be evaluated empirically, and must be proven --- without…

We study the computational tractability of PAC reinforcement learning with rich observations. We present new provably sample-efficient algorithms for environments with deterministic hidden state dynamics and stochastic rich observations. These methods operate in an oracle model of computation -- accessing policy and va…

EP-learning framework improves causal contrast estimation efficiency.

We study reinforcement learning in non-episodic factored Markov decision processes (FMDPs). We propose two near-optimal and oracle-efficient algorithms for FMDPs. Assuming oracle access to an FMDP planner, they enjoy a Bayesian and a frequentist regret bound respectively, both of which reduce to the near-optimal bound …

RPI combines imitation and reinforcement learning to improve policies efficiently.

New algorithm reduces online learning error for unknown feature distributions.

New algorithm for online omniprediction with strong guarantees for continuous hypothesis classes.

New algorithm for clustering with faulty oracle achieves optimal queries and efficiency.

Oracle-efficient algorithm for offline RL with partial data coverage.

New RLHF framework handles general preference oracles without reward functions.

New method removes oracle and reduces memory usage for robust MDPs.

New algorithms sample convex bodies using Markov chains and restricted Gaussian oracles.

Paper addresses hybrid learning with constrained adversaries, achieving optimal performance.

Improved algorithm for contextual bandits with reduced regret.

New algorithms achieve small prediction regret for learning from overlapping groups.

New algorithm tackles smooth online learning with optimal regret.

Paper addresses online alignment of large language models under uncertain preference feedback.

$Q$-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, approximating $Q$-functions with linear functions, it is still an open problem on how to design a pr…

We consider online learning in an adversarial, non-convex setting under the assumption that the learner has an access to an offline optimization oracle. In the general setting of prediction with expert advice, Hazan et al. (2016) established that in the optimization-oracle model, online learning requires exponentially …

MAPS and MAPS-SE learn from multiple suboptimal experts to improve policies efficiently.

Two novel procedures track quantiles efficiently using an oracle.

New oracle uses uncertainty for active classification with noisy feedback.

The paper addresses fairness in online learning by extending auditing schemes and presenting efficient algorithms.

New algorithms adapt to model misspecification in contextual bandits.

Semi-supervised active clustering (SSAC) utilizes the knowledge of a domain expert to cluster data points by interactively making pairwise "same-cluster" queries. However, it is impractical to ask human oracles to answer every pairwise query. In this paper, we study the influence of allowing "not-sure" answers from a w…

We presented Bayesian portfolio selection strategy, via the $k$ factor asset pricing model. If the market is information efficient, the proposed strategy will mimic the market; otherwise, the strategy will outperform the market. The strategy depends on the selection of a portfolio via Bayesian multiple testing methodol…

New algorithm learns FMDP structure while minimizing regret.

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…

CJE calibrates cheap LLM judges against an oracle, achieving high accuracy at a fraction of the cost.

Efficiently learns private models using public data.

We give nearly matching upper and lower bounds on the oracle complexity of finding $ε$-stationary points ($\| \nabla F(x) \| \leqε$) in stochastic convex optimization. We jointly analyze the oracle complexity in both the local stochastic oracle model and the global oracle (or, statistical learning) model. This allows u…

Adaptive pricing framework for perpetual contracts using liquidity curves and oracles.

Study on costs of manipulating AMM-based price oracles.

We introduce an efficient algorithmic framework for model selection in online learning, also known as parameter-free online learning. Departing from previous work, which has focused on highly structured function classes such as nested balls in Hilbert space, we propose a generic meta-algorithm framework that achieves o…

New algorithm estimates treatment effects for more efficient contextual bandits.

Efficiently clusters noisy data with minimal queries.

One of the most effective algorithms for differentially private learning and optimization is objective perturbation. This technique augments a given optimization problem (e.g. deriving from an ERM problem) with a random linear term, and then exactly solves it. However, to date, analyses of this approach crucially rely …

Algorithm samples composite logconcave densities efficiently.

New algorithm achieves faster multicalibration in online settings.

Gradient descent is efficient for solving feasibility problems with minimal memory and queries.

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and h…

A new Bayesian method optimizes time-dependent expensive functions with lookahead.