We construct 2-dimensional CAT(-1) groups which contain free subgroups with arbitrary iterated exponential distortion, and with distortion higher than any iterated exponential.
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,742 papers · 148 categories
Trend · papers per month
48 results for “exponential iterates”
We develop a class of integrals on a manifold M called exponential iterated integrals, an extension of K. T. Chen's iterated integrals. It is shown that the matrix entries of any upper triangular representation of the fundamental group of M can be expressed via these new integrals. The ring of exponential iterated inte…
Paper proves exponential lower bounds for policy iteration in MDPs.
problem Proving lower bounds for policy iteration in multi-action MDPs.
method Generalized previous results to k-action MDPs, constructed families of MDPs.
result Proved novel exponential lower bound of (3+k)2^(N/2-3) iterations.
We represent the coordinate ring of algebraic hulls (which are generalizations of the Malcev completions of nilpotent groups for solvable groups) of solvmanifolds by using Miller's exponential iterated integrals (which are extensions of Chen's iterated integrals) of invariant differential forms.
Two new PCA variants improve financial data analysis.
problem Numerical instability and nonstationarity in PCA for finance.
method Iterated and exponentially weighted moving PCA variants using Ogita-Aishima iteration.
result Improved stability and adaptability in financial data analysis.
Exponential distribution is ubiquitous in the framework of multi-agent systems. Usually, it appears as an equilibrium state in the asymptotic time evolution of statistical systems. It has been explained from very different perspectives. In statistical physics, it is obtained from the principle of maximum entropy. In th…
Paper provides exponential convergence guarantees for Iterative Markovian Fitting.
problem Addressing the Schrödinger Bridge problem in computational optimal transport and generative modeling.
method Develops non-asymptotic exponential convergence guarantees for Iterative Markovian Fitting.
result First non-asymptotic exponential convergence guarantees for IMF under mild structural assumptions.
Exponential distribution is ubiquitous in the framework of multi-agent systems. An alternative approach with an economic motivation to derive the exponential distribution in the framework of iterations in the space of distributions is disclosed.
This paper gives a new definition of the Contou-Carrere symbol in terms of an exponential of a Chen iterated integral and proves the corresponding reciprocity law.
The AdaBoost algorithm was designed to combine many "weak" hypotheses that perform slightly better than random guessing into a "strong" hypothesis that has very low error. We study the rate at which AdaBoost iteratively converges to the minimum of the "exponential loss." Unlike previous work, our proofs do not require …
PACE optimizes training for averaged language models, improving performance.
problem How to optimize training for averaged language model iterates.
method Formulated as an optimal-control problem, solved for minimizing error of the average with a penalty on intervention size.
result PACE improves the limiting squared error of the iterate-average estimator by an arbitrarily large factor on some instances.
New algorithms achieve high-probability parameter-free regret in online convex optimization with heavy-tailed data.
problem Achieving high-probability parameter-free regret in online convex optimization with heavy-tailed data.
method Developed new regularization techniques to handle exponentially large iterates and heavy-tailed subgradients.
result Achieved regret bound of with high probability for subgradients with bounded moments.
Adversarial training is a technique for training robust machine learning models. To encourage robustness, it iteratively computes adversarial examples for the model, and then re-trains on these examples via some update rule. This work analyzes the performance of adversarial training on linearly separable data, and prov…
A new algorithm detects changes in data with constant cost per iteration.
problem Detecting changes in data with low computational cost.
method Adapting pruning and maximisation techniques from Gaussian data to exponential family models.
result The algorithm can detect changes in a wide range of models with a constant per-iteration cost.
We describe and analyze a simple algorithm for principal component analysis and singular value decomposition, VR-PCA, which uses computationally cheap stochastic iterations, yet converges exponentially fast to the optimal solution. In contrast, existing algorithms suffer either from slow convergence, or computationally…
Adaptive importance samplers are adaptive Monte Carlo algorithms to estimate expectations with respect to some target distribution which \textit{adapt} themselves to obtain better estimators over a sequence of iterations. Although it is straightforward to show that they have the same convergen…
The L1 loss landscape of neural nets near local minima behaves differently, revealing exponential decay and increased vertex density.
problem Understanding the L1 loss landscape of neural nets near local minima.
method Iterative minimization of the loss function on adjacent vertices of the Deep ReLU Simplex algorithm.
result Exponential decay of loss levels and increased vertex density around local minima.
Proposes an exponentially increasing step-size for faster parameter estimation in statistical models.
problem Slow convergence of gradient descent in locally convex loss functions.
method Exponentially increasing step-size in gradient descent algorithm.
result Converges linearly to optimal solution under homogeneous assumptions.
MSTGD:A Memory Stochastic sTratified Gradient Descent Method with an Exponential Convergence Ratestat.ML
MSTGD optimizes gradient descent with stratified sampling for faster convergence.
problem Fluctuation in gradient expectation and variance between iterations.
method Memory Stochastic Stratified Gradient Descent (MSTGD) with stratified sampling and variance reduction.
result MSTGD achieves an exponential convergence rate independent of dataset size and batch size.
The study shows exponential distortion in virtually special groups containing free subgroups.
problem Understanding distortion in virtually special groups containing free subgroups.
method Constructing examples of virtually special groups with finite rank free subgroups.
result Distortion functions grow like exp^k(x^m) and can be superexponential.
Quantum systems with scrambling improve temporal information processing, but scaling requires exponential overhead.
problem Scalability and memory retention of quantum reservoirs in temporal information processing.
method Examined a quantum reservoir processing framework with scrambling reservoirs modeled by high-order unitary designs, analyzed in noiseless and noisy settings.
result Memory retention improves exponentially with reservoir size but worsens with reservoir iterations, requiring exponential shot overhead for scaling.
Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.
problem Achieving optimal error rates in clustering sub-exponential mixture models.
method Establishes universal lower bounds and demonstrates iterative algorithms' optimality in sub-exponential mixture models.
result Iterative algorithms achieve the universal lower bound in sub-exponential mixture models.
New stability theory for Sinkhorn semigroups with explicit decay rates.
problem Stability and convergence of Sinkhorn iterations for various divergences.
method Operator-theoretic framework based on Lyapunov techniques.
result Explicit exponential decay rates for Sinkhorn iterates.
We consider binary classification problems with positive definite kernels and square loss, and study the convergence rates of stochastic gradient methods. We show that while the excess testing loss (squared loss) converges slowly to zero as the number of observations (and thus iterations) goes to infinity, the testing …
Proposes an iterative algorithm for optimizing attention mechanisms in large language models.
problem Optimizing attention mechanisms in large language models.
method Iterative algorithm for rescaled hyperbolic functions regression.
result Efficiency and generalizability of the rescaled softmax regression framework.
A technique identifies memoryless algorithms approximating memory-dependent optimization methods.
problem Understanding how memory in optimization algorithms affects loss and generalization.
method Introducing a general technique to replace past iterates with the current one and adding a correction term.
result Lion does not have the same implicit anti-regularization as AdamW, explaining its better generalization performance.
Improving optimization for iterate-averaged language models
problem How to optimize the averaged model returned by Language Model pipelines
method Formulating optimizer design as an optimal-control problem
result Proven convergence rate and strict improvement in squared error
CAVI converges exponentially fast for Bayesian PCA models.
problem Characterizing the convergence speed of CAVI for BPCA.
method Proved exponential convergence using power iteration analogy and novel lower bounds.
result Exponential convergence of CAVI for BPCA models with any number of principal components.
In this paper, we study the properties of the Frank-Wolfe algorithm to solve the \ExactSparse reconstruction problem. We prove that when the dictionary is quasi-incoherent, at each iteration, the Frank-Wolfe algorithm picks up an atom indexed by the support. We also prove that when the dictionary is quasi-incoherent, t…
A new accelerated method with simpler momentum update rules.
problem Optimizing parameters in machine learning models.
method Proposes a novel accelerated stochastic gradient method with simpler momentum update rules.
result The method outperforms Sgdm and Adam in practical problems.
Slow north-south dynamics on math.GT
We consider the action of a pseudo-Anosov mapping class on . This action has north-south dynamics and so, under iteration, laminations converge exponentially to the stable lamination. We study the rate of this convergence and give examples of families of pseudo-Anosov mapping classes where the rate go…
Improved convergence rates for saddle-point optimization algorithms.
problem Understanding last-iterate convergence rates for saddle-point optimization algorithms in constrained settings.
method Expanding the understanding of last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) in the constrained setting.
result Linear last-iterate convergence achieved with a universal constant learning rate for OMWU in bilinear games over the simplex.
SGD converges to an invariant distribution with sub-Gaussian or sub-exponential properties.
problem Optimizing smooth and strongly convex objectives using SGD.
method Analysis through Markov chains, focusing on convergence and concentration properties.
result SGD iterates and their invariant limit distribution inherit sub-Gaussian or sub-exponential concentration properties.
The paper approximates financial derivatives using neural networks and iterated integrals.
problem Approximating -integrable financial derivatives.
method Using iterated Stratonovich integrals and neural networks.
result Approximate solutions to the -hedging problem.
Given an automorphism of a free group , we consider the following invariants: is the number of exponential strata (an upper bound for the number of different exponential growth rates of conjugacy classes); is the maximal degree of polynomial growth of conjugacy classes; is the rank of the fixed subgrou…
We provide non-asymptotic bounds for the well-known temporal difference learning algorithm TD(0) with linear function approximators. These include high-probability bounds as well as bounds in expectation. Our analysis suggests that a step-size inversely proportional to the number of iterations cannot guarantee optimal …
Softmax PG methods can take extremely long to converge, even with exact gradients.
problem Softmax policy gradient methods can take an impractically long time to converge in reinforcement learning.
method Softmax policy gradient methods with exact gradient computation.
result Softmax PG methods can take exponential number of iterations to converge, even with optimal initialization.
Gradient methods converge exponentially in concave network games.
problem Finding Nash equilibria in concave network zero-sum games.
method Gradient Ascent and Optimistic Gradient Ascent analyses.
result Exponential convergence rates in various game settings.
This paper analyzes a simplified strategy for nonlinear control using local linear models and iLQR updates.
problem Nonlinear policy optimization in control systems.
method Iterative estimation of local linear models and iLQR-like policy updates.
result Demonstrates polynomial sample complexity and overcomes exponential problem horizon dependence.
A new method for target propagation using iterative approximations converges fast and is more biologically plausible.
problem Improving target propagation methods for neural networks.
method Iterative approximate inverses and local auto-encoders.
result The method converges exponentially fast under certain conditions.
Proposes a privacy-preserving sign selection method for distributed systems.
problem Sign selection in distributed differentially private settings.
method Iterative peeling of stability function combined with exponential mechanism.
result Recovery of support and signs with optimal signal-to-noise ratio.
BEMA reduces bias in EMA, leading to faster convergence and better performance.
problem Stochasticity in language model fine-tuning destabilizes training.
method Bias-Corrected Exponential Moving Average (BEMA) augmentation of EMA.
result BEMA leads to significantly improved convergence rates and final performance.
PER-ETD improves ETD by reducing variance to polynomial complexity.
problem Large variance in ETD leading to exponential sample complexity.
method Periodically restart and update the follow-on trace for a finite period.
result PER-ETD converges to the same fixed point as ETD but with improved sample complexity.
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 defines conditions for a free-by-free group to be hyperbolic.
problem Conditions for a free-by-free group to be relatively hyperbolic.
method Necessary and sufficient conditions involving exponentially growing automorphisms and invariant subgroup systems.
result A subgroup system can be used to construct peripheral subgroups making the extension hyperbolic.
Private Topic Modelingstat.ML
We develop a privatised stochastic variational inference method for Latent Dirichlet Allocation (LDA). The iterative nature of stochastic variational inference presents challenges: multiple iterations are required to obtain accurate posterior distributions, yet each iteration increases the amount of noise that must be …
ELU algorithm improves on EM for over-specified Gaussian mixtures.
problem Slow convergence of EM in over-specified Gaussian mixtures.
method Developed ELU algorithm for two-component mixtures, combining exponential location update and gradient descent.
result ELU converges to final statistical radius after logarithmic iterations, resolving open question.
We prove that the control polygon of a Bezier curve B becomes homeomorphic and ambient isotopic to B via subdivision, and we provide closed-form formulas to compute the number of iterations to ensure these topological characteristics. We first show that the exterior angles of control polygons converge exponentially to …