# Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier

arXiv: https://arxiv.org/abs/2010.08999 · HTML: https://mlsanity.com/paper/2010.08999/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2020.

## Built on by (most cited first, 11 of 11)

- [Active Exploration via Experiment Design in Markov Chains](https://mlsanity.com/paper/2206.14332/) (2022)
- [DAVED: Data Acquisition via Experimental Design for Data Markets](https://mlsanity.com/paper/2403.13893/) (2024)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps](https://mlsanity.com/paper/2105.13913/) (2021)
- [Faster Stochastic First-Order Method for Maximum-Likelihood Quantum State Tomography](https://mlsanity.com/paper/2211.12880/) (2022)
- [Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging](https://mlsanity.com/paper/2311.02557/) (2023)
- [A conditional gradient homotopy method with applications to Semidefinite Programming](https://mlsanity.com/paper/2207.03101/) (2022)
- [Fast Learning of Multidimensional Hawkes Processes via Frank-Wolfe](https://mlsanity.com/paper/2212.06081/) (2022)
- [NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems](https://mlsanity.com/paper/2407.03294/) (2024)
- [A general optimization solver based on OP-to-MaxSAT reduction](https://mlsanity.com/paper/2604.21961/) (2026)
- [Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification](https://mlsanity.com/paper/2605.25592/) (2026)

## Abstract (arXiv)

We present and analyze a new generalized Frank-Wolfe method for the composite optimization problem (P):minx∈ℝn; f(mathsfA x) + h(x), where f is a θ-logarithmically-homogeneous self-concordant barrier, mathsfA is a linear operator and the function h has bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires O((δ0 + θ + Rh)ln(δ0) + (θ + Rh)2/varepsilon) iterations to produce an varepsilon-approximate solution, where δ0 denotes the initial optimality gap and Rh is the variation of h on its domain. This result establishes certain intrinsic connections between θ-logarithmically homogeneous barriers and the Frank-Wolfe method. When specialized to the D-optimal design problem, we essentially recover the complexity obtained by Khachiyan using the Frank-Wolfe method with exact line-search. We also study the (Fenchel) dual problem of (P), and we show that our new method is equivalent to an adaptive-step-size mirror descent method applied to the dual problem. This enables us to provide iteration complexity bounds for the mirror descent method despite even though the dual objective function is non-Lipschitz and has unbounded domain. In addition, we present computational experiments that point to the potential usefulness of our generalized Frank-Wolfe method on Poisson image de-blurring problems with TV regularization, and on simulated PET problem instances.