Pith. sign in

REVIEW 2 major objections 3 minor 48 references

An Absolute-Error Proximal Bundle Method through the Lens of Frank-Wolf

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A modified proximal bundle method whose null steps mirror a Frank-Wolfe algorithm on the dual's Moreau envelope solves smooth-plus-piecewise-linear convex problems in $O(\varepsilon^{-4/5} \log^{2/5}(1/\varepsilon))$ iterations, improving…

desk verdict Solid dual Frank-Wolfe framework, but Theorem 3.15's ε^{-4/5} rate is undone by two asymptotic errors; corrected balancing gives ε^{-8/9}, matching the paper's own abstract. read the letter →

arxiv 2411.15926 v3 pith:YVY647FG submitted 2024-11-24 math.OC

David Fersztand , Xu Andy Sun This is my paper · ORCID
classification math.OC MSC 90C2590C3090C6090C46
keywords proximalbundlemethodFrank-WolfealgorithmiterationcomplexitynonsmoothconvexoptimizationMoreauenvelopepiecewiselinearfunctionKelley'scutting-planedualcorrespondence
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 studies MPB-FA, a proximal bundle method variant with a fixed absolute-accuracy null-step test and a fixed proximal parameter, applied to minimizing the sum of a smooth convex function and a convex piecewise linear function. It establishes that the algorithm's null steps are exactly dual to a Fully Corrective Frank-Wolfe algorithm run on the Moreau envelope of the dual problem. Through this lens the paper proves an $O(\varepsilon^{-4/5} \log^{2/5}(1/\varepsilon))$ iteration complexity, a substantial improvement over the best-known $O(\varepsilon^{-2})$ guarantee for related bundle variants. A byproduct is a linear convergence result for Kelley's cutting-plane method when the smooth term is strongly convex and the piecewise linear term is general rather than positive homogeneous. The analysis also gives a theoretical reason to keep active cuts in the bundle after serious steps.

What carries the argument

The load-bearing object is the dual correspondence (Lemmas 3.1-3.3): the bundle subproblem $\min_x g(x)+f_k(x)+\frac{\rho}{2}\|x-x_k\|^2$ is dual to $\min_{(w,\beta)\in\operatorname{conv}(V^k)} M_{\rho,\varphi}(w-\rho x_k)-\beta$, with $y_{k+1}=-\nabla M_{\rho,\varphi}(w_{k+1}-\rho x_k)$. The argument that carries the improved rate is Lemma 3.9, a static-polytope angle lemma: if an FCFW search direction is within angle $\theta$ with $\sin\theta<\gamma/(3D)$ of a previously explored direction, then the current iterate is already optimal for the fixed problem, where $\gamma$ is the pyramidal width and $D$ the diameter of the polytope. Lemmas 3.11-3.12 transfer this to the changing-objective setting by bounding the change in $\nabla M_{\rho,\varphi}$ between consecutive proximal centers in terms of their distance, so a close center pair forces the angle condition and hence a consecutive serious step. The primal progress inequality (3.13) then bounds the number of non-consecutive serious steps, and Lemma 3.6 bounds null-step sequences logarithmically, yielding the total $O(\varepsilon^{-4/5} \log^{2/5}(1/\varepsilon))$ complexity.

What would settle it

Run MPB-FA on $\min_x \tfrac12\|x\|^2 + \max_i(a_i^T x + b_i)$ with known optimum, set $\delta=\varepsilon/2$, and record the angles between FCFW search directions at consecutive null steps; if a pair satisfies $\sin\theta<\gamma/(3D)$ while the Frank-Wolfe gap for the current dual problem (3.8) is still positive, Lemma 3.12 fails. Alternatively, measure total iterations for $\varepsilon=10^{-3},10^{-4},10^{-5}$: growth steeper than $\varepsilon^{-4/5}$ (e.g. roughly $\varepsilon^{-1}$) would contradict the claimed rate.

Watch

Extended reading notes

Core claim

The central discovery is that the sequence of null steps of MPB-FA, i.e. iterations where no progress to the prox-center is accepted, coincides iterate-for-iterate with Fully Corrective Frank-Wolfe applied to the problem $\min_{(w,\beta)\in\operatorname{conv}(V)} M_{\rho,\varphi}(w-\rho x_k)-\beta$, where $\varphi = g^*(-\cdot)$ and $\operatorname{conv}(V)$ encodes the piecewise linear structure of $f$. Because each minimization step of the bundle method is the primal of this dual problem, the null-step test $f(y_{k+1})-f_k(y_{k+1})\le\delta$ equals the Frank-Wolfe gap of that dual problem. Using a geometric lemma on polytopes, namely that two nearly parallel search directions of FCFW cannot both be non-optimal, the paper shows most serious steps are immediately followed by another serious step, and the remainder are controlled by the primal progress of the proximal center. The result is the iteration bound of Theorem 3.15: at most $\rho\|x_0-x^*\|^2/\varepsilon + O((\rho^{-3/2}/\sqrt{\varepsilon})\log(1/\varepsilon))$ iterations, minimized to $O(\varepsilon^{-4/5} \log^{2/5}(1/\varepsilon))$ by setting $\rho=\varepsilon^{1/5} \log^{2/5}(1/\varepsilon)$.

Load-bearing premise

The $O(\varepsilon^{-4/5})$ rate collapses unless a near-parallel pair of Frank-Wolfe search directions in the sequence of changing proximal problems certifies optimality for the current problem; the paper proves this for a fixed polytope (Lemma 3.9) and transfers it to changing Moreau envelopes (Lemma 3.12), but the transfer step is asserted rather than fully demonstrated.

Editorial extensions

If this is right

  • Worst-case iteration count for minimizing a smooth convex plus convex piecewise linear function drops from $O(\varepsilon^{-2})$ to $O(\varepsilon^{-4/5} \log^{2/5}(1/\varepsilon))$ when the proximal parameter is set to $\rho=\varepsilon^{1/5} \log^{2/5}(1/\varepsilon)$.
  • Kelley's cutting-plane method converges linearly when $g$ is smooth and strongly convex and $f$ is any convex piecewise linear function, extending the prior positive-homogeneous result.
  • The active-cut bundle-management policy, keeping active cuts after serious steps rather than all cuts or a single cut, is the one the improved rate requires, and the numerical experiments show it balances bundle size and runtime best.
  • In the high-dimensional, low-accuracy regime $n\gg 1/\varepsilon$, the earlier $O(\varepsilon^{-2} \log(1/\varepsilon))$-type bounds can be tighter than the new geometry-dependent rate, as the paper notes.
  • The dual view places MPB-FA in the family of inexact augmented Lagrangian methods whose subproblems are solved by FCFW, giving a concrete bridge between bundle methods and Frank-Wolfe theory.

Reading between the lines

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

  • Beyond the paper: Lemma 3.9's angle-repetition principle, a near-repeated FCFW direction certifies optimality on a polytope, looks like a general property of Frank-Wolfe on polytopes; it may yield similar improved rates for other FW variants, or with inexact linear minimization oracles.
  • Beyond the paper: the same proof machinery should carry to a general convex $f$ approximated by a growing cut bundle, with the rate governed by the geometry of the cut polytope; this is testable by replacing the LMO with a cut-generation oracle.
  • Beyond the paper: the angle condition fires exactly when the Frank-Wolfe gap is zero, so it could be used as a cheap inner optimality certificate to halt the bundle subproblem before the $\delta$-threshold is met.
  • Beyond the paper: the abstract states $O(\varepsilon^{-8/9})$ while Theorem 3.15 and the conclusions state $O(\varepsilon^{-4/5} \log^{2/5}(1/\varepsilon))$; the body is consistent in its favor, so the abstract rate appears stale and should be read as such.
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 / 3 minor

Summary. The paper studies MPB-FA, a proximal bundle method variant for minimizing the sum of a smooth convex function g and a piecewise linear convex function f. The main contributions are: (i) an extension of the linear convergence of Kelley's method from positive homogeneous f to general piecewise linear convex f when g is smooth and strongly convex; (ii) a dual interpretation of the null steps of MPB-FA as a Fully Corrective Frank-Wolfe algorithm applied to a Moreau-envelope dual problem; (iii) complexity bounds for MPB-FA, with a claimed improved rate of O(epsilon^{-4/5} log^{2/5}); and (iv) numerical experiments on bundle-management policies. The dual correspondence in Section 3.2 and the first complexity analysis in Theorem 3.7 are carefully derived, and the paper gives a useful new perspective on cut management after serious steps.

Significance. If the improved rate were established, the paper would substantially advance the theory of proximal bundle methods: the best known rate for related fixed-proximal-parameter bundle variants is O(epsilon^{-2} log), so an exponent below 2 would be a notable result. The paper also contains genuinely useful elements: the duality between null steps of MPB-FA and FCFW on the Moreau envelope is clearly developed, the extension of Kelley's linear convergence to non-homogeneous piecewise linear objectives is valuable, and the active-cut bundle management experiments give concrete empirical guidance. However, the central advertised improvement in Theorem 3.15 is not supported by the proof as written, because two asymptotic identities used in the balancing argument are incorrect and the geometric transfer in Lemma 3.12 has a gap. The paper therefore needs substantial revision before its main claim is reliable.

major comments (2)
  1. [Theorem 3.15, after (3.32)-(3.33)] The advertised O(epsilon^{-4/5}) rate is not supported by the proof's own asymptotics. The text after (3.32) claims (alpha*rho)^{-1} = O(rho/(2L_g)) as rho tends to 0, but Lemma 3.10 defines alpha = -1/2*sqrt(1/L_g^2 + 4/rho^2) + 1/(2L_g) + 1/rho, which tends to 1/(2L_g), so (alpha*rho)^{-1} = Theta(1/rho). Also, the text below (3.33) states that \bar{\mu}_{\psi,\rho}^{-1} = O(1/rho), whereas (3.15) contains a term 2L_g((4M_f/rho + ...)^2 + 1), giving \bar{\mu}_{\psi,\rho}^{-1} = Omega(1/rho^2). Consequently K in the proof is O(1/rho), not O(1), and the null-step bound in Lemma 3.6 is O(rho^{-3} log(1/epsilon)), not O(rho^{-2} log(1/epsilon)). Balancing rho ||x0-x*||^2/epsilon against the resulting 1/(rho^{7/2} sqrt(epsilon)) log(1/epsilon) term yields rho = epsilon^{1/9} and O(epsilon^{-8/9}) up to logarithmic factors, matching the abstract's exponent rather than the epsilon^{-4/5} claimed in Theorem 3.15. The theorem's parameter selection and rate statement therefore need to be corrected.
  2. [Lemma 3.12] Lemma 3.12 applies the static-polytope angle lemma (Lemma 3.9, claim 2) to a sequence of Frank-Wolfe problems whose objectives Psi_k change after every serious step because the proximal center x_k is updated. Lemma 3.9 is proved for a fixed objective psi and a fixed polytope, and claim 2 requires the direction d_1 to have been explored in the same FCFW run on the same objective. In Lemma 3.12, \tilde{y}_k is a gradient direction for Psi_{k-1}, while optimality is claimed for Psi_k; Lemma 3.11 bounds the difference between gradients at different points and different proximal centers, but it does not show that \tilde{y}_k is a direction of the current objective Psi_k at the appropriate iterate. The premise sin(theta') < gamma/(3D) therefore does not, as written, certify optimality for Psi_k. This is load-bearing: Lemma 3.12 is the mechanism that makes consecutive serious steps cheap, and without it the improved rate collapses to the O(epsilon^{-2} log(1/epsilon)) bound of Theorem 3.7.
minor comments (3)
  1. [Abstract vs. Theorem 3.15] The opening abstract states an O(epsilon^{-8/9}) iteration complexity, while the full-text abstract, Section 1.3, Section 1.4, Theorem 3.15, and the conclusion state O(epsilon^{-4/5} log^{2/5}). These are different exponents and the inconsistency must be resolved, especially in light of the corrected balancing in Theorem 3.15.
  2. [Section 3.1] The abstract refers to a modification of the serious-step test, while Algorithm 3.1 and Section 3.1 describe a null-step test. The terminology should be made consistent throughout.
  3. [Lemma 3.6] The displayed formula for the logarithmic factor in (3.14) contains a fraction that simplifies awkwardly; please check the expression \log(D^4/(\delta^2 \bar{\mu}_{\psi,\rho}^2)) and ensure it matches the substitution from Theorem 2.7.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivation chain is self-contained and its core rate is obtained by balancing algorithm parameters, not by fitting or by self-citation.

full rationale

The central claims do not reduce to their inputs by construction. The dual equivalence in Lemma 2.1 is a standard Fenchel/Sion minimax derivation, and Lemma 2.2 provides an explicit primal-dual variable correspondence rather than assuming the conclusion. The linear convergence of Kelley's method in Theorem 2.7 is imported from the external Frank-Wolfe linear-convergence result of Lacoste-Julien and Jaggi [27], with the geometric strong-convexity constant in Lemma 2.6 derived from the stated smoothness, strong-convexity, and diameter assumptions; none of these assumptions includes the target rate. The MPB-FA analysis in Section 3 likewise proceeds by computing the conjugate and Moreau envelope (Lemma 3.1), identifying the null-step test with the Frank-Wolfe gap (Lemma 3.3), and applying the external linear-convergence bound to each proximal subproblem (Lemma 3.6). Lemma 3.5 is an external proposition from Liang and Monteiro [33], not a self-citation. Theorem 3.15's O(epsilon^{-4/5}) rate comes from optimizing the free parameters rho and A in the bounds (3.32)-(3.33); this is standard complexity balancing, not fitting a parameter to output data. The paper does cite prior work by other authors for the FW rate and the null-step test, and these citations are real evidence rather than load-bearing self-citations. The geometric transfer asserted in Lemma 3.12 and the asymptotic simplifications after (3.32) may be correctness risks, but they are not circular reductions: they do not define a quantity in terms of the result being proved, nor do they rename a known result as a prediction. Accordingly, no circular step meeting the quoted-evidence standard is present, and the circularity score is 0.

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

The analysis introduces no new physical or mathematical entities. The algorithm MPB-FA is a variant of the proximal bundle method; the only 'new' constructs are the modified null-step test and the analysis parameters ρ, δ, A, none of which are postulates about nature.

free parameters (3)
  • ρ (proximal parameter) = ε^{1/5} log(1/ε)^{2/5} in Theorem 3.15
    Fixed in Algorithm 3.1; chosen in the analysis to balance the number of serious steps (∝ρ/ε) against null steps (∝1/(ρ^{3/2}√ε)); not fitted to data.
  • A (threshold for 'distant' serious steps) = A² = √2‖x0-x*‖γ / (6(1+5/(αρ))D√ρ ε^{-1/2}) as written, but the correct minimizer appears to be ∝1/√(ρε)
    Introduced in Lemma 3.12 to define the distance threshold A√ε; chosen to minimize the count of serious steps with null steps. The displayed formula and the resulting rate contain typos (see red flags).
  • δ (null-step test accuracy) = ε/2
    Accuracy parameter in the null-step test of Algorithm 3.1; fixed to ε/2 by the theorem statement.
assumptions (7)
  • standard math Sion's minimax theorem
    Used in Lemma 2.1 to establish strong duality between (1.1) and its dual (2.5).
  • standard math Fenchel duality and conjugate calculus
    Used to derive the dual problems, Lemma 2.1 and Lemma 3.1, including the formula (g + (ρ/2)‖·-x_k‖²)* = Moreau envelope.
  • standard math Moreau envelope smoothness and strong convexity
    Used in Lemma 3.6 and Lemma 3.11; cites Beck Theorem 6.60 and Rockafellar-Wets.
  • standard math Pyramidal width convergence results for FCFW from [27]
    Theorem 2.7 and Lemma 3.6 rely on the linear convergence of FCFW on polytopes from Lacoste-Julien and Jaggi.
  • domain assumption Finite piecewise linear representation with LMO
    Assumptions 1.5: f is convex piecewise linear with a finite V and a linear maximization oracle.
  • domain assumption g is L_g-smooth and (in Sec. 2) μ_g-strongly convex
    Assumptions 1.5; the smoothness of g drives the dual strong convexity and the Moreau envelope analysis.
  • domain assumption Subproblem solver oracle
    MPB-FA assumes an oracle solves min g+f_k+ (ρ/2)‖·-x_k‖² exactly; Section 1.5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Absolute-Error Proximal Bundle Method through the Lens of Frank-Wolf." pith.science (2026). https://pith.science/paper/YVY647FG

@misc{pith2026241115926,
  author       = {Pith},
  title        = {Pith review of: An Absolute-Error Proximal Bundle Method through the Lens of Frank-Wolf},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YVY647FG}},
  note         = {Machine review of arXiv:2411.15926}
}
abstract

The proximal bundle method (PBM) is a fundamental and computationally effective algorithm for solving optimization problems with nonsmooth components. In this paper, we conduct a theoretical investigation of a modified proximal bundle method, which we call the Modified Proximal Bundle with Fixed Absolute Accuracy (MPB-FA). MPB-FA modifies the serious-step test of the PBM serious-step test. In MPB-FA, it is based on an absolute accuracy criterion, and the accuracy is fixed over iterations, while the standard PBM uses a relative accuracy in the serious-step test, which changes with iterations. Also, similarly to multiple PBM analyses, the proximal parameter in MPB-FA is also fixed over iterations, while it is permitted to change in the standard PBM. These modifications allow us to build the first link between a proximal bundle method and a Frank-Wolfe algorithm on the Moreau envelope of the dual problem. In light of this correspondence, we first extend the linear convergence of Kelley's method on the sum of a smooth strongly convex function and a convex piecewise linear function from the positive homogeneous to the general case. Building on this result, we propose a novel complexity analysis of MPB-FA when the objective is the sum of a smooth and a piecewise function and derive an $\mathcal{O}(\epsilon^{-8/9})$ iteration complexity, improving upon the best known $\mathcal{O}(\epsilon^{-2})$ guarantee on a related variant of PBM. It is worth-noting that the best known complexity bound for the classical PBM in the general case is $\mathcal{O}(\epsilon^{-3})$ and $\mathcal{O}(\epsilon^{-2})$ when the proximal parameter is fixed. Our approach also reveals new insights on bundle management and empirical behavior of the proximal bundle methods.

Figures

Figures reproduced from arXiv: 2411.15926 by the authors.

Figure 1
Figure 1. The two leftmost plots compare the memory usage and the optimality gap across bundle management policies (n = 200). The last plot compares their runtime for varying problem dimension n with interquartiles. Sythetic data experiment. We illustrate the performance gain of the active-cut policy through a numerical study on the problem: min 1 2 ∥x∥ 2 + max{x T y + d : y ∈ [−1, 1]n, d ∈ [−1, 1], Ay + cd ≤ b}. The dimensio… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 31 canonical work pages

  1. [1]

    Alexander, The width and diameter of a simplex, Geometriae Dedicata, 6 (1977), pp

    R. Alexander, The width and diameter of a simplex, Geometriae Dedicata, 6 (1977), pp. 87–94, https://api.semanticscholar.org/CorpusID:123627093

    work page 1977

  2. [2]

    Projection-Free Non-Smooth Convex Programming

    K. Asgari and M. J. Neel y , Projection-free non-smooth convex programming, arXiv, (2023), https://arxiv.org/abs/2208.05127

    work page Pith review arXiv 2023

  3. [3]

    A tenas and C

    F. A tenas and C. Sagastizábal , A bundle-like progressive hedging algorithm. working paper or preprint, May 2024, https://hal.science/hal-03738298

    work page 2024

  4. [4]

    Azé and J.-P

    D. Azé and J.-P. Penot , Uniformly convex and uniformly smooth convex functions, Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série 6, 4 (1995), pp. 705–730, http://www.numdam.org/item?id=AFST_1995_6_4_4_705_0

    work page 1995

  5. [5]

    Bach, Learning with Submodular Functions: A Convex Optimization Perspective, Now Publishers Inc., Hanover, MA, USA, 2013, https://doi.org/10.1561/2200000039

    F. Bach, Learning with Submodular Functions: A Convex Optimization Perspective, Now Publishers Inc., Hanover, MA, USA, 2013, https://doi.org/10.1561/2200000039

    work page doi:10.1561/2200000039 2013

  6. [6]

    Bach, Duality between subgradient and conditional gradient methods, SIAM Journal on Optimization, 25 (2015), pp

    F. Bach, Duality between subgradient and conditional gradient methods, SIAM Journal on Optimization, 25 (2015), pp. 115–129, https://doi.org/10.1137/130941961. 26

    doi:10.1137/130941961 2015

  7. [7]

    Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017, https://doi.org/10.1137/1.9781611974997

    A. Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017, https://doi.org/10.1137/1.9781611974997

    doi:10.1137/1.9781611974997 2017

  8. [8]

    Beck and S

    A. Beck and S. Shtern , Linearly convergent away-step conditional gradient for non-strongly convex functions, Mathematical Programming, 164 (2017), pp. 1–27, https://doi.org/10. 1007/s10107-016-1069-4

    work page 2017

Show all 48 references
  1. [9]

    Ben-Tal, L

    A. Ben-Tal, L. Ghaoui, and A. Nemirovski , Robust Optimization, Princeton University Press, 2009, https://doi.org/10.1515/9781400831050

    2009 doi

  2. [10]

    Ber tsimas and D

    D. Ber tsimas and D. den Her tog , Robust and Adaptive Optimization, Dynamic Ideas LLC, 2022, https://books.google.com/books?id=V_RPzwEACAAJ

    2022

  3. [11]

    J. F. Bonnans, J. C. Gilbert, C. Lemaréchal, and C. A. Sagastizábal , Numerical Optimization: Theoretical and Practical Aspects, Universitext, Springer Berlin, Heidelberg, 2 ed., Sept. 2006, https://doi.org/10.1007/978-3-540-35447-5

    2006 doi

  4. [12]

    Braun, A

    G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokhtari, and S. Pokutta , Conditional gradient methods, 2023, https://arxiv.org/abs/2211.14103

    2023 arXiv

  5. [13]

    de Oliveira, C

    W. de Oliveira, C. Sagastizábal, and C. Lemaréchal , Convex proximal bundle methods in depth: a unified analysis for inexact oracles, Mathematical Programming, 148 (2014), pp. 241–277, https://doi.org/10.1007/s10107-014-0809-6

    2014 doi

  6. [14]

    Diaz and B

    M. Diaz and B. Grimmer , Optimal convergence rates for the proximal bundle method, SIAM Journal on Optimization, (2023), pp. 424–454, https://doi.org/10.1137/21M1428601

    2023 doi

  7. [15]

    Du and A

    Y. Du and A. Ruszczyński , Rate of convergence of the bundle method, Journal of Op- timization Theory and Applications, 173 (2017), pp. 908–922, https://doi.org/10.1007/ s10957-017-1108-1

    2017

  8. [16]

    Frank and P

    M. Frank and P. Wolfe , An algorithm for quadratic programming, Naval research logistics quarterly., 3 (1956), https://doi.org/10.1002/nav.3800030109

    1956 doi

  9. [17]

    R. M. Freund and P. Grigas , New analysis and results for the Frank–Wolfe method, Mathe- matical Programming, 155 (2016), pp. 199–230, https://doi.org/10.1007/s10107-014-0841-6

    2016 doi

  10. [18]

    M. R. Hestenes , Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4 (1969), pp. 303–320, https://doi.org/10.1007/BF00927479

    1969 doi

  11. [19]

    Hiriart-Urruty and C

    J.-B. Hiriart-Urruty and C. Lemaréchal , Fundamentals of Convex Analysis, Springer, Berlin, Heidelberg, 2001, https://doi.org/10.1007/978-3-642-56468-0

    2001 doi

  12. [20]

    C. A. Hollow ay, An extension of the Frank and Wolfe method of feasible directions, Mathe- matical Programming, 6 (1974), pp. 14–27, https://doi.org/10.1007/BF01580219

    1974 doi

  13. [21]

    Kaur and S

    A. Kaur and S. H. Lui , New lower bounds on the minimum singular value of a matrix, Linear Algebra and its Applications, 666 (2023), pp. 62–95, https://doi.org/10.1016/j.laa.2023.02. 013

    2023 doi

  14. [22]

    J. E. Kelley, Jr. , The cutting-plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics, 8 (1960), pp. 703–712, https://doi.org/10. 1137/0108053

    1960

  15. [23]

    K. C. Kiwiel , Proximity control in bundle methods for convex nondifferentiable minimization, Mathematical Programming, 46 (1990), pp. 105–122, https://doi.org/10.1007/BF01585731

    1990 doi

  16. [24]

    K. C. Kiwiel , Efficiency of proximal bundle methods, Journal of Optimization Theory and Applications, 104 (2000), pp. 589–603, https://doi.org/10.1023/A:1004689609425

    2000 doi

  17. [25]

    Kuchlbauer, F

    M. Kuchlbauer, F. Liers, and M. Stingl , Adaptive bundle methods for nonlinear robust optimization, INFORMS Journal on Computing, 34 (2022), pp. 2106–2124, https://doi.org/ 10.1287/ijoc.2021.1122

    2022

  18. [26]

    Lacoste-Julien and M

    S. Lacoste-Julien and M. Jaggi , An affine invariant linear convergence analysis for Frank- Wolfe algorithms, NIPS 2013 Workshop on Greedy Algorithms, Frank-Wolfe and Friends, (2013), https://doi.org/10.48550/arXiv.1312.7864

    2013 doi arXiv

  19. [27]

    Lacoste-Julien and M

    S. Lacoste-Julien and M. Jaggi , On the global linear convergence of Frank-Wolfe optimiza- tion variants, in NIPS’15, 2015, p. 496–504

    2015

  20. [28]

    Lan, The complexity of large-scale convex programming under a linear optimization oracle, 2014, https://arxiv.org/abs/1309.5550

    G. Lan, The complexity of large-scale convex programming under a linear optimization oracle, 2014, https://arxiv.org/abs/1309.5550

    2014 arXiv

  21. [29]

    Lan , Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization, Mathematical Programming, 149 (2015), pp

    G. Lan , Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization, Mathematical Programming, 149 (2015), pp. 1–45, https://doi.org/10.1007/ s10107-013-0737-x

    2015

  22. [30]

    Q. Le, A. Smola, and S. Vishw ana than , Bundle methods for machine learning, Advances in Neural Information Processing Systems, 20 (2007), https://proceedings.neurips.cc/paper_ files/paper/2007/file/26337353b7962f533d78c762373b3318-Paper.pdf

    2007

  23. [31]

    Lemaréchal, A

    C. Lemaréchal, A. Nemirovskii, and Y. Nesterov , New variants of bundle methods, Mathematical Programming, 69 (1995), pp. 111–147, https://doi.org/10.1007/BF01585555

    1995 doi

  24. [32]

    Liang and R

    J. Liang and R. D. C. Monteiro , A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes, SIAM Journal on Optimization, 31 (2021), pp. 2955–2986, 27 https://doi.org/10.1137/20M1327513

    2021 doi

  25. [33]

    Liang and R

    J. Liang and R. D. C. Monteiro , A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems, Mathematics of Operations Research, (2023), https://doi.org/10.1287/moor.2023.1372

    2023

  26. [34]

    Martinet, Algorithmes Pour La Résolution de Problèmes d’optimisation et de Minimax, PhD thesis, Université Scientifique et Médicale de Grenoble, 1972

    B. Martinet, Algorithmes Pour La Résolution de Problèmes d’optimisation et de Minimax, PhD thesis, Université Scientifique et Médicale de Grenoble, 1972

    1972

  27. [35]

    Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Applied Opti- mization, Springer New York, NY, 1 ed., 2004, https://doi.org/10.1007/978-1-4419-8853-9

    Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Applied Opti- mization, Springer New York, NY, 1 ed., 2004, https://doi.org/10.1007/978-1-4419-8853-9

    2004 doi

  28. [36]

    M. J. D. Powell , A method for nonlinear constraints in minimization problems, Optimization: Symposium of the Institute of Mathematics and Its Applications, University of Keele, England, 1968, (1969), pp. 283–298

    1969

  29. [37]

    Rockafellar , Convex Analysis, Princeton Mathematics, Princeton University Press, Princeton, New Jersey, 28 ed., 1970, https://doi.org/doi:10.1515/9781400873173

    R. Rockafellar , Convex Analysis, Princeton Mathematics, Princeton University Press, Princeton, New Jersey, 28 ed., 1970, https://doi.org/doi:10.1515/9781400873173

    1970 doi

  30. [38]

    R. T. Rockafellar , The multiplier method of hestenes and powell applied to convex pro- gramming, Journal of Optimization Theory and Applications, 12 (1973), pp. 555–562, https://doi.org/10.1007/BF00934777

    1973 doi

  31. [39]

    R. T. Rockafellar and R. J. B. Wets , Variational Analysis, vol. 317 of Grund- lehren der mathematischen Wissenschaften, Springer, 1998, https://doi.org/10.1007/ 978-3-642-02431-3

    1998

  32. [40]

    E. K. Ryu and W. Yin , Large-Scale Convex Optimization: Algorithms & Analyses via Monotone Operators, Cambridge University Press, Cambridge, UK, new ed., 2022

    2022

  33. [41]

    Schramm and J

    H. Schramm and J. Zowe , Bundle method for nonsmooth optimization: Concept, convergence, and computation, SIAM Journal on Optimization, 2 (1992), pp. 121–152, https://doi.org/ 10.1137/0802008

    1992 doi

  34. [42]

    Shalev-Shw artz and Y

    S. Shalev-Shw artz and Y. Singer , Efficient learning of label ranking by soft projections onto polyhedra, Journal of Machine Learning Research, 7 (2006), pp. 1567–1599, http: //jmlr.org/papers/v7/shalev-shwartz06a.html

    2006

  35. [43]

    Shalev-Shw artz, Y

    S. Shalev-Shw artz, Y. Singer, N. Srebro, and A. Cotter , Pegasos: primal estimated sub-gradient solver for SVM, Mathematical Programming, 127 (2011), pp. 3–30, https: //doi.org/10.1007/s10107-010-0420-4

    2011 doi

  36. [44]

    Sion, On general minimax theorems, Pacific Journal of Mathematics, 8 (1958), pp

    M. Sion, On general minimax theorems, Pacific Journal of Mathematics, 8 (1958), pp. 171–176, https://doi.org/10.2140/pjm.1958.8.171

    1958 doi

  37. [45]

    X. A. Sun and A. J. Conejo , Robust Optimization in Electric Energy Systems, International Series in Operations Research & Management Science, Springer Cham, 2021, https://doi. org/10.1007/978-3-030-85128-6

    2021 doi

  38. [46]

    C. H. Teo, S. Vishw anthan, A. J. Smola, and Q. V. Le , Bundle methods for regularized risk minimization, Journal of Machine Learning Research, 11 (2010), pp. 311–365, http: //jmlr.org/papers/v11/teo10a.html

    2010

  39. [47]

    v an Ackooij, V

    W. v an Ackooij, V. Berge, W. de Oliveira, and C. Sagastizábal , Probabilistic opti- mization via approximate p-efficient points and bundle methods, Computers & Operations Research, (2017), https://doi.org/10.1016/j.cor.2016.08.002

    2017 doi

  40. [48]

    S. Zhou, S. Gupt a, and M. Udell , Limited memory Kelley’s method converges for composite convex and submodular objectives, in Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, Red Hook, NY, USA, 2018, pp. 4419–4429, https://do...

    2018 doi arXiv

Pith tools

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