Frank-Wolfe

Author: Adeline Tse, Jeff Cheung, Tucker Barrett (SYSEN 5800 Fall 2021)

Introduction

The Frank-Wolfe algorithm is an iterative first-order optimization algorithm for constrained convex optimization, first proposed by Marguerite Frank and Philip Wolfe from Princeton University in 1956. It is also known as the “gradient and interpolation” algorithm or sometimes the “conditional gradient method” as it utilizes a simplex method of comparing an initial feasible point with a secondary basic feasible point to maximize the linear constraints in each iteration to find or approximate the optimal solution.

Major advantages of the Frank-Wolfe algorithm include that it is simple to implement; it results in a projection-free computation (that is, it does not require projections back to the constraint set to ensure feasibility); and it generates solution iterations that are sparse with respect to the constraint set. These features favor linear minimization, simple implementation, and low complexity. It is utilized in artificial intelligence, machine learning, traffic assignment, signal processing, and many more applications.

Theory & Methodology

Figure 1. The Frank-Wolfe method optimizes by considering the linearization of the objective function f and moving the initial position x towards the minimizer of the linear function.

The Frank-Wolfe algorithm uses step size and postulated convexity, which formulates a matrix of positive semidefinite quadratic form. Just like a convex function yields a global minimum at any local minimum on a convex set, by the definition of nonlinear programming, the concave quadratic function would yield a global maximum point at any local maximum on a convex constraint set.

The methodology of the Frank-Wolfe algorithm starts with obtaining the generalized Lagrange multipliers for a quadratic problem, PI. The found multipliers are considered solutions to a new quadratic problem,  PII. The simplex method is then applied to the new problem, PII, and the gradient and interpolation method is utilized to make incremental steps towards the solution of the original quadratic problem, PI. This is performed by taking an initial feasible point, obtaining a second basic feasible point along the gradient of the objective function at the initial point, and maximizing the objective function along the segment that joins these two points.  The found maximum along the segment is utilized as the starting point for the next iteration. Using this method, the values of the objective function converge to zero and in one of the iterations, a secondary point will yield a solution.

Proof

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is a [n x 1] matrix
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is a [m x n] matrix
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is a [n x n] matrix
• p and b are [1 x n] and [1 x m] matrices respectively
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla f(x)} is the gradient

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \sum_{j=1}^n p_jx_j - \sum_{j,k=1}^{n,n} X_jC_{jk}X_k} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle where \; \sum_{j=1}^n A_{ij}X_j \le b_i \quad (i=1, ..., m) \; and \; X_j \ge 0 \quad (j = 1, ..., n)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla f(x) = \frac{df(x)}{dx}}

PI is represented by the following equations using matrix notation:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Maximize} \qquad f(x) = px' - x'Cx \quad \text{subject to}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (I) = \begin{cases} x \ge 0 \\ Ax \le b \end{cases}}

Since PI is feasible, any local maximum found that is contained within the convex constraint set is a global maximum. Then by utilizing Kuhn and Tucker's generalizations of the Lagrange Multipliers of the maximization of the objective function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_0} is considered the solution of PI.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta f(x_0)x_0 = Max \, [ \, \delta f(x_0)w \, | \, w \ge 0, Aw \le b], \quad where \; w \; \text{is an [n x 1] matrix}}

By the Duality Theorem, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Min \, [ \, ub \, | \, u \ge 0, \, uA \ge \delta f(x_o)], \quad where \; u \; \text{is a [1 x m] matrix}}

Therefore, the solution Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} for PI is only valid if: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Max \, [ \, \delta f(x_0)x_0 - ub \, | \, u \ge 0, uA \ge \delta f(x_0)] = 0}

Since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta f(x) = p - 2x'Cx} Therefore, by the generalization of Lagrangian, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x,u)} is extracted with linear constraints: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x,u) = \delta f(x)x - ub = px - ub - 2x'Cx} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} x \ge 0, \quad u \ge 0,\\ Ax \le b, \quad \delta f(x) \le uA \end{cases}}

The completion of the generalized Lagrangian shows that m + n positive variables exist for PI, thus a feasible solution exists.

Based on the concavity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(y) - f(x) \le \delta f(x)(y-x)}

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,u)} satisfies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x,u) \le 0} (where x is a solution if for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u, \; g(x,u)=0} ), then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(y) - f(x) \le \delta f(x)x \le uAy - \delta f(x)x \le ub - \delta f(x)x = -g(x,u)}

By the Boundedness Criterion and the Approximation Criterion, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(y) - f(x) \le -g(x,u)}

The Frank-Wolfe algorithm then adds a non-negative variable to each of the inequalities to obtain the following:

• y and v are [m x 1] and [n x 1] matrices respectively

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x, \, u, \, y, \, \nu \ge 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Ax+y=b} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2Cx+A'u'-\nu '=p'} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x,u) = \delta f(x)x-ub = (uA-\nu )x-u(Ax+y) = - \nu x + uy}

Thus, the PII problem is to obtain search vectors to satisfy Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu x+uy=0} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is considered a solution of PI if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta f(x)} belongs to the convex cone spanned by the outward normals to the bounding hyperplanes on which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} lines as shown in Figure 1.

Algorithm

The Frank-Wolfe algorithm can generally be broken down into five steps as described below. Then the loop of iterations continues throughout Steps 2 to 5 until the minimum extreme point is identified.

Step 1. Define initial solution

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is the extreme point, the initial arbitrary basic feasible solution can be considered as:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k \in S \quad where \quad k = 0}

The letter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} denotes the number of iterations.

Step 2. Determine search direction

Search direction, that is the direction vector is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_k = y_k - x_k}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_k} are feasible extreme points and belong to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is convex

First-order Taylor expansion around Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k} and problem is now reformulated to LP:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}minimizes \quad & z_k(y) = f(x_k) + \nabla f(x_k)^T (y-x_k) \\ such\;that \quad & y \in S \\ \end{align}}

Step 3. Determine step length

Step size Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_k} is defined by the following formula where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_k} must be less than 1 to be feasible:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_k + \alpha_k p_k) < f(x_k)} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle minimize_{\alpha \in [0,1]} \, f(x_k + \alpha p_k)}

Step 4. Set new iteration point

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{k+1} = x_k + \alpha p_k}

Step 5. Stopping criterion

Check if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{k+1}} is an approximation of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , the extreme point. Otherwise, set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = k + 1} and return to Step 2 for the next iteration.

In the Frank-Wolfe algorithm, the value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} descends after each iteration and eventually decreases towards Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} , the global minimum.

Numerical Example

Consider the problem min z, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x^4 - 16x + y^2 - 10y = z }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x-y\leq1 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 3x+7\leq5 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x\geq0 } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle y\geq0 }

Step 1. Define initial solution

Begin by choosing the feasible point (0,0)

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \delta fx(x,y) = 4x^3 - 16 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \delta fy(x,y) = 2y-10 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \nabla f(0,0) = (-16,-10) }

We will need to minimize Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle z_0 (x,y) = (-16, -10) \cdot (x,y)^T }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle z_0 = (-16x, -10y) }

Utilize the extreme points of the defined region to find the minimum.

Extreme Points: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (0,0) } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (0,5) } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (1,0) } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (2,1) }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle z(0,0) = 0 } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle z(0,5) = -50 } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle z(1,0) = -16 } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle z(2,1) = -42 }

The minimizing solution is found at point Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (0,5) }

Step 2. Determine search direction

Obtain the line segment that joins the points Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (0,5) } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (0,0) }

This line segment is characterized by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (1-t)(0,0)+t(0,5) = (0,5t),0 \leq t \leq 1 }

The values on the line are found by the equation: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 0^4 + 32 (0) + (5t)^2 - 10(5t) }

The maximum on this line occurs at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle t = } 0

Step 3. Iterate

Utilize the found maximum in step two and re-iterate (obtain gradient, secondary point, and joining line) until an optimal solution is found.

Applications

Image and Video Co-localization

The process of co-localization that captures common objects by using bounding boxes.

Co-localization is one of the programming methods in the machine learning field used to find a common object within a set of images or video frames. The process of co-localization involves first generating multiple candidate bounding boxes for each image/ video frame, then identifying the specific box in each image/ video frame that jointly contains the common object. This technique is extremely important for analyzing online data. By being able to recognize the common objects, visual concepts can be tagged into specific labels, thus leveraging useful data for other marketing and product design purposes. Such development is especially useful for image and video hosting services such as Flickr and YouTube.

The formulation of co-localization using the Frank-Wolfe algorithm involves minimizing a standard quadratic programming problem and reducing it to a succession of simple linear integer problems. The benefit of the algorithm is that it allows many more images to be analyzed simultaneously and more bounding boxes are generated in each image/ video frame for higher accuracy. By relaxing the discrete non-convex set to its convex hull, the constraints that define the original set can now be separated from one image/ video to another. In the case of co-localizing videos, the constraints use the shortest-path algorithm to reach optimization.

Traffic Assignment Problem

A typical transportation network, also known as flow network, is considered as a convex programming problem with linear constraints. With the vertices called nodes and the edges called arcs, a directed graph called a network is formed and the flow is monitored via the movement from one node, origin (O), to another node, destination (D) along the arc. The objective of this programming problem is to achieve user-equilibrium, which means system flow is set optimal without incurring unnecessarily high cost for users.

The use of the Frank-Wolfe algorithm in this case means that the traffic assignment problem can be applied to nonlinear multicommodity network flow with flow dependent cost. The algorithm is also able to process a larger set of constraints with more O-D pairs. Since the Frank-Wolfe algorithm uses a descent method to search for the direction of extreme points, the technique only recognizes the sequence of the shortest route problems. Therefore, the Frank-Wolfe algorithm is known to solve the traffic assignment problem on networks with several hundred nodes efficiently with the minimal number of iterations.

Due to the algorithm’s effectiveness in optimizing traffic assignment problem, it has been widely applied in many fields other than the estimation of the total demand for travel via road between a set of roads and zones. These applications include data-driven computer networks, fluids in pipes, currents in an electrical circuit and more.

Deep Neural Network Training

Although Stochastic Gradient Descent (SGD) is still the conventional machine learning technique for deep learning, the Frank-Wolfe algorithm has been proven to be applicable for training neural networks as well. Instead of taking projection steps via SGD, the Conditional Gradient algorithms, aka Frank-Wolfe algorithm, adopts the simple projection-free first-order algorithm by using the linear minimization oracle (LMO) approach for constrained optimization.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta_{t+1} = \theta_t + \alpha(\nu_t - \theta_t)}

with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \in} [0,1] and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_t} being

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_t = argmin_{\nu \in C} <\nabla L (\theta_t) , \nu>}

Through LMO, non-unique solutions to the above equation that were deemed impossible by Gradient-Descent-based optimization would now be possible.

Conclusion

The Frank-Wolfe algorithm is one of the key techniques in the machine learning field. By using the simplex method that requires little alteration to the gradient and interpolation in each iteration, the optimization of the linearized quadratic objective function can be performed in a significantly shorter runtime. Moreover, with the main advantage of being projection-free, larger datasets can be processed more efficiently. Therefore, with the benefits that the algorithm brings, the algorithm gained popularity with many use cases in machine learning.

References

<reference />