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

Trend · papers per month

count % of corpus

7 results for “logarithmic-depth”

Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networkscs.LG

New algorithm proves deep networks can learn better than shallow ones.

problem Understanding the power difference between shallow and deep neural networks.

method Identifying a class of Boolean functions and proving that logarithmic-depth networks can learn them efficiently using hierarchical reconstruction.

result First algorithmic separation between constant-depth and logarithmic-depth neural networks.

neural networks depth separations algorithmic results Boolean functions Fourier spectra

2026-07-28abs ↗pdf ↗

LdSM: Logarithm-depth Streaming Multi-label Decision Treescs.LG

LdSM builds efficient multi-label decision trees with logarithmic depth.

problem Efficiently annotate data points with relevant subsets of labels from a large label set.

method Develops LdSM algorithm for multi-label decision trees with logarithmic depth, optimizing a novel objective function for balanced splits and high class purity.

result Minimizing the proposed objective function leads to pure and balanced data splits, achieving high prediction accuracy and low prediction time.

multi-label classification logarithmic-depth decision trees streaming approach high prediction accuracy

2019-05-24abs ↗pdf ↗

Conditional Probability Tree Estimation Analysis and Algorithmscs.LG

We consider the problem of estimating the conditional probability of a label in time O(log n), where n is the number of possible labels. We analyze a natural reduction of this problem to a set of binary regression problems organized in a tree structure, proving a regret bound that scales with the depth of the tree. Mot…

2014-08-09abs ↗pdf ↗

Towards Lower Bounds on the Depth of ReLU Neural Networkscs.LG

New research limits how deep neural networks can be for certain functions.

problem Understanding the depth required for neural networks to represent specific functions.

method Mixed-integer optimization, polyhedral theory, tropical geometry.

result Neural networks with more than one layer are necessary to represent certain functions.

Neural Networks ReLU Depth Mixed-Integer Optimization Polyhedral Theory

2021-05-31abs ↗pdf ↗

In-Context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-Separationcs.LG

Transformers can learn noisy linear systems with depth and IID data.

problem Learning noisy linear dynamical systems with transformers.

method Theoretical analysis of multi-layer and single-layer transformers with respect to

L^2

-testing loss.

result Single-layer transformers have a non-diminishing lower bound on approximation error, suggesting depth separation.

transformers linear dynamical systems approximation bounds depth-separation IID data

2025-02-12abs ↗pdf ↗

Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Datacs.LG

The study explains transformer scaling laws using statistical and approximation theories.

problem Understanding why transformer scaling laws exist for large models trained on low-dimensional data.

method Established statistical estimation and mathematical approximation theories for transformers on low-dimensional manifolds.

result Predicted a power law between generalization error and model and data sizes, with power depending on intrinsic data dimension.

Transformer scaling laws Statistical estimation Mathematical approximation Low-dimensional data Manifold hypothesis

2024-11-11abs ↗pdf ↗

Learnability of the output distributions of local quantum circuitsquant-ph

Study shows limitations and possibilities of learning quantum circuit output distributions.

problem Learnability of output distributions of local quantum circuits.

method Investigated within two oracle models: statistical query model and direct sample access model.

result Output distributions of super-logarithmic depth Clifford circuits are not efficiently learnable in the statistical query model.

quantum circuits learnability statistical query model Clifford group generative modelling

2021-10-11abs ↗pdf ↗