Self-concordant analysis of Frank-Wolfe algorithms (2020-02-11T00:00:00.000000Z)

TL;DR

The theory of SC functions is used to provide a new adaptive step size for FW methods and prove global convergence rate O(1/k) after k iterations, and if the problem admits a stronger local linear minimization oracle, a novel FW method with linear convergence rate for SC functions.

Abstract

Projection-free optimization via different variants of the Frank-Wolfe (FW), a.k.a. Conditional Gradient method has become one of the cornerstones in optimization for machine learning since in many cases the linear minimization oracle is much cheaper to implement than projections and some sparsity needs to be preserved. In a number of applications, e.g. Poisson inverse problems or quantum state tomography, the loss is given by a self-concordant (SC) function having unbounded curvature, implying absence of theoretical guarantees for the existing FW methods. We use the theory of SC functions to provide a new adaptive step size for FW methods and prove global convergence rate O(1/k) after k iterations. If the problem admits a stronger local linear minimization oracle, we construct a novel FW method with linear convergence rate for SC functions.

Authors

P. Dvurechensky

1 papers

Shimrit Shtern

1 papers

Mathias Staudigl

1 papers

TL;DR

Abstract

Authors

References52 items

Generalized self-concordant analysis of Frank–Wolfe algorithms

Second-order Conditional Gradient Sliding.

A Newton Frank–Wolfe method for constrained self-concordant minimization

Generalized Self-concordant Hessian-barrier algorithms

Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance

The condition number of a function relative to a set

Lectures on Convex Optimization

Finite-sample Analysis of M-estimators using Self-concordance

Linearly Convergent Frank-Wolfe with Backtracking Line-Search.

Complexity bounds for primal-dual methods minimizing the model of objective function

A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications

Generalized self-concordant functions: a recipe for Newton-type methods

Relatively Smooth Convex Optimization by First-Order Methods, and Applications

A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization

Randomized Block Proximal Damped Newton Method for Composite Self-Concordant Minimization

Frank-Wolfe works for non-Lipschitz continuous gradient objectives: Scalable poisson phase retrieval

Polytope Conditioning and Linear Convergence of the Frank-Wolfe Algorithm

On the Global Linear Convergence of Frank-Wolfe Optimization Variants

An Extended Frank-Wolfe Method with "In-Face" Directions, and Its Application to Low-Rank Matrix Completion

DiSCO: Distributed Optimization for Self-Concordant Empirical Loss

Linearly convergent away-step conditional gradient for non-strongly convex functions

Decreasing Weighted Sorted ${\ell_1}$ Regularization

An Inexact Proximal Path-Following Algorithm for Constrained Convex Minimization

The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

Self‐concordance for empirical likelihood

Composite self-concordant minimization

Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

Conditional gradient algorithms for norm-regularized smooth convex optimization

A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions

Gradient methods for minimizing composite functions

LIBSVM: A library for support vector machines

This is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms—Theory and Practice

Self-concordant analysis for logistic regression

Sparse Approximate Solutions to Semidefinite Programs

Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm

A conditional gradient method with linear rate of convergence for solving convex linear systems

Universal Prediction

Some comments on Wolfe's ‘away step’

Gaussian Markov Distributions over Finite Graphs

A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm

An algorithm for quadratic programming

Linearly Convergent Frank-Wolfe without Line-Search

Numerical Methods in Engineering with MATLAB®: Introduction to Optimization

Efficient algorithms for online convex optimization and their applications

Benchmarking optimization software with performance profiles

Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system

Nonlinear Programming

Interior-point polynomial algorithms in convex programming

Introduction to optimization

A method for solving the convex programming problem with convergence rate O(1/k^2)

Constrained minimization methods

Since s k = A(x k , r k , ∇ f (x k )), we know by definition of the LLOO that ∇ f (x k ), x * − x k ≥

Field of Study

Venue Information

Name

Type

URL

Alternate Names