Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes

• URL: http://arxiv.org/abs/2505.11259v1
• Date: Fri, 16 May 2025 13:50:55 GMT
• Title: Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes
• Authors: Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado, Elias Wirth, Sebastian Pokutta,
• Abstract summary: We study the linear convergence of Frank-Wolfe algorithms over product polytopes.<n>For convex objectives that are $mu$-Polyak-Lojasiewicz, we show linear convergence rates quantified in terms of the resulting condition numbers.
• Score: 20.7580525897407
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the linear convergence of Frank-Wolfe algorithms over product polytopes. We analyze two condition numbers for the product polytope, namely the \emph{pyramidal width} and the \emph{vertex-facet distance}, based on the condition numbers of individual polytope components. As a result, for convex objectives that are $\mu$-Polyak-{\L}ojasiewicz, we show linear convergence rates quantified in terms of the resulting condition numbers. We apply our results to the problem of approximately finding a feasible point in a polytope intersection in high-dimensions, and demonstrate the practical efficiency of our algorithms through empirical results.

Related papers

• Approximation Depth of Convex Polytopes [1.6180992915701702]
  We study the ability to approximate a target polytope by polytopes of a given depth.<n>Our main results imply that simplices can only be additive sums.
  arXiv  Detail & Related papers  (2025-07-10T13:58:55Z)
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
  This paper focuses on applying entropic mirror descent to solve linear systems.<n>The main challenge for the convergence analysis stems from the unboundedness of the domain.<n>To overcome this without imposing restrictive assumptions, we introduce a variant of Polyak-type stepsizes.
  arXiv  Detail & Related papers  (2025-05-05T12:33:18Z)
• Flows on convex polytopes [0.0]
  We show that any full-dimensional polytope is homeomorphic to a unit ball, and our approach harnesses flows defined on the ball, mapping them back to the original polytope.<n>Our experiments take inspiration from applications in metabolic flux analysis and demonstrate that our methods achieve competitive density estimation, sampling accuracy, as well as fast training and inference times.
  arXiv  Detail & Related papers  (2025-03-13T10:15:40Z)
• Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
  We propose a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method. Our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.
  arXiv  Detail & Related papers  (2023-12-14T09:53:54Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Enumeration of max-pooling responses with generalized permutohedra [39.58317527488534]
  Max-pooling layers are functions that downsample input arrays by taking the maximum over shifted windows of input coordinates. We characterize the faces of such polytopes and obtain generating functions and closed formulas for the number of vertices and facets in a 1D max-pooling layer depending on the size of the pooling windows and stride.
  arXiv  Detail & Related papers  (2022-09-29T17:45:54Z)
• Reconstruction of Convex Polytope Compositions from 3D Point-clouds [3.04585143845864]
  Reconstructing a composition (union) of convex polytopes that perfectly fits the corresponding input point-cloud is a hard optimization problem. We propose a pipeline that first extracts a set of planes, then partitions the input point-cloud into weakly convex clusters and finally generates a set of convex polytopes as the intersection of fitted planes for each partition. Finding the best-fitting convex polytopes is formulated as a optimization problem over the set of fitted planes and is solved using an Evolutionary Algorithm.
  arXiv  Detail & Related papers  (2021-04-27T00:14:55Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity [19.24470467199451]
  We prove that the Frank-Wolfe algorithm converges linearly with rate that depends explicitly only on the dimension of the optimal face. We motivate strict complementarity by proving that it implies sparsity-robustness of optimal solutions to noise.
  arXiv  Detail & Related papers  (2020-05-31T16:48:10Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.