An online reinforcement learning algorithm is anytime if it does not need to know in advance the horizon T of the experiment. A well-known technique to obtain an anytime algorithm from any non-anytime algorithm is the "Doubling Trick". In the context of adversarial or stochastic multi-armed bandits, the performance of …
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Doubling Trick”
Geometric trick simplifies link homotopy and concordance.
problem Homotopy and concordance of links in homology spheres.
method Relative Whitney trick to remove double points.
result Links in homology spheres can be simplified to topologically slice links.
New rule reduces exploration regret to logarithmic, improving bad episode handling.
problem Improving exploration regret in average reward MDPs.
method Replacing Doubling Trick with Vanishing Multiplicative rule in EVI-based algorithms.
result Regret is logarithmic under the new rule, significantly better than linear.
The procedure to remove double intersections called the Whitney trick is one of the main tools in the topology of manifolds. The analogues of Whitney trick for -tuple intersections were `in the air' since 1960s. However, only recently they were stated, proved and applied to obtain interesting results. Here we prove …
We claim that the recently discovered universal-matrix precursor for the functions, which define the differential expansion of colored polynomials for twist and double braid knots, can be extended from rectangular to non-rectangular representations. This case is far more interesting, because it involves multiplicit…
We prove that if an alternating knot has unknotting number one, then there exists an unknotting crossing in any alternating diagram. This is done by showing that the obstruction to unknotting number one developed by Greene in his work on alternating 3-braid knots is sufficient to identify all unknotting number one alte…
Boltzmann exploration is widely used in reinforcement learning to provide a trade-off between exploration and exploitation. Recently, in (Cesa-Bianchi et al., 2017) it has been shown that pure Boltzmann exploration does not perform well from a regret perspective, even in the simplest setting of stochastic multi-armed b…
We prove the following: there are infinitely many finite-covolume (resp. cocompact) Coxeter groups acting on hyperbolic space H^n for every n < 20 (resp. n < 7). When n=7 or 8, they may be taken to be nonarithmetic. Furthermore, for 1 < n < 20, with the possible exceptions n=16 and 17, the number of essentially distinc…
Study of skateboard flips as continuous curves in group.
problem Characterize skateboard flip tricks as continuous motions.
method Model flips as curves in , analyze lifts to , derive formulas.
result There are only four distinct flip tricks up to continuous deformation.
Nash's theorem proved with Günther's trick
problem Proving Nash's smooth embedding theorem
method Using Günther's trick
result Nash's theorem proved
Explains Conway's tangle trick and its mathematical origins.
problem Understanding the relationship between braids and elliptic curves.
method Discusses the tangle trick, its mathematical underpinnings, and historical context.
result Establishes the connection between braids and elliptic curves.
Unified framework for gradient estimation in combinatorial spaces.
problem Scaling relaxed gradient estimators to large combinatorial distributions.
method Introducing stochastic softmax tricks within the perturbation model framework.
result Stochastic softmax tricks improve model performance and discover more latent structure.
We prove all knots can be transformed into a trefoil using special diagrams.
problem Transforming any knot into a trefoil using magic tricks.
method Introducing knotholder diagrams to encode transformations.
result All knots can be transformed into a trefoil.
Outlier based Robust Principal Component Analysis (RPCA) requires centering of the non-outliers. We show a "bias trick" that automatically centers these non-outliers. Using this bias trick we obtain the first RPCA algorithm that is optimal with respect to centering.
A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learningcs.LG
The Gumbel-max trick and its extensions simplify sampling from categorical distributions in machine learning.
problem Sampling from categorical distributions with unnormalized probabilities.
method Extensions of the Gumbel-max trick for various applications.
result Simplified and efficient methods for sampling and gradient estimation.
A new gradient estimator for categorical distributions reduces bias and variance.
problem Intractability of gradients for categorical distributions in discrete latent variable models.
method CatLog-Derivative trick and IndeCateR gradient estimator.
result IndeCateR reduces bias and variance of gradients for categorical distributions.
Establishes necessary and sufficient conditions for smooth triviality of Lie subalgebras and Lie ideals, and proves Moser's trick for foliations.
problem Smooth triviality of Lie subalgebras and Lie ideals
method Establishing necessary and sufficient conditions and proving Moser's trick for foliations
result Direct proof of Moser's trick for foliations
Retail Product Image Classification is an important Computer Vision and Machine Learning problem for building real world systems like self-checkout stores and automated retail execution evaluation. In this work, we present various tricks to increase accuracy of Deep Learning models on different types of retail product …
A triple-point Whitney trickmath.GT
Triple-point Whitney trick classifies ornaments of 3-manifolds.
problem Classifying ornaments of 3-manifolds in high dimensions.
method Triple-point Whitney trick applied to orientable manifolds.
result Classification of ornaments by the μ-invariant.
Alexander trick applied to homology spheres for manifold homeomorphisms.
problem Group of homeomorphisms of contractible manifolds.
method Strong uniqueness statement for one-sided h-cobordisms.
result Group of homeomorphisms is contractible for .
Embolic volume of compact manifolds is defined in terms of Berger's embolic inequality. In this paper, we show a result of relating embolic volume to the first Betti number. The proof relies on Gromov's covering argument appeared in systolic geometry. Berger called this method covering trick. We exploit and present mor…
Expands Bredon's trick for applications in geometry and topology.
problem Local-to-global extension principles in geometric and topological contexts.
method Novel applications and frameworks for stratified pseudomanifolds, Ricci flow, and persistent homology.
result Establishes Bredon's trick as a unifying framework.
Dualizable tensor categoriesmath.QA
We investigate the relationship between the algebra of tensor categories and the topology of framed 3-manifolds. On the one hand, tensor categories with certain algebraic properties determine topological invariants. We prove that fusion categories of nonzero global dimension are 3-dualizable, and therefore provide 3-di…
Bredon's trick helps extend local properties to global topological spaces.
problem Extending local properties to global topological spaces.
method Bredon's trick for local properties to global spaces.
result Bredon's trick allows for natural alternative demonstrations of classic results.
We observe that gradients computed via the reparameterization trick are in direct correspondence with solutions of the transport equation in the formalism of optimal transport. We use this perspective to compute (approximate) pathwise gradients for probability distributions not directly amenable to the reparameterizati…
We introduce a family of pairwise stochastic gradient estimators for gradients of expectations, which are related to the log-derivative trick, but involve pairwise interactions between samples. The simplest example of our new estimator, dubbed the fundamental trick estimator, is shown to arise from either a) introducin…
The Gumbel trick is a method to sample from a discrete probability distribution, or to estimate its normalizing partition function. The method relies on repeatedly applying a random perturbation to the distribution in a particular way, each time solving for the most likely configuration. We derive an entire family of r…
We consider a family of learning strategies for online optimization problems that evolve in continuous time and we show that they lead to no regret. From a more traditional, discrete-time viewpoint, this continuous-time approach allows us to derive the no-regret properties of a large class of discrete-time algorithms i…
Proposes RCL method to improve ATE estimation from observational data.
problem Error-compounding issue and extreme estimates in DML estimators.
method Robust Causal Learning (RCL) method to offset DML deficiencies.
result RCL estimators are more stable and perform better than DML estimators.
Inference in popular nonparametric Bayesian models typically relies on sampling or other approximations. This paper presents a general methodology for constructing novel tractable nonparametric Bayesian methods by applying the kernel trick to inference in a parametric Bayesian model. For example, Gaussian process regre…
New trick builds hyperbolic manifolds from compact ones, proving some don't virtually fiber.
problem Proving some hyperbolic manifolds don't virtually fiber.
method Hyperbolic reflection group trick, embedding theory, manifold topology.
result Constructed Gromov hyperbolic 7-manifolds that don't virtually fiber over a circle.
The reparameterization trick has become one of the most useful tools in the field of variational inference. However, the reparameterization trick is based on the standardization transformation which restricts the scope of application of this method to distributions that have tractable inverse cumulative distribution fu…
In this paper, we study the behavior of the Hedge algorithm in the online stochastic setting. We prove that anytime Hedge with decreasing learning rate, which is one of the simplest algorithm for the problem of prediction with expert advice, is surprisingly both worst-case optimal and adaptive to the easier stochastic …
Boltzmann machines (BMs) are appealing candidates for powerful priors in variational autoencoders (VAEs), as they are capable of capturing nontrivial and multi-modal distributions over discrete variables. However, non-differentiability of the discrete units prohibits using the reparameterization trick, essential for lo…
New method for simplifying knots with specific properties.
problem Understanding knots with a specific unknotting number.
method Derive and apply the Montesinos trick for proper rational tangle replacement.
result Prove that knots with proper rational unknotting number one are prime and classify certain types.
Motivated by topological Tverberg-type problems and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into R^d without triple, quadruple, or, more generally, r-fold points. Specifically, we are interested in maps f from K to R^d…
Validation of the Replica Trick for Simple Modelscond-mat.dis-nn
We discuss replica analytic continuation using several simple models in order to prove mathematically the validity of replica analysis, which is used in a wide range of fields related to large scale complex systems. While replica analysis consists of two analytical techniques, the replica trick (or replica analytic con…
Paper develops a weighted linearization approach for vector fields.
problem Linearizability of vector fields under weighted conditions.
method Formal Moser trick applied to power series, addressing weighted non-resonance condition.
result Formal Moser trick works over any field of characteristic zero.
New algorithm reduces switching costs in RL beyond linear MDPs.
problem Costly policy switching in reinforcement learning.
method ELEANOR-LowSwitching algorithm for linear Bellman-complete MDPs.
result Achieves near-optimal regret with logarithmic switching cost.
Tricks adversarial attacks to target specific classes, improving classifier accuracy.
problem Recent adversarial defense approaches have failed to protect classifiers from untargeted attacks.
method Target Training defense tricks untargeted attacks into targeted attacks on designated classes, then derives the real class.
result 86.2% accuracy for CW-L2 (confidence=0) in CIFAR10, outperforming unsecured classifiers.
New formula connects holographic entanglement entropy to Willmore energy in 5D.
problem Analogous to 3D, find a new formula for 5D entanglement entropy.
method Prove equivalence between holographic entanglement entropy and Willmore energy in 5D.
result The Willmore energy in 5D is not globally minimized by a round ball.
This paper solves a complex differential relation using a novel 'avoidance trick'.
problem Classifying tangent distributions satisfying non-involutivity conditions.
method Convex integration with an 'avoidance trick'.
result First example of a differential relation that is ample in some directions but not all.
A new network model combines features of DCBM, LSM, and β-model, using a cancellation trick for parameter estimation.
problem Challenging parameter fitting in network models.
method Introducing a cancellation trick to resolve parameter fitting issues in the logit-DCBM.
result R-SCORE significantly improves community detection over existing methods.
Operator-Valued Kernels (OVKs) and associated vector-valued Reproducing Kernel Hilbert Spaces provide an elegant way to extend scalar kernel methods when the output space is a Hilbert space. Although primarily used in finite dimension for problems like multi-task regression, the ability of this framework to deal with i…
The reparameterization trick is widely used in variational inference as it yields more accurate estimates of the gradient of the variational objective than alternative approaches such as the score function method. Although there is overwhelming empirical evidence in the literature showing its success, there is relative…
Low-variance gradient estimation is crucial for learning directed graphical models parameterized by neural networks, where the reparameterization trick is widely used for those with continuous variables. While this technique gives low-variance gradient estimates, it has not been directly applicable to discrete variable…
Proves existence of planar curves with specific curvature.
problem Existence of planar closed curves with prescribed curvature.
method Variational methods, adding a parameter, monotonicity trick.
result Existence of planar closed curves with prescribed curvature for some curvature functions.
The article confirms two quasi-alternating surgeries for 9 asymmetric L-space knots.
problem Understanding quasi-alternating surgeries on asymmetric L-space knots.
method Using the Montesinos trick to confirm known surgeries.
result Confirmation of two quasi-alternating surgeries for each of 9 asymmetric L-space knots.