Pith. sign in

REVIEW 3 major objections 4 minor 46 references

On the Convergence and Complexity of Proximal Gradient and Accelerated Proximal Gradient Methods under Adaptive Gradient Estimation

T0 review · 3 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 Adaptively controlled gradient accuracy preserves optimal first-order iteration counts, even when gradients used are biased, and also yields optimal sample counts when unbiased.

desk verdict Solid adaptive-sampling proximal-gradient theory with a real APG extension, but the O(1/epsilon^1.5) convex stochastic bound is proven for a mixed stopping criterion and the sample-size rule is an oracle condition. read the letter →

arxiv 2507.14479 v1 pith:63IMGN6K submitted 2025-07-19 math.OC

Raghu Bollapragada , Shagun Gupta This is my paper · ORCID
classification math.OC MSC 90C2590C1565K0590C26
keywords compositeoptimizationproximalgradientmethodacceleratedadaptivesamplingbiasedestimatesstochasticcomplexitynormconditionconvex
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

This paper attempts to prove that the classical iteration guarantees of proximal gradient and accelerated proximal gradient methods survive when the gradient of the smooth part is replaced by an estimate whose accuracy is adaptively tightened as the iterates approach a solution. The accuracy rule (Condition 2.1) ties the gradient error to the norm of a reduced gradient, the natural stationarity measure of the proximal step, and allows the estimate to be biased. Under that rule the paper derives optimal iteration counts for first-order methods in nonconvex, convex, and strongly convex problems: $O(1/\epsilon)$ for the unaccelerated method in all three settings, $O(1/\sqrt{\epsilon})$ for the accelerated method in the convex setting, and $O(\kappa \log(1/\epsilon))$ and $O(\sqrt{\kappa}\log(1/\epsilon))$ for the unaccelerated and accelerated methods in the strongly convex setting. When the estimate is an unbiased sample average, the same analysis is claimed to yield optimal complexity in stochastic gradient evaluations as well, including $O(1/\epsilon^2)$, $O(1/\epsilon^{3/2})$, $O(\kappa/\epsilon)$, and $O(\sqrt{\kappa}/\epsilon)$ for the expectation problem, with the theorems using a mixed function-value and reduced-gradient stopping criterion. A reader should care because the result says that cheap, coarse gradient estimates early on can be refined automatically without sacrificing the rate of the underlying deterministic method, and that this remains true when bias cannot be removed.

What carries the argument

The mechanism is an adaptive norm condition on the gradient-estimation error, measured against the reduced gradient $R_{\alpha_k}(y_k)$ of the proximal substep. The reduced gradient is the composite-problem analogue of the gradient: its zero coincides with stationarity of $\phi$, and the proximal contraction property gives $\|R_{\alpha_k}(y_k)-R^{\mathrm{true}}_{\alpha_k}(y_k)\|\le\|g_k-\nabla f(y_k)\|$, so bounding the estimation error by $\|R_{\alpha_k}(y_k)\|$ controls the error in the stationarity measure itself. This condition converts a biased gradient estimate into a controlled perturbation with tunable tolerances $\eta_k,\delta_k$, which the descent lemmas absorb into telescoping sums or Lyapunov recursions; the tolerances are then shrunk with $k$ at rates chosen to preserve the deterministic iteration count. In the unbiased case the same condition becomes a sample-size rule: the number of samples in the stochastic average is set so that the conditional variance falls below the current tolerance, which yields the stochastic-gradient evaluation counts.

What would settle it

Run Algorithm 2.1 with the practical sampled-estimate rule for $|S_k|$ on a strongly convex quadratic whose exact solution is known, record at each iteration whether the true conditional variance actually satisfies Condition 2.1, and compare the total samples used against $O(\kappa/\epsilon)$ as the target $\epsilon$ tends to $10^{-8}$; a positive fraction of iterations where the condition fails, or empirical query counts growing faster than the stated rate, would show that the implemented rule does not inherit the optimal stochastic-gradient complexity.

Watch

Extended reading notes

Core claim

The central claim is that Algorithm 2.1—a proximal gradient update from a point $y_k$ using an approximate gradient $g_k$, with either no acceleration (Option I) or momentum acceleration (Option II)—keeps the deterministic first-order rate as long as the estimation error obeys the norm condition $\|g_k - \nabla f(y_k)\| \le (\eta_k/2)\|R_{\alpha_k}(y_k)\| + \iota_0\delta_k$ in the finite-sum case, and the analogous conditional-moment bound in the expectation case, where $R_{\alpha_k}(y_k)=(y_k-x_{k+1})/\alpha_k$ is the reduced gradient of the proximal step. The paper proves that biased estimates satisfying this condition give $\min_{k<K}\|R^{\mathrm{true}}_{\alpha}(x_k)\|^2=O(1/K)$ for nonconvex objectives, $\min_{k<K}E[\phi(x_k)-\phi^*]=O(1/K)$ for convex objectives under the unaccelerated option and $O(1/K^2)$ under acceleration, and linear rates for strongly convex objectives. With unbiased sample-average gradients, the analysis further bounds the total sample size, producing optimal stochastic-gradient complexities for the expectation problem: $O(\epsilon^{-2})$ and $O(\epsilon^{-3/2})$ in the convex case and $O(\kappa\epsilon^{-1})$ and $O(\sqrt{\kappa}\,\epsilon^{-1})$ in the strongly convex case, under the mixed stopping criterion stated in the theorems. These are the iteration counts a deterministic first-order method would achieve with exact gradients, so the message is that adaptive estimation does not degrade the rate.

Load-bearing premise

The rate proofs for unbiased sampling assume that at each iteration the algorithm can choose its sample size from the norm of the expected reduced gradient $\|E_k[R_{\alpha_k}(y_k)]\|$ before the next point is computed; a running solver does not know this expectation, and the implementation uses sampled estimates of it, so the proven query counts apply to the idealized rule rather than directly to the implemented one.

Editorial extensions

If this is right

  • A solver can start with coarse, cheap gradient estimates and automatically tighten them near the solution; if Condition 2.1 holds, the number of proximal steps to reach $\epsilon$ remains $O(1/\epsilon)$ for the unaccelerated method and $O(1/\sqrt{\epsilon})$ for the accelerated convex method, and $O(\kappa\log(1/\epsilon))$ or $O(\sqrt{\kappa}\log(1/\epsilon))$ for strongly convex problems, uncha
  • Biased estimates arising from non-IID data or surrogate models are covered by the iteration-complexity results, so bias does not have to be eliminated to keep the standard rate.
  • For expectation problems with unbiased stochastic gradients, the combined bounds let the algorithm also spend an optimal number of stochastic gradient evaluations: $O(\epsilon^{-2})$ for the unaccelerated and $O(\epsilon^{-3/2})$ for the accelerated convex method, and $O(\kappa/\epsilon)$ and $O(\sqrt{\kappa}/\epsilon)$ in the strongly convex case.
  • In the nonconvex case acceleration is not used; the paper proves the proximal gradient option only, with $O(1/\epsilon)$ iterations and $O(\epsilon^{-2})$ stochastic gradients, matching the known baseline for stochastic first-order methods.
  • The finite-sum stochastic-gradient complexity is asserted to follow by the same sample-size argument used for the expectation problem rather than proved in full, so the explicit query counts in the paper are for expectation problems.

Reading between the lines

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

  • The paper leaves implicit whether Condition 2.1 can be certified when only sampled estimates of $\|E_k[R_{\alpha_k}(y_k)]\|$ are available; proving a high-probability certification would transfer the optimal query counts to the practical sampled-rule implementation.
  • The mixed stopping criterion suggests an implementable early-exit rule that checks whichever residual, the expected function gap or the reduced-gradient norm, is cheaper to estimate; the optimal rates are proven for this disjunction rather than for function value alone.
  • A natural extension is to apply the same error-versus-reduced-gradient control to other proximal templates, such as primal-dual or proximal Newton methods, wherever a contraction inequality analogous to $\|R_\alpha-R^{\mathrm{true}}_\alpha\|\le\|g-\nabla f\|$ holds.
  • Tracking the constants in the query bounds would turn the asymptotic statements into explicit batch-size schedules, which the paper leaves as order-of-magnitude results.
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

3 major / 4 minor

Summary. The paper proposes proximal gradient and accelerated proximal gradient methods for composite optimization in which the smooth component is a finite sum or an expectation, and the gradient is replaced by an adaptively controlled, possibly biased estimate. The accuracy of the estimate is governed by a norm-type condition (Condition 2.1) adapted from earlier adaptive-sampling work. The authors prove iteration complexity under this condition for nonconvex, convex, and strongly convex objectives, claiming the optimal first-order iteration counts; for unbiased estimates in the expectation case, they also derive stochastic-gradient-evaluation complexity. A numerical section reports results on a strongly convex quadratic and two logistic-regression problems. The central claims are the optimal iteration complexity with biased estimates and simultaneous optimal iteration and stochastic-gradient complexity with unbiased estimates.

Significance. If the main claims are fully established, the paper is a useful extension of adaptive gradient-estimation techniques to composite and accelerated settings, and it covers biased estimators, which are important in several applications. The per-theorem algebra appears internally consistent under Condition 2.1, and the proofs of Theorems 3.8, 3.15, and 3.17 are detailed and use standard descent lemmas in a careful way. However, two load-bearing issues substantially weaken the current version: the sample-size rule (2.6) requires knowledge of a conditional expectation that is unavailable to an implementable algorithm, and the abstract/Table 1 state stochastic-gradient complexity rates for the convex accelerated case that are not what the theorems prove for the pure function-value criterion. These issues affect the central query-complexity claims rather than merely the presentation, so the paper needs revision before the results can be accepted in their stated form.

major comments (3)
  1. [Section 2, Lemma 2.2 and Eq. (2.6)] The prescribed sample size in (2.6) depends on ||E_k[R_{\alpha_k}(y_k)]|| = ||E_k[(y_k - prox_{\alpha_k,h}(y_k - \alpha_k g_k))/\alpha_k]||. Since g_k is a sample average over the not-yet-drawn set S_k, this expectation is not G_k-measurable and cannot be evaluated at Line 2 of Algorithm 2.1 before S_k is chosen; in the composite case with nonlinear h it is not simply ||\nabla f(y_k)||. Thus Condition 2.1 is an oracle condition rather than a certified implementable rule. Section 4 says the Adaptive strategies use 'sampled estimates as described in [43]', but no theorem in the paper shows that this empirical rule satisfies Condition 2.1 or keeps the sample count within a constant factor of (2.6). Consequently the stochastic-gradient complexity bounds of Theorems 3.4, 3.10, and 3.17 are not established for the algorithm as actually run. The paper needs either an implementable sample-size certification with matching bounds, or a clear statement that the query-count claims are conditional on an oracle that knows E_k[R_{\alpha_k}(y_k)].
  2. [Abstract, Table 1, and Theorem 3.10] The convex accelerated row of Table 1 reports O(\epsilon^{-1.5}) stochastic-gradient complexity, and the abstract claims simultaneous optimal iterative and stochastic-gradient complexity, but Theorem 3.10 proves this rate only for the mixed stopping criterion min{E[\phi(x_k)-\phi^*], ||R^{true}_{\alpha_k}(y_k)||^2} <= \epsilon. Under the pure function-value criterion E[\phi(x_k)-\phi^*] <= \epsilon used in Table 1's definition for convex objectives, Corollary 3.11 gives O(\epsilon^{-(2+\nu)}), or O(\epsilon^{-2}) with vanishing \tilde{\delta}_k, not O(\epsilon^{-1.5}). The abstract and Table 1 should either state the mixed stopping criterion explicitly or the authors should prove the stronger function-value rate.
  3. [Section 4 numerical validation] The numerical experiments validate convergence behavior, but they do not test the stochastic-gradient complexity rates claimed in Table 1. The 'Adaptive' and 'Adaptive-biased' strategies use sampled estimates of the norm condition as described in [43], yet the paper provides no guarantee that the resulting sample sizes match (2.6) or that Condition 2.1 holds. To close the gap identified in the first major comment, the experiments should be accompanied by an implementable rule with a theoretical guarantee, or the theoretical claims should be explicitly restricted to the oracle setting in which (2.6) can be evaluated.
minor comments (4)
  1. [Section 2, Eq. (2.1)] The displayed inequality f(a) <= f(b) + \nabla f(a)^T(b-a) + L/2 ||b-a||^2 appears to have the gradient evaluated at the wrong point; the standard L-smooth inequality is f(a) <= f(b) + \nabla f(b)^T(a-b) + L/2 ||a-b||^2. The subsequent use in Lemma 3.1 is correct, so this seems to be a typographical error in the displayed statement.
  2. [Theorem 3.8, part 1(b)] Part 1(b) is stated for the 'expectation problem (1.3)', but the text and proof treat the expectation problem (1.4); the reference should be corrected.
  3. [Notation in Section 1.4] The notation |\cdot| is used for both the Euclidean norm and the cardinality of a set, and the sentence defining it is somewhat confusingly worded. Splitting these into two symbols or explicitly writing 'cardinality' in Lemma 2.2 would improve readability.
  4. [Theorem 3.10, Corollary 3.11] The rates O(\epsilon^{-(2+\nu)}) in Corollary 3.11 are stated as if they are improvements, but for any fixed \nu > 0 they are worse than the O(\epsilon^{-2}) rate in Theorem 3.10; the relationship between these results and the optimal O(\epsilon^{-3/2}) rate should be clarified.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the optimal-complexity claims are derived from an explicit norm condition and external lower bounds, with only a non-implementable oracle sample-size rule as a gap.

full rationale

The paper's iteration-complexity theorems (Theorems 3.3, 3.8, 3.15) are proved directly from Assumptions 2.1/3.1/3.2 and Condition 2.1 using standard descent arguments, and the claimed optimal rates are matched against external lower bounds such as [9,31]. The stochastic-gradient-evaluation bounds in Theorems 3.4, 3.10, and 3.17 are obtained by summing the sample sizes from Lemma 2.2; Equation (2.6) is a sufficient condition on |S_k|, not an equivalent restatement of the target complexity, and the proofs do not substitute the desired rate into the assumption. Condition 2.1 is adapted from the authors' prior work [43], but it is used as an explicit assumption whose consequences are derived in Lemmas 3.2 and B.1, so the self-citation is not load-bearing. The main caveat is implementability rather than circularity: the sample-size rule (2.6) requires knowing E_k[R_alpha(y_k)] before the batch S_k is drawn, and Section 4 replaces this with sampled estimates as described in [43]; this creates a gap between the analyzed and the implemented algorithms, but it is not a case of a prediction being equivalent to its inputs by construction.

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

No quantities are fitted to experimental data in the theory; all listed parameters are user-chosen to satisfy the stated inequalities. The main model assumptions are smoothness, bounded stochastic variance, and an oracle that can certify Condition 2.1. No new physical or mathematical entities are introduced.

free parameters (5)
  • eta_k and eta_tilde_k = user-chosen in [0,1), e.g. 0.1 in experiments; must satisfy regime-specific bounds such as eta < 1/2 for convex PGM
    Controls how tightly the gradient error must track the reduced gradient in Condition 2.1; appears in every complexity bound.
  • iota_0 and iota_tilde_0 = user-chosen, e.g. 0 in experiments; restricted to intervals like (0, sqrt((1-eta)/2))
    Scales the absolute error term delta_k in Condition 2.1; chosen by hand to satisfy step-size inequalities.
  • delta_k and delta_tilde_k = sequences such as 1/(k+1)^(1+nu) or delta^k with delta in [0,1)
    Controls the decaying absolute error allowed in the gradient estimate; the exact form is chosen to satisfy summability conditions in the theorems.
  • step size alpha_k = tuned over {10^-i} in experiments; theoretically restricted by L, e.g. alpha <= (1-eta)/(2L)
    Standard proximal gradient step-size parameter; its upper bound is essential for descent lemmas.
  • acceleration sequence beta_k = Option I: beta=0; Option II: Nesterov sequence k-1 over k+2 or sqrt(kappa)-1 over sqrt(kappa)+1
    User-defined switch between proximal gradient and accelerated proximal gradient behavior.
assumptions (6)
  • domain assumption Assumption 2.1: f is L-smooth and h is closed, convex, proper.
    Underpins every descent lemma and step-size condition; standard in composite optimization.
  • domain assumption Assumption 2.2: bounded stochastic gradient variance or bounded component gradient deviation.
    Needed to convert the sample-size rule into stochastic-gradient complexity; can fail for heavy-tailed noise.
  • domain assumption Assumptions 3.1 and 3.2: f is convex or mu-strongly convex in the corresponding sections.
    Define the convex and strongly convex regimes in Sections 3.2 and 3.3.
  • ad hoc to paper Condition 2.1 is satisfiable by an implementable oracle for gradient estimates.
    The entire analysis assumes the gradient estimator can be certified against a norm condition involving the reduced gradient; Lemma 2.2 shows one sufficient construction but uses an expectation that is not directly computable.
  • domain assumption The proximal operator is evaluated exactly at every step.
    Algorithm 2.1 assumes an efficient exact proximal oracle for h; the paper explicitly excludes inexact proximal updates.
  • standard math Technical recursion and infinite-product bounds in Lemmas A.1 through A.4.
    The paper relies on these unverified but standard analysis tools to establish boundedness and linear-rate conclusions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Convergence and Complexity of Proximal Gradient and Accelerated Proximal Gradient Methods under Adaptive Gradient Estimation." pith.science (2026). https://pith.science/paper/63IMGN6K

@misc{pith2026250714479,
  author       = {Pith},
  title        = {Pith review of: On the Convergence and Complexity of Proximal Gradient and Accelerated Proximal Gradient Methods under Adaptive Gradient Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/63IMGN6K}},
  note         = {Machine review of arXiv:2507.14479}
}
read the original abstract

In this paper, we propose a proximal gradient method and an accelerated proximal gradient method for solving composite optimization problems, where the objective function is the sum of a smooth and a convex, possibly nonsmooth, function. We consider settings where the smooth component is either a finite-sum function or an expectation of a stochastic function, making it computationally expensive or impractical to evaluate its gradient. To address this, we utilize gradient estimates within the proximal gradient framework. Our methods dynamically adjust the accuracy of these estimates, increasing it as the iterates approach a solution, thereby enabling high-precision solutions with minimal computational cost. We analyze the methods when the smooth component is nonconvex, convex, or strongly convex, using a biased gradient estimate. In all cases, the methods achieve the optimal iteration complexity for first-order methods. When the gradient estimate is unbiased, we further refine the analysis to show that the methods simultaneously achieve optimal iteration complexity and optimal complexity in terms of the number of stochastic gradient evaluations. Finally, we validate our theoretical results through numerical experiments.

Figures

Figures reproduced from arXiv: 2507.14479 by the authors.

Figure 1
Figure 1. Optimality Gap (ϕ(xk) − ϕ ∗ ) with respect to the number of proximal operator evalua￾tions and the number of stochastic gradient evaluations of Algorithm 2.1, evaluated under Option I (Proximal Gradient) and Option II (Accelerated Proximal Gradient), using “Deterministic”, “Stochastic”, “Geometric”, “Adaptive” and “Adaptive-biased” sampling strategies on the strongly convex quadratic problem (4.1). 5 Final Remarks I… view at source ↗
Figure 2
Figure 2. Optimality Gap (ϕ(xk) − ϕ ∗ ) with respect to the number of proximal operator evalu￾ations and the number of stochastic gradient evaluations of Algorithm 2.1, evaluated under Op￾tion I (Proximal Gradient) and Option II (Accelerated Proximal Gradient), using “Determin￾istic”, “Stochastic”, “Geometric”, “Adaptive” and “Adaptive-biased” sampling strategies for l1- regularized binary classification logistic regression (… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 40 canonical work pages

  1. [43]

    Constrained and com- posite optimization via adaptive sampling methods

    Yuchen Xie, Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Constrained and com- posite optimization via adaptive sampling methods. IMA Journal of Numerical Analysis , 44(2):680–709, 2024

    work page 2024

  2. [1]

    Lower bounds for non-convex stochastic optimization

    Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1):165–214, 2023

    work page 2023

  3. [2]

    Fixed-point algorithms for inverse problems in science and engineering , volume 49

    Heinz H Bauschke, Regina S Burachik, Patrick L Combettes, Veit Elser, D Russell Luke, and Henry Wolkowicz. Fixed-point algorithms for inverse problems in science and engineering , volume 49. Springer Science & Business Media, 2011

    work page 2011

  4. [3]

    A fast iterative shrinkage-thresholding algorithm for linear inverse problems

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

    work page 2009

  5. [4]

    Adaptive sampling strategies for risk-averse stochastic optimization with constraints

    Florian Beiser, Brendan Keith, Simon Urbainczyk, and Barbara Wohlmuth. Adaptive sampling strategies for risk-averse stochastic optimization with constraints. IMA Journal of Numerical Analysis, 43(6):3729–3765, 2023

    work page 2023

  6. [5]

    Convex optimization algorithms

    Dimitri Bertsekas. Convex optimization algorithms . Athena Scientific, 2015

    work page 2015

  7. [6]

    Adaptive sampling strategies for stochastic optimization

    Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Adaptive sampling strategies for stochastic optimization. SIAM Journal on Optimization , 28(4):3312–3343, 2018

    work page 2018

  8. [7]

    Inertial variable metric tech- niques for the inexact forward–backward algorithm

    Silvia Bonettini, Simone Rebegoldi, and Valeria Ruggiero. Inertial variable metric tech- niques for the inexact forward–backward algorithm. SIAM Journal on Scientific Computing , 40(5):A3180–A3210, 2018

    work page 2018

Show all 46 references
  1. [8]

    Sample size selection in optimization methods for machine learning

    Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning. Mathematical programming, 134(1):127–155, 2012

    2012

  2. [9]

    Lower bounds for finding stationary points i

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71–120, 2020

    2020

  3. [10]

    Lower bounds for finding stationary points ii: first-order methods

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185(1):315–355, 2021

    2021

  4. [11]

    On the global convergence of trust region algorithms using inexact gradient information

    Richard G Carter. On the global convergence of trust region algorithms using inexact gradient information. SIAM Journal on Numerical Analysis , 28(1):251–265, 1991

    1991

  5. [12]

    LIBSVM: A library for support vector machines

    Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology , 2:27:1–27:27, 2011. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm

    2011

  6. [13]

    Graph-structured multi-task regression and an efficient optimization method for general fused lasso

    Xi Chen, Seyoung Kim, Qihang Lin, Jaime G Carbonell, and Eric P Xing. Graph-structured multi-task regression and an efficient optimization method for general fused lasso. arXiv preprint arXiv:1005.3579, 2010

    2010 arXiv

  7. [14]

    Composite objective mirror descent

    John C Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In Colt, volume 10, pages 14–26. Citeseer, 2010

    2010

  8. [15]

    Total variation projection with first order schemes

    Jalal M Fadili and Gabriel Peyr´ e. Total variation projection with first order schemes. IEEE Transactions on Image Processing, 20(3):657–669, 2010

    2010

  9. [16]

    Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework

    Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization , 22(4):1469–1492, 2012

    2012

  10. [17]

    Accelerated gradient methods for nonconvex nonlinear and stochastic programming

    Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59–99, 2016

    2016

  11. [18]

    Deblurring images: matrices, spectra, and filtering

    Per Christian Hansen, James G Nagy, and Dianne P O’leary. Deblurring images: matrices, spectra, and filtering. SIAM, 2006

    2006

  12. [19]

    Accelerated gradient methods for stochastic optimization and online learning

    Chonghai Hu, Weike Pan, and James Kwok. Accelerated gradient methods for stochastic optimization and online learning. Advances in Neural Information Processing Systems , 22, 2009. 34

    2009

  13. [20]

    Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization

    Sashank J Reddi, Suvrit Sra, Barnabas Poczos, and Alexander J Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29, 2016

    2016

  14. [21]

    Smoothed variable sample-size accelerated proximal methods for nonsmooth stochastic convex programs

    Afrooz Jalilzadeh, Uday Shanbhag, Jose Blanchet, and Peter W Glynn. Smoothed variable sample-size accelerated proximal methods for nonsmooth stochastic convex programs. Stochas- tic Systems , 12(4):373–410, 2022

    2022

  15. [22]

    Proximal meth- ods for sparse hierarchical dictionary learning

    Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, and Francis R Bach. Proximal meth- ods for sparse hierarchical dictionary learning. In ICML, volume 1, page 2. Citeseer, 2010

    2010

  16. [23]

    A generic acceleration framework for stochastic com- posite optimization

    Andrei Kulunchakov and Julien Mairal. A generic acceleration framework for stochastic com- posite optimization. Advances in Neural Information Processing Systems , 32, 2019

    2019

  17. [24]

    An optimal method for stochastic composite optimization

    Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1):365–397, 2012

    2012

  18. [25]

    On the conver- gence of fedavg on non-iid data

    Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the conver- gence of fedavg on non-iid data. arXiv preprint arXiv:1907.02189 , 2019

    1907 arXiv

  19. [26]

    A simple proximal stochastic gradient method for nonsmooth nonconvex optimization

    Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. Advances in neural information processing systems , 31, 2018

    2018

  20. [27]

    Zeroth-order gradient and quasi-newton methods for nonsmooth nonconvex stochastic optimization

    Luke Marrinan, Uday V Shanbhag, and Farzad Yousefian. Zeroth-order gradient and quasi-newton methods for nonsmooth nonconvex stochastic optimization. arXiv preprint arXiv:2401.08665, 2023

    2023

  21. [28]

    Network newton distributed optimization methods

    Aryan Mokhtari, Qing Ling, and Alejandro Ribeiro. Network newton distributed optimization methods. IEEE Transactions on Signal Processing , 65(1):146–161, 2016

    2016

  22. [29]

    Gradient methods for minimizing composite functions

    Yu Nesterov. Gradient methods for minimizing composite functions. Mathematical program- ming, 140(1):125–161, 2013

    2013

  23. [30]

    A method for unconstrained convex minimization problem with the rate of convergence o (1/k2)

    Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o (1/k2). In Dokl. Akad. Nauk. SSSR , volume 269, page 543, 1983

    1983

  24. [31]

    Lectures on convex optimization , volume 137

    Yurii Nesterov et al. Lectures on convex optimization , volume 137. Springer, 2018

    2018

  25. [32]

    Stochastic ista/fista adaptive step search algorithms for convex composite optimization

    Lam M Nguyen, Katya Scheinberg, and Trang H Tran. Stochastic ista/fista adaptive step search algorithms for convex composite optimization. arXiv preprint arXiv:2402.15646 , 2024

    2024 arXiv

  26. [33]

    Fast unconstrained optimization via hessian averaging and adaptive gradient sampling methods

    Thomas O’Leary-Roseberry and Raghu Bollapragada. Fast unconstrained optimization via hessian averaging and adaptive gradient sampling methods. arXiv preprint arXiv:2408.07268 , 2024

    2024 arXiv

  27. [34]

    Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization

    Nhan H Pham, Lam M Nguyen, Dzung T Phan, and Quoc Tran-Dinh. Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 21(110):1–48, 2020

    2020

  28. [35]

    Scaled, inexact, and adaptive generalized fista for strongly convex optimization

    Simone Rebegoldi and Luca Calatroni. Scaled, inexact, and adaptive generalized fista for strongly convex optimization. SIAM Journal on Optimization , 32(3):2428–2459, 2022. 35

    2022

  29. [36]

    Fast first-order methods for composite con- vex optimization with backtracking

    Katya Scheinberg, Donald Goldfarb, and Xi Bai. Fast first-order methods for composite con- vex optimization with backtracking. Foundations of Computational Mathematics , 14:389–417, 2014

    2014

  30. [37]

    Convergence rates of inexact proximal- gradient methods for convex optimization

    Mark Schmidt, Nicolas Roux, and Francis Bach. Convergence rates of inexact proximal- gradient methods for convex optimization. Advances in neural information processing systems, 24, 2011

    2011

  31. [38]

    Practical bayesian optimization of machine learning algorithms

    Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems , 25, 2012

    2012

  32. [39]

    Convergence rates of accelerated proximal gradient algorithms under independent noise

    Tao Sun, Roberto Barrio, Hao Jiang, and Lizhi Cheng. Convergence rates of accelerated proximal gradient algorithms under independent noise. Numerical Algorithms , 81:631–654, 2019

    2019

  33. [40]

    Conditional convergence of infinite products

    William F Trench. Conditional convergence of infinite products. The American mathematical monthly, 106(7):646–651, 1999

    1999

  34. [41]

    Computational methods for sparse solution of linear inverse problems

    Joel A Tropp and Stephen J Wright. Computational methods for sparse solution of linear inverse problems. Proceedings of the IEEE, 98(6):948–958, 2010

    2010

  35. [42]

    Jingyi Wang and Cosmin G. Petra. A sequential quadratic programming algorithm for non- smooth problems with upper- c2 objective. SIAM Journal on Optimization , 33(3):2379–2405, 2023

    2023

  36. [44]

    T0 + kX i=0 (si + Ri) # ≤ ˆa

    Qinzi Zhang, Hoang Tran, and Ashok Cutkosky. Private zeroth-order nonsmooth nonconvex optimization. arXiv preprint arXiv:2406.19579 , 2024. A Technical Results In this section, we present some technical results that have been used in the paper. Lemma A.1. Given a1, a2 ∈ Rd and...

    2024 arXiv

  37. [45]

    For the finite-sum problem (1.3): 1 − ηk 2 ∥gk − ∇f (yk)∥ ≤ηk 2 Rtrue αk (yk) + ι0δk, ∀k ≥ 0

  38. [46]

    Determin- istic

    For the expectation problem (1.4): 1 − ˜η2 k 2 Ek ∥gk − ∇f (yk)∥2 ≤ ˜η2 k 2 Ek h Rtrue αk (yk) 2i + ˜ι2 0˜δ2 k, ∀k ≥ 0. Proof. For the finite-sum problem (1.3), using Condition 2.1, we get, ∥gk − ∇f (yk)∥ ≤ηk 2 Rαk (yk) − Rtrue αk (yk) + Rtrue αk (yk) + ι0δk ≤ ηk 2 Rαk (yk) − ...

Pith tools

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