Paper speeds up tensor factorization algorithms.
problem Improving convergence speed of tensor factorization algorithms.
method Proposes an extrapolation strategy between block updates.
result HER significantly accelerates convergence speed.
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,181 papers · 148 categories
Trend · papers per month
48 results for “Block Coordinate Descent”
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.
We demonstrate that distributed block coordinate descent can quickly solve kernel regression and classification problems with millions of data points. Armed with this capability, we conduct a thorough comparison between the full kernel, the Nyström method, and random features on three large classification tasks from va…
Paper analyzes ADMM convergence for nonconvex Gaussian phase retrieval.
problem Nonconvex optimization in Gaussian phase retrieval.
method Block coordinate descent as ADMM with dual variable fixed.
result Block coordinate descent converges linearly to global minimizer.
DID solves NMF for large distributed data.
problem Large distributed nonnegative matrix factorization.
method Distributed incremental block coordinate descent.
result Only one communication step per iteration.
Large-scale L1-regularized loss minimization problems arise in high-dimensional applications such as compressed sensing and high-dimensional supervised learning, including classification and regression problems. High-performance algorithms and implementations are critical to efficiently solving these problems. Building…
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…
In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is …
This paper introduces a new method for optimizing large-scale problems using Markov chain block updates.
problem Optimizing large-scale problems with efficient and natural block selection.
method Markov chain block coordinate descent (BCD) for optimization.
result The method converges for minimizing Lipschitz differentiable functions, with sublinear and linear convergence rates for convex and strongly convex functions, respectively.
A new algorithm for training deep neural networks efficiently.
problem Efficient training of deep neural networks due to nonconvex optimization.
method Proximal block coordinate descent (BCD) algorithm based on the Kurdyka-Lojasiewicz (KL) property.
result Global convergence results and competitive efficiency compared to standard optimizers.
Improved DNN training with BCD converging faster than SGD.
problem Training deep neural networks efficiently and accurately.
method Developed a smooth multi-convex formulation and BCD algorithm for training Tikhonov regularized DNNs.
result BCD algorithm converges globally to a stationary point with R-linear rate.
This paper provides a block coordinate descent algorithm to solve unconstrained optimization problems. In our algorithm, computation of function values or gradients is not required. Instead, pairwise comparison of function values is used. Our algorithm consists of two steps; one is the direction estimate step and the o…
BCD algorithm finds global minima in neural networks.
problem Training deep neural networks to find global minima.
method Block coordinate descent with skip connections and non-negative projection.
result Proves convergence to global minima for strictly monotonic and ReLU activations.
Paper compares optimization methods for sparse NCP decomposition of tensors.
problem Efficiently extract meaningful nonnegative and sparse components from tensors.
method Sparse NCP decomposition with l1-norm regularization and block coordinate descent.
result Comparison of optimization methods for tensor decomposition effectiveness and speed.
In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an -accurate solution with probability at least in at most iterations, where is the numbe…
BCD methods provide provable convergence guarantees for deep learning models.
problem Theoretical convergence guarantees for BCD methods in deep learning.
method Established global convergence rate of O(1/k) for DNN training models.
result Global convergence to a critical point at a rate of O(1/k) for most DNN training models.
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 analyze the randomized block-coordinate descent (RBCD) methods proposed in [8,11] for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov's technique developed in [8] for analyzing the RBCD method for minimizing a smooth convex functio…
Paper shows how to use geometric median for robust SGD in high dimensions.
problem Robustifying SGD for high-dimensional optimization problems with gross corruption.
method Applying geometric median to only chosen blocks of coordinates at a time.
result Retains optimal breakdown point of 0.5 for smooth non-convex problems.
BCD-prox improves robustness and accuracy in filtering and parameter estimation.
problem Simultaneous filtering and parameter estimation of complex ODE models.
method Block coordinate descent proximal algorithm (BCD-prox) for ODE systems.
result BCD-prox outperforms state-of-the-art methods in robustness, accuracy, and training time.
CD methods tackle nonconvex optimization with three terms, achieving critical points.
problem Minimizing nonconvex functions with specific structure.
method Developed randomized CD, randomly permuted CD, and accelerated CD methods.
result CD methods converge to critical points with sublinear complexity.
Paper relaxes MAP inference for discrete MRFs, achieving better solutions.
problem Optimizing discrete MRFs for complex real-world problems.
method Nonconvex continuous relaxation, block coordinate descent, gradient methods, ADMM.
result ADMM significantly outperforms other methods in real-world applications.
The cyclic block coordinate descent-type (CBCD-type) methods, which performs iterative updates for a few coordinates (a block) simultaneously throughout the procedure, have shown remarkable computational performance for solving strongly convex minimization problems. Typical applications include many popular statistical…
LPOM approximates neural nets with proximal operators for efficient training.
problem Training feed-forward neural networks efficiently and avoiding gradient issues.
method Rewriting activation functions as proximal operators, using block coordinate descent.
result LPOM converges and performs well on MNIST and CIFAR-10.
Two-layer model sparsifies image residuals for CT image reconstruction.
problem Image reconstruction from limited and corrupted data.
method Pre-learning a two-layer sparsifying transform model with block coordinate descent optimization.
result Preliminary experiments show the two-layer model improves CT image reconstruction from low-dose measurements.
We develop randomized (block) coordinate descent (CD) methods for linearly constrained convex optimization. Unlike most CD methods, we do not assume the constraints to be separable, but let them be coupled linearly. To our knowledge, ours is the first CD method that allows linear coupling constraints, without making th…
Proposes blockwise adaptive stepsize for faster training and better generalization in deep learning.
problem Widespread use of coordinate-wise adaptive methods like RMSprop and Adam leads to worse generalization than SGD.
method Splits network parameters into blocks and uses a blockwise adaptive stepsize, balancing adaptivity and generalization.
result Blockwise adaptive gradient descent converges faster and has lower generalization error than coordinate-wise adaptive methods.
Novel neural network models using convex optimization for improved training.
problem Improving the training of neural networks.
method Representing activation functions as argmin of convex optimization problems, applying block-coordinate descent methods.
result Proposed models provide excellent initial guesses and avenues for extensions.
New algorithm for nonconvex optimization on constrained Riemannian manifolds converges quickly.
problem Optimization on constrained Riemannian manifolds.
method Block majorization-minimization (BMM) for smooth nonconvex objectives with Riemannian constraints.
result Converges to stationary points within iterations.
Clusterpath estimator simplifies graphical model interpretation for large datasets.
problem Difficulty in interpreting graphical models with many variables.
method Clusterpath estimator that groups variables for block-structured precision matrix.
result CGGM outperforms other methods in variable clustering and practical applications.
A new method solves the projection robust Wasserstein distance problem efficiently.
problem Computing the projection robust Wasserstein distance is challenging due to the curse of dimensionality.
method Riemannian block coordinate descent (RBCD) method to solve the regularized max-min problem over the Stiefel manifold.
result RBCD method significantly improves the complexity of obtaining an ε-stationary point compared to existing methods.
Proposes a self-paced multi-label learning method to handle diverse labels efficiently.
problem Learning from multi-label data with a large label space is NP-hard and prone to overfitting.
method Self-paced multi-label learning with diversity (SPMLD) approach, incorporating gradual label inclusion and diversity maintenance.
result The proposed SPMLD framework optimizes a non-convex objective function using block coordinate descent.
We propose a variable decomposition algorithm -greedy block coordinate descent (GBCD)- in order to make dense Gaussian process regression practical for large scale problems. GBCD breaks a large scale optimization into a series of small sub-problems. The challenge in variable decomposition algorithms is the identificati…
First-order methods avoid saddle points for most initializations.
problem Avoiding saddle points in optimization problems.
method First-order methods, including gradient descent and variants, analyzed using dynamical systems and the Stable Manifold Theorem.
result First-order methods avoid saddle points for almost all initializations.
New algorithm efficiently learns sparse causal graphs from time series data.
problem Learning sparse causal graphs from time series data efficiently and automatically selecting the number of edges.
method Cyclical coordinate descent algorithm with two non-parametric error metrics for LASSO coefficient selection.
result State-of-the-art performance on simulated and real datasets.
mlr3mbo is a modular R toolbox for Bayesian optimization.
problem Efficiently solving optimization problems with multiple objectives and constraints.
method Bayesian optimization with support for multi-objective, multi-point proposals, parallelization, and custom algorithms.
result mlr3mbo performs competitively with state-of-the-art optimizers and robustly handles various optimization regimes.
In this article, we derive a Bayesian model to learning the sparse and low rank PARAFAC decomposition for the observed tensor with missing values via the elastic net, with property to find the true rank and sparse factor matrix which is robust to the noise. We formulate efficient block coordinate descent algorithm and …
We propose a randomized nonmonotone block proximal gradient (RNBPG) method for minimizing the sum of a smooth (possibly nonconvex) function and a block-separable (possibly nonconvex nonsmooth) function. At each iteration, this method randomly picks a block according to any prescribed probability distribution and solves…
Random scan CAVI converges linearly under log-concave assumptions.
problem Analyzing the convergence rate of random scan Coordinate Ascent Variational Inference (CAVI) under log-concave conditions.
method Building on previous work, we analyze the random scan version of CAVI using optimal transport geometry.
result We obtain tight linear convergence rates for the random scan version of CAVI.
Paper accelerates NMF algorithms using extrapolation.
problem Efficiently solving nonnegative matrix factorization problems.
method Inspired by convex optimization, uses extrapolation for two-block exact coordinate descent algorithms.
result Significantly accelerates NMF algorithms on various data sets.
Fenchel lifted networks improve neural network training without performance loss.
problem The difficulty and non-convexity of training deep neural networks.
method Introduces Fenchel lifted networks that represent activation functions as biconvex constraints and uses Lagrange Multipliers to create a lower bound of the training problem.
result Fenchel lifted networks match or outperform traditional neural networks in performance.
In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring…
Recent years have witnessed the rapid development of block coordinate update (BCU) methods, which are particularly suitable for problems involving large-sized data and/or variables. In optimization, BCU first appears as the coordinate descent method that works well for smooth problems or those with separable nonsmooth …
A novel hierarchical Bayesian approach to Federated Learning reduces data exposure and improves convergence rates.
problem Data privacy and convergence in Federated Learning.
method Hierarchical Bayesian modeling and block-coordinate descent optimization.
result The proposed algorithm converges to an optimal solution with a rate of and guarantees vanishing generalization error.
Training structured prediction models is time-consuming. However, most existing approaches only use a single machine, thus, the advantage of computing power and the capacity for larger data sets of multiple machines have not been exploited. In this work, we propose an efficient algorithm for distributedly training stru…
This paper studies the partial estimation of Gaussian graphical models from high-dimensional empirical observations. We derive a convex formulation for this problem using -regularized maximum-likelihood estimation, which can be solved via a block coordinate descent algorithm. Statistical estimation performance …
SCOPE fuses categorical variable levels to estimate high-dimensional linear models.
problem Estimating high-dimensional linear models with nominal categorical data.
method SCOPE uses nonconvex concave penalties to fuse levels and achieve efficient computation.
result SCOPE achieves oracle least squares solution under certain conditions.
Study tackles nonlinear factor models with unknown monotone links from incomplete and noisy data.
problem Learning nonlinear factor models with unknown monotone links from incomplete and noisy data.
method Formulated as joint recovery of low-rank factors, loadings, and nonlinear link function; proposed BCD algorithm with regularization.
result Established convergence guarantees and sublinear regret bounds for link-function updates.