Optimization of very expensive black-box functions requires utilization of maximum information gathered by the process of optimization. Model Guided Sampling Optimization (MGSO) forms a more robust alternative to Jones' Gaussian-process-based EGO algorithm. Instead of EGO's maximizing expected improvement, the MGSO use…
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.
169,291 papers · 148 categories
Trend · papers per month
48 results for “sample-optimal algorithms”
Optimizes decisions without knowing the true distribution using historical data.
problem Optimizing decisions without knowing the true distribution.
method Combines sampling and bisection search algorithms to solve an optimization problem.
result Proves sufficient conditions for local out-of-sample optimality.
Quantum algorithms improve reinforcement learning policies.
problem Optimizing decision-making in environments with unknown dynamics.
method Combining quantum value iteration with quantum mean estimation and maximum finding.
result Improved query complexities for computing optimal policies.
Efficiently estimates prediction error in regression with Gaussian covariates under privacy constraints.
problem Private regression with Gaussian covariates under differential privacy constraints.
method Sum-of-Squares framework combined with robust estimators.
result Sample-optimal private regression algorithm with optimal error rates.
Efficiently allocate budgets for LLM-assisted virtual screening to reduce costs.
problem Reducing the cost of evaluating alternatives in large-scale screening tasks.
method Propose a top- greedy evaluation mechanism and the EFG- algorithm for efficient budget allocation.
result Prove that EFG- is both sample-optimal and consistent in large-scale virtual screening.
Optimizes Q-learning for MDPs with linear features, achieving sample efficiency.
problem Finding optimal policies in large-scale MDPs with limited samples.
method Parametric Q-learning with linearly additive features, exploiting monotonicity and noise structure.
result Proves sample optimality with samples for -optimality.
Efficiently learns tree-structured Ising models with minimal samples.
problem Learning tree-structured Ising models efficiently and accurately.
method Plug-in estimator for mutual information using the Chow-Liu algorithm.
result Proper learning of tree-structured Ising models with samples.
Unified plug-in approach for estimating symmetric properties of distributions efficiently.
problem Estimating symmetric properties of distributions with high accuracy and efficiency.
method Profile-maximum-likelihood (PML) based estimator.
result Achieves theoretical limit for universal symmetric property estimation.
Protocol learns pure quantum states with minimal disturbance.
problem Efficiently learn quantum states with minimal disturbance.
method Sequential measurements with minimal disturbance.
result Achieves maximal precision with polylogarithmic regret.
Optimal testing of discrete distributions with high probability, achieving sample complexity bounds.
problem Testing discrete distributions with high probability accuracy.
method Characterizing sample complexity as a function of parameters like δ, providing sample-optimal testers.
result Optimal algorithms for closeness and independence testing, achieving within constant factors of information-theoretic lower bounds.
Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithmscs.LG
This paper solves the best arm identification problem with both quick commitment and reward maximization.
problem Simultaneously identifying the best arm and minimizing regret in a stochastic Multi-Armed Bandit problem.
method Introduces Regret Optimal Best Arm Identification (ROBAI) and presents algorithms EOCP and its variants.
result Achieves asymptotic optimal regret and quick commitment to the optimal arm in both pre-determined and adaptive stopping times.
New sampling algorithm for non-smooth potentials.
problem Sampling from non-smooth potentials.
method Proximal algorithm based on rejection sampling.
result Achieves better complexity than existing methods.
We analyze a new Markov chain model for better sampling and optimization.
problem Developing a new Markov chain model for improved sampling and optimization.
method We introduce a new class of Ito chains with arbitrary noise and inexact drift/diffusion coefficients, proving a bound in -distance.
result Our analysis provides improved or first results for various applications like SGLD, sampling, and boosting.
LoCoV reduces portfolio optimization errors from sample covariance matrices.
problem Large errors in sample covariance matrix for optimal portfolio weights.
method LoCoV (low dimension covariance voting) algorithm to reduce these errors.
result LoCoV outperforms classical methods in portfolio optimization experiments.
Sampling can be faster than optimization in nonconvex settings.
problem Limited theoretical understanding of optimization vs sampling efficiency.
method Examined nonconvex objective functions in mixture modeling and multi-stable systems.
result Sampling algorithms are linearly scalable in model dimension, while optimization algorithms are exponentially scalable.
Optimal algorithm finds if point is in convex hull of distributions.
problem Determining if a point is inside the convex hull of means of multiple distributions.
method Thompson-CHM algorithm with modular design of stopping and sampling rules.
result First asymptotically optimal algorithm for CHM problem in one dimension.
A simple algorithm for Gaussian mean testing with optimal sample complexity.
problem Distinguishing between standard Gaussian and other Gaussian distributions with unknown mean and covariance.
method An extremely simple algorithm with a one-page analysis.
result Optimal sample complexity of Θ(√d/ε^2) with sample linear time.
Efficiently learns Gaussian tree models with near-optimal sample complexity.
problem Learning tree-structured Gaussian distributions efficiently.
method Conditional mutual information tester for Gaussian variables, near-optimal sample complexity.
result Near-optimal sample complexity for structure learning of Gaussian tree models.
Two statistical tasks are shown to have equivalent sample complexity.
problem Determining if a function depends on only a few variables and identifying those variables.
method Proved statistical equivalence of feature selection and junta testing through sample complexity analysis.
result Brute-force algorithm is sample-optimal for both tasks with optimal sample size.
This paper develops a scalable Thompson Sampling method using optimal transport.
problem Efficiently approximating posterior distributions for complex models in Thompson Sampling.
method The approach uses distribution optimization techniques via Wasserstein gradient flows to approximate posterior distributions efficiently.
result The proposed method achieves superior performance on both synthetic and real large-scale data.
We solve learning mixtures of graphs from epidemic cascades, establishing conditions and algorithms.
problem Learning the weighted edges of a balanced mixture of two undirected graphs from epidemic cascades.
method Established necessary and sufficient conditions for polynomial-time solvability, provided efficient algorithms with optimal sample complexity.
result First rigorous conditions and algorithms for learning graph mixtures from epidemic cascades.
New algorithms for sampling and optimization without tuning.
problem Efficient sampling and optimization over probability measures.
method Optimization on the space of probability measures, using gradient flows.
result Strong theoretical guarantees and similar performance to optimally tuned algorithms.
Sparse GCA finds linear relationships in multiple datasets, using gradient descent.
problem Finding linear relationships across multiple datasets with sparse loading vectors.
method Formulated as generalized eigenvalue problems, used a thresholded gradient descent algorithm.
result Proposed algorithm yields tight estimation error bounds and demonstrates effectiveness on synthetic datasets.
Optimizes sample and round complexity in adaptive sampling from multiple distributions.
problem Adaptive sampling from multiple distributions with limited rounds and samples.
method Introduces OODS framework and analyzes tradeoffs between sample and round complexity.
result Achieves near-optimal sample complexity and sub-polynomial round complexity.
Quantum algorithm speeds up learning from big data exponentially.
problem Scalable learning from big data with optimized random features.
method Quantum algorithm for sampling optimized random features.
result Exponential speedup in runtime compared to classical algorithms.
Improved Thompson Sampling outperforms existing Bayesian optimization methods.
problem Thompson Sampling's performance in Bayesian optimization is suboptimal compared to other methods.
method Developed Stagger Thompson Sampler (STS), which more precisely samples the optimal arm with less computation.
result STS outperforms TS, PSS, and other acquisition methods in various optimization tasks.
New algorithms bound graph structure sampling and learning high-dimensional graphical models.
problem Learning high-dimensional graphical models and efficient graph structure sampling.
method Online learning framework with exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters using log loss function.
result New sample complexity bounds and efficient algorithms for learning Bayes nets, including trees and chordal skeletons.
Improved analysis shows Maillard sampling achieves optimal regret bounds.
problem Optimal regret bounds for K-armed bandit problem.
method Improved analysis of Maillard sampling (MS) to achieve asymptotical optimality and minimax regret bound.
result MS achieves both asymptotical optimality and minimax regret bound of √(KT log T).
Top-two algorithm improved for best-k-arm selection.
problem Best-k-arm identification in multi-armed bandits.
method Information-directed selection based on dual variables.
result Top-two Thompson sampling with IDS is asymptotically optimal.
Scalable verifier for recurrent neural networks using polyhedral abstractions.
problem Certifying the correctness of recurrent neural networks.
method Combining sampling, optimization, and Fermat's theorem for polyhedral abstractions; gradient descent for refinement.
result Successfully verified challenging recurrent models in various domains.
Combines machine learning and optimization for real-time decision-making.
problem Optimizing decisions in contextually constrained problems.
method Generative model combining interior point methods and adversarial learning.
result Generative model produces optimal decisions with in-sample and out-of-sample guarantees.
Improved function approximation for noisy data.
problem Efficient estimation of conditional expectations from highly polluted data.
method Hybrid approach combining Christoffel sampling and optimal experimental design.
result Improved computational efficiency and sample complexity compared to existing methods.
Optimizes noisy IS with better proposal densities.
problem Improving IS estimators with noisy data.
method Derives optimal proposal densities considering noise variance.
result Optimal proposals enhance IS estimators by focusing on noisy regions.
Boosting with unlabeled data achieves optimal sample complexity in agnostic settings.
problem Boosting's sample inefficiency in agnostic learning.
method Designing an agnostic boosting algorithm with unlabeled data to match ERM's sample complexity.
result The total sample complexity is optimal, with a vanishing fraction needing to be labeled.
Bandits roaming Hilbert spacequant-ph
The thesis optimizes quantum state exploration using bandit algorithms.
problem Maximizing reward in online learning of quantum state properties.
method Multi-armed bandit approach to select observables, minimizing regret.
result Optimal strategies with matching upper and lower bounds for regret.
EM algorithm achieves optimal sample complexity for well-separated Gaussian mixtures.
problem Estimating parameters of well-separated Gaussian mixtures.
method New EM convergence proof for well-separated Gaussian mixtures.
result EM algorithm converges with separation, achieving samples.
New algorithm approximates distributions with near-linear time and optimal sample efficiency.
problem Approximating distributions from samples efficiently and accurately.
method Near-linear-time estimator for distributions using universal polynomial approximation.
result Establishes for all , achieving optimal approximation.
Unified framework for set-valued classification tackles ambiguous multi-class datasets.
problem Ambiguous multi-class datasets in modern statistics.
method Unified statistical framework encompassing various set-valued classification formulations.
result Infinite sample optimal strategies and plug-in principle for data-driven algorithms.
Paper addresses RLHF alignment challenges with novel algorithms.
problem Challenges in RLHF alignment, especially in strategic exploration.
method Develops a reverse-KL regularized contextual bandit formulation and proposes efficient algorithms with theoretical guarantees.
result Proposed methods significantly outperform existing RLHF algorithms in real-world experiments.
Pessimistic model-based algorithm finds Nash equilibria in zero-sum Markov games from offline data.
problem Learning Nash equilibria in two-player zero-sum Markov games from limited data.
method Pessimistic model-based algorithm with Bernstein-style lower confidence bounds (VI-LCB-Game).
result Proves sample complexity no larger than , achieving minimax optimality.
Two new sampling methods improve machine learning optimization.
problem Efficiently solving machine learning empirical risk minimization problems.
method Randomly sampled quasi-Newton methods for optimization.
result Sampled methods outperform classical variants in machine learning tasks.
New algorithm finds optimal policies without knowing reward functions.
problem Reward-agnostic exploration in reinforcement learning.
method Designs an algorithm that explores without reward information, achieving minimax optimality.
result Achieves provable minimax optimality in finding optimal policies for multiple reward functions.
Improved sample complexity for learning halfspaces with malicious noise.
problem Efficiently learning halfspaces in the presence of malicious noise.
method New analysis of Awasthi et al. algorithm with matrix Chernoff inequality and localization schemes.
result Achieved near-optimal sample complexity of for isotropic log-concave distributions.
We consider the problem of learning the underlying graph of an unknown Ising model on p spins from a collection of i.i.d. samples generated from the model. We suggest a new estimator that is computationally efficient and requires a number of samples that is near-optimal with respect to previously established informatio…
On Next-Token Prediction in LLMs: How End Goals Determine the Consistency of Decoding Algorithmsstat.ML
This paper examines how different decoding algorithms for LLMs align with various goals.
problem Consistency of decoding algorithms with different goals in LLMs.
method Analysis of greedy, lookahead, random sampling, and temperature-scaled random sampling algorithms.
result Random sampling is consistent with the true probability distribution, but other goals require optimal algorithms for specific probability distributions.
This survey explores various optimality concepts in importance sampling.
problem Designing optimal proposal densities for Monte Carlo methods.
method Review of multiple frameworks and theoretical comparisons.
result Comprehensive understanding of optimality in importance sampling.
Geometric methods solve sampling, optimisation, inference, and adaptive decision-making.
problem Efficient solutions for sampling, optimisation, inference, and adaptive decision-making.
method Derive algorithms exploiting geometric structures of Hamiltonian systems, Hilbertian subspaces, and information geometry.
result Wide range of geometric theories emerge in these fields, enabling efficient solutions.
A new framework controls false alarms in multi-A/B tests.
problem Controlling false alarms in multiple A/B tests over time.
method Replace A/B tests with MAB instances, monitor with online FDR.
result Achieves low sample complexity and online FDR control.