Accelerates nonparametric estimation to near-linear time.
problem Quadratic time complexity in local polynomial regression.
method Novel use of binary indexed trees for multi-dimensional data.
result Near-linear time complexity in computation.
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.
169,236 papers · 148 categories
Trend · papers per month
48 results for “polynomial time-complexity”
Fixed-parameter tractable computation of Reshetikhin--Turaev knot polynomials via tensor networksmath.GT
New algorithm speeds up knot polynomial calculations.
problem Computing Reshetikhin--Turaev knot polynomials efficiently.
method Fixed-parameter tractable computation via tensor networks.
result Knot polynomial computations are fixed-parameter tractable.
EKM solves the K-medoids problem in polynomial time.
problem The -medoids problem in data analysis.
method EKM is a novel algorithm using transformational programming and combinatorial generation.
result EKM solves the -medoids problem in worst-case $O\left(N^{K+1}
ight)$ time complexity.
Algorithm calculates polynomial coefficients of link invariants.
problem Computing first coefficients of link invariants.
method Dynamic programming algorithm for Homflypt and Kauffman polynomials.
result Polynomial time complexity for first coefficients.
On the exact minimization of saturated loss functions for robust regression and subspace estimationcs.LG
Exact minimization of saturated loss functions for robust regression and subspace estimation.
problem Minimizing saturated loss functions for robust regression and subspace estimation.
method Developed an exact algorithm with polynomial time-complexity for robust regression and subspace estimation, relating the problems to linear model approximation.
result Exact minimization of saturated loss functions for robust regression and subspace estimation is possible with polynomial time-complexity.
SCRiBLe optimizes online bandit linear optimization with a polynomial run time.
problem Efficiently solving online bandit linear optimization problems.
method SCRiBLe setup and algorithm with regret bound and polynomial run time complexity.
result Achieves regret bound and polynomial run time complexity.
The paper establishes a nearly-sharp statistical threshold for efficient learning in Latent MDPs with separated components.
problem Learning Latent Markov Decision Processes (LMDPs) with separated components.
method The paper considers various notions of separation and establishes a nearly-sharp statistical threshold for efficient learning. It also presents a quasi-polynomial algorithm with time complexity scaling in terms of the statistical threshold under a weaker assumption of separability under the optimal policy, and a near-matching time complexity lower bound under the exponential time hypothesis.
result Establishes a nearly-sharp statistical threshold for efficient learning in Latent MDPs with separated components.
Algorithm classifies surface homeomorphisms with polynomial time complexity.
problem Classifying surface homeomorphisms with polynomial time complexity.
method Algorithm to compute curve distances and decide Nielsen-Thurston types.
result Polynomial time classification of surface homeomorphisms.
This paper establishes for the first time the predictive performance of speed priors and their computational complexity. A speed prior is essentially a probability distribution that puts low probability on strings that are not efficiently computable. We propose a variant to the original speed prior (Schmidhuber, 2002),…
Paper introduces algorithms for explaining monotonic classifiers.
problem Need for explanations of monotonic classifiers.
method Polynomial algorithms for formal explanations of monotonic classifiers.
result Efficient model-agnostic algorithm for enumerating explanations.
Study on quantitative aspects of trace polynomials in free groups.
problem Understanding the exact formula and bounds for trace polynomials in free groups.
method Proved exact formula for leading homogeneous part, obtained sharp bounds, studied random words, and provided deterministic algorithm.
result Sharp bounds on the degree of trace polynomials and growth rates of polynomial sizes.
Improved time complexity for parallel stochastic optimization in heterogeneous systems.
problem Time complexity in parallel stochastic optimization for large-scale machine learning models.
method Proposes Rennala MVR, a variance-reduced extension of Rennala SGD based on momentum-based variance reduction.
result Variance reduction improves time complexity in relevant parameter regimes for parallel stochastic optimization in heterogeneous systems.
New distances for causal graphs improve evaluation of learned structures.
problem Difficulty in evaluating graphs learned by causal discovery algorithms.
method Developed a framework for causal distances, including new reachability algorithms.
result Improved distances are faster and more scalable than existing methods.
Improving scalability and stability of Stein discrepancies for scalable goodness-of-fit testing
problem Improving scalability and stability of Stein discrepancies for scalable goodness-of-fit testing
method Reformulating Stein discrepancy construction as an explicit SNR^2 maximisation problem
result Avoiding exponential SNR^2 collapse and achieving stable SNR^2
This paper optimizes matrix-based Renyi's entropy computation for large datasets.
problem Efficiently calculating matrix-based Renyi's entropy for large-scale applications.
method Develops randomized approximations for matrix-based Renyi's entropy with arbitrary α orders.
result Achieves a significant reduction in time complexity from O(n^3) to O(n^2sm), where s, m << n.
Algorithm constructs Grushko decomposition of certain groups.
problem Decomposing fundamental groups of graphs of free groups.
method Analyzing vertex links of CAT(0) square complexes.
result Transforms complex to one with strong connectivity vertex links.
Ringmaster ASGD improves Asynchronous SGD's efficiency under varying worker times.
problem Suboptimal performance of Asynchronous SGD under heterogeneous worker computation times.
method Ringmaster ASGD, a novel Asynchronous SGD method with optimal time complexity.
result Ringmaster ASGD achieves optimal time complexity under arbitrary worker heterogeneity.
Optimal algorithms for mixable losses in dynamic environments with reduced redundancy.
problem Online optimization of mixable loss functions in a dynamic environment.
method Introduce online mixture schemes with polynomial and logarithmic time complexities.
result Achieves optimal redundancy up to a constant multiplicity gap.
Quantum SVM clustering speeds up big data analysis.
problem Performance degradation of classical SVM clustering on big data.
method Developed a quantum version of SVM clustering using quantum support vector machine and kernels.
result Significant speed-up gain on run-time complexity.
Polynomial-time algorithm learns high-dimensional halfspaces without labels.
problem Learning high-dimensional halfspaces with margins in polynomial time.
method Contrastive moments and polynomial-time algorithm.
result Establishes the unique and efficient identifiability of the hidden halfspace.
Let be a real closed field, with $ °_{Y}(Q) \leq 2, °_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m$, and with $°_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$. Let be a semi-alg…
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.
The problem of Non-Gaussian Component Analysis (NGCA) is about finding a maximal low-dimensional subspace in so that data points projected onto follow a non-gaussian distribution. Although this is an appropriate model for some real world data analysis problems, there has been little progress on t…
New computational lower bounds for clustering and related problems.
problem Statistical-computational gaps in high-dimensional clustering problems.
method Investigation of low-degree polynomials in latent space models to derive lower bounds.
result New and sharper computational lower bounds for clustering, sparse clustering, and biclustering.
New insights into Khovanov homology complexity and topological structure.
problem Complexity of computing Khovanov homology for closed braids.
method Analysis of independence simplicial complexes and polynomial time algorithms.
result Independence simplicial complexes associated to 4-braid diagrams are homotopy equivalent to wedges of spheres.
A new bootstrapping method reduces key sizes and runtime in FHE.
problem Large plaintext evaluation in FHE increases bootstrapping complexity.
method New polynomial vector representation and monic monomial permutation matrices.
result Polynomial factor improvement in key size and constant factor in runtime.
Paper accelerates nonlinear mapping in online systems with lower time complexity.
problem Speeding up nonlinear mapping in online systems.
method Integrates an acceleration module into Dendrite Net (DD) to reduce time complexity.
result DD with AC has lower time complexity while maintaining nonlinear mapping and system identification properties.
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexitycs.DS
Optimal algorithm learns Gaussian under halfspace truncation with minimal samples.
problem Learning a Gaussian distribution truncated to an unknown halfspace.
method Efficient algorithm using samples and runtime dominated by empirical covariance matrix computation.
result Optimal sample and time complexity bounds for learning a Gaussian under halfspace truncation.
This work introduces a polynomial kernel method for inferring ODE models.
problem Estimating future behavior of dynamical systems from observations.
method Parametric polynomial kernel regression using Backpropagation and Stochastic Gradient Descent.
result Successfully tracks future behavior of chaotic dynamical systems over long time periods.
Federated learning supports exact support recovery with minimal communication.
problem Learning the exact support of sparse linear regression in federated learning.
method One-shot communication algorithm for exact support recovery without optimization.
result Polynomial sample complexity and logarithmic number of clients required.
Efficient algorithms improve learning of large-margin halfspaces.
problem Learning large-margin halfspaces efficiently and reproducibly.
method Design of efficient, dimension-independent, polynomial-time algorithms; SGD-based approach; DP-to-Replicability reduction.
result Improved sample complexity compared to previous algorithms, with optimal sample complexity for one algorithm.
TaLK Convolutions improve sequence modeling efficiency.
problem Efficiently modeling sequences with limited time complexity.
method Adaptive convolution operation that learns kernel size.
result Time complexity reduced to , making sequence encoding linear.
Quantum algorithms improve regret bounds for bandits with knapsacks.
problem Combining stochastic integer programming and online learning.
method Quantum algorithms for BwK with improved regret and time complexities.
result Quantum algorithms achieve better regret bounds than classical methods.
Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscs.LG
Path regularization reveals convex optimization in deep ReLU networks.
problem Understanding the optimization landscape of deep neural networks.
method Introducing path regularization to make the training problem convex and sparsity-inducing.
result Path regularized parallel ReLU networks are a parsimonious convex model in high dimensions.
Improved sample and time complexity for identifying mixtures of product distributions.
problem Identifying a mixture of product distributions from statistics.
method Combining robust tensor decomposition and Hadamard extensions to bound the condition number of key matrices.
result Achieved sample complexity and run-time complexity of for .
Paper proposes efficient SHAP computation methods.
problem Efficient computation of SHAP values for machine learning models.
method Develops polynomial time methods for SHAP computation based on model structure.
result Exact SHAP computation in polynomial time for various model structures.
CascadeBAI identifies best arms in cascading bandits with fixed confidence.
problem Finding the best set of items in cascading bandits with limited feedback.
method Developed CascadeBAI algorithm, derived upper and lower bounds on time complexity, introduced left-sided sub-Gaussian random variables.
result CascadeBAI is optimal in some practical regimes and performs well with limited feedback.
RationalNet improves graph convolutional networks by approximating jump discontinuities more efficiently.
problem Graph convolutional networks struggle with approximating jump discontinuities, leading to oscillations and high computational costs.
method RationalNet uses rational functions to approximate graph signals, avoiding oscillations and reducing computational complexity.
result RationalNet effectively characterizes jump discontinuities, outperforming other methods on both synthetic and real-world graphs.
Fuzzy clustering with similarity queries improves efficiency and accuracy.
problem Clustering uncertain or vague datasets.
method Semi-supervised active clustering framework with oracle similarity queries.
result Polynomial-time approximation algorithm for fuzzy clustering with few similarity queries.
Freya PAGE optimizes nonconvex optimization with heterogeneous, asynchronous workers.
problem Optimizing nonconvex finite-sum problems with varying worker processing times.
method Freya PAGE, a parallel method robust to stragglers and adaptive to slow computations.
result Freya PAGE offers improved time complexity guarantees compared to previous methods.
Paper presents a faster classical algorithm for principal component regression.
problem Efficiently solving principal component regression problems.
method Uses quantum-inspired linear algebra techniques.
result Achieves polylogarithmic runtime, significantly faster than state-of-the-art.
Faster methods for large-scale constrained linear regression using sketching and optimization.
problem Efficiently solving large-scale constrained linear regression problems.
method Combining (accelerated) mini-batch SGD with two-step preconditioning.
result Achieves faster approximate solutions with lower time complexity.
Paper tackles robust estimation of tree-structured Ising models without side information.
problem Learning tree-structured Ising models with flipped signs of variables.
method Proves unidentifiability, proposes an algorithm with logarithmic sample complexity and polynomial run-time complexity.
result Empirically demonstrates robustness of proposed algorithm in the flipped signs setting.
ASCEND discovers causal relationships in multi-omics data by leveraging known hierarchical structure.
problem Causal inference in high-dimensional multi-omics data, especially when ignoring the hierarchical structure.
method Two-tiered divide-and-conquer strategy with ancestral conditioning sets.
result Achieves polynomial-time complexity and accurately recovers ancestral relationships.
Statistical and machine-learning algorithms are frequently applied to high-dimensional data. In many of these applications data is scarce, and often much more costly than computation time. We provide the first sample-efficient polynomial-time estimator for high-dimensional spherical Gaussian mixtures. For mixtures of a…
Wavelet SGM accelerates generative modeling with linear time complexity.
problem High computational cost in SGMs.
method Factorizing data distribution into wavelet coefficients.
result WSGM synthesizes wavelet coefficients with linear time complexity.
Robust estimation is much more challenging in high dimensions than it is in one dimension: Most techniques either lead to intractable optimization problems or estimators that can tolerate only a tiny fraction of errors. Recent work in theoretical computer science has shown that, in appropriate distributional models, it…
New algorithm improves online binary classification with constant time complexity.
problem Online binary classification with rebalancing.
method Non-iteratively reweighted recursive least-squares.
result Exacts converges to batch formulation and outperforms existing algorithms.