arXiv research

New Frank-Wolfe algorithm speeds up SVM-type multi-category learning.

In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a prob…

In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a prob…

Negative step sizes improve second-order methods for neural networks.

Boosted Frank-Wolfe accelerates optimization for nonconvex problems.

Frank-Wolfe optimization applied to a small deep network shows slower convergence compared to gradient descent.

Improved Frank-Wolfe algorithm for polytopes converges linearly with dimension dependence on optimal face.

A new L-BFGS method tackles large-scale optimization with fewer evaluations.

We extend the well-known BFGS quasi-Newton method and its memory-limited variant LBFGS to the optimization of nonsmooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: the local quadratic model, the identification of a descent direction, and the Wolfe …

During recent years there has been an increased interest in stochastic adaptations of limited memory quasi-Newton methods, which compared to pure gradient-based routines can improve the convergence by incorporating second order information. In this work we propose a direct least-squares approach conceptually similar to…

A major challenge in current optimization research for deep learning is to automatically find optimal step sizes for each update step. The optimal step size is closely related to the shape of the loss in the update step direction. However, this shape has not yet been examined in detail. This work shows empirically that…

Step sizes in neural network training are largely determined using predetermined rules such as fixed learning rates and learning rate schedules. These require user input or expensive global optimization strategies to determine their functional form and associated hyperparameters. Line searches are capable of adaptively…

Recent works have shown that stochastic gradient descent (SGD) achieves the fast convergence rates of full-batch gradient descent for over-parameterized models satisfying certain interpolation conditions. However, the step-size used in these works depends on unknown quantities and SGD's practical performance heavily re…

In this paper, we consider a class of possibly nonconvex, nonsmooth and non-Lipschitz optimization problems arising in many contemporary applications such as machine learning, variable selection and image processing. To solve this class of problems, we propose a proximal gradient method with extrapolation and line sear…

A Clifford-Wolf translation of a connected Finsler space is an isometry which moves each point the same distance. A Finsler space $(M, F)$ is called Clifford-Wolf homogeneous if for any two points $x_1, x_2\in M$ there is a Clifford-Wolf translation $ρ$ such that $ρ(x_1)=x_2$. In this paper, we give a complete classifi…

Adaptive gradient methods converge faster with over-parameterization and line-search.

Unified framework for efficient Frank-Wolfe optimization of 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 $(M, F)$ is called Clifford-Wolf homogeneous if for any two point $x_1, x_2\in M$ there is a Clifford-Wolf translation $ρ$ such that $ρ(x_1)=x_2$. In this paper, we study Clifford-Wolf transl…

Improved SGD methods converge faster for nonconvex optimization.

GOLS-I automatically determines learning rates for various neural network training algorithms.

In this paper, we propose a convergent parallel best-response algorithm with the exact line search for the nondifferentiable nonconvex sparsity-regularized rank minimization problem. On the one hand, it exhibits a faster convergence than subgradient algorithms and block coordinate descent algorithms. On the other hand,…

Armijo line-search speeds up gradient descent for various functions.

A new line search rule improves support recovery in high-dimensional data.

New algorithm optimizes AUC in binary classification and changepoint detection.

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…

The group lasso is a penalized regression method, used in regression problems where the covariates are partitioned into groups to promote sparsity at the group level. Existing methods for finding the group lasso estimator either use gradient projection methods to update the entire coefficient vector simultaneously at e…

Unified view of Lion and Muon as Stochastic Frank-Wolfe methods.

New methods solve saddle point problems without line search.

GOALS improves learning rate selection for dynamic MBSS in deep learning.

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,…

We study a distributionally robust mean square error estimation problem over a nonconvex Wasserstein ambiguity set containing only normal distributions. We show that the optimal estimator and the least favorable distribution form a Nash equilibrium. Despite the non-convex nature of the ambiguity set, we prove that the …

Momentum accelerates Frank Wolfe algorithms on certain problems.

Online boosting method improves weak to strong learner.

Simple DP algorithms find approximate solutions for nonconvex ERM.

Paper introduces a privacy-preserving line search method for optimization.

Choosing appropriate step sizes is critical for reducing the computational cost of training large-scale neural network models. Mini-batch sub-sampling (MBSS) is often employed for computational tractability. However, MBSS introduces a sampling error, that can manifest as a bias or variance in a line search. This is bec…

Paper introduces FoMoH for optimization without backpropagation.

The Frank-Wolfe method and its extensions are well-suited for delivering solutions with desirable structural properties, such as sparsity or low-rank structure. We introduce a new variant of the Frank-Wolfe method that combines Frank-Wolfe steps and steepest descent steps, as well as a novel modification of the "Frank-…

A new method approximates expected empirical loss for stochastic deep learning tasks.

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.

In this paper, we study the properties of the Frank-Wolfe algorithm to solve the \ExactSparse reconstruction problem. We prove that when the dictionary is quasi-incoherent, at each iteration, the Frank-Wolfe algorithm picks up an atom indexed by the support. We also prove that when the dictionary is quasi-incoherent, t…

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…

SALSA automatically adjusts learning rates in stochastic gradient methods.

Learning rates in stochastic neural network training are currently determined a priori to training, using expensive manual or automated iterative tuning. This study proposes gradient-only line searches to resolve the learning rate for neural network training algorithms. Stochastic sub-sampling during training decreases…

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.

In this paper, we propose three online algorithms for submodular maximisation. The first one, Mono-Frank-Wolfe, reduces the number of per-function gradient evaluations from $T^{1/2}$ [Chen2018Online] and $T^{3/2}$ [chen2018projection] to 1, and achieves a $(1-1/e)$-regret bound of $O(T^{4/5})$. The second one, Bandit-F…