Groups on CAT(0) cube complexes grow exponentially uniformly.
problem Uniform exponential growth of groups acting on CAT(0) cube complexes.
method Study groups acting without global fixed points on CAT(0) square complexes.
result Groups with uniform exponential growth or stabilize Euclidean subcomplexes.
Proves new concentration inequalities for sub-gaussian and sub-exponential variables.
problem Understanding functions of independent random variables better.
method Sub-gaussian and sub-exponential conditions, Rademacher complexities, Lipschitz function classes.
result Extension of Rademacher complexities to unbounded sub-exponential distributions.
We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from com…
New bounds for score matching in polynomial exponential families.
problem Understanding the sample complexity of score matching for polynomial exponential families.
method Non-asymptotic sample complexity analysis for score matching.
result First finite sample bounds for score matching in polynomial exponential families.
CDEFs reduce model complexity and uncover time correlations.
problem Model complexity and data efficiency in probabilistic modeling.
method Builds on deep exponential families, ties weights for reduced parameters.
result CDEFs uncover time correlations with fewer parameters.
Study shows exponential gap in sample complexity between noisy and non-noisy recurrent neural networks.
problem Understanding the impact of noise on the sample complexity of recurrent neural networks.
method Analyzing noisy multi-layered sigmoid recurrent neural networks with independent noise and proving lower bounds.
result Exponential gap in sample complexity between noisy and non-noisy networks, even for small noise values.
Classifies toric dually flat manifolds into complex space forms.
problem Classifying 1D toric dually flat manifolds.
method Using complex space forms and exponential families.
result Toric dually flat manifolds are complex space forms.
New algorithm trains deep neural networks without global optimization.
problem Training deep neural networks efficiently and without global optimization.
method Uses random complex exponential activation functions and Markov Chain Monte Carlo sampling.
result Consistently attains theoretical approximation rate for residual networks.
The paper provides results regarding the computational complexity of hybrid system identification. More precisely, we focus on the estimation of piecewise affine (PWA) maps from input-output data and analyze the complexity of computing a global minimizer of the error. Previous work showed that a global solution could b…
Improved sample complexity for identifying best policies in risk-sensitive reinforcement learning.
problem Identifying approximately optimal policies in risk-sensitive reinforcement learning with exponential horizon dependence.
method Forward-model based algorithm with KL-based exploration bonuses adapted for entropic criterion, leveraging smoothness properties of exponential utility and a new stopping rule.
result Achieved sample complexity matching the lower bound, closing the gap between upper and lower bounds.
New method reduces sample complexity for learning Ising model dynamics exponentially.
problem Learning binary graphical models from correlated samples produced by a dynamical process.
method Two estimators based on interaction screening objective and conditional likelihood loss.
result Sample complexity reduces exponentially for samples from a dynamical process far from equilibrium.
Classical knot recognition problem solved in NP with exponential time algorithm.
problem Determining if a virtual knot is classical.
method Proved NP membership and provided an exponential time algorithm.
result Classical knot recognition problem is in NP.
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.
Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential …
In three-dimensional computational topology, the theory of normal surfaces is a tool of great theoretical and practical significance. Although this theory typically leads to exponential time algorithms, very little is known about how these algorithms perform in "typical" scenarios, or how far the best known theoretical…
Analogous exponential map defined for Hopf algebras.
problem Defining an exponential map for Hopf algebras.
method Analogy with Lie groups, interpretation as states, Hilbert C* bimodules, dual Hopf algebra elements.
result Multiple interpretations of exponential map values in Hopf algebras.
New t-LC triangulated manifolds are exponentially many.
problem Counting t-LC triangulated manifolds. method Introducing t-LC triangulated manifolds and proving their exponential growth. result There are at most $2^{ rac{d^3}{2}N}$ triangulated 2-LC d-manifolds with N facets. New algorithm reduces online logistic regression regret without exponential constant.
problem Improper learning in online logistic regression with logarithmic regret.
method Regularized empirical risk minimization with surrogate losses.
result Regret scaling as O(B log(Bn)) with low computational complexity.
The paper calculates the growth rates of billiard languages in hyperbolic polygons.
problem Computing the exponential growth rates of billiard languages in polygons.
method New methods relating to minimal tiling paths.
result Explicit computation of exponential growth rates for q even, and bounds for q odd. We consider a vector field X on a closed manifold which admits a Lyapunov one form. We assume X has Morse type zeros, satisfies the Morse--Smale transversality condition and has non-degenerate closed trajectories only. For a closed one form η, considered as flat connection on the trivial line bundle, the differen…
DeepPAMM models complex survival data with deep learning, improving predictive performance.
problem Complex hazard structures in survival analysis with small data sets and censoring.
method Deep learning framework for piecewise exponential models, addressing high-dimensional feature settings.
result DeepPAMM outperforms other machine learning approaches in predictive performance.
For a Morse map f:M→S1 Novikov [11] has introduced an analog of Morse complex, defined over the ring $\ZZZ[[t]][t^{-1}]$ of integer Laurent power series. Novikov conjectured, that generically the matrix entries of the differentials in this complex are of the form ∑iaiti, where ai grow at most exponenti…
We prove an exponential estimate for the asymptotics of Bergman kernels of a positive line bundle under hypotheses of bounded geometry. We give further Bergman kernel proofs of complex geometry results, such as separation of points, existence of local coordinates and holomorphic convexity by sections of positive line b…
It is known that describing or calculating the conditional probabilities of multiple events is exponentially expensive. In this work, Bayesian tensor network (BTN) is proposed to efficiently capture the conditional probabilities of multiple sets of events with polynomial complexity. BTN is a directed acyclic graphical …
Quantum algorithm speeds up pricing of financial derivatives.
problem Pricing autocallable options efficiently.
method Integration-based exponential amplitude loading technique.
result 50x reduction in circuit depth for payoff component.
This paper undertakes a study of the structure of the fibers of the Chevalley exponentiation maps f(i1,…,id). The fibers of these maps f(i1,…,id) encode the nonnegative real relations amongst exponentiated Chevalley generators. Our main theorems show that the fibers admit cell stratifications, t…
Efficient method for learning continuous exponential families beyond Gaussian.
problem Learning continuous exponential families with unbounded support.
method Interaction Screening approach for scalable learning of continuous graphical models.
result Our estimator maintains similar accuracy and sample complexity scalings compared to alternative approaches, while improving run-time.
TensorPlan shows an exponential lower bound for planning in MDPs with linearly realizable value functions.
problem Finding an exponential lower bound for planning in MDPs with linearly realizable value functions.
method TensorPlan and a few action lower bound approach.
result An exponentially large lower bound is shown for planning in MDPs with linearly realizable value functions.
We show that the probability that a finitely supported random walk on a non-elementary subgroup of the the mapping class group gives a non-pseudo-Anosov element decays exponentially in the length of the random walk. More generally, we show that if R is a set of mapping class group elements with an upper bound on their …
In this short note, we propose an unified method to derive formulas for derivations conjugated by exponential functions on an almost complex manifold. In v3, we corrected some mistakes in previous versions.
Study symmetry groups and curves from sums of exponentials.
problem Understanding the geometry and symmetry of curves from sums of exponentials.
method Analysis of symmetry groups, winding numbers, and parametrization of the unit circle.
result Unified method for constructing curves with specific properties.
Hyperbolic space outperforms Euclidean in learning hierarchical data.
problem Learning hierarchical data in Euclidean space requires exponentially many samples.
method Established geometric obstruction in Euclidean space and showed hyperbolic space's advantage.
result Hyperbolic space enables learning with O(mRlogm) samples, matching information-theoretic optimum. The paper explores connections between dg manifolds and homotopy Lie algebras.
problem Understanding the relationship between dg manifolds and homotopy Lie algebras.
method Study of formal exponential maps, Atiyah classes, and Kapranov L-infinity algebras.
result Existence of formal exponential maps linked to vanishing of Atiyah classes.
This study investigates self-organizing dynamics in a stochastic exponential DAM model using Temporal Complexity.
problem Understanding self-organizing behavior in artificial neural systems.
method Investigation of a stochastic exponential DAM model through Temporal Complexity analysis.
result The model exhibits regimes of complex intermittency with nontrivial temporal correlations and scale-free behavior.
The study provides error bounds for the generalized Lasso with sub-exponential data.
problem Analyzing the generalized Lasso under sub-exponential data distributions.
method Non-asymptotic analysis using generic chaining-based proof strategy.
result Error bounds for the generalized Lasso can be controlled by two complexity parameters.
The study analyzes when Bayesian averaging over decision trees is reliable.
problem When do Bayesian model averaging weights over decision trees provide reliable information?
method Closed-form solution for Bayesian decision trees with Catalan-exponential priors.
result Established a complete non-asymptotic theory of rational commitment thresholds.
Unified complexity bound for sampling logconcave distributions
problem Sampling arbitrary logconcave distributions
method In-and-Out algorithm with exponential lifting
result Nearly tight convergence rate
Efficiently learns exponential family distributions with i.i.d. samples.
problem Learning natural parameters of truncated exponential families efficiently.
method Proposes a novel loss function and computationally efficient estimator.
result Achieves optimal sample complexity and asymptotic normality.
We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy. We design new algorithms for RL with a generic model class and analyze their statistical properties. Our algorithms have sample …
The paper develops algorithms to restore monotonicity in non-monotone functions.
problem Non-monotone solutions from heuristic algorithms need to be corrected.
method Develops algorithms to restore monotonicity with limited queries.
result Restores monotonicity while degrading the function value by at most ε.
Efficient active learning with abstention reduces label complexity exponentially.
problem Achieving high accuracy with minimal labels.
method Developed a computationally efficient active learning algorithm with abstention.
result Achieves polylog(1/ε) label complexity, reducing by an exponential factor.
Loosely speaking, the Volume Conjecture states that the limit of the n-th colored Jones polynomial of a hyperbolic knot, evaluated at the primitive complex n-th root of unity is a sequence of complex numbers that grows exponentially. Moreover, the exponential growth rate is proportional to the hyperbolic volume of the …
Learning to control linear systems is statistically hard, especially for underactuated systems.
problem Statistical difficulty of learning to control linear systems, especially underactuated ones.
method Utilized minimax lower bounds and structural assumptions to prove learning complexity can be exponential.
result Learning complexity can be at most exponential with the controllability index of the system.
We introduce a new statistical tool (the TP-statistic and TE-statistic) designed specifically to compare the behavior of the sample tail of distributions with power-law and exponential tails as a function of the lower threshold u. One important property of these statistics is that they converge to zero for power laws o…
Gaussians as noise in NCE lead to exponentially bad conditioning, hindering its efficiency.
problem Exponential conditioning of Hessian in NCE with Gaussian noise.
method Using Gaussian as the noise distribution in NCE.
result Gaussian noise in NCE leads to exponentially bad conditioning of the loss Hessian.
Exponentially smoothed RNNs improve industrial forecasting.
problem Complexity and non-stationarity in industrial time series data.
method Exponential smoothed recurrent neural networks (RNNs) for modeling non-linear dynamics.
result Exponentially smoothed RNNs outperform traditional models in multi-step forecasting.
Closed-form formulas for path-independent options in a specific Lévy model.
problem Valuation of path-independent options in the exponential NIG model.
method Closed-form pricing formulas derived using a factorized representation in Mellin space and complex analysis.
result Valid closed-form formulas with quickly convergent series for various options.
We give a new and self-contained proof of the existence and unicity of the flow for an arbitrary (not necessarily homogeneous) smooth vector field on a real supermanifold, and extend these results to the case of holomorphic vector fields on complex supermanifolds. Furthermore we discuss local actions associated to supe…