New algorithms sample convex bodies using Markov chains and restricted Gaussian oracles.
problem Sampling uniformly from convex bodies efficiently.
method Markov chain Monte Carlo with proximal sampler and restricted Gaussian oracle.
result Efficient implementation of RGO for uniform sampling on convex bodies.
Minimizing a function over an intersection of convex sets is an important task in optimization that is often much more challenging than minimizing it over each individual constraint set. While traditional methods such as Frank-Wolfe (FW) or proximal gradient descent assume access to a linear or quadratic oracle on the …
We provide tight upper and lower bounds on the complexity of minimizing the average of m convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient de…
Riemannian Proximal Sampler improves sampling on manifold data.
problem Sampling from densities on Riemannian manifolds.
method Uses MBI and RHK oracles for high-accuracy sampling.
result Sampling with ε-accuracy requires O(log(1/ε)) iterations in KL divergence.
Improved Frank-Wolfe algorithm for constrained convex optimization with nearest extreme point oracle.
problem Constrained smooth convex minimization with limited linear optimization oracle access.
method Frank-Wolfe algorithm with nearest extreme point oracle.
result Improved complexity bounds for specific feasible sets, including linear convergence for 0ext−−1 polytopes. We investigate active learning with access to two distinct oracles: Label (which is standard) and Search (which is not). The Search oracle models the situation where a human searches a database to seed or counterexample an existing solution. Search is stronger than Label while being natural to implement in many situati…
New characterization limits sampling with inexact scores.
problem Limiting sampling with inexact scores for unbiased results.
method Characterized types of inexact score oracle access.
result Weaker error assumptions rule out tractability of unbiased sampling.
We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder bu…
Oracle inequality for sparse neural nets adapts to unknown structure.
problem Sparse deep neural nets in nonparametric regression.
method Gibbs posterior distribution with Metropolis-adjusted Langevin algorithms and mixture of uniform priors.
result Oracle inequality showing adaptation to unknown regularity and structure, achieving minimax-optimal rate of convergence.
Quantum algorithms for multi-armed bandits are explored with limited reward access.
problem Exploring quantum speed-ups in multi-armed bandit problems with limited reward information.
method Introduced new bandit models and showed query complexity equivalence with classical algorithms.
result No quadratic speed-up is possible for multi-armed bandits with limited reward access.
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 …
Study on tradeoffs between mistakes and ERM oracle calls in online and transductive learning.
problem Analyzing online and transductive learning with limited ERM and weak consistency oracle access.
method Proves lower bounds and upper bounds on mistakes and oracle calls, considering realizable and agnostic cases.
result Achieves optimal mistake bounds with weak consistency queries for certain concept classes.
A new method samples from a target density without initial samples using Monte Carlo estimation of the score.
problem Sampling from a target density without initial samples.
method Monte Carlo estimation of the score using oracle access to the log likelihood.
result Samples can be produced from the target density without needing initial samples.
Improved method reduces projection calls for nonsmooth convex optimization.
problem Optimizing nonsmooth convex functions with convex constraints.
method MOPES and MOLES methods combining Moreau-Yosida smoothing and accelerated first-order schemes.
result Achieves ε-suboptimality with significantly fewer projection calls. Study exact partition recovery with same-cluster oracle, bounded error.
problem Exact recovery of partitions with same-cluster oracle in adversarial error.
method Novel connection to correlation clustering, Rényi-Ulam framework, upper and lower bounds, randomized algorithm analysis, adaptivity-query complexity study.
result Upper and lower bounds on worst-case query complexity, expected performance bounds of randomized algorithm.
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…
We provide an efficient algorithm for the classical problem, going back to Galton, Pearson, and Fisher, of estimating, with arbitrary accuracy the parameters of a multivariate normal distribution from truncated samples. Truncated samples from a d-variate normal N(μ,Σ) means a samples is only re…
Three new oracle-efficient algorithms for private synthetic data release.
problem Constructing private synthetic data that preserves statistical query answers.
method Oracle-efficient algorithms using optimization oracles for differential privacy.
result Better accuracy in large workload and high privacy regime compared to state-of-the-art.
Parrot learns optimal cache replacement policies using imitation learning.
problem Improving cache hit rates in complex access patterns.
method Imitation learning approach using Belady's oracle policy.
result Parrot increases cache hit rates by 61% on a web search benchmark.
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 …
Study exact community recovery in noisy SBM with limited queries.
problem Community recovery in noisy stochastic block models with limited queries.
method Balanced uniform querying, two-stage adaptive strategy, sublinear queries, subsampled graph.
result Adaptive querying can improve exact recovery limits in noisy SBM.
New algorithm learns POMDPs without computational oracles.
problem Learning near-optimal policies in POMDPs with computationally hard oracles.
method Quasipolynomial-time algorithm using barycentric spanners for policy covers.
result First oracle-free learning algorithm for observable POMDPs.
ConfHit provides valid guarantees for generative models without oracle access.
problem Reliable guarantees for novel candidate generation in generative models.
method Formalizes certification and refinement of generated sets, leveraging weighted exchangeability and density-ratio weighted conformal p-values.
result Consistently delivers valid coverage guarantees and compact certified sets across various generative tasks.
MAMBA learns policies competitive with multiple conflicting oracles.
problem Learning policies from multiple conflicting oracles in reinforcement learning.
method MAMBA uses a gradient estimator in the style of GAE to optimize policies, leveraging demonstrations from multiple weak oracles.
result MAMBA outperforms the state-of-the-art in learning policies competitive with multiple conflicting oracles.
Simplifies online learning with consistent oracle to fewer mistakes.
problem Online learning with computationally intractable Littlestone dimension computation.
method Novel algorithm making at most O(256d) mistakes, simpler proof. result No algorithm can make less than 3d mistakes. We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model that allows access to the data via a matrix-vector product oracle. We show that for polynomial accuracy, Θ(d) calls to the oracle are nece…
We present a novel technique based on deep learning and set theory which yields exceptional classification and prediction results. Having access to a sufficiently large amount of labelled training data, our methodology is capable of predicting the labels of the test data almost always even if the training data is entir…
New algorithms optimize actions under time-varying constraints without projecting.
problem Optimizing actions under time-varying constraints without projecting.
method Projection-free algorithms using linear optimization oracle.
result Guaranteed ildeO(T3/4) regret and O(T7/8) constraints violation. Algorithm identifies nearest mode in noisy data.
problem Identifying the point with the minimum k-th nearest neighbor distance in unknown multivariate probability density.
method Sequential learning algorithm using noisy oracle queries to adaptively decide which points to query.
result Upper bounds on query complexity show significant improvement over baselines.
New algorithms achieve small prediction regret for learning from overlapping groups.
problem Online multi-group learning with fairness applications.
method Oracle-efficient algorithms for groups not explicitly enumerated.
result Sublinear regret in various settings.
Minimax PAC bounds for learning in exogenous contextual MDPs
problem PAC learning in tabular discounted Markov decision processes with exogenous i.i.d. contexts
method Variance-reduced algorithm for policy evaluation, best-value estimation, and best-policy extraction
result Minimax optimal sample complexity
MAPS and MAPS-SE learn from multiple suboptimal experts to improve policies efficiently.
problem Learning from multiple suboptimal experts in reinforcement learning.
method Active policy improvement from multiple black-box oracles.
result MAPS and MAPS-SE achieve sample efficiency and state-wise imitation learning.
Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, O(T−1/2) accuracy. Extracts fairness truth from classifiers using an oracle.
problem Fairness in classification algorithms without context.
method Uses fairness oracle to learn underlying fairness truth.
result Extracts metric fairness from classifiers.
Oracle-efficient algorithms for online learning with smoothed and hint-adversaries.
problem Online learning with beyond worst-case adversaries.
method Oracle-efficient algorithms for two settings: smoothed analysis and K-hint transductive learning. result Oracle-efficient regret bounds for learning real-valued and binary-valued functions.
New sampling methods for constrained and composite distributions.
problem Sampling from log-concave distributions with constraints and composite structures.
method Proximal sampler applied to lifted convex sets with separation and subgradient oracles.
result Practical and unbiased samplers for constrained and composite distributions.
Oracle-efficient algorithm for offline RL with partial data coverage.
problem Offline reinforcement learning with partial data coverage and constraints.
method PDOCRL, a primal-dual algorithm with decomposed linear-programming formulation.
result Near-optimal, near-feasible policy with \(\widetilde{\mathcal O}(ε^{-2})\) sample guarantee.
Paper proposes a new black-box attack approach to minimize visual distortion.
problem Constructing adversarial examples that minimize visual distortion in a black-box threat model.
method Learning the noise distribution of adversarial examples to approximate the gradient of a non-differentiable loss function.
result The proposed attack results in much lower visual distortion compared to state-of-the-art black-box attacks.
The paper analyzes the efficiency of gradient estimation methods in noisy function evaluations.
problem Estimating gradients of smooth functions using noisy function evaluations.
method Information-theoretic lower bounds and finite difference method analysis.
result The finite difference method is not minimax optimal, suggesting room for improvement in gradient estimation.
A quantum reinforcement learning algorithm reduces sample complexity.
problem Quantum reinforcement learning under model-free settings with quantum oracle access.
method Quantum Natural Policy Gradient (QNPG) algorithm replacing random sampling with deterministic gradient estimation.
result QNPG achieves a sample complexity of ildeO(ε−1.5) for queries to the quantum oracle, significantly improving classical lower bound. Gradient descent is efficient for solving feasibility problems with minimal memory and queries.
problem Finding a point in a given set using a memory-constrained algorithm with a separation oracle.
method Oracle complexity lower bounds for gradient descent and other algorithms.
result Gradient descent is Pareto-optimal in the oracle complexity/memory tradeoff for feasibility problems.
Efficient algorithms for planning in cooperative multi-agent reinforcement learning with combinatorial action spaces.
problem Planning in cooperative multi-agent reinforcement learning with a combinatorial action space.
method Efficient algorithms using local access to a simulator and linear function approximation, with improvements for additive feature decomposition and kernelized settings.
result Polynomial compute and query complexity in relevant problem parameters.
This paper studies the lower bound complexity for the optimization problem whose objective function is the average of n individual smooth convex functions. We consider the algorithm which gets access to gradient and proximal oracle for each individual component. For the strongly-convex case, we prove such an algorith…
We design a stochastic algorithm to train any smooth neural network to ε-approximate local minima, using O(ε−3.25) backpropagations. The best result was essentially O(ε−4) by SGD. More broadly, it finds ε-approximate local minima of any smooth nonconvex function in …
Constrained second-order convex optimization algorithms are the method of choice when a high accuracy solution to a problem is needed, due to their local quadratic convergence. These algorithms require the solution of a constrained quadratic subproblem at every iteration. We present the \emph{Second-Order Conditional G…
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.
RichID learns optimal control policies from nonlinear observations.
problem Continuous control with unknown nonlinearity in system model.
method RichID algorithm using a least-squares regression oracle.
result First provable sample complexity guarantee for continuous control.
New algorithm reduces super-arm selection complexity exponentially.
problem Combinatorial multi-armed bandits with cardinality constraint.
method Combination of group-testing and quantized Thompson sampling.
result Achieves same regret order as state-of-the-art algorithms with perfect oracle, but with reduced complexity.