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,657 papers · 148 categories

Trend · papers per month

count % of corpus

8 results for “SETH”

The complexity of non-stationary reinforcement learningcs.LG

Non-stationary reinforcement learning is challenging due to the complexity of updating value functions.

problem Challenges in non-stationary reinforcement learning, especially in updating value functions.

method Proved a worst-case complexity result for modifying reinforcement learning problems.

result Modifying reinforcement learning problems requires an amount of time almost as large as the number of states.

reinforcement learning non-stationary value function complexity SETH

2023-07-13abs ↗pdf ↗

Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiencycs.LG

Single-head transformers with a single self-attention layer can approximate any sequence-to-sequence function and are efficient under certain conditions.

problem Statistical and computational limits of prompt tuning for transformer-based models.

method Investigation of single-head transformers with a single self-attention layer, proving universality and efficiency under SETH.

result Existence of almost-linear time prompt tuning inference algorithms under certain conditions.

transformers prompt tuning universality SETH approximation

2024-11-25abs ↗pdf ↗

On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysiscs.LG

We analyze computational limits of modern Hopfield models based on pattern norms.

problem Understanding the efficiency of modern Hopfield models from a fine-grained complexity perspective.

method Fine-grained complexity analysis and upper bound criterion for pattern norms.

result Below a specific norm threshold, efficient variants of modern Hopfield models exist.

Hopfield models fine-grained complexity phase transition pattern norms SETH

2024-02-07abs ↗pdf ↗

On the Fine-Grained Hardness of Inverting Generative Modelsstat.ML

This paper explores the computational hardness of generating latent vectors for generative models.

problem Computational hardness of generating latent vectors for generative models.

method Established lower bounds for exact and approximate model inversion under strong exponential time hypothesis (SETH) and exponential time hypothesis (ETH).

result Lower bounds for computational complexity of exact and approximate model inversion.

Generative models Latent vectors Computational hardness NP-hard Exact inversion

2023-09-11abs ↗pdf ↗

Algorithms and Hardness for Linear Algebra on Geometric Graphscs.DS

The paper explores efficient graph algorithms on geometric graphs and their computational limits.

problem Efficiently solving spectral graph theory problems on geometric graphs.

method Investigates algorithms and hardness results for multiplying vectors, finding spectral sparsifiers, and solving Laplacian systems on

\mathsf{K}

-graphs.

result Formal limitations on subquadratic time algorithms for spectral graph theory problems on geometric graphs, including the Gaussian kernel and Neural tangent kernels.

geometric graphs spectral graph theory algorithms hardness Laplacian systems

2020-11-04abs ↗pdf ↗

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscs.LG

We analyze the computational limits of LoRA for transformer models using fine-grained complexity theory.

problem Computational efficiency of LoRA fine-tuning for transformer models.

method Fine-grained complexity theory, identifying phase transitions, almost linear algorithms.

result Existence of almost linear algorithms for LoRA adaptation based on specific norms.

Transformer models Low-Rank Adaptation Fine-tuning Complexity theory Algorithm efficiency

2024-06-05abs ↗pdf ↗

On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)stat.ML

Latent DiTs improve data distribution recovery and inference efficiency under low-dimensional latent space.

problem Improving data distribution recovery and inference efficiency in latent DiTs.

method Investigates statistical and computational limits of latent DiTs under low-dimensional latent space assumption, deriving approximation error bounds, sample complexity, and efficient inference and training algorithms.

result Latent DiTs can bypass high dimensionality challenges and achieve almost-linear time inference and training.

Latent Diffusion Transformers Statistical Rates Efficient Inference Low-Dimensional Space Sample Complexity

2024-07-01abs ↗pdf ↗

Faster Algorithms for Structured Linear and Kernel Support Vector Machinesmath.OC

Faster algorithms for structured SVMs reduce computation time.

problem Efficiently solving quadratic programming problems with specific structures.

method Designing nearly-linear time algorithms for quadratic programs with low-rank factorizations and few linear constraints.

result First nearly-linear time algorithms for solving quadratic programs with specific structures.

Support Vector Machines Quadratic Programming Linear Constraints Low-Rank Factorization Fast Algorithms

2023-07-15abs ↗pdf ↗