projection-free methods

Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems

Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes … Read more

The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach

Categories Nonlinear Optimization, Nonsmooth Optimization, Other Topics Tags , , ,

We analyze the problem of identifying large cliques in graphs that are affected by adversarial uncertainty. More specifically, we consider a new formulation, namely the adversarial maximum clique problem, which extends the classical maximum-clique problem to graphs with edges strategically perturbed by an adversary. The proposed mathematical model is thus formulated as a two-player zero-sum … Read more

Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

Recent works have developed new projection-free first-order methods based on utilizing linesearches and normal vector computations to maintain feasibility. These oracles can be cheaper than orthogonal projection or linear optimization subroutines but have the drawback of requiring a known strictly feasible point to do these linesearches with respect to. In this work, we develop new … Read more

Frank-Wolfe and friends: a journey into projection-free first-order optimization methods

Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

Invented some 65 years ago in a seminal paper by Marguerite Straus-Frank and Philip Wolfe, the Frank-Wolfe method recently enjoys a remarkable revival, fuelled by the need of fast and reliable first-order optimization methods in Data Science and other relevant application areas. This review tries to explain the success of this approach by illustrating versatility … Read more