MomentQuant: an even more minimalist interval method with linear time complexity for time series classification

• URL: http://arxiv.org/abs/2609.05136v1
• Date: Fri, 04 Sep 2026 13:37:51 GMT
• Title: MomentQuant: an even more minimalist interval method with linear time complexity for time series classification
• Abstract summary: Time series data is very common in many real-world applications and in numerous domains.<n>Time series classification consists in assigning a label to each new, unseen time series.<n>Many algorithms have been developed over the past decades, with the trade-off between predictive performance and computational cost being consistently discussed.
• Score: 0.4145742235679815
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Time series data is very common in many real-world applications and in numerous domains, with increasing interest for automated information extraction using machine learning. One of these subfields is time series classification, which consists in assigning a label to each new, unseen time series. Many algorithms have been developed over the past decades, with the trade-off between predictive performance and computational cost being consistently discussed. Quant, an interval-based algorithm extracting quantiles from recursive, fixed, dyadic intervals, was shown to achieve high accuracy, while being very fast. We propose two changes to make this algorithm even faster. The first one is a better optimized implementation of the exact same algorithm. The second one is to derive approximate quantiles, using the Cornish-Fisher expansion, instead of exact quantiles. This change removes the necessity to sort the time series, leading to a smaller computational complexity. We call this novel algorithm MomentQuant. We provide evidence that our implementation of Quant is faster than the original one, and that MomentQuant is even faster than our implementation of Quant, at the cost of a tiny decrease in predictive performance. These improvements are especially relevant for real-life applications, where inference is performed much more often than training.

Related papers

• Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
  Federated matrices bilevel optimization has been actively studied in recent years due to its widespread applications in machine learning.<n>Most existing federated bilevel optimization algorithms require the computation of second-order Hessian and Jacobian matrices.<n>We propose a novel federated convergence variance-reduced bilevel descent algorithm that relies solely on first-order oracles.
  arXiv  Detail & Related papers  (2026-09-14T21:12:59Z)
• Randomized and quantum approximate matrix multiplication [0.718791111462057]
  A long line of literature considers randomized algorithms, which return an approximate solution in faster time.<n>We first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (99), and based on sketching by Sarl'os (06) and Drineas-Kannan-Mahoney (06)<n>We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches.
  arXiv  Detail & Related papers  (2025-10-09T17:44:03Z)
• Efficient Quantum Approximate $k$NN Algorithm via Granular-Ball Computing [4.294483824607684]
  High time complexity is one of the biggest challenges faced by $k$-Nearest Neighbors ($k$NN)<n>We propose an innovative algorithm called Granular-Ball based Quantum $k$NN(GB-Q$k$NN)
  arXiv  Detail & Related papers  (2025-05-29T04:16:29Z)
• A system identification approach to clustering vector autoregressive time series [50.66782357329375]
  Clustering time series based on their underlying dynamics is keeping attracting researchers due to its impacts on assisting complex system modelling.<n>Most current time series clustering methods handle only scalar time series, treat them as white noise, or rely on domain knowledge for high-quality feature construction.<n>Instead of relying on feature/metric construction, the system identification approach allows treating vector time series clustering by explicitly considering their underlying autoregressive dynamics.
  arXiv  Detail & Related papers  (2025-05-20T14:31:44Z)
• Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
  We provide efficient algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and Sorrell [STOC 2022]
  arXiv  Detail & Related papers  (2024-02-21T15:06:51Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [3.5707423185282665]
  We present an improved quantum algorithm for computing persistent Betti numbers.<n>We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
  arXiv  Detail & Related papers  (2022-09-26T17:56:11Z)
• OMPQ: Orthogonal Mixed Precision Quantization [72.63889596498004]
  Mixed precision quantization takes advantage of hardware's multiple bit-width arithmetic operations to unleash the full potential of network quantization.<n>We propose to optimize a proxy metric, the concept of networkity, which is highly correlated with the loss of the integer programming.<n>This approach reduces the search time and required data amount by orders of magnitude, with little compromise on quantization accuracy.
  arXiv  Detail & Related papers  (2021-09-16T10:59:33Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2021-03-03T22:42:15Z)
• Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
  We develop an algorithm for principal component regression that runs in time polylogarithmic to the number of data points. This exponential speed up allows for potential applications in much larger data sets.
  arXiv  Detail & Related papers  (2020-10-16T20:50:48Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Quantum Ensemble for Classification [2.064612766965483]
  A powerful way to improve performance in machine learning is to construct an ensemble that combines the predictions of multiple models. We propose a new quantum algorithm that exploits quantum superposition, entanglement and interference to build an ensemble of classification models.
  arXiv  Detail & Related papers  (2020-07-02T11:26:54Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.