Monotone and nonmonotone linearized block coordinate descent methods for nonsmooth composite optimization problems

Lahcen El Bourkhissi; Sebastian U. Stich; Tuomo Valkonen; Yassine Nabou

REVIEW 3 major objections 5 minor 39 references

Monotone and nonmonotone linearized block coordinate descent methods for nonsmooth composite optimization problems

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Two randomized block-coordinate Gauss-Newton methods reach ε-stationarity at O(1/ε²) iterations for nonsmooth composite objectives.

desk verdict The monotone half is a clean contribution; the nonmonotone half's central theorem is stated without proof, so the paper needs major revision before it can be trusted. read the letter →

arxiv 2506.12397 v1 pith:3GAC2527 submitted 2025-06-14 math.OC

Yassine Nabou , Lahcen El Bourkhissi , Sebastian U. Stich , Tuomo Valkonen This is my paper · ORCID

classification math.OC MSC 90C2690C3065K0590C06

keywords blockcoordinatedescentGauss-Newtonmethodnonsmoothcompositeoptimizationnonconvexiterationcomplexitynonmonotonealgorithmrandomizedselectionquadraticpenalty

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 aims to show that a Gauss-Newton-type linearization can be combined with random block coordinate updates without losing the optimal O(1/ε²) iteration complexity for minimizing f(x)+h(F(x))+Σg_i(x_i). Each step linearizes f and F only in one randomly chosen block while keeping h and the block regularizer g_i intact, then solves a strongly convex subproblem with an adaptive proximal weight. The monotone variant enforces objective decrease and is proved to converge in expectation to stationarity whenever the iterates stay in a compact set. The nonmonotone variant swaps that requirement for a compact level set and an affine lower bound on g, so it needs neither global Lipschitz constants nor a priori bounded iterates. Numerical experiments on binary classification problems indicate the block version can beat both proximal block coordinate descent and the full-block Gauss-Newton method.

What carries the argument

The load-bearing object is the randomized block Gauss-Newton surrogate $\bar{\varphi}_i(s;\bar x) + \frac{\beta_{k+1}}2\|s-\bar x_i\|^2$, where $\bar\varphi_i$ linearizes $f$ and $F$ only along block $i$ and keeps $h$ and $g_i$ intact; the adaptive proximal weight $\beta_{k+1}$ is doubled until the monotone decrease test $\varphi(x_{k+1})\le \varphi(x_k)-\frac{\beta_{k+1}}2\|x_{k+1}-x_k\|^2$ passes, or until the nonmonotone memory sequence $R_{k+1}=(1-u_{k+1})R_k+u_{k+1}\varphi(x_{k+1})$ drops enough. Strong convexity of the surrogate yields the sufficient decrease, block Lipschitz continuity yields the descent lemma and the iterates-difference bound on the Mordukhovich subdifferential, and the two-case split of that bound produces the $O(1/\epsilon^2)+O(1/\epsilon)$ iteration count.

What would settle it

Run Monotone LiBCoD on a small instance of problem (1) that provably satisfies Assumption 1 on a known compact set, and compare the first iteration at which E[dist(0,∂φ(x_k))] ≤ ε with the theorem's predicted O(1/ε²) count; a single such instance that fails to reach ε-stationarity in the stated order would refute Theorem 3.1. Alternatively, for the nonmonotone variant, choose an instance with compact level set L_{φ(x0)} and g bounded below by an affine function, and check empirically whether the iterates really stay in that level set and the rate holds.

Watch

Extended reading notes

Core claim

The paper claims that both LiBCoD variants converge globally, in expectation, to a stationary point of problem (1), and that the first time E[dist(0,∂φ(x_{k+1}))] ≤ ε is at most O(1/ε²) iterations for each variant. This means a single randomly chosen block per iteration does not cost extra iteration complexity compared with updating the full block stack, provided the regularization parameter is chosen on the order of √L_h. The nonmonotone version achieves the same order under assumptions that are checked by the data—a compact level set and an affine lower bound on g—rather than by an unverified bounded-iterate hypothesis.

Load-bearing premise

For the monotone variant, everything rests on the generated iterates staying inside a fixed compact set where all block Lipschitz constants are finite; the algorithm does not enforce or verify this containment, so the descent lemma can silently fail if an iterate leaves the set.

Editorial extensions

If this is right

Both LiBCoD variants produce, in expectation, a point with dist(0,∂φ(x)) ≤ ε after O(1/ε²) sampled-block iterations; with β_min = O(√L_h) the constant matches the full-block Gauss-Newton guarantee.
The nonmonotone variant attains the same rate under a compact level-set plus affine-lower-bound assumption, so users do not need to know global Lipschitz constants or verify bounded iterates in advance.
Because each subproblem is strongly convex, the inner minimization can be solved efficiently with an accelerated proximal gradient method, keeping per-iteration cost to a single-block proximal step rather than a full Jacobian update.
For equality-constrained problems min f+Σg_i subject to F(x)=0, using either variant on the quadratic penalty φ_ρ yields an ε-KKT point in O(1/ε^{2.5}) Jacobian evaluations when ρ=O(1/ε), matching the full-block linearized penalty bound.
Numerical results on LIBSVM classification problems show that using only 10% of the blocks routinely outperforms proximal block coordinate descent and often matches the full-block Gauss-Newton method in loss reduction.

Reading between the lines

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

The proof's two-case split (linear versus quadratic term in the subgradient bound) suggests the O(1/ε²) rate is governed by a small number of difficult iterations; a possible extension is to track the online concentration of those cases to tighten the constant.
The nonmonotone R_k Lyapunov machinery comes from proximal gradient theory and could plausibly be transplanted into other block surrogate schemes, such as sketched-Jacobian or higher-order Taylor methods, to remove their global Lipschitz assumptions in the same way.
If block sampling probabilities were chosen adaptively rather than fixed, the constants could improve on problems whose blocks have very different Lipschitz constants; the paper does not explore adaptive sampling.
The conclusion notes that only separable nonsmooth parts are covered; a natural test is to replace Σg_i(x_i) by g(Mx) and see whether a block surrogate remains solvable or whether a dual decomposition is required.

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.

Desk Editor's Note

read the letter

Short version: the monotone variant is a real contribution, but the nonmonotone section's central theorem is not actually proved in the text. Treat Theorem 4.2 as conjectural in this version.

What's new: combining Gauss-Newton linearization with block-coordinate selection for composite nonsmooth problems with separable regularizers. That specific combination is absent in the cited literature. The monotone analysis is solid: Lemmas 3.1 and 3.2 are fully proved, and Theorem 3.1 telescopes correctly to O(√Lh/ε²), matching the full-block rate while updating one block per iteration. The adaptive β backtracking is a nice practical touch. The experiments are reasonable and the observation that a 10% block size approaches full-block performance is useful. No code, so reproducibility is limited.

Soft spots: the nonmonotone section leans almost entirely on other papers. Lemma 4.1 says "follows similar reasoning as in [19,11]"; Proposition 4.1 and Theorem 4.2 have no proofs. The stress-test note is correct that this isn't a trivial transfer: the monotone proof telescopes over φ(x_k) − φ(x_{k+1}), while the nonmonotone version must telescope over R_k − R_{k+1}, introducing the u_min factor and requiring a direct bound on E[dist²] by that same difference. That step is missing entirely. It's probably repairable via the approach in [18,19], but it isn't done. There's also a minor slip in Eq. (9): the bound on β_k is stated independent of β_1, but Algorithm 3.1 accepts arbitrary β_1 and only decays it, so early iterates can violate it. Absorbing β_1 into the constants fixes it.

Citations look fine: [5] self-citation is appropriate for the penalty complexity comparison, and the paper doesn't hide its dependence on [21,19,11]. The Mordukhovich subdifferential is the standard choice here.

Recommendation: send to a referee. The monotone part alone justifies a look, and the nonmonotone gap is fixable with a real proof added. I wouldn't rely on the nonmonotone result until that's done.

Referee Report

3 major / 5 minor

Summary. The paper proposes monotone and nonmonotone randomized block coordinate descent methods for minimizing composite objectives of the form f(x)+h(F(x))+sum_i g_i(x_i). At each iteration a random block is selected, the smooth maps f and F are linearized along that block in a Gauss-Newton fashion while h is kept intact, and a dynamic quadratic regularization term is added; an inner backtracking loop enforces sufficient decrease with respect to either phi(x_k) (monotone variant) or a Lyapunov sequence R_k (nonmonotone variant). The claimed results are O(1/epsilon^2) expected iteration complexity to an epsilon-stationary point under compactness/bounded-iterate assumptions, matching the full-block Gauss-Newton rate of [21], plus an application of the framework to quadratic-penalty formulations of nonconvex equality-constrained problems. Numerical experiments on LIBSVM binary-classification problems compare the monotone variant with proximal block coordinate descent and full Gauss-Newton.

Significance. If fully established, the paper would make a useful contribution: it extends the prox-linear/Gauss-Newton machinery to randomized block updates and, for the nonmonotone variant, relaxes global Lipschitz and bounded-iterate requirements to a compact level-set assumption while retaining an explicit O(1/epsilon^2) rate. The monotone analysis is largely self-contained, the algorithm is parameter-light (only beta_min, p_min, u_min), and the numerical experiments are presented in reasonable detail. However, the headline nonmonotone theorem currently rests on delegated proofs from proximal-gradient papers, and the transfer to the block Gauss-Newton setting is nontrivial; the advertised complexity for Nonmonotone LiBCoD is therefore not established in the manuscript as written. The equality-constrained application in Section 5 inherits this gap whenever it invokes Theorem 4.2.

major comments (3)

[Section 4, Lemma 4.1] The well-definedness of the inner loop is asserted with the single sentence 'The formal proof of the above lemma follows similar reasoning as in [19,11],' and no proof is given. This is not a routine transfer: [19,11] analyze proximal-gradient iterations for f+g, whereas Algorithm 4.1 uses a block Gauss-Newton model with h(F(x_k)+nabla_{i_k}F(x_k)(s-x_k^{i_k})) and a stopping test in Line 17 that is measured against the Lyapunov value R_k rather than phi(x_k). The argument that the backtracking loop terminates must use the affine lower bound on g and must show that beta_{k+1} cannot grow without bound under the R_k-based test. Because Lemma 4.1 is needed before R_k can serve as a Lyapunov function in Theorem 4.1, this omission is load-bearing.
[Section 4, Proposition 4.1 and Theorem 4.2] Both proofs are omitted; the text says only that they follow 'similar lines' or 'a similar reasoning' as Proposition 3.1 and Theorem 3.1. The monotone complexity proof telescopes the sum E[phi(x_k)-phi(x_{k+1})], which is valid only under the monotone decrease enforced by Algorithm 3.1. In Algorithm 4.1, phi may increase, so a correct proof must telescope over R_k-R_{k+1}, using R_{k+1} <= R_k - u_{k+1} beta_{k+1} ||x_{k+1}-x_k||^2/2 and the lower bound u_{k+1} >= u_min; this is also where the 1/u_min factor in the stated bound enters. Neither this telescoping step nor the direct bound of E[dist^2] by R_k-R_{k+1} appears in the manuscript, so the claimed O(1/epsilon^2) rate with constants p_min u_min beta_min in the denominator is not demonstrated. The same gap affects Theorem 5.1 whenever it is invoked with Nonmonotone LiBCoD.
[Section 3, Eq. (9)] The claim that beta_k is bounded above by a quantity independent of the input beta_1 is false as stated. Algorithm 3.1 accepts any beta_1 >= beta_min/2 and decays beta by a factor of 1/4 only after a successful inner iteration, so a large beta_1 can make early beta_k exceed the right-hand side of (9). This bound is used in Lemma 3.2 and in the constants of Theorem 3.1. The issue is repairable by absorbing beta_1 into the definition of \bar{beta} or by initializing beta_1 below the threshold in (2), but as written the displayed complexity bound is not justified.

minor comments (5)

[Algorithms 3.1 and 4.1] The line 'beta_{k+1} := 2 beta_{k+1}' is notationally ambiguous inside the repeat loop because beta_{k+1} has not been assigned before the loop; the intent is to double the current regularization parameter before testing the sufficient-decrease condition.
[Section 4, paragraph before Lemma 4.2] The range 'i = 1. . . . , m' for the block indices of the Jacobian bounds should be i = 1, ..., n_block; F maps to R^m but the block gradient is with respect to block i of the domain.
[Section 4, after Theorem 4.1] The sentence 'Next, we derive the following convergence rate. Next, we derive the following convergence rate.' is duplicated.
[Section 6.1.2] The nonmonotone experiments report loss curves for different u values but do not compare against a baseline or record any epsilon-stationarity measure, so the numerical section provides no direct corroboration of the claimed complexity of Nonmonotone LiBCoD.
[Throughout] Minor typos include 'bellow' for 'below', 'Nonmototone' for 'Nonmonotone', and the inconsistent table header 'mean(%) iter(%)' in Table 4; these should be corrected in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No load-bearing circularity: main rates derive from Assumption 1 plus external descent lemmas; self-citations are background only.

full rationale

The central derivation is self-contained rather than circular. Theorem 3.1's O(1/epsilon^2) bound follows from Assumption 1, Lemma 3.1's sufficient decrease, Lemma 3.2's subgradient bound, and telescoping of E[phi(x_k)-phi(x_{k+1})]; the descent lemma is proved in the text (adapted from the external full-block result [21]). The nonmonotone variant uses a genuine Lyapunov sequence R_k defined in Algorithm 4.1, with Theorem 4.1 proving R_{k+1} <= R_k - u_{k+1} beta_{k+1} ||x_{k+1}-x_k||^2/2 and x_k in the level set; no fitted parameter is renamed as a prediction. The proof gaps are real but are not circularity: Lemma 4.1 says 'The formal proof of the above lemma follows similar reasoning as in [19, 11]', and Theorem 4.2 says 'The proof follows a similar reasoning as that of theorem 3.1', with the R_k-based telescoping not displayed; [19,11] are external references, so this is omitted support, not self-referential reduction. Likewise Eq. (9)'s claim that beta_k is bounded by a threshold independent of beta_1 is not actually valid for arbitrary beta_1, but this is a repairable constant/rigor slip rather than circularity. The only self-citations ([5],[6],[10],[17],[22]) are background comparisons (e.g., 'this iteration complexity matches the optimal one derived ... in [5]') or subdifferential/penalty-method background; none is load-bearing for Theorems 3.1-4.2. Hence no circular step is established.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central derivation rests on the stated smoothness and lower-boundedness assumptions, the compactness of the level set, and the affine lower bound on the nonsmooth term. The algorithmic hyperparameters βmin, pmin, and umin appear in the complexity constants but are not fitted to data. No invented entities are introduced.

free parameters (1)

β_min (penalty floor) = user-specified; set O(√Lh) for optimal rate in Section 3, O(√ρ) in Section 5
Appears in the denominator of the iteration complexity bounds. Any positive value works; the asymptotic scaling is chosen by hand to match known optimal rates, not fitted to data.

assumptions (5)

domain assumption Assumption 1: block-coordinate Lipschitz continuity of gradients of f and F on a compact set, Lh-smoothness of h, lsc convexity of g_i, and lower boundedness of all components.
Used in Lemma 3.1, Lemma 3.2, and all convergence theorems for both variants.
domain assumption For the nonmonotone variant, g is bounded below by an affine function.
Required for the inner backtracking loop to terminate (Lemma 4.1) and for Theorem 4.1 and Theorem 4.2.
domain assumption The level set L_{φ(x0)} = {x : φ(x) ≤ φ(x0)} is compact.
Used in Theorem 4.1 to deduce boundedness of iterates for the nonmonotone variant, which replaces the monotone variant's explicit bounded-iterates assumption.
domain assumption Assumption 2 (Section 5): an error-bound condition relating ||F(x)|| to the horizon subdifferential of g holds on the relevant compact set.
Used in Theorem 5.1 to convert stationarity of the penalty problem into a KKT point of the constrained problem.
domain assumption Mordukhovich subdifferential calculus: exact sum rule ∂(f + h∘F + g) = ∇f + ∇F^T ∂h(F) + Σ ∂g_i and the blockwise product structure of the subdifferential are valid; qualification conditions are not stated.
Used implicitly to define dist(0,∂φ) and to pass from block distances to full distance in Proposition 3.1 and Theorem 3.1. The paper does not discuss the qualification conditions needed for these rules.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Monotone and nonmonotone linearized block coordinate descent methods for nonsmooth composite optimization problems." pith.science (2026). https://pith.science/paper/3GAC2527

@misc{pith2026250612397,
  author       = {Pith},
  title        = {Pith review of: Monotone and nonmonotone linearized block coordinate descent methods for nonsmooth composite optimization problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3GAC2527}},
  note         = {Machine review of arXiv:2506.12397}
}

read the original abstract

In this paper, we introduce both monotone and nonmonotone variants of LiBCoD, a \textbf{Li}nearized \textbf{B}lock \textbf{Co}ordinate \textbf{D}escent method for solving composite optimization problems. At each iteration, a random block is selected, and the smooth components of the objective are linearized along the chosen block in a Gauss-Newton approach. For the monotone variant, we establish a global sublinear convergence rate to a stationary point under the assumption of bounded iterates. For the nonmonotone variant, we derive a global sublinear convergence rate without requiring global Lipschitz continuity or bounded iterates. Preliminary numerical experiments highlight the promising performance of the proposed approach.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 35 canonical work pages

[5]

L. E. Bourkhissi and I. Necoara, Complexity of linearized quadratic penalty for optimiza- tion with nonlinear equality constraints, Journal of Global Optimization (2024)

work page 2024
[21]

Marumo, T

N. Marumo, T. Okuno, and A. Takeda, Accelerated-gradient-based generalized Levenberg– Marquardt method with oracle complexity bound and local quadratic convergence, Mathematical Programming (2024), 1–52

work page 2024
[1]

Beck and M

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM journal on imaging sciences 2 (2009), 183–202

work page 2009
[2]

E. G. Birgin and J. M. Mart ´ ınez, Block coordinate descent for smooth nonconvex con- strained minimization, Computational Optimization and Applications 83 (2022), 1–27

work page 2022
[3]

Bodard, K

A. Bodard, K. Oikonomidis, E. Laude, and P. Patrinos, The inexact power aug- mented Lagrangian method for constrained nonconvex optimization, arXiv preprint arXiv:2410.20153 (2024)

arXiv 2024
[4]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning, SIAM review 60 (2018), 223–311

work page 2018
[6]

L. E. Bourkhissi, I. Necoara, P. Patrinos, and Q. Tran-Dinh, Complexity of Linearized Perturbed Augmented Lagrangian Methods for Nonsmooth Nonconvex Optimization with Nonlinear Equality Constraints, arXiv preprint arXiv:2503.01056 (2025)

work page Pith review arXiv 2025
[7]

Cartis, J

C. Cartis, J. Fowkes, and Z. Shao, A randomised subspace Gauss-Newton method for nonlinear least-squares, arXiv preprint arXiv:2211.05727 (2022)

arXiv 2022

Show all 39 references

[8]

Cartis, N

C. Cartis, N. I. Gould, and P. L. Toint, On the evaluation complexity of composite func- tion minimization with applications to nonconvex nonlinear programming, SIAM Journal on Optimization 21 (2011), 1721–1739

2011
[9]

C. C. Chang and C. J. Lin, LIBSVM: A library for support vector machines, ACM Transactions on Intelligent Systems and Technology (TIST) 2 (2011), 1–27

2011
[10]

Clason and T

C. Clason and T. Valkonen, Introduction to Nonsmooth Analysis and Optimization, 2024, arXiv:2001.00216. textbook, submitted

2024 arXiv
[11]

De Marchi, Proximal gradient methods beyond monotony, Journal of Nonsmooth Analysis and Optimization 4 (2023)

A. De Marchi, Proximal gradient methods beyond monotony, Journal of Nonsmooth Analysis and Optimization 4 (2023)

2023
[12]

Deng and C

Q. Deng and C. Lan, Efficiency of coordinate descent methods for structured nonconvex optimization, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases , 2020, 74–89. 26 Yassine Nabou ∗ et al

2020
[13]

J. C. Duchi and F. Ruan, Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval, Information and Inference: A Journal of the IMA 8 (2019), 471–529

2019
[14]

Dutter and P

R. Dutter and P. J. Huber, Numerical methods for the nonlinear robust regression prob- lem, Journal of Statistical Computation and Simulation 13 (1981), 79–113

1981
[15]

J. A. Fessler, Optimization methods for magnetic resonance image reconstruction: Key models and optimization algorithms, IEEE signal processing magazine 37 (2020), 33–40

2020
[16]

W. N. Goetzmann, S. J. Brown, M. J. Gruber, and E. J. Elton, Modern portfolio theory and investment analysis, John Wiley & Sons 237 (2014)

2014
[17]

Jauhiainen, P

J. Jauhiainen, P. Kuusela, A. Sepp¨ anen, and T. Valkonen, Relaxed Gauss–Newton meth- ods with applications to electrical impedance tomography, SIAM Journal on Imaging Sciences 13 (2020), 1415–1445, doi:10.1137/20m1321711, arXiv:2002.08044

2020 arXiv
[18]

Kanzow and L

C. Kanzow and L. Lehmann, Convergence of Nonmonotone Proximal Gradient Methods under the Kurdyka-Lojasiewicz Property without a Global Lipschitz Assumption, arXiv preprint arXiv:2411.12376 (2024)

2024 arXiv
[19]

Kanzow and P

C. Kanzow and P. Mehlitz, Convergence properties of monotone and nonmonotone proximal gradient methods revisited, Journal of Optimization Theory and Applications 195 (2022), 624–646

2022
[20]

Maillard, T

S. Maillard, T. Roncalli, and J. Te ¨ ıletche, The properties of equally weighted risk contri- bution portfolios, Journal of Portfolio Management 36 (2010), 60

2010
[22]

Nabou and I

Y. Nabou and I. Necoara, Regularized higher-order Taylor approximation methods for nonlinear least-squares, arXiv preprint arXiv:2503.02370 (2025)

2025 arXiv
[23]

Nesterov, Modified Gauss–Newton scheme with worst case guarantees for global performance, Optimisation methods and software 22 (2007), 469–483

Y. Nesterov, Modified Gauss–Newton scheme with worst case guarantees for global performance, Optimisation methods and software 22 (2007), 469–483

2007
[24]

Nesterov, Efficiency of coordinate descent methods on huge-scale optimization prob- lems, SIAM Journal on Optimization 22 (2012), 341–362

Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization prob- lems, SIAM Journal on Optimization 22 (2012), 341–362

2012
[25]

Nesterov, Gradient methods for minimizing composite functions, Mathematical pro- gramming 140 (2013), 125–161

Y. Nesterov, Gradient methods for minimizing composite functions, Mathematical pro- gramming 140 (2013), 125–161

2013
[26]

Nesterov, Lectures on convex optimization , volume 137, Springer, 2018

Y. Nesterov, Lectures on convex optimization , volume 137, Springer, 2018

2018
[27]

Nocedal and S

J. Nocedal and S. J. Wright, Numerical optimization, Springer, 1999

1999
[28]

Patrascu and I

A. Patrascu and I. Necoara, Efficient random coordinate descent algorithms for large- scale structured nonconvex optimization, Journal of Global Optimization 61 (2015), 19–46

2015
[29]

J. B. Rawlings, D. Q. Mayne, and M. Diehl,Model predictive control: theory, computation, and design , volume 2, Nob Hill Publishing Madison, WI, 2017

2017
[30]

Richt´ arik and M

P. Richt´ arik and M. Tak´ aˇ c, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Mathematical Programming 144 (2014), 1–38

2014
[31]

R. T. Rockafellar and R. J. B. Wets, Variational analysis, volume 317, Springer Science & Business Media, 2009

2009
[32]

Roosta-Khorasani, K

F. Roosta-Khorasani, K. Van Den Doel, and U. Ascher, Stochastic algorithms for in- verse problems involving PDEs and many measurements, SIAM Journal on Scientific Computing 36 (2014), S3–S22

2014
[33]

M. F. Sahin, A. Alacaoglu, F. Latorre, V. Cevher, et al., An inexact augmented La- grangian framework for nonconvex optimization with nonlinear constraints, Advances in Neural Information Processing Systems 32 (2019)

2019
[34]

Salzo and S

S. Salzo and S. Villa, Convergence analysis of a proximal Gauss-Newton method, Com- putational Optimization and Applications 53 (2012), 557–589

2012
[35]

Tepper, A

M. Tepper, A. M. Sengupta, and D. Chklovskii, Clustering is semidefinitely not that hard: Nonnegative SDP for manifold disentangling, Journal of Machine Learning Research 19 (2018), 1–30

2018
[36]

Tran-Dinh, N

Q. Tran-Dinh, N. Pham, and L. Nguyen, Stochastic gauss-newton algorithms for non- convex compositional optimization, in International Conference on Machine Learning , 2020, 9572–9582

2020
[37]

S. J. Wright, Coordinate descent algorithms, Mathematical programming 151 (2015), 3–34. Monotone and nonmonotone linearized block coordinate descent method 27

2015
[38]

Xie and S

Y. Xie and S. J. Wright, Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints, Journal of Scientific Computing 86 (2021), 1–30

2021
[39]

L. Zhao, M. Mammadov, and J. Yearwood, From convex to nonconvex: a loss function analysis for binary classification, in 2010 IEEE international conference on data mining workshops, 2010, 1281–1288

2010

Pith tools

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

[1] [5]

L. E. Bourkhissi and I. Necoara, Complexity of linearized quadratic penalty for optimiza- tion with nonlinear equality constraints, Journal of Global Optimization (2024)

work page 2024

[2] [21]

Marumo, T

N. Marumo, T. Okuno, and A. Takeda, Accelerated-gradient-based generalized Levenberg– Marquardt method with oracle complexity bound and local quadratic convergence, Mathematical Programming (2024), 1–52

work page 2024

[3] [1]

Beck and M

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM journal on imaging sciences 2 (2009), 183–202

work page 2009

[4] [2]

E. G. Birgin and J. M. Mart ´ ınez, Block coordinate descent for smooth nonconvex con- strained minimization, Computational Optimization and Applications 83 (2022), 1–27

work page 2022

[5] [3]

Bodard, K

A. Bodard, K. Oikonomidis, E. Laude, and P. Patrinos, The inexact power aug- mented Lagrangian method for constrained nonconvex optimization, arXiv preprint arXiv:2410.20153 (2024)

arXiv 2024

[6] [4]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning, SIAM review 60 (2018), 223–311

work page 2018

[7] [6]

L. E. Bourkhissi, I. Necoara, P. Patrinos, and Q. Tran-Dinh, Complexity of Linearized Perturbed Augmented Lagrangian Methods for Nonsmooth Nonconvex Optimization with Nonlinear Equality Constraints, arXiv preprint arXiv:2503.01056 (2025)

work page Pith review arXiv 2025

[8] [7]

Cartis, J

C. Cartis, J. Fowkes, and Z. Shao, A randomised subspace Gauss-Newton method for nonlinear least-squares, arXiv preprint arXiv:2211.05727 (2022)

arXiv 2022