This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistence, and e…
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,341 papers · 148 categories
Trend · papers per month
48 results for “logarithmic lower bound”
Paper proves tight lower bounds for online multicalibration, separating it from marginal calibration.
problem Proving lower bounds for online multicalibration in relation to marginal calibration.
method Information-theoretic approach, constructing group families from orthonormal bases.
result Establishes tight lower bounds for online multicalibration, matching upper bounds up to logarithmic factors.
Sharp rigidity for quasilinear Liouville equation on manifolds with nonnegative Ricci curvaturemath.AP
Sharp rigidity theorem for quasilinear Liouville equation on manifolds with nonnegative Ricci curvature.
problem Characterizing solutions to the quasilinear Liouville equation on manifolds with nonnegative Ricci curvature.
method Using a sharp logarithmic lower bound and a sharp upper bound on the total volume of the solution.
result If a solution satisfies a specific logarithmic lower bound, the manifold is isometric to Euclidean space and the solution is a standard bubble solution.
New bounds for Bayesian bandits show prior improves performance.
problem Improving regret bounds for Bayesian bandits.
method Upper confidence bound algorithm with finite-time logarithmic regret bounds.
result Derives and upper bounds for Bayesian bandits.
The paper analyzes Q-learning in 2-player Markov games and provides gap-dependent logarithmic regret bounds.
problem Analyzing the cumulative regret of Nash Q-learning in 2-player turn-based stochastic Markov games.
method Proposed gap-dependent logarithmic upper bounds for cumulative regret in episodic tabular setting and discounted game setting.
result The proposed bounds match theoretical lower bounds up to a logarithmic term.
This paper tightens the law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
problem Developing nonasymptotic concentration bounds for empirical KL_inf with optimal constants and rates.
method Presenting a tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
result A tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
We analyze the problem of sequential probability assignment for binary outcomes with side information and logarithmic loss, where regret---or, redundancy---is measured with respect to a (possibly infinite) class of experts. We provide upper and lower bounds for minimax regret in terms of sequential complexities of the …
Logarithmic regret for continuous-time reinforcement learning.
problem Continuous-time Markov decision processes with unknown transition probabilities and holding times.
method Upper confidence reinforcement learning, mean holding time estimation, stochastic comparison of point processes.
result Logarithmic regret bound achieved in finite time.
Directly proves logarithmic systolic growth for all hyperbolic surfaces.
problem Proving logarithmic systolic growth for all hyperbolic surfaces.
method Using original Brooks/Buser-Sarnak surfaces through a direct approach.
result Directly proves logarithmic systolic growth for all hyperbolic surfaces.
Lower bound on colors needed for non-zero determinant links.
problem Finding the minimum number of colors for non-zero determinant links.
method Proved a lower bound using logarithmic function.
result Minimal number of colors is at least 1 + log2(n).
Prove rigidity and classification results for quasilinear Liouville equation on manifolds with nonnegative Ricci curvature.
problem Quasilinear Liouville equation on manifolds with nonnegative Ricci curvature.
method Prove rigidity and classification results for the quasilinear Liouville equation associated with the -Laplacian on complete noncompact Riemannian manifolds with nonnegative Ricci curvature.
result Under a sharp logarithmic lower bound, the ambient manifold must be isometric to the Euclidean space and the solution must be one of the standard bubbles.
Study proves a tight lower bound for MNL-Bandit assortment selection problems.
problem Dynamic assortment planning under MNL bandit model with capacity constraints.
method Proved a tight lower bound on accumulated regret for all parameters.
result Tight lower bound matches existing upper bounds up to logarithmic factors.
Logarithmic regret achieved in Q-learning with positive gap.
problem Achieving logarithmic cumulative regret in Q-learning with positive sub-optimality gap.
method Optimistic Q-learning with logarithmic regret bound.
result Logarithmic cumulative regret bound proven for optimistic Q-learning.
Study on regret minimization in deterministic MDPs.
problem Minimizing regret in deterministic reinforcement learning.
method Logarithmic regret lower bounds, leveraging graph theory and cycles.
result Explicitly quantifies the fundamental limit of performance achievable by any learning algorithm.
We show that gradient shrinking, expanding or steady Ricci solitons have potentials leading to suitable reference probability measures on the manifold. For shrinking solitons, as well as expanding soltions with nonnegative Ricci curvature, these reference measures satisfy sharp logarithmic Sobolev inequalities with low…
Paper tightens lower bounds on decentralized training complexity.
problem Understanding and optimizing iteration complexity in decentralized training.
method Proved a tight lower bound on iteration complexity and proposed DeTAG algorithm.
result DeTAG achieves the theoretical lower bound with only a logarithmic gap.
In this paper, we consider low rank matrix estimation using either matrix-version Dantzig Selector or matrix-version LASSO estimator . We consider sub-Gaussian measurements, , the measurements have sub-Gaussian entries. Suppose $\textrm…
Study sparsity benefits in infinite feature contextual bandits.
problem Minimizing regret in infinite feature contextual bandits.
method Novel reduction to multi-armed bandits, Feel-Good Thompson Sampling algorithm.
result Regret bounds match lower bounds up to logarithmic factors, logarithmic dependence on effective features.
New method tackles bilevel optimization with polyhedral constraints.
problem Challenges in bilevel optimization with active-set changes and expensive Hessian inversions.
method Logarithmic barrier smoothing and proxy-gradient algorithm for differentiable approximation.
result Stationarity rates of in deterministic setting and under stochastic noise.
Paper explores entropic curvature in Markov chains, comparing it to other curvatures.
problem Comparing entropic curvature to other curvatures in Markov chains.
method Adapted Γ-calculus for θ-curvatures, explicit lower bounds, curvature perturbation.
result Entropic curvature differs significantly from other curvature notions.
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.
Study heat flow on changing surfaces, proving existence and uniqueness.
problem Existence and uniqueness of heat flow on time-varying manifolds.
method Establishes estimates for heat flow under minimal assumptions, focusing on logarithmic derivative of volume measure.
result Proves estimates hold for Ricci flow with scalar curvature bounded below, dependent only on initial data.
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.
New algorithm reduces regret in linear bandits by nearly optimal factors.
problem Optimizing regret in linear contextual bandits with limited actions.
method Variable-Confidence-Level (VCL) SupLinUCB algorithm.
result Regret matches minimax lower bound with iterated logarithmic factors.
New algorithm reduces regret in bandits with occasional free observations.
problem Reducing regret in bandit problems with occasional free observations.
method Developed an algorithm with a regret bound of Σ_i (log(1/ε) / Δ_i) up to constants and loglog terms.
result Proved that the algorithm's regret is optimal, matching lower bounds.
We study the Seiberg-Witten equations on surfaces of logarithmic general type. First, we show how to construct irreducible solutions of the Seiberg-Witten equations for any metric which is "asymptotic" to a Poincaré type metric at infinity. Then we compute a lower bound for the -norm of scalar curvature on these…
Random surfaces with long systoles created from graph theory ideas.
problem Finding surfaces with long systoles.
method Two constructions inspired by graph theory.
result Proved a new lower bound on systole length.
Study minimax regret in sequential probability assignment with and without side information.
problem Minimax regret analysis in sequential probability assignment.
method Upper and lower bounds on minimax regret using square-root entropy.
result Lower bound matches upper bound for Donsker classes, up to log factors.
Improved regret bounds for bandits with expert advice.
problem Optimizing decision-making in environments with expert advice.
method Proved lower and upper bounds for regret in restricted and standard feedback models.
result Proved a new upper bound of order for the worst-case regret, matching a previously known lower bound.
Improved GNN simulation of WL test with exponentially lower complexity.
problem Improving the complexity of simulating the Weisfeiler-Lehman test with GNNs.
method Exponentially lower complexity simulation of WL test using GNNs with polylogarithmic parameters and O(log n) bits feature vectors.
result Near-optimal construction with logarithmic lower bounds for feature vector length and neural network size.
Logarithmic regret achieved in RL with linear function approximation.
problem Achieving logarithmic regret in reinforcement learning with linear function approximation.
method LSVI-UCB for linear MDP assumption, UCRL-VTR for linear mixture MDP assumption.
result Logarithmic regret bounds established for RL with linear function approximation.
Improved uniform convergence bound with fat-shattering dimension reduces sample complexity gap.
problem Gap between upper and lower bounds on sample complexity for fat-shattering dimension.
method Provided an improved uniform convergence bound.
result Closed the gap between existing upper and lower bounds on sample complexity.
The paper tackles sequential learning with Gaussian payoffs and side observations, providing lower bounds and algorithms.
problem Sequential learning with Gaussian payoffs and side information.
method Non-asymptotic lower bounds and algorithms for minimizing regret.
result Proved non-asymptotic lower bounds and provided algorithms achieving these bounds.
Optimizes quantile and semi-adversarial regret with novel root-logarithmic regularizers.
problem Minimizes regret in adversarial and semi-adversarial online learning.
method FTRL with root-logarithmic regularizers for quantile and semi-adversarial settings.
result Achieves minimax optimal regret bounds in both paradigms.
The paper improves regret lower bounds for communicating MDPs.
problem Regret lower bounds for communicating MDPs.
method Lower bound proof and optimization problem formulation.
result Regret lower bound becomes significantly more complex in communicating MDPs.
The paper improves estimates of eigenfunctions and nodal sets on manifolds with nonpositive sectional curvature.
problem Improving estimates of eigenfunctions and nodal sets on manifolds with nonpositive sectional curvature.
method Combining Toponogov's triangle comparison theorem and propagation of singularities arguments.
result Logarithmic improvements of eigenfunction and nodal set estimates.
New lower bounds for private covariance estimation of Gaussian distributions are proven.
problem Proving tight lower bounds for private estimation tasks under differential privacy.
method Generalized fingerprinting method for exponential families and private Assouad method.
result Tight lower bounds for private covariance estimation in Frobenius and spectral norms.
Lower bounds on Bayes risk for realizable models derived using information theory.
problem Deriving lower bounds on Bayes risk for realizable machine learning models.
method Information-theoretic analysis using rate-distortion theory and mutual information.
result Lower bounds on Bayes risk for realizable models, matching known bounds up to logarithmic factors.
New bounds reveal double exponential growth in conjugacy classes of fully irreducibles.
problem Counting conjugacy classes of fully irreducibles in Out(F_r).
method Equivalence to pseudo-Anosovs and logarithmic dilatations.
result Double exponential growth in the number of conjugacy classes.
Study Kähler-Einstein potentials on stable varieties near singularities
problem Asymptotic behavior of Kähler-Einstein potentials on stable varieties near singularities
method Using iterated logarithmic functions and refined lower bounds
result Improved estimates for Kähler-Einstein potentials
The paper sets bounds on how much regret is unavoidable in adaptive LQR with unknown B-matrix.
problem Understanding the limits of adaptive LQR with unknown B-matrix.
method Local asymptotic minimax regret lower bounds using van Trees' inequality and Bellman error representation.
result Logarithmic regret is impossible if the parametrization induces an uninformative optimal policy.
Study on statistical estimation over Gaussian MAC, comparing analog and digital schemes.
problem Distributed minimax statistical estimation over a Gaussian MAC.
method Developed analog joint estimation-communication schemes and derived information-theoretic lower bounds.
result Achieved risk within a logarithmic factor of information-theoretic lower bounds.
The paper extends statistical estimation techniques under differential privacy.
problem Establishing sample complexity bounds for estimation tasks under differential privacy.
method Proposes analogues of Le Cam's method, Fano's inequality, and Assouad's lemma under central differential privacy.
result Optimal sample complexity bounds for discrete distribution estimation under total variation and distances.
This paper establishes lower bounds for smooth nonconvex finite-sum optimization.
problem Understanding the complexity of finding optimal solutions in nonconvex finite-sum optimization.
method Proving tight lower bounds for the complexity of finding ε-suboptimal points and ε-approximate stationary points.
result Existing algorithms achieve optimal IFO complexity up to logarithmic factors.
Study shows sample complexity for learning optimal policies in SSP with generative model.
problem Learning optimal policies in Stochastic Shortest Path problems.
method Derive and prove lower and upper bounds on sample complexity.
result Lower bound of samples for general case, and up to logarithmic factors for bounded hitting time condition.
Study tackles online auctions with unknown values, achieving optimal regret bounds.
problem Online auctions with unknown good values and bandit feedback.
method Online learning approach with bandit feedback, stochastic and adversarial models.
result Achieves logarithmic and sublinear regret bounds in both models.
Score attack method provides a lower bound on privacy-constrained minimax risk.
problem Characterizing the optimality of privacy-constrained statistical models.
method Score attack based on tracing attack concept.
result Optimally lower bounds the minimax risk of estimating unknown model parameters.
Algorithm approximates functions into manifolds with curvature bounds.
problem Approximating functions into manifolds with lower curvature bounds.
method Algorithm using manifold exponential and logarithm, with error bounds based on sectional curvature.
result Error bounds for nonnegative sectional curvature are similar to linear space approximations.