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

count % of corpus

48 results for “algorithm transformation”

Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcs.LG

Transformers learn to make decisions in new contexts from offline data.

problem Understanding when and how transformers can perform in-context reinforcement learning.

method Theoretical framework analyzing supervised pretraining for ICRL, including algorithm distillation and decision-pretrained transformers.

result Transformers can efficiently approximate optimal reinforcement learning algorithms for various environments.

transformers in-context reinforcement learning supervised pretraining algorithm distillation decision-pretrained transformers

2023-10-12abs ↗pdf ↗

A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learningcs.DS

Strongly polynomial algorithm for approximate Forster transforms and halfspace learning.

problem Computing approximate Forster transforms and halfspace learning.

method Strongly polynomial time algorithm for approximate Forster transforms and halfspace learning.

result First strongly polynomial time algorithm for distribution-free PAC learning of halfspaces.

Forster transform PAC learning halfspaces strongly polynomial time regularization

2022-12-06abs ↗pdf ↗

Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizationscs.LG

Fast linear transforms are ubiquitous in machine learning, including the discrete Fourier transform, discrete cosine transform, and other structured transformations such as convolutions. All of these transforms can be represented by dense matrix-vector multiplication, yet each has a specialized and highly efficient (su…

2019-03-14abs ↗pdf ↗

Learning Filter Bank Sparsifying Transformsstat.ML

Data is said to follow the transform (or analysis) sparsity model if it becomes sparse when acted on by a linear operator called a sparsifying transform. Several algorithms have been designed to learn such a transform directly from data, and data-adaptive sparsifying transforms have demonstrated excellent performance i…

2018-03-06abs ↗pdf ↗

Efficient, Anytime Algorithms for Calibration with Isotonic Regression under Strictly Convex Lossescs.LG

Efficient algorithms find optimal monotone transforms for calibration under strictly convex losses.

problem Calibrating estimations to improve performance with monotone transforms.

method Proposed linear-time and space algorithm for finding optimal monotone transforms for specific loss functions. Also proposed an anytime algorithm with linear space and pseudo-linearithmic time complexity.

result Optimal monotone transforms are unique and can be found efficiently for various strictly convex loss functions.

calibration monotone transforms optimal transforms strictly convex losses linear time

2021-10-31abs ↗pdf ↗

Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncs.LG

Transformers can adaptively select and perform various machine learning tasks in context.

problem Transformers' ability to perform multiple machine learning tasks without explicit prompting.

method Statistical theory and efficient implementation of in-context gradient descent, enabling transformers to implement various algorithms and tasks.

result Transformers can implement a broad class of standard machine learning algorithms in context, including algorithm selection.

transformers in-context learning algorithm selection statistical theory machine learning

2023-06-07abs ↗pdf ↗

What Algorithms can Transformers Learn? A Study in Length Generalizationcs.LG

Study shows Transformers can generalize to varying task lengths.

problem Understanding when and how Transformers can generalize to different input lengths.

method Proposed a unifying framework and introduced the RASP-Generalization Conjecture.

result Transformers tend to length generalize on tasks if solvable by short RASP programs.

Transformers length generalization RASP min-degree-interpolator algorithmic tasks

2023-10-24abs ↗pdf ↗

Riemannian Geometry Approach for Minimizing Distortion and its Applicationscs.CV

Algorithm finds optimal affine transformation to minimize overall distortion.

problem Minimizing distortion in affine transformations.

method Riemannian geometry approach to define and minimize distortion.

result Mean distorting transformation found for minimizing overall distortion.

Riemannian geometry affine transformations distortion minimization mean distorting transformation rendering panoramas

2022-07-25abs ↗pdf ↗

A Batch-to-Online Transformation under Random-Order Modelcs.LG

Transforms offline algorithms to online with low regret in random order model.

problem Developing online algorithms with low approximate regret from offline approximation algorithms.

method General reduction theorem and coreset construction method.

result Achieves polylogarithmic ε-approximate regret for various online problems.

online algorithms offline approximation random-order model approximate regret coreset construction

2023-06-12abs ↗pdf ↗

Fast Partial Fourier Transformcs.LG

A new algorithm computes Fourier coefficients for a specified range efficiently.

problem Inefficiency in FFT due to fixed output size for all applications.

method Fast Partial Fourier Transform (PFT) that allows specifying the range of Fourier coefficients to compute.

result PFT achieves significant speedup over state-of-the-art FFT algorithms for small output sizes.

Fourier transform Partial Fourier Transform Fast Fourier Transform Efficiency Machine learning

2020-08-28abs ↗pdf ↗

How Well Can Transformers Emulate In-context Newton's Method?cs.LG

Transformers can approximate Newton's method for logistic regression.

problem Implementing higher order optimization methods in Transformers.

method Linear attention Transformers with ReLU layers approximating second order optimization algorithms.

result Transformers can implement a single step of Newton's iteration for matrix inversion.

Transformers Newton's method logistic regression in-context learning higher order optimization

2024-03-05abs ↗pdf ↗

From Robustness to Privacy and Backcs.LG

Transforms robust algorithms into private ones with optimal error rates.

problem Balancing privacy and robustness in machine learning.

method Black-box transformation method to convert robust algorithms to private ones with optimal error rates.

result Optimal private estimators for various tasks, including Gaussian and PCA.

differential privacy robustness machine learning algorithm transformation statistical inference

2023-02-03abs ↗pdf ↗

Looped Transformers with Layer Normalization Provably Learn the Power Methodcs.LG

Looped transformers with LN converge to power method for principal component prediction.

problem Understanding how transformers learn algorithmic procedures.

method Study of principal component prediction with looped linear transformers and layer normalization.

result Gradient descent trains looped transformers with LN to implement the power method for principal component prediction.

transformers layer normalization power method principal component prediction gradient descent

2026-05-30abs ↗pdf ↗

ModelDiff: A Framework for Comparing Learning Algorithmscs.LG

ModelDiff compares learning algorithms by identifying feature transformations.

problem Comparing models trained with different learning algorithms.

method ModelDiff uses datamodels framework to find distinguishing feature transformations.

result ModelDiff can compare models trained with/without data augmentation, pre-training, and different SGD hyperparameters.

algorithm comparison feature transformations learning algorithms data augmentation pre-training

2022-11-22abs ↗pdf ↗

Transformers as Unsupervised Learning Algorithms: A study on Gaussian Mixturescs.LG

Transformers solve Gaussian Mixture Models without supervision.

problem Solving Gaussian Mixture Models (GMMs) unsupervised.

method Proposes TGMM, a transformer-based framework for GMM tasks.

result Transformers can effectively solve GMM tasks, improving upon classical methods.

transformers unsupervised learning Gaussian Mixture Models statistical estimation EM algorithm

2025-05-17abs ↗pdf ↗

Toward TransfORmers: Revolutionizing the Solution of Mixed Integer Programs with Transformerscs.AI

Transformers improve solving mixed-integer programs, especially CLSP.

problem Solving Capacitated Lot Sizing Problem (CLSP) with mixed-integer programming.

method Employing transformer models to predict binary variables in CLSP.

result Transformer model outperforms CPLEX and LSTM in solving CLSP.

Transformers Mixed-Integer Programming Capacitated Lot Sizing Problem Deep Learning NP-Hard

2024-02-20abs ↗pdf ↗

Automatic Domain Adaptation by Transformers in In-Context Learningcs.LG

Paper presents a Transformer model for automatic domain adaptation.

problem Challenges in selecting or designing domain adaptation algorithms.

method Transformer model approximates and selects domain adaptation algorithms.

result Transformers can approximate and automatically select domain adaptation algorithms.

Transformers Domain Adaptation In-Context Learning Unsupervised Learning

2024-05-27abs ↗pdf ↗

Algorithmic Task Capture, Computational Complexity, and Inductive Bias of Infinite Transformerscs.LG

Transformers capture combinatorial tasks with bounded error and logarithmic sample dependence.

problem Capturing complex combinatorial tasks with bounded error and sample efficiency.

method Formal definition of algorithmic capture, empirical analysis of infinite-width transformers, upper bounds on computational complexity.

result Transformers exhibit an inductive bias favoring simpler algorithmic procedures over higher complexity ones.

Transformers Algorithmic capture Inductive bias Computational complexity Infinite-width

2026-03-11abs ↗pdf ↗

Learning Spectral Methods by Transformersstat.ML

Transformers can learn spectral methods and perform unsupervised learning.

problem Learning spectral methods using unsupervised learning.

method Using multi-layered Transformers, pre-trained on a large set of instances, to learn and perform statistical estimation tasks.

result Proven that pre-trained Transformers can learn spectral methods and perform tasks like PCA and clustering.

Transformers unsupervised learning spectral methods statistical estimation PCA

2025-01-02abs ↗pdf ↗

Transformers versus the EM Algorithm in Multi-class Clusteringstat.ML

Transformers learn to cluster Gaussian mixtures as well as the EM algorithm.

problem Learning guarantees of Transformers in multi-class clustering of Gaussian mixtures.

method Developed a theory connecting Transformer's Softmax Attention layers to the EM algorithm's workflow.

result Transformers achieve minimax optimal rate for clustering Gaussian mixtures with sufficient training samples and initialization.

Transformers EM algorithm Gaussian mixture models Softmax Attention Clustering

2025-02-09abs ↗pdf ↗

Transformers as Algorithms: Generalization and Stability in In-context Learningcs.LG

Transformers learn algorithms for in-context learning with bounds and stability analysis.

problem Understanding and formalizing in-context learning as an algorithm learning problem.

method Formalizing ICL as a multitask learning problem, deriving generalization bounds, and analyzing stability.

result Transformers can implement near-optimal algorithms for classical regression tasks with i.i.d. and dynamic data.

in-context learning transformers multitask learning generalization stability

2023-01-17abs ↗pdf ↗

\ell_0

Sparsifying Transform Learning with Efficient Optimal Updates and Convergence Guaranteesstat.ML

Many applications in signal processing benefit from the sparsity of signals in a certain transform domain or dictionary. Synthesis sparsifying dictionaries that are directly adapted to data have been popular in applications such as image denoising, inpainting, and medical image reconstruction. In this work, we focus in…

2015-01-13abs ↗pdf ↗

In-Context Algorithm Emulation in Fixed-Weight Transformerscs.LG

Transformers can emulate various algorithms by prompting, proving universality.

problem How to emulate algorithms using fixed-weight Transformers.

method Two modes of in-context algorithm emulation: task-specific and prompt-programmable. Constructing prompts that encode algorithm parameters into token representations.

result Fixed-weight Transformers can emulate a broad class of algorithms via prompts.

Transformer algorithm emulation in-context learning prompt-programmable fixed weights

2025-08-24abs ↗pdf ↗

Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARLcs.LG

Paper proves efficiency of MARL with transformers, addressing agent complexity.

problem Theoretical understanding of MARL with many agents and limited relational reasoning.

method Set Transformer for relational reasoning, model-free and model-based MARL algorithms.

result Provable efficiency of MARL algorithms, suboptimality gaps independent of number of agents.

MARL Transformer Relational Reasoning Model-Free Model-Based

2022-09-20abs ↗pdf ↗

An EM Gradient Algorithm for Mixture Models with Components Derived from the Manly Transformationstat.ML

A new EM gradient algorithm for mixture models with skewed components.

problem Fitting mixture models with skewed components derived from the Manly transformation.

method Proposes an alternative EM gradient algorithm using Newton's method for better parameter updates.

result Shows improved convergence and parameter estimation compared to the Nelder-Mead optimization.

EM algorithm mixture models skewed components Manly transformation Newton's method

2024-10-01abs ↗pdf ↗

Transformers Provably Implement In-Context Reinforcement Learning with Policy Improvementstat.ML

Transformers can implement reinforcement learning algorithms from data without updates.

problem Training reinforcement learning algorithms from data without parameter updates.

method Design a teacher-mimicking training procedure for transformers to implement policy-improvement methods.

result Gradient flow converges to an optimal parameter manifold corresponding to the desired RL update.

transformers in-context reinforcement learning policy improvement gradient flow reinforcement learning algorithms

2026-05-07abs ↗pdf ↗

The 2D Tree Sliding Window Discrete Fourier Transformcs.DS

We present a new algorithm for the 2D Sliding Window Discrete Fourier Transform (SWDFT). Our algorithm avoids repeating calculations in overlapping windows by storing them in a tree data-structure based on the ideas of the Cooley- Tukey Fast Fourier Transform (FFT). For an $N_0 \times N_1$ array and $n_0 \times n_1$ wi…

2017-07-25abs ↗pdf ↗

Generalization vs. Memorization in the Presence of Statistical Biases in Transformerscs.LG

Study shows statistical biases can mislead transformer models, impairing their generalization.

problem Statistical biases in transformers affect their ability to generalize.

method Evaluated transformer models on synthetic algorithmic tasks with varying statistical biases.

result Statistical biases lead to overestimation of transformer models' generalization capabilities.

transformers statistical biases generalization algorithmic tasks overestimation

2024-09-06abs ↗pdf ↗

Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcs.LG

Transforms offline greedy algorithms to online algorithms for combinatorial problems.

problem Online decision-making in time-varying combinatorial environments.

method General framework using Blackwell approachability and Bandit Blackwell approachability.

result Achieves

O(\sqrt{T})

regret in full information setting and

O(T^{2/3})

regret in bandit setting.

Online Learning Greedy Algorithms Blackwell Approachability Bandit Blackwell Approachability Regret Analysis

2021-02-18abs ↗pdf ↗

Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?cs.LG

Looped Transformers learn to implement multi-step gradient descent for in-context learning.

problem Understanding the learnability of multi-step algorithms in multi-layer Transformers.

method Training weight-sharing looped Transformers for in-context linear regression, proving gradient dominance condition for convergence.

result Looped Transformers implement multi-step preconditioned gradient descent, converging to global minimizer.

Transformers Gradient Descent Multi-step Algorithms In-context Learning Weight Sharing

2024-10-10abs ↗pdf ↗

Learning Multi-Layer Transform Modelscs.LG

Learned data models based on sparsity are widely used in signal processing and imaging applications. A variety of methods for learning synthesis dictionaries, sparsifying transforms, etc., have been proposed in recent years, often imposing useful structures or properties on the models. In this work, we focus on sparsif…

2018-10-19abs ↗pdf ↗

Composing inference algorithms as program transformationsstat.ML

Probabilistic inference procedures are usually coded painstakingly from scratch, for each target model and each inference algorithm. We reduce this effort by generating inference procedures from models automatically. We make this code generation modular by decomposing inference algorithms into reusable program-to-progr…

2016-03-06abs ↗pdf ↗

TiK-means:

K

-means clustering for skewed groupsstat.ML

The $K$ -means algorithm is extended to allow for partitioning of skewed groups. Our algorithm is called TiK-Means and contributes a $K$ -means type algorithm that assigns observations to groups while estimating their skewness-transformation parameters. The resulting groups and transformation reveal general-structured cl…

2019-04-21abs ↗pdf ↗

Hyperparameter optimization with REINFORCE and Transformerscs.LG

Improved hyperparameter optimization using simplified Transformer blocks.

problem Discovering optimal architectures in high-dimensional search spaces with limited exploration budgets.

method Simplified Transformer block for modeling hyper-parameter dependencies, actor-critic style algorithm, ensembling.

result Outperformed most algorithms on NAS-Bench-101 and Random Search in discovering more accurate model architectures.

Hyperparameter optimization Transformer Reinforcement Learning Neural Architecture Search Actor-Critic

2020-06-01abs ↗pdf ↗

Use Short Isometric Shapelets to Accelerate Binary Time Series Classificationcs.LG

A new algorithm reduces time complexity for binary time series classification.

problem High time complexity of ensemble shapelet transform limits its application.

method Introduces short isometric shapelet transform with two strategies: fixed shapelet length and single linear classifier.

result Demonstrates superior performance and reduced time complexity.

time series classification shapelet transform short isometric shapelet binary classification time complexity reduction

2019-12-27abs ↗pdf ↗

A topological algorithm for the Fourier transform of Stokes data at infinitymath.AG

Algorithm describes Fourier transform of Stokes data at infinity.

problem Understanding the Fourier transform of Stokes data at infinity.

method Topological description and algorithmic approach using recent results and language of Stokes local systems.

result Explicit isomorphisms between wild character varieties are induced.

Fourier transform Stokes data wild character varieties topological description isomorphisms

2024-02-07abs ↗pdf ↗

SMILES Transformer: Pre-trained Molecular Fingerprint for Low Data Drug Discoverycs.LG

SMILES Transformer learns molecular fingerprints for drug discovery.

problem Poor performance of rule-based molecular fingerprints in shallow prediction models or small datasets.

method Unsupervised pre-training of a sequence-to-sequence language model on a corpus of SMILES.

result SMILES Transformer outperformed existing methods in small-data settings.

drug discovery molecular fingerprints Transformer pre-training language model

2019-11-12abs ↗pdf ↗

Transforming Graph Representations for Statistical Relational Learningstat.ML

Relational data representations have become an increasingly important topic due to the recent proliferation of network datasets (e.g., social, biological, information networks) and a corresponding increase in the application of statistical relational learning (SRL) algorithms to these domains. In this article, we exami…

2012-03-30abs ↗pdf ↗

Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Contextcs.LG

Transformers trained on random classification tasks generalize well and can overfit without error.

problem Understanding how transformers generalize and overfit in-context.

method Analysis of implicit regularization during gradient descent training.

result Transformers can overfit without error and still generalize well.

transformers gradient descent classification generalization overfitting

2024-10-02abs ↗pdf ↗

Pricing of European Calls with the Quantum Fourier Transformquant-ph

Quantum algorithm for pricing European call options.

problem Accurate valuation of financial derivatives, especially for complex models and options.

method Transforms classical FFT into quantum QFT for pricing European call options.

result Quantum algorithm outperforms classical Monte Carlo simulation in NISQ era.

quantum computing financial derivatives European call options quantum Fourier transform Monte Carlo simulation

2024-04-22abs ↗pdf ↗

Characterizing the invariances of learning algorithms using category theorycs.LG

Many learning algorithms have invariances: when their training data is transformed in certain ways, the function they learn transforms in a predictable manner. Here we formalize this notion using concepts from the mathematical field of category theory. The invariances that a supervised learning algorithm possesses are …

2019-05-06abs ↗pdf ↗

Ouroboros: On Accelerating Training of Transformer-Based Language Modelscs.CL

Language models are essential for natural language processing (NLP) tasks, such as machine translation and text summarization. Remarkable performance has been demonstrated recently across many NLP domains via a Transformer-based language model with over a billion parameters, verifying the benefits of model size. Model …

2019-09-14abs ↗pdf ↗

On the Equivalence of Spacetimes, the Cartan-Karlhede Algorithmgr-qc

Paper presents an algorithm to check spacetime equivalence.

problem Determining physical equivalence of spacetimes via coordinate transformations.

method Cartan-Karlhede algorithm for checking spacetime equivalence.

result Illustrates the method through simple examples.

spacetime equivalence coordinate transformations general relativity Cartan-Karlhede algorithm

2020-07-08abs ↗pdf ↗

Optimizing Recurrent Neural Networks Architectures under Time Constraintsstat.ML

Recurrent neural network (RNN)'s architecture is a key factor influencing its performance. We propose algorithms to optimize hidden sizes under running time constraint. We convert the discrete optimization into a subset selection problem. By novel transformations, the objective function becomes submodular and constrain…

2016-08-29abs ↗pdf ↗

Transformers Meet In-Context Learning: A Universal Approximation Theorycs.LG

Transformers enable in-context learning with guarantees for a wide range of tasks.

problem How to enable in-context learning with transformers for various tasks.

method Developed a universal approximation theory integrating Barron's function approximation with transformer capabilities.

result Transformers can approximate any target function with vanishingly small risk using a few in-context examples.

Transformers In-context Learning Universal Approximation Universal Function Approximation Lasso

2025-06-05abs ↗pdf ↗

Thwarting Adversarial Examples: An

L_0

-RobustSparse Fourier Transformcs.LG

We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that has been corrupted by worst-case $L_0$ noise, namely a bounded number of coordinates of the signal have been corrupted arbitrarily. Our techniques generalize to a wide range of linear transformations that are…

2018-12-12abs ↗pdf ↗

MultiRocket: Multiple pooling operators and transformations for fast and effective time series classificationcs.LG

MultiRocket boosts TSC speed and accuracy with pooling and transformations.

problem Efficient time series classification with high accuracy.

method Multiple pooling operators and transformations applied to raw and differenced series.

result MultiRocket outperforms MiniRocket and is competitive with state-of-the-art methods in terms of accuracy and speed.

time series classification fast algorithms transformations pooling operators accuracy

2021-01-31abs ↗pdf ↗

Private Online Learning via Lazy Algorithmscs.LG

New private algorithms for online learning improve regret in high privacy regimes.

problem Private online learning from experts and convex optimization.

method Transformed lazy algorithms for differential privacy.

result Improved regret bounds for DP-OPE and DP-OCO.

private online learning differential privacy online prediction online convex optimization lazy algorithms

2024-06-05abs ↗pdf ↗