This paper analyzes regret bounds for Gaussian process Thompson sampling.
problem Analyzing the performance of Gaussian process Thompson sampling (GP-TS) in Bayesian optimization.
method The paper derives several regret bounds for GP-TS, including a lower bound, upper bounds on the second moment of cumulative regret, expected lenient regret, and improved cumulative regret.
result The paper provides improved regret upper bounds for GP-TS, showing that it suffers from a polynomial dependence on 1 / δ 1/δ 1/ δ with probability δ δ δ . New method improves adversarial training robustness.
problem Lack of tight upper bounds for adversarial training.
method Holistic expansion of the network for upper bound minimization.
result RUB and aRUB methods are more robust than state-of-the-art methods.
Paper improves regret bounds for Gaussian process upper confidence bound in Bayesian optimization.
problem Minimizing regret in Gaussian process bandit optimization.
method Gaussian process upper confidence bound (GP-UCB) algorithm with refined analysis.
result Achieves O ( T ln 2 T ) O(\sqrt{T \ln^2 T}) O ( T ln 2 T ) cumulative regret under squared exponential kernel. Optimal volume limit found for Kähler manifolds with positive Ricci curvature.
problem Bounding the volume of Kähler manifolds with positive Ricci curvature.
method Using δ-invariants and Newton--Okounkov bodies.
result Derive the optimal volume upper bound and new characterization of the complex projective space.
Two batch Bayesian optimization algorithms with regret guarantees.
problem Efficiently optimizing multiple objectives in batch feedback settings.
method Gaussian process upper confidence bound and Thompson sampling approaches.
result Frequentist regret guarantees and numerical results.
New lower bounds for gradient methods in strongly convex finite-sum optimization.
problem Developing tight lower bounds for randomized gradient methods in finite-sum optimization.
method Deriving tight lower complexity bounds for SAG, SAGA, SVRG, SARAH, and related methods.
result Tight matches between lower bounds and upper bounds for various methods under specific conditions.
The paper bounds the mean absolute error in DNN vector-to-vector regression.
problem Bounding the mean absolute error in deep neural network based vector-to-vector regression.
method Error decomposition techniques in statistical learning theory and non-convex optimization theory were used to derive upper bounds for approximation, estimation, and optimization errors.
result Theoretical upper bounds for mean absolute error in DNN vector-to-vector regression were derived and validated experimentally.
Sharp bounds found on shortest geodesic on punctured spheres.
problem Finding the shortest closed geodesic on punctured spheres.
method Sharp curvature-free upper bounds expressed in terms of area, extremal metrics described.
result Optimal bounds for spheres with up to four ends, extended to larger numbers of punctures.
Upper bounds for Steklov eigenvalues of warped products are derived.
problem Finding upper limits for Steklov eigenvalues of warped product manifolds.
method Using volume, boundary volume, fiber Laplace eigenvalues, and warping function norms.
result Optimal upper bounds and stability estimates for eigenvalues are obtained.
Study optimal stopping for diffusion processes using data-driven methods.
problem Optimal stopping for diffusion processes under unknown conditions.
method Data-driven approach, deriving upper and lower bounds on simple and cumulative regret.
result Verified minimax optimality and improved convergence rates.
A new method optimizes robustness measures under input uncertainty using randomized Gaussian process upper confidence bound.
problem Optimizing robustness measures under input uncertainty.
method Randomized robustness measure GP-UCB (RRGP-UCB) that samples β from a chi-squared-based distribution.
result RRGP-UCB provides tight bounds on expected regret.
Upper bounds for Steklov eigenvalues derived from intersection indices.
problem Finding upper bounds for Steklov eigenvalues of submanifolds in Euclidean space.
method Using intersection indices of submanifolds and their boundaries.
result Explicit upper bounds involving intersection index, volume, and dimensional constants.
Improves GP models with known bounds for sampling and optimization.
problem Functions with known upper and lower bounds.
method Transforms GP models with bounds for posterior sampling and BO.
result Bounded entropy search (BES) selects points satisfying constraints.
GP-UCB performs suboptimally under certain conditions, as shown by a new regret lower bound.
problem The suboptimality of GP-UCB under polynomial effective optimism.
method Analysis of effective optimism level and new regret lower bound.
result GP-UCB is not minimax optimal under polynomial growth of effective optimism.
Study noise-free kernel bandits, finding upper bounds on regret.
problem Optimizing unknown functions without noise.
method Upper bounds on regret for noise-free kernel-based bandits.
result No order optimal regret bounds are established, conjecture on optimal bound.
Upper and lower bounds on regret for noisy optimization of Brownian motion.
problem Optimizing a one-dimensional Brownian motion with noisy observations.
method Upper bound uses confidence bounds and Markov property; lower bound uses hypothesis testing reduction.
result Upper and lower bounds are tight up to a factor of O ( ( log T ) 1.5 ) O((\log T)^{1.5}) O (( log T ) 1.5 ) . A new upper bound for variational inference improves the efficiency of Bayesian deep learning.
problem Improving variational inference in Bayesian deep learning.
method Presented a new upper bound (EUBO) for evidence, derived from KL-divergence and log marginal likelihood, and used SGD for optimization.
result The new upper bound (EUBO) is tighter than previous methods and outperforms state-of-the-art results in Bayesian neural networks.
Study finds optimal regret bound for multi-armed bandit problem with expert advice.
problem Optimizing decision-making in a multi-armed bandit problem with expert advice.
method Proved a tight lower bound matching the upper bound of Kale (2014) for minimax expected regret.
result The minimax optimal expected regret is Θ(√(T K log (N/K))) for the problem.
Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.
problem Achieving optimal regret bounds for optimistic Hedge in two-player zero-sum games.
method Refined regret analysis and optimization problem formulation.
result Optimistic Hedge achieves O ( log m log n ) O(\sqrt{\log m \log n}) O ( log m log n ) regret bounds, matching upper and lower bounds. On a closed weighted Riemannian manifold with nonnegative Bakry-Émery Ricci curvature, it is shown that the ratio of the k k k -th to first eigenvalues of the weighted Laplacian is dominated by 641 k 2 641k^2 641 k 2 , using an argument via the Cheeger constant. While improving the previous exponential upper bound, the order of k k k here…
Study bounds Neumann and Steklov eigenvalues on manifolds and submanifolds.
problem Bounding Neumann and Steklov eigenvalues on manifolds and submanifolds.
method Using conformal and extrinsic volumes, the paper derives upper bounds for eigenvalues.
result Upper bounds for harmonic mean of Neumann and Steklov eigenvalues.
New algorithms identify best policies in discounted linear MDPs efficiently.
problem Identifying the best policy in discounted linear MDPs with limited samples.
method Derive lower bounds and devise simple yet near-optimal algorithms.
result Upper bound on sample complexity matches existing bounds.
Improved GP bandit algorithms for noiseless, varying noise, and RKHS norms.
problem Minimizing regret in Gaussian process bandits with unknown reward functions.
method New upper bound on maximum posterior variance, refined MVR and PE algorithms.
result Optimal regret bounds for noiseless, varying noise, and RKHS norms.
New bounds for prediction with experts using geometric stopping.
problem Online prediction with expert advice, focusing on geometric stopping.
method Potential-based framework, explicit bounds construction.
result First explicit lower and upper bounds in geometric stopping setting.
Paper establishes lower bounds for non-stationary kernelized bandits.
problem Optimizing functions with noisy observations in non-stationary scenarios.
method Develops algorithm-independent lower bounds for time-varying functions under total variation constraints.
result First algorithm-independent lower bounds for time-varying kernelized bandits.
Generative Flow Networks use submodular upper bounds to generate more data.
problem Generating data from unknown, complex reward functions efficiently.
method Introduce submodular upper bounds to estimate reward, use Optimism in the Face of Uncertainty principle to train GFNs.
result SUBo-GFN generates significantly more data than classical GFNs.
Paper improves stochastic bilevel optimization methods for highly-smooth problems.
problem Finding ε ε ε -stationary points in stochastic bilevel optimization. method Proposes F 2 {}^2 2 SA- p p p methods using p p p th-order finite differences for hyper-gradient approximation. result Achieves upper complexity bound of i l d e O ( p ε − 4 − p / 2 ) ilde{\mathcal{O}}(p ε^{-4-p/2}) i l d e O ( p ε − 4 − p /2 ) for p p p th-order smooth problems. Optimal sampling bounds for various classification losses under different regularization terms.
problem Achieving optimal sampling complexity for classification losses under different regularization terms.
method Proved optimal sampling bounds for a broad class of Lipschitz continuous classification loss functions under various regularization terms.
result Proved k 2 / ε 2 k^2/\varepsilon^2 k 2 / ε 2 upper and lower bounds for ∥ ⋅ ∥ 2 / k \|\cdot\|_2/k ∥ ⋅ ∥ 2 / k regularization, and k / ε 2 k/\varepsilon^2 k / ε 2 upper and lower bounds for ∥ ⋅ ∥ 1 / k \|\cdot\|_1/k ∥ ⋅ ∥ 1 / k regularization. The paper tackles estimating optimal policy value in linear bandits with general context distributions.
problem Estimating the optimal policy value in linear bandits with general context distributions.
method The paper provides lower bounds and an algorithm for sublinear estimation of V ∗ V^* V ∗ under stronger assumptions. result A practical algorithm that estimates a problem-dependent upper bound on V ∗ V^* V ∗ with O ~ ( d ) \widetilde{\mathcal{O}}(\sqrt{d}) O ( d ) samples. The paper achieves nearly optimal regret bounds for contextual multinomial logit bandits.
problem The contextual multinomial logit (MNL) bandit problem with varying rewards.
method Established lower bounds and proposed OFU-MNL+ algorithm with matching upper bounds.
result Achieved minimax optimal regret bounds for both uniform and non-uniform reward settings.
The paper tightens bounds on covering numbers for deep ReLU networks.
problem Characterizing the capacity and performance of deep ReLU networks.
method Derives tight lower and upper bounds on metric entropy of ReLU networks.
result Establishes optimality in nonparametric regression via deep networks.
This paper improves Bayesian optimization by using pseudo-points to enhance model accuracy.
problem Expensive black-box optimization problems, especially in parameter tuning and experimental design.
method Generates pseudo-points to improve Gaussian process models in Bayesian optimization.
result Cumulative regret can be generally upper bounded using the proposed framework.
We introduce a new link invariant called the algebraic genus, which gives an upper bound for the topological slice genus of links. In fact, the algebraic genus is an upper bound for another version of the slice genus proposed here: the minimal genus of a surface in the four-ball whose complement has infinite cyclic fun…
Algorithm optimizes cascaded functions with known structure.
problem Optimizing a function network with known structure.
method GPN-UCB algorithm with upper confidence bounds and theoretical regret bounds.
result Near-optimal cumulative and simple regret bounds.
New policy optimizes product assortment in the presence of unpredictable customers.
problem Optimizing product assortment in the presence of outlier customers.
method Developed a robust online assortment optimization policy using an active elimination strategy.
result Established upper and lower bounds on regret, showing optimality up to logarithmic factor in T T T . New algorithm reduces regret in linear mixture SSPs without cost bounds.
problem Learning optimal paths in stochastic environments with cost constraints.
method Extended value iteration with variance-aware confidence set.
result Achieves nearly minimax optimal regret bound of O ( d B ∗ K ) O(dB_*\sqrt{K}) O ( d B ∗ K ) . Optimal control strategy uses random noise to adaptively control systems with unknown parameters.
problem Online adaptive control of linear quadratic regulator with unknown system parameters.
method Certainty equivalent control with exploratory random noise, refined estimates of system matrices.
result Achieves optimal regret scaling as Θ(√(d_u^2 d_x T)) with self-bounding ODE method.
In this paper, we analyze a generic algorithm scheme for sequential global optimization using Gaussian processes. The upper bounds we derive on the cumulative regret for this generic algorithm improve by an exponential factor the previously known bounds for algorithms like GP-UCB. We also introduce the novel Gaussian P…
Lower bounds found for nonconvex-strongly-concave min-max optimization problems.
problem Finding stationary points in nonconvex-strongly-concave min-max optimization.
method Provided lower bounds for first-order oracle complexity.
result Lower bounds of Ω(√κε⁻²) for deterministic oracles and Ω(√κε⁻² + κ¹/₃ε⁻⁴) for stochastic oracles.
This study tightens bounds on how GD and SGD generalize in smooth convex optimization problems.
problem Understanding how GD and SGD generalize in smooth stochastic convex optimization problems.
method Provided tight excess risk lower bounds for GD and SGD under different conditions.
result Lower bounds suggest overfitting occurs and gaps remain in some cases.
New method makes robust estimators work without knowing corruption levels.
problem Robust estimation algorithms struggle with unknown corruption levels.
method Abstracted geometric puzzle solution to universal meta technique.
result Converts any robust estimator to work without corruption bounds.
New DG method minimizes barycentric alignment and reconstruction loss.
problem Improving domain generalization in machine learning.
method Introduces a new upper bound and WBAE algorithm.
result WBAE outperforms state-of-the-art DG algorithms.
New bounds on adaptivity cost in stochastic optimization.
problem Understanding the cost of changing strategies in stochastic optimization.
method Proving impossibility results for adaptivity in non-smooth stochastic convex optimization.
result Lower bounds on the price of adaptivity for different levels of uncertainty.
New algorithm for identifying optimal arms in stochastic bandit problems.
problem Optimal arm identification in stochastic bandit problems with many arms.
method Characterized optimal learning rates and provided algorithms with matching bounds.
result Lower bounds and matching upper bounds for cumulative regret and best-arm identification.
The standard approach to supervised classification involves the minimization of a log-loss as an upper bound to the classification error. While this is a tight bound early on in the optimization, it overemphasizes the influence of incorrectly classified examples far from the decision boundary. Updating the upper bound …
Study learns optimal auctions from corrupted or perturbed bidder valuation samples.
problem Learning revenue-optimal auctions from corrupted or perturbed samples.
method Proves upper bounds, proposes algorithms for learning near-optimal auctions.
result Proves tight upper bounds and proposes algorithms for near-optimal auctions.
It is a theorem of Bers that any closed hyperbolic surface admits a pants decomposition consisting of curves of bounded length where the bound only depends on the topology of the surface. The question of the quantification of the optimal constants has been well studied and the best upper bounds to date are linear in ge…
Upper bounds on fixed points in PWL neural networks with hyperplane analysis.
problem Analyzing the number of fixed points in neural networks with PWL activation.
method Hyperplane arrangements to bound the number of fixed points.
result Upper bounds on the number of fixed points for PWL networks, showing exponential growth in layers.