Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization

• URL: http://arxiv.org/abs/2603.06369v1
• Date: Fri, 06 Mar 2026 15:20:52 GMT
• Title: Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization
• Abstract summary: We propose ALFCG, the first textitadaptive projection-free framework for composite nontracking variants.<n>Unlike prior methods that use openloop diminishing steps, ALFCG maintains self-normalized accumulators.<n>ALFCG-FS attains $tildemathcalO(2+-2$ and $tildemathcalO(-3+-2) $to 0$, while ALFCG-MVR2 achieve $tildemathcalO(2+
• Score: 23.28384210732827
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose ALFCG (Adaptive Lipschitz-Free Conditional Gradient), the first \textit{adaptive} projection-free framework for stochastic composite nonconvex minimization that \textit{requires neither global smoothness constants nor line search}. Unlike prior conditional gradient methods that use openloop diminishing stepsizes, conservative Lipschitz constants, or costly backtracking, ALFCG maintains a self-normalized accumulator of historical iterate differences to estimate local smoothness and minimize a quadratic surrogate model at each step. This retains the simplicity of Frank-Wolfe while adapting to unknown geometry. We study three variants. ALFCG-FS addresses finite-sum problems with a SPIDER estimator. ALFCG-MVR1 and ALFCG-MVR2 handle stochastic expectation problems by using momentum-based variance reduction with single-batch and two-batch updates, and operate under average and individual smoothness, respectively. To reach an $ε$-stationary point, ALFCG-FS attains $\mathcal{O}(N+\sqrt{N}ε^{-2})$ iteration complexity, while ALFCG-MVR1 and ALFCG-MVR2 achieve $\tilde{\mathcal{O}}(σ^2ε^{-4}+ε^{-2})$ and $\tilde{\mathcal{O}}(σε^{-3}+ε^{-2})$, where $N$ is the number of components and $σ$ is the noise level. In contrast to typical $\mathcal{O}(ε^{-4})$ or $\mathcal{O}(ε^{-3})$ rates, our bounds reduce to the optimal rate up to logarithmic factors $\tilde{\mathcal{O}}(ε^{-2})$ as the noise level $σ\to 0$. Extensive experiments on multiclass classification over nuclear norm balls and $\ell_p$ balls show that ALFCG generally outperforms state-of-the-art conditional gradient baselines.

Related papers

• Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness [0.0]
  We analyze gradient clipping (G-Clip) and show that it recovers the rate above for $ge1+s$ while in the very heavy-tailed regime regime it has $1+s$.
  arXiv  Detail & Related papers  (2026-09-11T12:40:43Z)
• Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization [0.0]
  We present a new type of nonconstrained Monte Carlo optimization for a single ergodic chain.<n>In particular, we address the projection-free setting using the generalized Carlo-Wolfevious gradient $MC-ALFCFC.<n>We show that the tuned method achieves expected sample complexity $widetildeO(_mathrmmix2G_+_mathrmmix5G_2)varepsilon-3+_mathrmmix5varepsilon-2.
  arXiv  Detail & Related papers  (2026-07-28T14:37:47Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe [1.3537117504260623]
  We develop an algorithm that drops the assumption on $min_bmx in mathcalX.<n>The analysis extends to heavy-tailed noise oracles with bounded moments for $r$in (1, 2]$ and recovers the rates of the noise as the noise.
  arXiv  Detail & Related papers  (2026-05-14T19:20:22Z)
• Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise [7.692336118507715]
  We study non-smoother optimization under the Blum-Gladyshev ($mathsfBG$-0) noise model.<n>We prove that normalized gradient descent with momentum, using only one parameter per gradient, converges under $mathsfBG$-0 noise with complexity $O(varepsilon-6)$.
  arXiv  Detail & Related papers  (2026-05-14T18:27:49Z)
• Progressive Power Homotopy for Non-convex Optimization [5.737648067191245]
  We propose a novel first-order method for non- optimization of the form $max_bmwinmathbbdmathbbdmathR bmxsimmathcalD.<n>We show that Prog-PowerHP converges to a small neighborhood of the global optimum with mild complexity scaling nearly as $O(d2varepsilon-2)$.
  arXiv  Detail & Related papers  (2026-01-22T12:44:25Z)
• Decentralized Stochastic Nonconvex Optimization under the Relaxed Smoothness [21.090579632247707]
  We propose a novel algorithm called decentralized normalized gradient descent (DNS)<n>DNS can achieve an $bold$ilon point at each local agent.<n>We show the upper bounds on the sample complexity of $mathcal O(m-1(L_fsigma2Delta_fepsilon-4 + sigma2epsilon-2 + L_f-1)$ per agent.
  arXiv  Detail & Related papers  (2025-09-10T16:17:19Z)
• Adaptive Extrapolated Proximal Gradient Methods with Variance Reduction for Composite Nonconvex Finite-Sum Minimization [7.9047096855236125]
  This paper proposes sf-SPIDER, an Adaptive Extrapolated Prox Gradient (AEPG) method with variance reduction.<n>It integrates $jascalO(N + sqrtN epsilon)$ for finding stationary points, where $N is number of component functions.<n>Experiments demonstrate superior performance of sf AEPG-SPIDER compared to existing methods.
  arXiv  Detail & Related papers  (2025-02-28T14:37:56Z)
• Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
  We show that gradient descent with a fixed learning rate $eta$ can only find local minima that represent smooth functions. We also prove a nearly-optimal MSE bound of $widetildeO(n-4/5)$ within the strict interior of the support of the $n$ data points.
  arXiv  Detail & Related papers  (2024-06-10T22:57:27Z)
• Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimization [41.28002701420715]
  Minimax optimization has been widely applied in many machine learning tasks.<n>We show that our methods have the best known sample complexity without relying on any specific types.
  arXiv  Detail & Related papers  (2023-03-07T15:33:12Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  We propose an adaptive variance method, called AdaSpider, for $L$-smooth, non-reduction functions with a finitesum structure. In doing so, we are able to compute an $epsilon-stationary point with $tildeOleft + st/epsilon calls.
  arXiv  Detail & Related papers  (2022-11-03T14:41:46Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
  A VI involves finding $xstar in mathcalX$ such that $langle F(x), x - xstarrangle geq 0$ for all $x in mathcalX$. We propose a $pth$-order method that does textitnot require any line search procedure and provably converges to a weak solution at a rate of $O(epsilon-2/(p+1))$.
  arXiv  Detail & Related papers  (2022-05-06T13:29:14Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

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.