There has been significant recent work on the theory and application of randomized coordinate descent algorithms, beginning with the work of Nesterov [SIAM J. Optim., 22(2), 2012], who showed that a random-coordinate selection rule achieves the same convergence rate as the Gauss-Southwell selection rule. This result su…
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 “coordinate selection”
Coordinate descent methods usually minimize a cost function by updating a random decision variable (corresponding to one coordinate) at a time. Ideally, we would update the decision variable that yields the largest decrease in the cost function. However, finding this coordinate would require checking all of them, which…
Method selects interpretable circular coordinates from data.
problem Abstract circular coordinates are hard to interpret.
method Minimum-weight basis problem in vector matroid for selecting interpretable circle-valued coordinates.
result Proves consistency of cochain inner product estimator.
Coordinate descent with random coordinate selection is the current state of the art for many large scale optimization problems. However, greedy selection of the steepest coordinate on smooth problems can yield convergence rates independent of the dimension , and requiring upto times fewer iterations. In this pap…
Coordinate descent (CD) algorithms have become the method of choice for solving a number of optimization problems in machine learning. They are particularly popular for training linear models, including linear support vector machine classification, LASSO regression, and logistic regression. We consider general CD with …
A new method for high-dimensional Bayesian optimization.
problem Challenges in extending BO to high dimensions.
method Expected Coordinate Improvement (ECI) criterion for high-dimensional Bayesian optimization.
result Significantly better results than standard BO and competitive results with state-of-the-art methods.
Isometry pursuitstat.ML
Isometry pursuit identifies orthonormal submatrices from wide matrices.
problem Identifying isometric embeddings from wide matrices.
method A convex algorithm combining normalization and multitask basis pursuit.
result The method identifies isometric embeddings from interpretable dictionaries.
In machine learning, Feature Selection (FS) is a major part of efficient algorithm. It fuels the algorithm and is the starting block for our prediction. In this paper, we present a new method, called Optimal Coordinate Ascent (OCA) that allows us selecting features among block and individual features. OCA relies on coo…
To answer the existence of optimal swimmer learning/teaching strategies, this work introduces a two-level clustering in order to analyze temporal dynamics of motor learning in breaststroke swimming. Each level have been performed through Sparse Fisher-EM, a unsupervised framework which can be applied efficiently on lar…
Study uses reinforcement learning to optimize metachronal paddling at low Reynolds number.
problem Optimizing metachronal paddling strategies for efficient swimming at low Reynolds numbers.
method Applied reinforcement learning to a swimmer model with varying paddle spacings.
result The reinforcement learning algorithm selects a back-to-front metachronal wave-like stroke as the most efficient, regardless of the number of paddles.
Coordinate descent methods employ random partial updates of decision variables in order to solve huge-scale convex optimization problems. In this work, we introduce new adaptive rules for the random selection of their updates. By adaptive, we mean that our selection rules are based on the dual residual or the primal-du…
We propose and analyze a new parallel coordinate descent method---`NSync---in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen non-uniformly. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities t…
Datasets with hundreds to tens of thousands features is the new norm. Feature selection constitutes a central problem in machine learning, where the aim is to derive a representative set of features from which to construct a classification (or prediction) model for a specific task. Our experimental study involves micro…
Solving tasks with sparse rewards is one of the most important challenges in reinforcement learning. In the single-agent setting, this challenge is addressed by introducing intrinsic rewards that motivate agents to explore unseen regions of their state spaces; however, applying these techniques naively to the multi-age…
This paper investigates the grant-free random access with massive IoT devices. By embedding the data symbols in the signature sequences, joint device activity detection and data decoding can be achieved, which, however, significantly increases the computational complexity. Coordinate descent algorithms that enjoy a low…
In this paper we develop and analyze Hydra: HYbriD cooRdinAte descent method for solving loss minimization problems with big data. We initially partition the coordinates (features) and assign each partition to a different node of a cluster. At every iteration, each node picks a random subset of the coordinates from tho…
In recent years, state-of-the-art methods for supervised learning have exploited increasingly gradient boosting techniques, with mainstream efficient implementations such as xgboost or lightgbm. One of the key points in generating proficient methods is Feature Selection (FS). It consists in selecting the right valuable…
The method of block coordinate gradient descent (BCD) has been a powerful method for large-scale optimization. This paper considers the BCD method that successively updates a series of blocks selected according to a Markov chain. This kind of block selection is neither i.i.d. random nor cyclic. On the other hand, it is…
Differentially private random block coordinate descent improves utility in machine learning.
problem Lack of privacy in classical CD methods when handling sensitive information.
method Proposes a differentially private random block coordinate descent method using sketch matrices and importance sampling.
result Demonstrates improved convergence rates and utility guarantees compared to non-private methods.
Improved greedy 2-coordinate updates for optimization problems with constraints.
problem Minimizing smooth functions subject to constraints.
method Exploiting a connection to steepest descent in the 1-norm, we give faster convergence rates and efficient computation.
result Greedy selection converges faster than random selection and can be computed in time.
Coordinate Descent for SLOPEmath.OC
A new fast algorithm solves SLOPE optimization problem.
problem Inefficient algorithms for SLOPE optimization in high dimensions.
method Combines proximal gradient descent and proximal coordinate descent steps.
result Our method outperforms competing algorithms in benchmarks.
A new sampling method reduces computational cost for high-dimensional log-concave distributions.
problem High computational cost of ULMC in high dimensions.
method Random Coordinate ULMC (RC-ULMC) selects a single coordinate per iteration.
result RC-ULMC is cheaper than classical ULMC, especially in highly skewed and high-dimensional problems.
Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is also the same as accelerated stochastic gradient descent that is one of the central methods used in machine learning. In this paper, we imp…
Picasso is a new library for sparse learning problems in R and Python.
problem Sparse learning problems in high-dimensional data analysis.
method Unified framework of pathwise coordinate optimization with efficient active set selection strategies.
result picasso can efficiently handle large-scale problems.
Study improves model robustness in noisy datasets.
problem Instance-specific label noise in robust classification tasks.
method Coordinated Sparse Recovery (CSR) method introduces a collaboration matrix and confidence weights to reduce generalization error.
result CSR and CSR+ significantly reduce generalization error compared to existing methods.
Efficiently identifies important variables in binary outcomes using variational Bayes.
problem Bayesian variable selection for binary outcomes with computational challenges.
method Mean-field variational Bayes approximation with closed-form updates and efficient inference algorithm.
result Successfully identifies important variables and is orders of magnitude faster than MCMC.
New method selects sparse predictors in large LMMs.
problem Sparse learning for LMMs is computationally infeasible for large datasets.
method Developed an regularized method with coordinate descent and local search algorithms.
result Method selects thousands of predictors in seconds to minutes.
We consider convex-concave saddle point problems with a separable structure and non-strongly convex functions. We propose an efficient stochastic block coordinate descent method using adaptive primal-dual updates, which enables flexible parallel optimization for large-scale problems. Our method shares the efficiency an…
Most prior work on active learning of classifiers has focused on sequentially selecting one unlabeled example at a time to be labeled in order to reduce the overall labeling effort. In many scenarios, however, it is desirable to label an entire batch of examples at once, for example, when labels can be acquired in para…
Bayesian model selection via mean-field variational approximation improves efficiency and accuracy.
problem Bayesian model selection under model mis-specification and latent variables.
method Mean-field variational approximation with non-asymptotic properties and geometric convergence.
result ELBO tends to select models closer to the true model than BIC as sample size increases.
Many manifold embedding algorithms fail apparently when the data manifold has a large aspect ratio (such as a long, thin strip). Here, we formulate success and failure in terms of finding a smooth embedding, showing also that the problem is pervasive and more complex than previously recognized. Mathematically, success …
We consider a generic convex-concave saddle point problem with separable structure, a form that covers a wide-ranged machine learning applications. Under this problem structure, we follow the framework of primal-dual updates for saddle point problems, and incorporate stochastic block coordinate descent with adaptive st…
In this paper, we introduce DICOD, a convolutional sparse coding algorithm which builds shift invariant representations for long signals. This algorithm is designed to run in a distributed setting, with local message passing, making it communication efficient. It is based on coordinate descent and uses locally greedy u…
We introduce the Locally Linear Latent Variable Model (LL-LVM), a probabilistic model for non-linear manifold discovery that describes a joint distribution over observations, their manifold coordinates and locally linear maps conditioned on a set of neighbourhood relationships. The model allows straightforward variatio…
We study data-driven assistants that provide congestion forecasts to users of shared facilities (roads, cafeterias, etc.), to support coordination between them, and increase efficiency of such collective systems. Key questions are: (1) when and how much can (accurate) predictions help for coordination, and (2) which as…
Promoting Coordination through Policy Regularization in Multi-Agent Deep Reinforcement Learningcs.LG
In multi-agent reinforcement learning, discovering successful collective behaviors is challenging as it requires exploring a joint action space that grows exponentially with the number of agents. While the tractability of independent agent-wise exploration is appealing, this approach fails on tasks that require elabora…
Researchers in functional neuroimaging mostly use activation coordinates to formulate their hypotheses. Instead, we propose to use the full statistical images to define regions of interest (ROIs). This paper presents two machine learning approaches, transfer learning and selection transfer, that are compared upon their…
Gibbs sampler mixes quickly for certain smooth distributions.
problem Drawing samples from log-smooth log-concave distributions.
method Analyzes Gibbs sampler on log-smooth and strongly log-concave distributions.
result Gibbs sampler mixes in steps.
We introduce GAMSEL (Generalized Additive Model Selection), a penalized likelihood approach for fitting sparse generalized additive models in high dimension. Our method interpolates between null, linear and additive models by allowing the effect of each variable to be estimated as being either zero, linear, or a low-co…
A new sampling method, RC-LMC, reduces computational cost for high-dimensional log-concave distributions.
problem High computational cost of LMC in high dimensions.
method RC-LMC updates only one coordinate at a time, adding noise.
result RC-LMC is more efficient than LMC in high dimensions, especially for skewed distributions.
MaxMax Q-Learning improves coordination in multi-agent reinforcement learning by refining action selection.
problem Relative over-generalization in decentralized multi-agent reinforcement learning.
method MaxMax Q-Learning employs iterative sampling and evaluation of potential next states to refine approximations of ideal state transitions.
result MaxMax Q-Learning frequently outperforms existing baselines, demonstrating enhanced convergence and sample efficiency.
A new family of penalty functions, adaptive to likelihood, is introduced for model selection in general regression models. It arises naturally through assuming certain types of prior distribution on the regression parameters. To study stability properties of the penalized maximum likelihood estimator, two types of asym…
New retraction on symplectic Stiefel manifold with closed-form inverse.
problem Efficient mapping of manifold data to Euclidean domain.
method Introduces a new retraction map with a closed-form inverse.
result The new retraction has a closed-form inverse, unlike previous methods.
CobBO optimizes expensive functions in high dimensions by using a two-stage kernel approach.
problem Bayesian optimization struggles in high dimensions due to computational inefficiency.
method Coordinate backoff Bayesian Optimization with two-stage kernels.
result CobBO finds solutions comparable to or better than other methods in high dimensions.
Efficient NTF algorithm for large sparse tensors.
problem Sparse multi-dimensional data and limitations of existing NTF algorithms.
method Saturating Coordinate Descent with element selection based on Lipschitz continuity.
result Proposes a scalable NTF algorithm for large tensors.
Typical cohorts in brain imaging studies are not large enough for systematic testing of all the information contained in the images. To build testable working hypotheses, investigators thus rely on analysis of previous work, sometimes formalized in a so-called meta-analysis. In brain imaging, this approach underlies th…
Stability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selectionmath.ST
Improved Lasso estimator speeds up variable selection.
problem Efficient variable selection in high-dimensional data.
method Stability principle-based generalized debiased Lasso.
result Significantly reduces computational cost of resampling-based methods.
We propose a novel algorithm for efficiently computing a sparse directed adjacency matrix from a group of time series following a causal graph process. Our solution is scalable for both dense and sparse graphs and automatically selects the LASSO coefficient to obtain an appropriate number of edges in the adjacency matr…