Paper proposes a new method to minimize submodular functions with fewer calls to simpler oracles.
problem Minimizing the sum of submodular set functions with limited information.
method Introduces a modified convex problem requiring constrained total variation oracles that can be solved with fewer calls to minimization oracles.
result Shows significant reduction in the number of calls to minimization oracles.
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.
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. New lower bounds for bilevel optimization with first-order oracles.
problem Complexity of bilevel optimization with first-order oracles.
method Development of hard instances and proof of lower bounds.
result Nontrivial lower bounds for first-order zero-respecting algorithms.
A new method for creating derivatives without oracles.
problem Lack of trust in external oracles for derivatives pricing.
method Using Replicating Market Makers (RMMs) to create derivative instruments.
result Demonstrated the feasibility of on-chain expiring options without oracles.
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with O ( log log T ) O(\log\log T) O ( log log T ) oracle queries for worst-case linear rewards. 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.
We revisit the question of reducing online learning to approximate optimization of the offline problem. In this setting, we give two algorithms with near-optimal performance in the full information setting: they guarantee optimal regret and require only poly-logarithmically many calls to the approximation oracle per it…
Optimizes bilevel empirical risk minimization with improved oracle calls.
problem Optimizing bilevel empirical risk minimization problems.
method Proposes a bilevel extension of the SARAH algorithm.
result Demonstrates improved oracle calls to achieve stationarity.
Study on gradient complexity of private optimization with private oracles.
problem Analyzing the efficiency of differentially private optimization algorithms.
method Lower bounds on the number of first-order oracle queries for private optimization.
result Lower bounds on the number of queries for private optimization algorithms, showing a dimension-dependent runtime penalty.
Paper shows how to replicate payoffs without oracles in CFMMs.
problem Replicating payoffs without oracles in CFMMs.
method Using liquidity provider shares in CFMMs to match any monotonic payoff.
result Explicit method and formula for trading functions and earnings.
META-DES.Oracle uses meta-learning and feature selection to improve ensemble selection accuracy.
problem Dynamic Ensemble Selection (DES) issues with classifier competence estimation.
method META-DES.Oracle integrates multiple criteria and an Oracle-based meta-feature selection scheme.
result META-DES.Oracle significantly improves classification accuracy compared to previous methods.
New data-dependent priors improve PAC-Bayes bounds.
problem Improving PAC-Bayes bounds for nonconvex learning.
method Using data to learn a conditional expectation of the posterior, given a subset of training data.
result Data-dependent oracle priors lead to stronger PAC-Bayes bounds.
Algorithm solves online binary classification and infinite games using ERM oracle.
problem Online learning and solving infinite games with computationally inefficient oracles.
method Proposes an algorithm relying solely on ERM oracle calls for online binary classification and nonparametric games.
result Achieves finite and sublinearly growing regret in various settings.
Improved complexity for machine learning optimization methods.
problem Optimizing over-parametrized models in machine learning.
method Stochastic conditional gradient methods with interpolation-like conditions.
result Improved oracle complexities for finding optimal solutions.
New algorithms solve non-convex optimization problems efficiently.
problem Non-convex stochastic compositional optimization problems.
method Developed two stochastic Gauss-Newton algorithms.
result Established global oracle complexity for stochastic Gauss-Newton methods.
New algorithms adapt to friendly environments in online learning.
problem Oracle-efficient algorithms struggle with friendly environments.
method Follow-the-perturbed-leader algorithms with approximability condition.
result Best-of-both-worlds bound in oracle-efficient setting.
A new algorithm for solving constrained convex optimization problems efficiently.
problem Constrained convex optimization problems requiring high accuracy solutions.
method Second-Order Conditional Gradient Sliding (SOCGS) algorithm, using projection-free methods to solve quadratic subproblems inexactly.
result Converges quadratically in primal gap after a finite number of linearly convergent iterations.
Improved algorithm for contextual bandits with reduced regret.
problem Adversarial contextual bandits with i.i.d. contexts.
method Oracle-efficient relaxation with O ( T 2 3 ( K log ( ∣ Π ∣ ) ) 1 3 ) O(T^{\frac{2}{3}}(K\log(|Π|))^{\frac{1}{3}}) O ( T 3 2 ( K log ( ∣Π∣ ) ) 3 1 ) regret bound. result First to improve regret bound and match original bound for stochastic case.
We analyze stochastic gradient algorithms for optimizing nonconvex, nonsmooth finite-sum problems. In particular, the objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a possibly non-differentiable but convex component. We propose a proximal stochastic gradie…
A new approach to fraud detection minimizes human intervention.
problem Minimizing the number of non-fraudulent operations requiring human verification.
method Computer-assisted fraud detection using a meta-algorithm to minimize oracle calls.
result A simple meta-algorithm provides competitive results in minimizing non-fraudulent operations.
New algorithms for private data synthesis using heuristics.
problem Private data synthesis for complex functions.
method Developed algorithms using non-private oracles and certifiable heuristics.
result Efficient private data synthesis for broad classes of functions.
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
Framework reduces contextual bandit learning to offline regression with near-optimal regret.
problem Efficient learning with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that minimizes regret with near-optimal oracle calls.
result Near-optimal regret for contextual bandits with large action spaces and O ( l o g ( T ) ) O(log(T)) O ( l o g ( T )) offline oracle calls. Faster algorithm reduces contextual bandit regret with fewer offline regression calls.
problem Optimizing reward in contextual bandits with unknown functions.
method Designing a simple algorithm with O ( log T ) {O}(\log T) O ( log T ) offline regression calls. result Achieves statistically optimal regret with minimal offline calls.
The paper analyzes CFMMs to ensure accurate price reporting.
problem Ensuring accurate price reporting for CFMMs.
method Analyzes CFMMs under general assumptions to incentivize correct price reporting.
result Agents are incentivized to correctly report asset prices in a computationally efficient way.
OE2D framework reduces contextual bandits to offline regression for near-optimal regret.
problem Efficiently learning contextual bandits with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that reduces contextual bandits to offline regression.
result Near-optimal regret for contextual bandits with large action spaces and O ( log T ) O(\log T) O ( log T ) calls to an offline regression oracle. This paper analyzes and compares different Automated Market Maker mechanisms.
problem Impermanent loss in Constant Function Market Makers.
method Mean-Variance analysis of liquidity providers' profit and loss, comparison of different mechanisms.
result Optimized oracle-based mechanisms outperform Constant Function Market Makers.
The paper explores MAB strategies for very short horizons, introducing new methods and showing improved performance.
problem Short horizon multi-armed bandit problems in games.
method Regression oracles, forced exploration, UCBT strategy.
result Combination of epsilon-greedy or epsilon-decreasing with regression oracles outperforms other strategies.
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 ) O(T^{-1/2}) O ( T − 1/2 ) accuracy. New algorithm tackles smooth online learning with optimal regret.
problem Smoothed online learning with adversarial distributions.
method Oracle-efficient algorithms for nonparametric function classes.
result Oracle-efficient algorithms achieve optimal regret bounds.
Crowdsourcing is an effective tool for human-powered computation on many tasks challenging for computers. In this paper, we provide finite-sample exponential bounds on the error rate (in probability and in expectation) of hyperplane binary labeling rules under the Dawid-Skene crowdsourcing model. The bounds can be appl…
Lower bounds show linear complexity for linear regression.
problem Computational complexity of linear regression.
method Reduction to estimating the least eigenvalue of a random Wishart matrix.
result Θ(d) calls to the oracle are necessary and sufficient for polynomial accuracy.
Study efficient algorithms for nonconvex optimization with state-dependent Markov data.
problem Stochastic optimization with Markovian data and state-dependent transition kernels.
method Projection-based and projection-free algorithms for constrained nonconvex problems.
result The number of oracle calls to achieve an ε ε ε -stationary point is O ( 1 / ε 2.5 ) \mathcal{O}(1/ε^{2.5}) O ( 1/ ε 2.5 ) . Algorithm ensures safe optimization under unknown constraints.
problem Optimization under unknown safety constraints.
method Reliable Frank-Wolfe (Reliable-FW) algorithm for non-convex functions.
result Algorithm finds approximate first-order stationary points safely.
Paper tackles noisy comparison oracle for robust clustering algorithms.
problem Finding robust clustering algorithms under noisy comparison oracle.
method Develops algorithms for k-center clustering and agglomerative hierarchical clustering using noisy comparison oracle.
result Proves robust algorithms achieve good approximation guarantees with high probability.
New method recovers clusters in non-convex finite metric spaces with oracle queries.
problem Exact recovery of clusters in non-convex finite metric spaces.
method Introducing ( β , γ ) (β,γ) ( β , γ ) -convexity and a deterministic algorithm using oracle queries. result Clusters can be recovered using O ( k 2 log n + k 2 ( 6 / β γ ) d e n s ( X ) ) O(k^2 \log n + k^2 (6/βγ)^{dens(X)}) O ( k 2 log n + k 2 ( 6/ β γ ) d e n s ( X ) ) same-cluster queries. New algorithm for online omniprediction with strong guarantees for continuous hypothesis classes.
problem Online adversarial learning with continuous hypothesis classes.
method Developed an oracle-efficient online multicalibration algorithm for infinite benchmark classes.
result First efficient online omnipredictor with strong guarantees for Lipschitz convex loss functions.
Quantum computing speeds up Bermudan option pricing.
problem Efficient pricing of financial derivatives, especially Bermudan options.
method Quantum amplitude estimation combined with Chebyshev interpolation.
result Quadratic speed-up over classical methods.
New algorithm reduces contextual bandit identification to argmax calls.
problem Best-arm identification in stochastic contextual bandits.
method Instance-optimal PAC algorithm using argmax oracle calls.
result First instance-dependent PAC sample complexity for contextual bandits.
New algorithm reduces regret in online learning for piecewise continuous functions.
problem Exponential loss in efficiency when moving from classical to adversarial learning.
method Introduces generalized bracketing numbers and Follow-the-Perturbed-Leader algorithm.
result Optimal scaling of optimization oracle calls with average regret.
In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate O ( 1 ε 2 ) O\left(\frac{1}{\varepsilon^2}\right) O ( ε 2 1 ) improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan an…
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.
Efficiently learns private models using public data.
problem Improving private learning performance with public data.
method Proves computationally efficient algorithms for private learning with public data.
result First computationally efficient algorithms for private learning with public data.
We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K K K actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problem…
New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
problem Thompson Sampling's theoretical limits with greedy approximations in combinatorial semi-bandits.
method Study with greedy oracle, providing lower and upper bounds on regret.
result First theoretical results showing TS can work with greedy approximations, breaking misconceptions.
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.
New algorithm solves complex optimization problems without needing projections.
problem Optimizing nested functions under convex constraints with noisy evaluations.
method Projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization.
result The algorithm achieves ε ε ε -stationary solutions with complexity bounds independent of ε ε ε and T T T .