In this paper, we study Clifford-Wolf translations of Finsler spaces. We first give a characterization of Clifford-Wolf translations of Finsler spaces in terms of Killing vector fields. In particular, we show that there is a natural correspondence between Clifford-Wolf translations and the Killing vector fields of cons…
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,051 papers · 148 categories
Trend · papers per month
48 results for “Wolfe condition”
Improved Frank-Wolfe algorithm for polytopes converges linearly with dimension dependence on optimal face.
problem Efficiently solving convex minimization problems over polytopes with linear rate.
method Revisiting Frank-Wolfe algorithm with strict complementarity assumption and away-steps.
result Linear convergence rate independent of polytope dimension for optimal face.
New algorithm improves CRF inference and learning.
problem Efficient inference and learning for dense CRFs.
method Regularized Frank-Wolfe algorithm for nonconvex CRF optimization.
result Regularized Frank-Wolfe outperforms mean field and CNN baselines.
The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine learning applications. However, its convergence rate is known to be slow (sublinear) when the solution lies at the boundary. A simple less-know…
This work extends Ledoit-Wolf shrinkage to unknown mean covariance estimation.
problem Large dimensional covariance matrix estimation with unknown mean under Kolmogorov asymptotics.
method Extending Ledoit-Wolf linear shrinkage to translation-invariant estimators, proving their convergence properties.
result A new estimator outperforms other standard estimators empirically.
In this paper, we introduce a new type of Finsler metrics, called -metrics. We define the notion of the good datum of a homogeneous -metric and use that to study the geometric properties. In particular, we give a formula of the S-curvature and deduce a condition for the S-curvature to be vanishing…
New conditions ensure Dantzig-Wolfe relaxation matches rank-constrained optimization problems.
problem Rank-constrained optimization problems with linear matrix inequalities.
method Investigates Dantzig-Wolfe relaxation and develops conditions for exactness.
result Conditions for extreme point, convex hull, and objective exactness.
Paper improves Frank-Wolfe algorithm's efficiency bounds.
problem Establishing efficient iteration complexity for Frank-Wolfe algorithm.
method Using metric entropy to provide lower bounds.
result Frank-Wolfe requires many iterations for certain problems.
We consider a distributed parameter estimation problem, in which multiple terminals send messages related to their local observations using limited rates to a fusion center who will obtain an estimate of a parameter related to observations of all terminals. It is well known that if the transmission rates are in the Sle…
Improved Frank-Wolfe algorithm for constrained convex optimization with nearest extreme point oracle.
problem Constrained smooth convex minimization with limited linear optimization oracle access.
method Frank-Wolfe algorithm with nearest extreme point oracle.
result Improved complexity bounds for specific feasible sets, including linear convergence for polytopes.
New method solves stochastic optimization problems with affine constraints.
problem Stochastic optimization problems with affine constraints.
method Stochastic Frank-Wolfe method.
result Guarantees convergence rates for objective residual and feasibility gap.
A Clifford-Wolf translation of a connected Finsler space is an isometry which moves each point the same distance. A Finsler space is called Clifford-Wolf homogeneous if for any two points there is a Clifford-Wolf translation such that . In this paper, we give a complete classifi…
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.
A Clifford-Wolf translation of a connected Finsler space is an isometry which moves each point the sam distance. A Finsler space is called Clifford-Wolf homogeneous if for any two point there is a Clifford-Wolf translation such that . In this paper, we study Clifford-Wolf transl…
The move from hand-designed to learned optimizers in machine learning has been quite successful for gradient-based and -free optimizers. When facing a constrained problem, however, maintaining feasibility typically requires a projection step, which might be computationally expensive and not differentiable. We show how …
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.
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.
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.
We study Frank-Wolfe methods for nonconvex stochastic and finite-sum optimization problems. Frank-Wolfe methods (in the convex case) have gained tremendous recent interest in machine learning and optimization communities due to their projection-free property and their ability to exploit structured constraints. However,…
Recovering matrices from compressive and grossly corrupted observations is a fundamental problem in robust statistics, with rich applications in computer vision and machine learning. In theory, under certain conditions, this problem can be solved in polynomial time via a natural convex relaxation, known as Compressive …
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.
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 .
We introduce a few variants on Frank-Wolfe style algorithms suitable for large scale optimization. We show how to modify the standard Frank-Wolfe algorithm using stochastic gradients, approximate subproblem solutions, and sketched decision variables in order to scale to enormous problems while preserving (up to constan…
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 dissertation on scalable projection-free optimization methods.
problem Efficient optimization algorithms for large-scale machine learning problems.
method Study of Frank-Wolfe variants and their extensions to distributed and derivative-free settings.
result Development of 1-SFW and QFW, achieving state-of-the-art complexity and efficiency.
We study the formality of the total space of principal SU(2) and SO(3)-bundles over a Wolf space, that is a symmetric positive quaternionic Kähker manifold. We apply this to conclude that all the 3-Sasakian homogeneous spaces are formal. We also determine the principal SU(2) and SO(3)-bundles over the Wolf spaces whose…
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…
New method solves constrained self-concordant minimization problems efficiently.
problem Constrained self-concordant minimization problems.
method Newton Frank-Wolfe method using linear minimization oracles.
result The method uses nearly the same number of linear minimization calls as the Frank-Wolfe method.
In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan an…
We propose a rank- variant of the classical Frank-Wolfe algorithm to solve convex optimization over a trace-norm ball. Our algorithm replaces the top singular-vector computation (-SVD) in Frank-Wolfe with a top- singular-vector computation (-SVD), which can be done by repeatedly applying -SVD times. …
New Frank-Wolfe algorithm speeds up SVM-type multi-category learning.
problem Improving pattern recognition performance in multi-category SVM learning.
method Developed a new optimization algorithm based on Frank-Wolfe framework for MC-SVM variants.
result Closed-form solutions for direction finding and line search in the Frank-Wolfe framework for MC-SVM.
Improved Frank-Wolfe method reduces dependence on data size for empirical risk minimization.
problem Reducing dependence on number of data observations in Frank-Wolfe methods.
method Taylor-series approximated gradients applied to Frank-Wolfe method.
result Significant speed-ups over existing methods on real-world datasets.
New algorithm estimates barycenters of distributions using Frank-Wolfe.
problem Estimating the average of arbitrary probability distributions.
method Frank-Wolfe optimization for Sinkhorn divergence, incrementally populating support.
result Converges in both discrete and continuous distributions, with proven rates.
The main purpose of the following article is to introduce a \emph{Lie theoretical} approach to the problem of classifying pseudo quaternionic-Kähler (QK) reductions of the pseudo QK symmetric spaces, otherwise called \emph{generalized Wolf spaces}.
In this paper, we study Clifford-Wolf translations of homogeneous Randers metrics on spheres. It turns out that we can present a complete description of all the Clifford-Wolf translations of all the homogeneous Randers metrics on spheres. The most important point of this paper is that a new phenomena surfaces. Namely, …
We introduce a globally-convergent algorithm for optimizing the tree-reweighted (TRW) variational objective over the marginal polytope. The algorithm is based on the conditional gradient method (Frank-Wolfe) and moves pseudomarginals within the marginal polytope through repeated maximum a posteriori (MAP) calls. This m…
The Frank-Wolfe (FW) algorithm has been widely used in solving nuclear norm constrained problems, since it does not require projections. However, FW often yields high rank intermediate iterates, which can be very expensive in time and space costs for large problems. To address this issue, we propose a rank-drop method …
An isometry of a Finsler space is called Clifford-Wolf translation (CW-translation) if it moves all points the same distance. A Finsler space is called Clifford-Wolf homogeneous (CW-homogeneous) if for any there is a CW-translation such that . We prove that if is a homogeneous Finsl…
Researchers found a counterexample disproving a 1962 conjecture.
problem Disproving the Homogeneity Conjecture for Lie groups.
method Constructing a specific counterexample on the Lie group Sp(2).
result The Riemannian quotient of the group is not homogeneous.
Optimized projection-free algorithms for online learning: construction and worst-case analysismath.OC
Optimized algorithms for online learning with linear constraints improve performance and provide worst-case analysis.
problem Improving online learning algorithms for constrained optimization problems.
method Developed an optimized variant of an online Frank-Wolfe algorithm and used semidefinite programming for numerical analysis.
result No pure online Frank-Wolfe algorithm can have a better regret guarantee than O(T^3/4) without additional assumptions.
Frank-Wolfe optimization applied to a small deep network shows slower convergence compared to gradient descent.
problem Training deep neural networks is challenging due to many parameters and optimization difficulties.
method Frank-Wolfe optimization method applied to a deep network.
result Frank-Wolfe optimization converges slowly and is unstable in a stochastic setting.
In this paper, using connections between Clifford-Wolf isometries and Killing vector fields of constant length on a given Riemannian manifold, we classify simply connected Clifford-Wolf homogeneous Riemannian manifolds. We also get the classification of complete simply connected Riemannian manifolds with the Killing pr…
A new method improves convergence in large-scale stochastic optimisation.
problem Improving convergence in large-scale stochastic optimisation problems.
method A direct least-squares approach with a Cholesky factor and adaptive line search.
result Improved convergence compared to existing methods on real-world problems.
Quantized Frank-Wolfe reduces communication costs in distributed optimization.
problem Efficiently reducing communication overhead in distributed machine learning optimization.
method Quantized Frank-Wolfe (QFW), a projection-free algorithm for constrained optimization.
result Strong theoretical guarantees on convergence rate, efficient compression of gradients.
Motivated principally by the low-rank matrix completion problem, we present an extension of the Frank-Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. This is accomplished by a new approach to generating ``in-face" directions at each iteration, as well as t…
Improved Frank-Wolfe algorithm speeds up training of differentially private LASSO models.
problem Training differentially private LASSO models on sparse data.
method Adapted Frank-Wolfe algorithm for sparse inputs, reducing runtime.
result Training time reduced from to .