Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms

• URL: http://arxiv.org/abs/2507.17545v2
• Date: Sat, 02 Aug 2025 10:10:34 GMT
• Title: Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms
• Authors: Sebastian Pokutta,
• Abstract summary: We consider the problem of minimizing a difference of (smooth) convex functions over a compact convex feasible region $P$.<n>We empirically show that constrained DC problems can be efficiently solved using a combination of the Blended Pairwise Gradients (BPCG) algorithm.
• Score: 26.645423762494985
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of minimizing a difference of (smooth) convex functions over a compact convex feasible region $P$, i.e., $\min_{x \in P} f(x) - g(x)$, with smooth $f$ and Lipschitz continuous $g$. This computational study builds upon and complements the framework of Maskan et al. [2025] by integrating advanced Frank-Wolfe variants to reduce computational overhead. We empirically show that constrained DC problems can be efficiently solved using a combination of the Blended Pairwise Conditional Gradients (BPCG) algorithm [Tsuji et al., 2022] with warm-starting and the adaptive error bound from Maskan et al. [2025]. The result is a highly efficient and scalable projection-free algorithm for constrained DC optimization.

Related papers

• Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization [17.227158587717934]
  adaptive gradient methods, including GRAAL (Malitsky, 2020), have been developed.<n>We prove that our algorithm achieves the desired optimal convergence rate for Lipschitz smooth functions.<n>In contrast to existing methods, it does so with an arbitrary, even excessively small, initial stepsize at the cost of a logarithmic additive term in the complexity.
  arXiv  Detail & Related papers  (2025-07-13T23:07:45Z)
• Revisiting Frank-Wolfe for Structured Nonconvex Optimization [33.44652927142219]
  We introduce a new projection (Frank-Wolfe) method for optimizing structured non functions that are expressed as a difference of two convex functions.<n>We prove that the proposed method achieves in $O-(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(O-)$(
  arXiv  Detail & Related papers  (2025-03-11T22:09:44Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Distributed Difference of Convex Optimization [1.2661010067882734]
  A class of distributed problems involvingn$ agents with the local objective function at every agenti by the difference of the difference of $-difference on $-f_i$ and $-f_i$ are presented. The DDC-Consensus algorithm is developed to solve the non-regularized distributed squares problem.
  arXiv  Detail & Related papers  (2024-07-23T14:41:32Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
  Most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive. Recent work by GK22 gave sublinear adaptive regret guarantees with projection free algorithms based on the Frank Wolfe approach. We give projection-free algorithms that are based on a different technique, inspired by Mhammedi22, that replaces projections by set-membership computations.
  arXiv  Detail & Related papers  (2022-11-22T23:53:06Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  We structured convex optimization problems with additive objective $r:=p + q$, where $r$ is $mu$-strong convex similarity. We proposed a method to solve problems master to agents' communication and local calls. The proposed method is much sharper than the $mathcalO(sqrtL_q/mu)$ method.
  arXiv  Detail & Related papers  (2022-05-30T14:28:02Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)

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.