Dimensionality reduction methods are very common in the field of high dimensional data analysis. Typically, algorithms for dimensionality reduction are computationally expensive. Therefore, their applications for the analysis of massive amounts of data are impractical. For example, repeated computations due to accumula…
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
48 results for “algorithmic reductions”
New algorithm reduces optimization complexity in adaptive mirror descent.
problem Optimizing complex, non-smooth, non-convex functions efficiently.
method SVRAMD: Variance Reduced Adaptive Mirror Descent.
result Variance reduction accelerates convergence in adaptive mirror descent.
This paper proposes BRIEF, a backward reduction algorithm that explores compact CNN-model designs from the information flow perspective. This algorithm can remove substantial non-zero weighting parameters (redundant neural channels) of a network by considering its dynamic behavior, which traditional model-compaction te…
This work examines consistency issues in Gaussian Mixture Model reduction algorithms.
problem Consistency issues in Gaussian Mixture Model reduction algorithms.
method Discussion of the importance of dissimilarity measure choice and consistency of GMR algorithms.
result Most existing GMR algorithms are not consistent with a unique measure, leading to suboptimal reduced GMs.
Paper develops momentum schemes with variance reduction for non-convex composition optimization.
problem Lack of convergence guarantee and efficient momentum design in existing algorithms.
method Develops various momentum schemes with SPIDER-based variance reduction.
result Achieves near-optimal sample complexity and linear convergence rate.
We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD). Remarkable recent progress has been made in this direction through development of algorithms like SAG, SVRG, SAGA. These algorithms have been shown to outperform SGD, both theoretically and empirically. However, asynchro…
Develops a new SPP algorithm with variance reduction for weakly convex optimization.
problem Weakly convex, composite optimization problems.
method Inexact semismooth Newton framework with variance reduction for stochastic proximal point updates.
result Establishes convergence results for the proposed algorithm.
The diverse world of machine learning applications has given rise to a plethora of algorithms and optimization methods, finely tuned to the specific regression or classification task at hand. We reduce the complexity of algorithm design for machine learning by reductions: we develop reductions that take a method develo…
Introduces a reduction system for Artin-Tits groups, improving algorithms and proving periodicity results.
problem Computing reduction systems in Artin-Tits groups of spherical type.
method Introduces a canonical reduction system, proves periodicity of centralizers, and provides algorithms.
result Improved algorithms for computing reduction systems in braid groups and Artin-Tits groups.
We propose a greedy mixture reduction algorithm which is capable of pruning mixture components as well as merging them based on the Kullback-Leibler divergence (KLD). The algorithm is distinct from the well-known Runnalls' KLD based method since it is not restricted to merging operations. The capability of pruning (in …
Sliced inverse regression (SIR) is a pioneer tool for supervised dimension reduction. It identifies the effective dimension reduction space, the subspace of significant factors with intrinsic lower dimensionality. In this paper, we propose to refine the SIR algorithm through an overlapping slicing scheme. The new algor…
New algorithm for context bandits with continuous actions.
problem Efficient decision-making with unknown action structures.
method Reduction-style algorithm combining supervised learning.
result Proven to work in general and validated with experiments.
Principal component analysis balancing prediction and approximation accuracy for spatial datastat.ME
New algorithm balances spatial data approximation and prediction accuracy.
problem Lack of methods considering spatial correlation and downstream modeling in dimension reduction.
method Formalizes approximation and modeling utility as metrics, proposes a balanced algorithm.
result Optimal trade-off between approximation accuracy and downstream modeling utility.
FibeRed reduces complex data dimensions while preserving topology.
problem Hard embedding of topologically complex datasets in low-dimensional Euclidean space.
method Modeling datasets with vector bundles, reducing fibers while preserving topology.
result FibeRed learns topologically faithful embeddings in lower dimensions than existing methods.
MARS optimizes large model training by reducing variance, outperforming AdamW.
problem Training large models efficiently and scalably.
method Unified optimization framework MARS combining preconditioned gradient updates and variance reduction.
result MARS outperforms AdamW in training GPT-2 models.
Ensemble learning has had many successes in supervised learning, but it has been rare in unsupervised learning and dimensionality reduction. This study explores dimensionality reduction ensembles, using principal component analysis and manifold learning techniques to capture linear, nonlinear, local, and global feature…
Riemannian stochastic quasi-Newton algorithm with variance reduction and its convergence analysiscs.LG
Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite number of loss functions. The present paper proposes a Riemannian stochastic quasi-Newton algorithm with variance reduction (R-SQN-VR). The key challenges of averaging, adding, and subtracting multipl…
Ant colonies and boosting algorithms both reduce bias and variance through adaptive mechanisms.
problem Understanding the mathematical principles behind ensemble learning and ant colony behavior.
method Developed a formal mapping between AdaBoost's adaptive reweighting and ant recruitment dynamics.
result Proved that the fundamental theorem of weak learnability has a direct analog in colony decision-making.
New algorithms for clustering and dimension reduction using relative von Neumann entropy.
problem Clustering and dimension reduction for complex data sets.
method Construct graphs from data points, select graph maximizing relative von Neumann entropy, use eigenvectors for dimension reduction.
result Outperforms existing methods on non-trivial data sets.
Paper identifies reductive MDPs, solving them in polynomial time.
problem Computational hardness of general MDPs and tractability of finite-horizon MDPs.
method Defines reductivity, a new class of SSPs, and develops a polynomial-time solution.
result Optimal policies can be found in polynomial time for reductive SSPs and MDPs.
Proposes a faster Isomap algorithm by reducing eigenvalue decomposition complexity.
problem High computational complexity of Isomap, especially in eigenvalue decomposition stage.
method Introduces a projection operator to reduce the complexity of the eigenvalue decomposition stage to linear order.
result Reduces Isomap's computational complexity to linear order while preserving structural information.
Study reduces dimensions for -means clustering for better accuracy.
problem Improving accuracy of -means clustering with high-dimensional data.
method Four randomized algorithms: two feature selection and two feature extraction.
result Provably accurate approximations of -means clustering are obtained.
This thesis explores fast algorithms for large matrices and data augmentation to improve model efficiency.
problem Efficient handling of large models and data in scientific computing and machine learning.
method Randomized low-rank decomposition algorithms and data augmentation techniques.
result Improved sample efficiency and generalization of machine learning models.
TrIM improves gradient-based dimension reduction and regression.
problem Efficiently identifying relevant feature subspace for high-dimensional regression.
method Introduced TrIM forest, an iterative approach using Mondrian forest and EGOP estimate.
result Consistency guarantees and convergence rates for EGOP matrix and random forest estimator.
Branching embedding: A heuristic dimensionality reduction algorithm based on hierarchical clusteringstat.ML
This paper proposes a new dimensionality reduction algorithm named branching embedding (BE). It converts a dendrogram to a two-dimensional scatter plot, and visualizes the inherent structures of the original high-dimensional data. Since the conversion part is not computationally demanding, the BE algorithm would be ben…
UMAP (Uniform Manifold Approximation and Projection) is a novel manifold learning technique for dimension reduction. UMAP is constructed from a theoretical framework based in Riemannian geometry and algebraic topology. The result is a practical scalable algorithm that applies to real world data. The UMAP algorithm is c…
Conjugate gradient (CG) methods are a class of important methods for solving linear equations and nonlinear optimization problems. In this paper, we propose a new stochastic CG algorithm with variance reduction and we prove its linear convergence with the Fletcher and Reeves method for strongly convex and smooth functi…
New DR method uses Gromov-Wasserstein distance for high-dimensional data.
problem Analyzing relationships between high-dimensional objects.
method Optimal transportation theory and Gromov-Wasserstein distance.
result Robust and efficient solution for complex high-dimensional datasets.
Unsupervised learning of time series data, also known as temporal clustering, is a challenging problem in machine learning. Here we propose a novel algorithm, Deep Temporal Clustering (DTC), to naturally integrate dimensionality reduction and temporal clustering into a single end-to-end learning framework, fully unsupe…
Novel technique reduces Bayesian network complexity while preserving inference accuracy.
problem Complexity reduction in Bayesian networks for efficient inference.
method Directed convex hull structure and polynomial-time algorithm for identifying minimum localized networks.
result High dimension reduction capability and improved inference efficiency in real networks.
A new framework for bilevel optimization tackles stochastic and global variance reduction.
problem Bilevel optimization challenges in large-scale empirical risk minimization.
method Introducing a novel framework where inner and main variables evolve simultaneously, leading to unbiased estimates and global variance reduction algorithms.
result SABA algorithm achieves $O( rac{1}{T})$ convergence rate and linear convergence under Polyak-Lojasciewicz assumption.
Dimensionality reduction is a topic of recent interest. In this paper, we present the classification constrained dimensionality reduction (CCDR) algorithm to account for label information. The algorithm can account for multiple classes as well as the semi-supervised setting. We present an out-of-sample expressions for …
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
This work improves understanding of dimension reduction algorithms and their probabilistic embeddings.
problem Improving theoretical understanding of non-linear dimension reduction algorithms.
method Analytical investigation of a generalized multidimensional scaling optimization problem.
result Probabilistic formulation of the problem leads to deterministic embeddings, contrary to standard implementations.
BlosSOM improves data visualization for large datasets.
problem Insufficient performance of dimensionality reduction methods for large datasets.
method GPU-accelerated semi-supervised EmbedSOM algorithm.
result Produces high-quality visualizations with user control.
A new framework learns clustering and dimensionality reduction together.
problem Challenges in clustering high-dimensional data.
method Gradient-based manifold optimization for joint learning.
result Better performance compared to existing clustering algorithms.
Stochastic gradient Markov Chain Monte Carlo (SG-MCMC) has been developed as a flexible family of scalable Bayesian sampling algorithms. However, there has been little theoretical analysis of the impact of minibatch size to the algorithm's convergence rate. In this paper, we prove that under a limited computational bud…
Paper proposes a method to estimate variance reduction in DNN training using importance sampling.
problem Challenges in assessing variance reduction during DNN training using importance sampling.
method Proposes a method for estimating variance reduction using minibatches sampled under importance sampling.
result Demonstrates consistent reduction in variance, improved training efficiency, and enhanced model accuracy.
It is difficult to find the optimal sparse solution of a manifold learning based dimensionality reduction algorithm. The lasso or the elastic net penalized manifold learning based dimensionality reduction is not directly a lasso penalized least square problem and thus the least angle regression (LARS) (Efron et al. \ci…
Adaptive reduction scheme approximates optimal policy in regularized MDPs.
problem Finding near optimal policy in regularized MDPs with biased solutions.
method Adaptive reduction of regularization parameter λ to approximate optimal policy.
result Iteration complexity reduced for obtaining ε-optimal policy.
Enhances option pricing for American-style options using JDOI method.
problem Pricing American-style options efficiently under stochastic volatility.
method Extends DOI variance reduction technique to Lévy dynamics, combining with LSMC.
result Strong variance reduction in option pricing compared to standard LSMC.
New algorithms reduce variance in solving complex mathematical problems.
problem Solving convex-concave saddle point problems, variational inequalities, and inclusions.
method Stochastic variance reduction for extragradient, forward-backward-forward, and forward-reflected-backward methods.
result All proposed methods converge with complexities matching or improving deterministic counterparts.
We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algor…
We give a reduction from {\sc clique} to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.
Efficiently reduces tensor ranks using mean-field approximation.
problem Low-rank approximation of non-negative tensors.
method Mean-field approximation of tensor rank reduction.
result Our algorithm achieves faster and competitive tensor rank reduction.
Dictionary leaning (DL) and dimensionality reduction (DR) are powerful tools to analyze high-dimensional noisy signals. This paper presents a proposal of a novel Riemannian joint dimensionality reduction and dictionary learning (R-JDRDL) on symmetric positive definite (SPD) manifolds for classification tasks. The joint…
Scalability of statistical estimators is of increasing importance in modern applications and dimension reduction is often used to extract relevant information from data. A variety of popular dimension reduction approaches can be framed as symmetric generalized eigendecomposition problems. In this paper we outline how t…
Modeling data as being sampled from a union of independent subspaces has been widely applied to a number of real world applications. However, dimensionality reduction approaches that theoretically preserve this independence assumption have not been well studied. Our key contribution is to show that projection vect…