Pith. sign in

REVIEW 2 major objections 4 minor 46 references

Variable Smoothing for Weakly Convex Problems with Non-Euclidean Directions

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A geometry-aware smoothing algorithm, MELMO, proves schedule-dependent convergence rates for weakly convex composite problems, including O(k^{-1/4}) stationarity under a balanced schedule.

desk verdict Solid extension of variable smoothing to non-Euclidean LMO geometry, with a real but fixable gap in the full schedule-family theorem. read the letter →

arxiv 2608.04584 v1 pith:CAVDFYN7 submitted 2026-08-05 math.OC

Farid Najar (UVSQ) This is my paper · ORCID
classification math.OC MSC 90C2690C3065K05
keywords Moreauenvelopeweaklyconvexoptimizationlinearminimizationoraclenon-Euclideangeometrycompositevariablesmoothingstationaritycertificatesnonsmooth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes MELMO, an algorithm for minimizing f(x)+g(Tx) where f is smooth and g may be non-smooth and only weakly convex. MELMO smooths g with a Moreau envelope and then takes update steps in a direction chosen by a linear minimization oracle over the unit ball of a user-specified norm, so the updates can follow ℓ¹, spectral, or other non-Euclidean geometries. The central claim is that this geometry-aware method comes with a family of convergence rates governed by the step-size and smoothing schedules: a balanced schedule gives O($k^{{-1/4}}$) rates for both the smoothed-gradient norm and a composite stationarity proxy, and an epoch-wise variant returns computable certificates in O($ε^{{-3}}$) iterations, matching the best known bound while allowing arbitrary LMO geometries. If correct, this fills a gap between Euclidean variable-smoothing methods and conditional-gradient methods for weakly convex composite problems.

What carries the argument

The central mechanism is the combination of Moreau envelope smoothing, g_{β}(Tx)=min_u{g(u)+‖Tx-u‖$_2^{2}$/(2β)}, with a linear minimization oracle that returns a direction ̂d_k approximately minimizing ⟨u,∇F_k(x_k)⟩ over the unit ball of a chosen norm. The update is x_{k+1}=x_k+γ_k̂d_k. The envelope turns g into a 1/β-smooth surrogate whose proximal gap satisfies ‖Tx_k-prox_{βg}(Tx_k)‖_2≤βL_g, while the LMO encodes the geometry; the trade-off is that shrinking β improves fidelity to the original objective but worsens conditioning, and the descent lemma in the geometry norm turns this into the rate exponents in Theorem 3.

What would settle it

Take R^n with the ℓ^∞ geometry, where the exact LMO output on a vector v is -sign(v), whose Euclidean norm is √n; check whether the descent inequality in Lemma 12 holds with a constant independent of n for a simple quadratic objective with g=0. If the constant or the observed convergence rate degrades with n, the theorem's claim of geometry-independent O($k^{{-1/4}}$) convergence fails.

Watch

Extended reading notes

Core claim

MELMO establishes that when g is L_g-Lipschitz and ρ-weakly convex, power schedules β_k=$βk^{{-q}}$ and γ_k=$γk^{{-p}}$ yield min_{j≤k}‖∇F_j(x_j)‖_* = O($k^{{max{p-1,-p,q-p}}$}) for the smoothed-gradient norm, with the composite stationarity proxy bounded by O($k^{{max{p-1,-p,q-p,-q}}$}) when T is surjective. Two concrete regimes are isolated: (p,q)=(7/12,1/3) gives O($k^{{-1/4}}$) for both quantities, while (p,q)=(2/3,1/4) gives O($k^{{-1/3}}$) for the smoothed gradient and O($k^{{-1/4}}$) for the proxy. A fixed-horizon variant with constant schedules reaches O($K^{{-1/3}}$) for both. The epoch-wise version converts these prefix-minimum bounds into explicit ε-proxy certificates, achieving O($ε^{{-4}}$) iterations with power schedules and O($ε^{{-3}}$) with per-epoch constant smoothing and restarts; under surjective T, such certificates imply near-stationarity of the original composite problem.

Load-bearing premise

The general-norm convergence theorem silently assumes a norm-equivalence constant that bridges the chosen geometry and the Euclidean norm when bounding the oracle direction; without that constant explicitly supplied, the claimed rates for arbitrary non-Euclidean geometries are not fully established.

Editorial extensions

If this is right

  • Under the balanced schedule (7/12,1/3), MELMO produces an iterate with both smoothed-gradient norm and composite proxy at O(k^{-1/4}) after k iterations.
  • The epoch-constant specialization with restarts yields explicit ε-proxy certificates in O(ε^{-3}) iterations, matching the complexity of Euclidean variable smoothing while allowing non-Euclidean update geometries.
  • When T is surjective, the ε-proxy certificate implies the original composite problem is O(ε)-near-stationary at a nearby point, with distance controlled by σ_min(T)^{-1}ε.
  • The method reduces to normalized steepest descent when the geometry is Euclidean, so the framework unifies classical steepest descent with geometry-aware variants like spectral or ℓ¹ updates.
  • MELMO does not need to know the gradient Lipschitz constant L_{∇f} to set its step size, which the paper identifies as an advantage over the variable-smoothing baseline.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The stated rates hide norm-equivalence constants c_1,c_2,c_3 that relate the chosen geometry to the Euclidean norm; for geometries like ℓ^∞, whose exact LMO direction has Euclidean norm √n, these constants may introduce a dimension dependence that the O(k^{-1/4}) notation does not expose.
  • The stronger composite-stationarity statement requires T surjective, which excludes natural operators such as the image gradient; extending the proxy-to-stationarity transfer to non-surjective T would broaden the practical reach of the certificates.
  • The explicit dependence on (p,q) suggests an adaptive schedule-selection rule: choose q to control the proximal gap and p to roughly balance the exponents p-1, -p, and q-p, which could yield parameter-free or self-tuning variants.
  • A stochastic-gradient version of MELMO is mentioned as future work; if the descent lemma in the geometry norm survives stochastic oracles, the epoch-wise certificate structure would transfer directly to large-scale settings.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper proposes MELMO, an algorithm for composite optimization problems of the form min_x f(x)+g(Tx), where f is smooth and g is ρ-weakly convex and possibly nonsmooth. The method smooths g via the Moreau envelope and uses an (possibly inexact) linear minimization oracle over the unit ball of a chosen norm to generate geometry-aware descent directions. The main theoretical contribution is a family of convergence bounds parameterized by power schedules (p,q): the smoothed-gradient norm converges at rate O(k^{max{p-1,-p,q-p}}), and under surjective T a composite stationarity proxy converges at rate O(k^{max{p-1,-p,q-p,-q}}). Specific choices yield O(k^{-1/4}) rates for both quantities and an O(k^{-1/3}) smoothed-gradient rate with O(k^{-1/4}) proxy rate; a fixed-horizon variant yields O(K^{-1/3}) for both, and epoch-wise variants produce computable ϵ-proxy certificates with O(ϵ^{-4}) and O(ϵ^{-3}) complexity. Experiments on sparse low-rank matrix factorization, total variation denoising, and masked matrix recovery show that MELMO is competitive with Euclidean variable-smoothing and subgradient baselines.

Significance. If the technical gaps below are fixed, the paper makes a solid contribution: it is, to my knowledge, the first analysis of Moreau-envelope smoothing with LMO-based non-Euclidean directions for unconstrained weakly convex composite problems, and it matches the state-of-the-art O(ϵ^{-3}) certificate complexity while preserving the freedom to choose problem geometry. The schedule trade-off between smoothed-gradient minimization and composite stationarity is made explicit, and the epoch-wise certificates are genuinely computable. The paper is also honest about scope: it provides a theory-compliant masked-matrix-recovery testbed, and it explicitly states when the experiments fall outside the theorems (denoising with non-surjective T, low-rank factorization without global smoothness). Code is provided. The stress-test concern about Lemma 11 mixing norms does not survive inspection: the oracle bound in Lemma 11 is in the chosen norm, and Lemma 12 applies the descent lemma in that same norm; the displayed proof is just typographically awkward. The genuine issues are in Lemmas 13 and 14.

major comments (2)
  1. [Appendix A.1, Lemma 14; Appendix A.2, Theorem 3 proof] Lemma 14's case list covers p>1/2 (cases 1–3) and p=1/2 (case 4), but Theorem 3 allows 0<q<p<1 with p<1/2. The proof of Theorem 3 states 'Lemma 14 applies' for these parameters without justification. The missing case is straightforward: for p<1/2, ∑k^{-2p}=O(K^{1-2p}) and ∑k^{-2p+q}=O(K^{1-2p+q}), so (36) gives min_j ||φ_j||_* = O(K^{max{-p,q-p}}), which matches the theorem's exponent since p−1<−p. This does not affect Corollaries 4–5 or Proposition 9, but the full 'family of schedule-dependent bounds' advertised in the abstract is not proven as written.
  2. [Appendix A.1, Lemma 13] Lemma 13 is stated with the geometry norm ∥·∥, but the cited inequalities (Lemma 4.1 of [16] and Property 7.3 of [17]) are Euclidean-norm statements and the proof silently uses the Euclidean norm. As stated, the lemma is false for non-Euclidean geometry norms. For example, take g(y)=|y1|+|y2|, ∥·∥=∥·∥∞, f=0, T=I, β_k=1, β_{k+1}=3/4, y=(2,2). Then the left side of (17) is g_{β_{k+1}}(y)-g_{β_k}(y)=1/4, while the right side with the geometry norm is (1/2)(1/4)(4/3)·1^2=1/6. The subsequent use in Theorem 3 is valid if the lemma is read with the Euclidean norm, because ∥∇gβ∥_2≤L_g; the lemma should be restated with ∥·∥_2 or with an explicit norm-equivalence constant.
minor comments (4)
  1. [Appendix A.1, Lemma 11] The display '∥ed∥^2 ≤(δ+1)^2' and the proof's '∥ed+d−d∥^2' are typographically confusing; the intended statement is ∥ed∥ ≤ δ+1 by the triangle inequality in the chosen norm, and the squared form used in Lemma 12 follows. The bound is valid and does not mix Euclidean and geometry norms.
  2. [Appendix A.2, Theorem 3 proof] In the stationarity translation, the inequality ∥∇f(˜x_j)−∇f(x_j)∥_2 ≤ c_2 c_3 L_{∇f}∥˜x_j−x_j∥_2 does not follow from the stated norm-equivalence constants; a correct chain gives a product involving c_1 and c_3 (e.g., c_1 c_3). Since the constants are absorbed in O(·), this does not affect the rates, but it should be corrected.
  3. [Appendix A.4, Theorem 7 proof] The paragraph arguing that the constant C is bounded independently of K is terse; it would be clearer to state explicitly that F_1(x_1)−F⋆_1 remains bounded as β_1=βK^{-1/3}→0 by the standard Lipschitz approximation property of the Moreau envelope (0≤g(x)−g_β(x)≤βL_g^2/2).
  4. [Section 4.3] For the spectral-norm implementation of MELMO, the smoothness constant of f(X)=1/2∥P_Ω(X−Y)∥_F^2 with respect to the spectral norm is not 1 but a norm-equivalence factor (√min(m,n) up to constants); the paper's phrase 'a finite norm-equivalence constant' is correct but could be made precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular dependency: MELMO's convergence proof is a direct telescoping argument built on external lemmas, with schedules selected to optimize derived exponents rather than fitted to data.

full rationale

I walked the derivation chain of Theorems 2, 3, 7, 8 and Proposition 9 and found no step that reduces to its own inputs. All load-bearing analytic ingredients are external: Lemma 1 is cited to Bauschke-Combettes and Hoheisel-Laborde-Oberman; Lemma 13 uses Lemma 4.1 of Böhm-Wright [16] and Property 7.3 of Yurtsever et al. [17]; the inexact-LMO definition is attributed to [28]; and the Moreau-envelope fidelity bound in Theorem 2 is a direct consequence of Lemma 3.3 in [16]. The proof of Theorem 3 is a telescoping-sum argument with explicit constants, and the schedule exponents (p,q) are chosen after the fact to optimize the derived exponents max{p-1,-p,q-p}, not fitted to any data or to the target rates. The epoch-wise certification statements are complexity bounds for a stopping rule that explicitly evaluates both certificate quantities; the sentence 'by construction' in Appendix A.5 refers to the stopping rule's definition, not to a hidden equivalence between the theorem and its conclusion. There is no self-citation loop: the single author does not cite his own prior work, and no 'uniqueness' or 'forced choice' argument is imported from the authors. The only substantive issue is a proof gap, not circularity: Lemma 14 states cases only for p>1/2 and p=1/2, while Theorem 3 permits 0<q<p<1 with p<1/2; the proof's assertion 'Lemma 14 applies' is therefore incomplete for that parameter range. This is fixable and does not touch the headline rates (Corollaries 4-5, Theorem 7, Theorem 8, Proposition 9 all use p>1/2). The paper itself also flags the TV-denoising experiment as an empirical extension rather than an instantiation of the surjective-T theorem, which further evidences that the theoretical claims are not being stretched by definitional sleight of hand. Overall, no specific circular reduction could be quoted, so the circularity score is 0.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new postulated entities such as particles or forces. It relies on standard assumptions on the problem data (Lipschitz smoothness, weak convexity, Lipschitz continuity), on standard finite-dimensional norm equivalence, and on published external lemmas for Moreau envelope smoothing. The only hand-chosen numbers are the user-facing schedule parameters and experimental hyperparameters, which are not fitted to data.

free parameters (2)
  • Decay exponents (p, q) = (7/12,1/3) balanced; (2/3,1/4) smoothed-favoring; (2/3,1/3) epoch experiment outside theory
    Chosen by hand to optimize the derived bound; the central rate claims for specific corollaries depend on these choices, but the main theorem holds for any 0<q<p<1 (with p not 1/2).
  • Smoothing scale beta and step-size scale gamma = beta0=1, gamma=1 in experiments
    User-set hyperparameters in Algorithm 1; theory requires beta <= 1/(2 rho) and gamma>0. Not fitted to data; listed for completeness because experimental outcomes depend on them.
assumptions (7)
  • domain assumption g is rho-weakly convex with beta_k <= 1/(2rho) for all k
    Invoked in Lemma 1 and Remark 1 to guarantee a single-valued proximal operator and 1/beta-smoothness of the Moreau envelope; Section 2.2.
  • domain assumption g is L_g-Lipschitz
    Used in Theorem 2 and in the proofs of Theorems 3, 7, 8, Proposition 9 to bound the Moreau envelope gradient norm by L_g; Section 2.1 and Appendix A.
  • domain assumption f is L_f-smooth with respect to the chosen norm
    Required by the descent lemma in Lemma 12 and by Lemma 10; Section 2.1.
  • domain assumption Boundedness F*_1 = inf_x F_1(x) > -infinity
    Stated in Theorem 3 to make the constant C0 finite; Appendix A.2.
  • standard math Existence of norm-equivalence constants c1, c2, c3 in finite dimension
    Used in the proof of Theorem 3 and Lemma 10 to convert between Euclidean and geometry norms; Section 2.4.
  • standard math External lemmas: Lemma 3.3 and Lemma 4.1 of Boehm-Wright (2021), Property 7.3 of Yurtsever et al. (2019)
    The Moreau-envelope smoothing inequalities and proximal-gap bound are lifted from these papers; Sections 3.1 and Appendix A.
  • domain assumption T is surjective when translating smoothed-gradient bounds to the composite stationarity proxy
    Only needed for the dist(...) statements in Theorem 3, Corollaries 4-5, Theorem 7, and Remark 4; Section 2.4, equation (1).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Variable Smoothing for Weakly Convex Problems with Non-Euclidean Directions." pith.science (2026). https://pith.science/paper/CAVDFYN7

@misc{pith2026260804584,
  author       = {Pith},
  title        = {Pith review of: Variable Smoothing for Weakly Convex Problems with Non-Euclidean Directions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CAVDFYN7}},
  note         = {Machine review of arXiv:2608.04584}
}
abstract

We propose MELMO (Moreau Envelope Smoothing with Linear Minimization Oracles), an algorithm for composite optimization problems of the form min x f (x) + g(T x), where f is smooth and g may be non-smooth. The method leverages the Moreau envelope to smooth the non-smooth component while adapting to problem geometry through linear minimization oracles. Assuming g is $\rho$-weakly convex, we establish a family of convergence bounds parameterized by the step-size and smoothing schedules, thereby making explicit the trade-off between optimizing the smoothed objective and recovering stationarity for the original composite problem. In particular, one regime yields O(k -1/4 ) rates for both the smoothed-gradient norm and a composite stationarity proxy, while another yields O(k -1/3 ) for the smoothed-gradient norm together with O(k -1/4 ) for the composite proxy. We also establish a K-horizon-dependent convergence rate that yields O(K -1/3 ) for the composite proxy. Empirically, MELMO is competitive with variable smoothing and subgradient baselines on sparse low-rank matrix factorization and image denoising.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 39 canonical work pages

  1. [16]

    Journal of optimization theory and applications188, 628–649 (2021)

    B¨ ohm, A., Wright, S.J.: Variable smoothing for weakly convex composite functions. Journal of optimization theory and applications188, 628–649 (2021)

    work page 2021

  2. [17]

    In: International Conference on Machine Learning, pp

    Yurtsever, A., Fercoq, O., Cevher, V.: A conditional-gradient-based augmented lagrangian framework. In: International Conference on Machine Learning, pp. 7272–7281 (2019). PMLR

    work page 2019

  3. [1]

    Journal of the Royal Statistical Society Series B: Statistical Methodology58(1), 267–288 (1996)

    Tibshirani, R.: Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology58(1), 267–288 (1996)

    1996

  4. [2]

    The Annals of Statistics38(2), 894–942 (2010)

    Zhang, C.-H.: Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics38(2), 894–942 (2010)

    work page 2010

  5. [3]

    Journal of the American statistical Association96(456), 1348–1360 (2001)

    Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association96(456), 1348–1360 (2001)

    work page 2001

  6. [4]

    In: 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp

    Candes, E.J., Recht, B.: Exact low-rank matrix completion via convex optimization. In: 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 806–812 (2008). IEEE

    work page 2008

  7. [5]

    Cand` es, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? Journal of the ACM (JACM)58(3), 1–37 (2011)

    work page 2011

  8. [6]

    Physica D: nonlinear phenomena60(1-4), 259–268 (1992)

    Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena60(1-4), 259–268 (1992)

    1992

Show all 46 references
  1. [7]

    In: Breakthroughs in Statistics: Methodology and Distribution, pp

    Huber, P.J.: Robust estimation of a location parameter. In: Breakthroughs in Statistics: Methodology and Distribution, pp. 492–518. Springer, Berlin (1992)

    1992

  2. [8]

    Optimization for machine learning5(19-53), 8 (2011)

    Bach, F., Jenatton, R., Mairal, J., Obozinski, G.,et al.: Convex optimization with sparsity-inducing norms. Optimization for machine learning5(19-53), 8 (2011)

    2011

  3. [9]

    NIPS9, 10 (2015)

    Carlson, D.E., Collins, M., Hsieh, Y.-P., Sahin, G., Vaidya, A., Cevher, V.: Preconditioned spectral descent for deep learning. NIPS9, 10 (2015)

    2015

  4. [10]

    https://keller jordan.github.io/posts/muon/

    Jordan, K., Jin, Y., Boza, V., Jiacheng, Y., Cesista, F., Newhouse, L., Bernstein, J.: Muon: An optimizer for hidden layers in neural networks (2024). https://keller jordan.github.io/posts/muon/

    2024

  5. [11]

    arXiv preprint arXiv:2002.08056 (2020)

    Balles, L., Pedregosa, F., Roux, N.L.: The geometry of sign gradient descent. arXiv preprint arXiv:2002.08056 (2020)

    2020 arXiv

  6. [12]

    In: High-dimensional Learning Dynamics 2025 (2025)

    Vasudeva, B., Deora, P., Thrampoulidis, C.: On generalization of spectral gradient descent: A case study on imbalanced data. In: High-dimensional Learning Dynamics 2025 (2025)

    2025

  7. [13]

    In: International Conference on Machine Learning, pp

    Nutini, J., Schmidt, M., Laradji, I., Friedlander, M., Koepke, H.: Coordinate descent converges faster with the gauss-southwell rule than random selection. In: International Conference on Machine Learning, pp. 1632–1641 (2015). PMLR

    2015

  8. [14]

    In: Artificial Intelligence and Statistics, pp

    Carlson, D., Cevher, V., Carin, L.: Stochastic spectral descent for restricted boltzmann machines. In: Artificial Intelligence and Statistics, pp. 111–119 (2015). 24 PMLR

    2015

  9. [15]

    Advances in Neural Information Processing Systems 31(2018)

    Kovalev, D., Richtarik, P., Gorbunov, E., Gasanov, E.: Stochastic spectral and conjugate descent methods. Advances in Neural Information Processing Systems 31(2018)

    2018

  10. [18]

    arXiv preprint arXiv:2606.00853 (2026)

    Silveti-Falls, A., Molinari, C., Woodstock, Z.: Frank-wolfe with moreau envelope smoothing for nonsmooth nonconvex problems. arXiv preprint arXiv:2606.00853 (2026)

    2026 arXiv

  11. [19]

    Journal of Scientific Computing85(2), 33 (2020)

    Bot ¸, R.I., B¨ ohm, A.: Variable smoothing for convex optimization problems using stochastic gradients. Journal of Scientific Computing85(2), 33 (2020)

    2020

  12. [20]

    Cambridge University Press, ??? (2023)

    Boumal, N.: An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, ??? (2023)

    2023

  13. [21]

    USSR computational mathematics and mathematical physics7(3), 200–217 (1967)

    Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics7(3), 200–217 (1967)

    1967

  14. [22]

    Naval research logistics quarterly3(1-2), 95–110 (1956)

    Frank, M.,et al.: An algorithm for quadratic programming. Naval research logistics quarterly3(1-2), 95–110 (1956)

    1956

  15. [23]

    USSR Computa- tional mathematics and mathematical physics6(5), 1–50 (1966)

    Levitin, E.S., Polyak, B.T.: Constrained minimization methods. USSR Computa- tional mathematics and mathematical physics6(5), 1–50 (1966)

    1966

  16. [24]

    Mathematical programming120(1), 221–259 (2009)

    Nesterov, Y.: Primal-dual subgradient methods for convex problems. Mathematical programming120(1), 221–259 (2009)

    2009

  17. [25]

    In: Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp

    Kelner, J.A., Lee, Y.T., Orecchia, L., Sidford, A.: An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity gener- alizations. In: Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 217–226 (2014)...

    2014

  18. [26]

    arXiv preprint arXiv:2511.11163 (2025)

    Pethick, T., Antonakopoulos, K., Silveti-Falls, A., Vankadara, L.C., Cevher, V.: Training neural networks at any scale. arXiv preprint arXiv:2511.11163 (2025)

    2025

  19. [27]

    In: Forty-second International Conference on Machine Learning (2025) 25

    Pethick, T., Xie, W., Antonakopoulos, K., Zhu, Z., Silveti-Falls, A., Cevher, V.: Training deep learning models with norm-constrained lmos. In: Forty-second International Conference on Machine Learning (2025) 25

    2025

  20. [28]

    arXiv preprint arXiv:2510.19933 (2025)

    Shulgin, E., AlRashed, S., Orabona, F., Richt´ arik, P.: Beyond the ideal: Analyzing the inexact muon update. arXiv preprint arXiv:2510.19933 (2025)

    2025

  21. [29]

    arXiv preprint arXiv:1312.7864 (2013)

    Lacoste-Julien, S., Jaggi, M.: An affine invariant linear convergence analysis for frank-wolfe algorithms. arXiv preprint arXiv:1312.7864 (2013)

    2013 arXiv

  22. [30]

    Journal of Nonsmooth Analysis and Optimization2(Original research articles) (2021)

    Silveti-Falls, A., Molinari, C., Fadili, J.: Inexact and stochastic generalized con- ditional gradient with augmented lagrangian and proximal step. Journal of Nonsmooth Analysis and Optimization2(Original research articles) (2021)

    2021

  23. [31]

    Regularization, Optimization, Kernels, and Support Vector Machines, 53–82 (2014)

    Argyriou, A., Signoretto, M., Suykens, J.: Hybrid conditional gradient-smoothing algorithms with applications to sparse and low rank regularization. Regularization, Optimization, Kernels, and Support Vector Machines, 53–82 (2014)

    2014

  24. [32]

    SIAM Journal on Optimization 30(4), 2687–2725 (2020)

    Silveti-Falls, A., Molinari, C., Fadili, J.: Generalized conditional gradient with augmented lagrangian for composite minimization. SIAM Journal on Optimization 30(4), 2687–2725 (2020)

    2020

  25. [33]

    SIAM Journal on Optimization35(1), 347–368 (2025)

    Woodstock, Z., Pokutta, S.: Splitting the conditional gradient algorithm. SIAM Journal on Optimization35(1), 347–368 (2025)

    2025

  26. [34]

    Bauschke, H.H., Combettes, P.L.: Infimal Convolution, pp. 203–217. Springer, Cham (2017). h t t p s : / / d o i . o r g / 1 0 . 1 0 0 7 / 9 7 8- 3 - 3 1 9 - 4 8 3 1 1 - 51 2 . https://doi.org/10.1007/978-3-319-48311-5 12

    2017 doi

  27. [35]

    Optimization Online (2010)

    Hoheisel, T., Laborde, M., Oberman, A.: On proximal point-type algorithms for weakly convex functions and their connection to the backward euler method. Optimization Online (2010)

    2010

  28. [36]

    IEEE Transactions on Signal Processing64(6), 1597–1608 (2015)

    Bayram, I.: On the convergence of the iterative shrinkage/thresholding algorithm with a weakly convex penalty. IEEE Transactions on Signal Processing64(6), 1597–1608 (2015)

    2015

  29. [37]

    arXiv preprint arXiv:2504.13633 (2025)

    Wertz, S., Vandaele, A., Gillis, N.: Efficient algorithms for the hadamard decomposition. arXiv preprint arXiv:2504.13633 (2025)

    2025 arXiv

  30. [38]

    IEEE Transactions on Image Processing13(4), 600–612 (2004) 26 A Proofs A.1 Preliminaries The following is a simple lemma that we include for completeness

    Wang, Z., Bovik, A.C., Sheikh, H.R., Simoncelli, E.P.: Image quality assess- ment: From error visibility to structural similarity. IEEE Transactions on Image Processing13(4), 600–612 (2004) 26 A Proofs A.1 Preliminaries The following is a simple lemma that we include for compl...

    2004

  31. [39]

    Ifp >1/2 andq= 2p−1, we have min j∈[K] ϕj ≤ O log(K)K p−1 .(20)

  32. [40]

    Ifp >1/2 and 2p > q >2p−1, we have min j∈[K] ϕj ≤ O K max{p−1, q−p} .(21)

  33. [41]

    Ifp >1/2 andq <2p−1, we have min j∈[K] ϕj ≤ O K p−1 .(22)

  34. [42]

    Hence, by combining and substituting these bounds in Equation (19), we get these possible (and permitted) cases

    Ifp= 1/2 andq∈(0,1/2), we have min j∈[K] ϕj ≤ O log(K)K −1/2 +K q−1/2 .(23) 29 ProofFor the left hand side we have KX k=1 C kp ϕk ≥ KX k=1 C Kp min j∈[K] ϕj ≥CK 1−p min j∈[K] ϕj (24) And we have with the integral test for continuous, positive, decreasing functions, and with p̸...

  35. [43]

    Ifp >1/2 andq= 2p−1, we have CK 1−p min j∈[K] ϕj ≤C 1 +C 3 +C 2 2p 2p−1 +C 3 log(K) (26) Which gives min j∈[K] ϕj ≤ C1 +C 3 C + C22p C(2p−1) K p−1 + C3 C log(K)K p−1 (27)

  36. [44]

    Ifp >1/2 and 2p > q >2p−1, we have CK 1−p min j∈[K] ϕj ≤C 1 +C 2 2p 2p−1 + C3 1−2p+q K 1−2p+q (28) 30 Which gives min j∈[K] ϕj ≤ C1 +C 2 2p 2p−1 K p−1 C + C3 C(1−2p+q) K q−p (29)

  37. [45]

    Ifp >1/2 andq <2p−1, we have CK 1−p min j∈[K] ϕj ≤C 1 +C 2 2p 2p−1 +C 3 2p−q 2p−q−1 (30) Which gives min j∈[K] ϕj ≤ C1 +C 2 2p 2p−1 +C 3 2p−q 2p−q−1 K p−1 C (31)

  38. [46]

    Ifp= 1/2 andq∈(0,1/2), we have CK 1/2 min j∈[K] ϕj ≤C 1 +C 2 +C 2 log(K) +C 3 K q q (32) Which gives min j∈[K] ϕj ≤ C1 +C 2 C K −1/2 + C2 C log(K)K −1/2 + C3 Cq K q−1/2 (33) □ A.2 Proof of Theorem 3 ProofWriteφ k =∇F k(xk). By Lemmas 12 and 13, and becausegisL g-Lipschitz, Fk+...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.