We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the d…
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,341 papers · 148 categories
Trend · papers per month
48 results for “Block Coordinate Frank-Wolfe”
Improves BCFW for SSVM optimization with adaptive sampling and caching.
problem Optimizing SSVM objective using BCFW algorithm.
method Adaptive gap-based sampling, pairwise and away-step Frank-Wolfe, cache-hit criterion for oracle calls, regularization path computation.
result First method to compute approximate SSVM regularization paths.
New method optimizes MAP inference for structured problems.
problem Structured energy minimization problems
method Proximal bundle method with block-coordinate Frank-Wolfe
result Empirically outperforms state-of-the-art algorithms
We develop parallel and distributed Frank-Wolfe algorithms; the former on shared memory machines with mini-batching, and the latter in a delayed update framework. Whenever possible, we perform computations asynchronously, which helps attain speedups on multicore machines as well as in distributed environments. Moreover…
New Frank-Wolfe method for sparse neural networks.
problem Training sparse neural networks.
method Combines Frank-Wolfe steps and steepest descent steps, with in-face directions and block coordinate steps.
result Significant improvements in training sparse neural networks.
Improved Frank-Wolfe for sparse/low-rank problems.
problem Sparse/low-rank optimization problems.
method Primal-Dual Block Frank-Wolfe algorithm.
result Empirically outperforms state-of-the-art methods in classification tasks.
In this paper, we study optimization methods consisting of iteratively minimizing surrogates of an objective function. By proposing several algorithmic variants and simple convergence analyses, we make two main contributions. First, we provide a unified viewpoint for several first-order optimization techniques such as …
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.
Distributed block coordinate descent solves large kernel problems.
problem Large scale kernel learning problems.
method Distributed block coordinate descent for kernel regression and classification.
result Nyström method generally achieves better statistical accuracy than random features.
Stochastic Frank-Wolfe method solves large-scale Lasso problems efficiently.
problem Sparse model optimization for large-scale Lasso regression.
method Randomized Stochastic Frank-Wolfe algorithm with convergence guarantees.
result Algorithm outperforms state-of-the-art methods on large datasets.
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.
It is shown that, in four dimensions, it is possible to introduce coordinates so that an analytic metric locally takes block diagonal form. i.e. one can find coordinates such that for where . We call a coordinate system in which the metric takes this for…
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.
Efficient method solves large-scale saddle point problems with parallel updates.
problem Large-scale convex-concave saddle point problems with separable structure.
method Stochastic parallel block coordinate descent with adaptive primal-dual updates.
result Significantly better performance than state-of-the-art methods in various applications.
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.
A fast metric learning framework using Gershgorin disc alignment.
problem Learning effective metrics for graph-based data.
method Fast projection-free metric learning via Gershgorin disc alignment.
result Efficiently computed graph metric matrices outperform competing methods.
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.
New adaptive stepsize method for stochastic approximation converges to target point.
problem Finding optimal step sizes for stochastic approximation algorithms.
method Adaptive block-coordinate stepsizes using online estimates of second moment.
result New method converges almost surely to a small neighborhood of the target point.
New taxonomy and improved solvers for discrete energy minimization.
problem Maximum-a-posteriori inference in discrete graphical models.
method Dual block-coordinate ascent rule, theoretical analysis, new solver variants.
result Improved state-of-the-art solver outperforming existing methods on all test instances.
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…
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 …
New nonconvex Frank-Wolfe methods for faster optimization.
problem Nonconvex optimization problems in machine learning.
method Stochastic Frank-Wolfe methods for nonconvex optimization.
result Improved convergence rates for nonconvex optimization.
Accelerated method for solving convex optimization problems with linear constraints.
problem Solving large-scale convex optimization problems with linear constraints.
method Primal-dual proximal block coordinate updating method with accelerated convergence.
result Achieves convergence rate for strongly convex objectives and linear rate for independent blocks.
Unified framework for efficient Frank-Wolfe optimization of Dominant Set Clustering.
problem Optimizing Dominant Set Clustering with various Frank-Wolfe algorithms.
method Unified framework for pairwise, standard, and away-steps Frank-Wolfe algorithms, with explicit convergence rates.
result Explicit convergence rates for Frank-Wolfe methods in Dominant Set Clustering.
Improved Frank-Wolfe algorithms for large-scale optimization.
problem Efficiently solving large-scale optimization problems.
method Modifications to Frank-Wolfe algorithm using stochastic gradients, approximate solutions, and sketched variables.
result Achieves optimal convergence rate of for large problems.
Accelerated Block Coordinate Proximal Gradients with Applications in High Dimensional Statisticsmath.OC
New method accelerates optimization for nonconvex problems in statistics.
problem Nonconvex optimization problems in statistics and machine learning.
method Adaptive momentum and block coordinate proximal gradient method with specific update rules.
result The method achieves provable local linear convergence in sparse linear regression problems.
Paper studies Frank-Wolfe algorithm for solving sparse reconstruction problems.
problem Sparse reconstruction problem
method Frank-Wolfe algorithm applied to quasi-incoherent dictionaries
result Algorithm converges exponentially fast for quasi-incoherent dictionaries
Boosted Frank-Wolfe accelerates optimization for nonconvex problems.
problem Optimizing nonconvex and quasar-convex objectives efficiently.
method Developed a novel step size strategy for stochastic Frank-Wolfe, extending it to various gradient estimators.
result Boosted Frank-Wolfe achieves faster convergence rates than non-boosted Frank-Wolfe.
Optimal Coordinate Ascent (OCA) improves feature selection in machine learning.
problem Efficiently selecting features in machine learning models.
method Optimal Coordinate Ascent (OCA) for feature selection.
result OCA outperforms previous methods in feature selection and model performance.
New algorithm for parallel inference without block partitioning.
problem Slow inference in probabilistic models due to single-variable updates.
method Lower bounds ELBO with forest mixture bound for parallel inference.
result Algorithm converges faster for 'forest-like' models.
Unified view of Lion and Muon as Stochastic Frank-Wolfe methods.
problem Optimization of constrained problems in deep learning.
method Interpreting Lion and Muon as Stochastic Frank-Wolfe methods and extending the approach to heavy-tailed noise.
result Convergence guarantees and KKT point convergence for Lion and Muon.
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.
New algorithm for convex optimization with coupled constraints and linear constraints.
problem General multi-block convex optimization with coupled objective and linear constraints.
method Randomized primal-dual proximal block coordinate updates.
result Established convergence rate for objective value and feasibility measure.
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.
Improved Frank-Wolfe algorithm solves convex trace-norm ball problems.
problem Optimizing convex functions over trace-norm balls.
method Rank-k variant of Frank-Wolfe algorithm using top-k singular-vector computation.
result Linear convergence rate for smooth and strongly convex objectives with rank-limited solutions.
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.
Momentum accelerates Frank Wolfe algorithms on certain problems.
problem Improving convergence rate of Frank Wolfe algorithms.
method Introducing momentum into Frank Wolfe algorithms and proving faster convergence rate.
result Accelerated Frank Wolfe (AFW) converges with a faster rate of .
A new metric learning framework for signed graphs using Gershgorin disc alignment.
problem Learning Mahalanobis metrics from signed graphs efficiently.
method Proposes a fast metric learning framework using Gershgorin disc perfect alignment (GDPA) to circumvent full eigen-decomposition.
result Proves that Gershgorin disc left-ends of similarity transform are perfectly aligned at the smallest eigenvalue, enabling efficient optimization.
Async-parallel method solves convex problems with nonseparable linear constraints.
problem Solving convex problems with nonseparable linear constraints in an asynchronous setting.
method Randomized primal-dual block coordinate update (BCU) method.
result The objective value sequence converges to the optimal value and constraint residual to zero under convexity assumption.
A new method reduces rank in Frank-Wolfe steps for nuclear norm problems.
problem High rank intermediate iterates in Frank-Wolfe algorithm for nuclear norm problems.
method Rank-drop steps to ensure rank decreases and feasibility.
result Reduced rank of solutions compared to Frank-Wolfe and variants.
Efficiently trains structured SVMs on multiple machines.
problem Training structured prediction models is slow.
method Distributed block-coordinate descent method.
result Our method is efficient, as shown by both theory and experiments.
A hybrid method combines Jacobian and Gauss-Seidel updates for linearly constrained convex programming.
problem Solving linearly constrained convex programming problems with nonseparable constraints.
method Hybrid Jacobian and Gauss-Seidel proximal block coordinate update method.
result The hybrid method converges and performs as well as Gauss-Seidel method and better than a randomized primal-dual BCU method.
A new algorithm solves bilinear saddle-point problems efficiently.
problem Solving bilinear saddle-point problems in optimization.
method Doubly stochastic primal-dual coordinate method.
result The method converges linearly and has lower complexity than existing methods.
Frank-Wolfe algorithm finds stationary points at rate for non-convex objectives.
problem Finding stationary points in non-convex objectives.
method Frank-Wolfe algorithm with a rate analysis.
result The Frank-Wolfe algorithm achieves a convergence rate of for non-convex objectives.
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…
Improved Frank-Wolfe algorithm for generalized self-concordant functions converges quickly.
problem Efficiently solving learning problems with generalized self-concordant objectives.
method Simple Frank-Wolfe variant with open-loop step size strategy .
result Achieves convergence rate for primal and Frank-Wolfe gaps.
Three online algorithms for submodular maximization with varying feedback types.
problem Maximizing submodular functions under different feedback models.
method Mono-Frank-Wolfe, Bandit-Frank-Wolfe, Responsive-Frank-Wolfe.
result Achieved -regret bounds for each algorithm.
A matrix factorization method detects text outliers using low rank approximations.
problem Challenges in detecting outliers in text data with mostly zero values.
method TONMF based on block coordinate descent (BCD) framework.
result Effective in distinguishing anomalies from natural variations in text data.