New bounds on complexity for finding near-stationary points in stochastic convex optimization.
problem Finding near-stationary points in stochastic convex optimization.
method Joint analysis of local stochastic oracle and global oracle models; extensions of recursive regularization technique.
result Logarithmic dependence on smoothness in global oracle model for finding near-stationary points.
New model shows online and statistical learning are computationally equivalent with optimization oracle.
problem Online learning in non-convex games with adversarial settings.
method Strengthening the oracle model to make online and statistical learning computationally equivalent.
result Efficient computation of non-convex game equilibria, including GANs, with optimization oracle.
Paper addresses online alignment of large language models under uncertain preference feedback.
problem Online alignment of large language models with misspecified preference feedback.
method Formulates an oracle-robust objective as a worst-case optimization problem for log-linear policies, and develops projected stochastic composite updates.
result Shows that the robust objective admits an exact closed-form decomposition and achieves O ~ ( ε − 2 ) \widetilde{O}(\varepsilon^{-2}) O ( ε − 2 ) oracle complexity. 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.
Quantum oracles help identify counterfactuals better than classical ones.
problem Identifying unknown causal parameters in causal models.
method Using quantum oracles to query and identify all causal parameters and counterfactuals.
result Quantum oracles enable identification of all two-way joint counterfactuals and tighter bounds on higher-order counterfactuals.
Paper studies how to cluster data with a weak oracle, reducing the number of queries needed.
problem Cluster data with limited oracle answers.
method Proposes algorithms for semi-supervised active clustering with weak oracles.
result Shows that a small number of queries is sufficient for effective clustering.
New oracle Search improves active learning performance exponentially.
problem Enhancing active learning with limited oracle access.
method Combines Label and Search oracles for better decision-making.
result Exponential improvement in problem-solving performance.
The paper tackles sequential mode estimation with oracle queries.
problem Adaptively PAC-learning a probability distribution's mode.
method Two query models: index queries and pair queries. Sequential algorithms for mode estimation.
result Lower bounds on optimal query complexity for both models.
An algorithm learns from multiple models to match an oracle's risk.
problem Learning from multiple noisy models to estimate a target parameter.
method Elimination rounds algorithm for adaptive learning.
result Risk of weak-oracle learner matches that of an oracle in multiple source case.
Paper proposes handling uncertainties in clustering supervision.
problem Ineffective human oracles in answering all clustering queries.
method Introduces weak oracles that can answer 'not sure' and proposes an algorithm to use these answers effectively.
result Small query complexity is sufficient for effective clustering with high probability.
New algorithm tackles contextual bandits with a regression oracle.
problem Designing practical and theoretically sound algorithms for contextual bandits.
method Leverages a regression oracle to combine realizability-based and agnostic methods.
result Achieves low regret under certain assumptions and comparable/superior performance in empirical evaluations.
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.
New RLHF framework handles general preference oracles without reward functions.
problem Handling general preference oracles without assuming a reward function.
method Developed a minimax game between two LLMs for RLHF under a general preference oracle, focusing on KL-regularized preference.
result Proposed algorithms for efficient offline and online RLHF learning.
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.
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 ( 256 d ) O(256^d) O ( 25 6 d ) mistakes, simpler proof. result No algorithm can make less than 3 d 3^d 3 d mistakes. 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. Bayesian strategy selects efficient portfolios outperforming market.
problem Selecting efficient portfolios in an inefficient market.
method Bayesian multiple testing with discrete-mixture and hierarchical Bayes models.
result Bayes Oracle test provides upper bound of type-II error and uniformly better power for k-factor models.
Novel framework learns efficient student models from teacher networks.
problem Model capacity gap between teacher and student networks.
method Neural architecture search and oracle knowledge distillation.
result Searched student models often outperform teacher models.
New algorithms for efficient reinforcement learning with rich observations.
problem Efficient reinforcement learning with rich observations in environments with deterministic dynamics.
method Oracle-efficient algorithms using standard optimization primitives.
result Proved sample efficiency and presented examples of challenges.
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.
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.
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.
The study sets up a framework to analyze parallel optimization problems with graph dependencies.
problem Analyzing the complexity of parallel stochastic optimization problems with graph dependencies.
method Developed a graph oracle-based framework to derive lower bounds and highlight gaps.
result Identified gaps between lower and upper bounds for specific parallel optimization settings.
Paper tackles interactive learning with noisy labels and comparisons, showing how comparison oracles can improve learning efficiency.
problem Interactive learning with noisy labels and comparisons.
method Characterizes comparison oracle as threshold function learning problem, presents algorithm with query complexity analysis.
result Lower bounds show almost optimal label and total query complexity.
New method removes oracle and reduces memory usage for robust MDPs.
problem Applying robust MDPs in practice due to model estimation and oracle requirements.
method Transformed robust MDPs into an alternative form allowing stochastic gradient methods and model-free approach.
result Sample-efficient algorithm with lower storage requirement and no oracle.
Paper introduces structured sparsity estimators for Generalized Linear Models.
problem Estimating structured sparsity in GLMs with debiased estimators.
method Extends Stucky and van de Geer's results to GLMs with structured sparsity.
result Proves oracle inequalities for structured sparsity estimators in GLMs.
A model learns from valid examples while avoiding invalid ones to generate better data.
problem Generative models produce nonsense when fitting to observed data.
method Active distribution learning using an invalidity oracle.
result Improper distribution learning can be done with polynomial queries, unlike proper learning which requires exponentially many.
Estimates heavy hitters in data streams with queries, balancing accuracy and efficiency.
problem Identifying elements with high probability in i.i.d. samples.
method Sequential estimation algorithms for two query models: index and pair queries.
result Upper and lower bounds on query complexity for different distributions and noise models.
Spatial metamodels improve root finding in uncertain oracle responses.
problem Finding roots in noisy, location-dependent oracle responses.
method Propose spatial metamodels to infer oracle distribution and update Bayesian knowledge.
result Spatial PBA algorithm outperforms earlier models in synthetic and real-world problems.
New oracle uses uncertainty for active classification with noisy feedback.
problem Improving query complexity in interactive binary classifier learning.
method Proposes a new pairwise comparison oracle that considers uncertainty and an adaptive labeling algorithm.
result Demonstrates improved performance and efficiency compared to existing methods.
Study on costs of manipulating AMM-based price oracles.
problem Cost of manipulation in AMM-based on-chain price oracles.
method Analyzes the robustness of AMM-based oracles to strategic manipulation, considering different aggregation methods and market conditions.
result Manipulation costs depend on the total quote depth and can be minimized by optimal liquidity weights.
SoQal reduces oracle label requests in active learning by up to 35%.
problem Exploiting unlabelled data in healthcare requires costly oracle labeling.
method Dynamic questioning strategy to minimize oracle label requests.
result SoQal reduces oracle label requests by up to 35%.
Combines RL and imitation learning with oracle to optimize policies.
problem Optimizing policies in complex environments with limited oracle accuracy.
method Truncated Horizon Policy Search (THOR) using reward shaping.
result THOR achieves superior performance compared to RL and IL baselines.
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.
New oracles improve stochastic optimization with noisy or biased measurements.
problem Optimizing functions with noisy or biased measurements.
method Introduced biased gradient oracles for stochastic optimization, analyzed RSG and SGD algorithms with these oracles.
result Derived non-asymptotic bounds for convergence rates of algorithms with biased gradient oracles.
Generative model improves safety in self-driving simulators and human motion generation.
problem Improving generative models for constrained domains like safety-critical applications.
method Developed Gen-neG, a denoising diffusion model that uses oracle-assisted guidance.
result Empirically validated Gen-neG for collision avoidance and safety-guarded human motion generation.
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.
Study finds on-chain data can proxy off-chain cryptocurrency pricing.
problem Develop methods to proxy off-chain cryptocurrency pricing using on-chain data.
method Graphical models, mutual information, and ensemble machine learning.
result A significant amount of pricing information is contained in on-chain data, but precise prices are hard to recover except on short time scales.
Framework combines generative and predictive models for input design.
problem Maximizing or achieving specified values of properties given stochastic oracles.
method Probabilistic modeling and adaptive sampling algorithm.
result Substantially outperforms other methods in experimental tests.
New research shows label refinement and weak training have limitations for aligning LLMs.
problem Limitations of refinement methods for aligning large language models.
method Analyzed probabilistic assumptions and alternative approaches to label refinement and weak training.
result Label refinement and weak training suffer from irreducible error, leaving a performance gap.
Efficient model selection framework for online learning without parameter tuning.
problem Model selection in online learning without predefined parameters.
method Generic meta-algorithm framework for model selection in arbitrary Banach spaces under mild smoothness assumptions.
result First computationally efficient parameter-free algorithms in arbitrary Banach spaces.
The article studies a combined L 1 L_1 L 1 and concave regularization method for high-dimensional models.
problem Tackles variable selection and prediction in high-dimensional settings.
method Uses combined L 1 L_1 L 1 and concave penalties to optimize model sparsity and prediction risk. result Global optimum of the method achieves oracle prediction risk and false sign rate bounds.
New algorithm learns efficiently with a simple 'yes/no' oracle.
problem Can efficient learning be achieved with a simpler oracle than ERM?
method Developed an oracle that returns 'yes' or 'no' for realizable datasets.
result Learnability is possible with a polynomial price in VC dimension.
Study of clustering with noisy queries, providing lower bounds and efficient algorithms.
problem Recovering true clustering from noisy oracle queries.
method Information theoretic lower bounds, novel algorithms for adaptive and non-adaptive settings.
result First algorithms matching query complexity lower bound, computationally efficient.
New model for learning from noisy human comparisons, improving search efficiency.
problem Designing efficient algorithms for content search with noisy human feedback.
method Introducing a weak oracle model for comparison-based queries and developing WORCS-I and WORCS-II algorithms.
result Provable algorithms locating target objects with close to entropy of target distribution.
New algorithm for clustering with faulty oracle achieves optimal queries and efficiency.
problem Clustering with a faulty oracle, especially for multiple clusters.
method Built on stochastic block model, provides nearly-optimal query complexity.
result Time-efficient algorithm with nearly-optimal query complexity for all constant k and any δ.
New study shows Gaussian samplers struggle with heavy-tailed targets, while stable samplers excel.
problem The difficulty of sampling from heavy-tailed distributions using Gaussian versus stable oracles.
method Comparison of Gaussian and stable oracles for proximal samplers.
result Gaussian samplers have a fundamental barrier for high-accuracy guarantees in heavy-tailed sampling, while stable samplers excel.
Average Oracle outperforms DCC+NLS in portfolio optimization.
problem Optimizing portfolio performance in volatile markets.
method Comparing the Average Oracle to various DCC+NLS variants.
result The Average Oracle consistently yields higher Sharpe ratios.