Pith. sign in

REVIEW 3 major objections 6 minor 3 cited by

Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper claims that weakly convex constrained optimization with nonsmooth objective and constraints can be solved by subgradient methods at polynomial rates: $O(1/\epsilon^4)$ deterministically and $\tilde{O}(1/\epsilon^6)$…

desk verdict First provable subgradient rates for weakly convex constrained problems, with an unresolved dependence of the uniform Slater constants on ε that could weaken the central rate claim. read the letter →

arxiv 1908.01871 v3 pith:SQP2BOHG submitted 2019-08-05 math.OC

Runchao Ma , Qihang Lin , Tianbao Yang This is my paper · ORCID
classification math.OC MSC 90C2690C3090C2590C15
keywords weaklyconvexoptimizationnonsmoothconstraintssubgradientmethodproximalpointnear-stationarycomplexityguaranteefairnessstochastic
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 claims that a class of first-order subgradient methods can solve constrained optimization problems in which both the objective and the constraints are weakly convex and nonsmooth, and can do so with the first polynomial complexity guarantees for such problems. The method adds a quadratic proximal term to the objective and to every constraint, turning each step into a strongly convex subproblem that existing algorithms can solve. Provided a uniform Slater condition holds, the paper proves that a random iterate becomes a nearly stationary point within $O(1/\epsilon^2)$ main iterations, and that deterministic and stochastic oracle implementations yield total complexities $O(1/\epsilon^4)$ and $\tilde{O}(1/\epsilon^6)$, respectively. These rates matter because machine learning tasks such as fairness-constrained learning and classification with nonconvex losses are naturally of this form, and no subgradient method with such guarantees previously existed.

What carries the argument

The load-bearing object is the proximally regularized subproblem (9), in which the same quadratic term $\frac{\hat{\rho}}{2}\|y-x_t\|^2$ is added to the objective $f$ and to the constraint $g$. Because $f$ and $g$ are $\rho$-weakly convex, choosing $\hat{\rho}>\rho$ makes the subproblem $(\hat{\rho}-\rho)$-strongly convex in both the objective and the constraint, so its solution is unique and approximable by strongly convex optimization algorithms. The uniform Slater condition (Assumption 1B) supplies the critical uniform bound on the subproblem's Lagrange multiplier, $\lambda_t \le (M+\hat{\rho}D)/\sqrt{2\sigma_\epsilon(\hat{\rho}-\rho)}$, which is what keeps the descent recursion from blowing up. The deterministic oracle is a single-loop switching subgradient method that takes an objective subgradient step when the regularized constraint is $\hat{\epsilon}^2$-feasible and a constraint subgradient step otherwise, with a weighted average over feasible iterates as output; this oracle is deterministic and satisfies the required error bounds exactly.

What would settle it

Build a weakly convex constrained problem whose feasible region satisfies ordinary Slater's condition but has an $\epsilon^2$-feasible path along which $\min_{y\in X}\{g(y)+((\rho+\rho_\epsilon)/2)\|y-x\|^2\}$ approaches zero; run Algorithm 1 on this problem. If the subproblem Lagrange multipliers fail to stay bounded, or the promised $O(1/\epsilon^4)$ rate does not appear, then the uniform Slater assumption is doing essential work rather than being a technical convenience.

Watch

Extended reading notes

Core claim

The central claim is that every iteration of the inexact proximally constrained method approximately solves $\hat{x}_t = \arg\min_{y\in X}\{ f(y) + \frac{\hat{\rho}}{2}\|y-x_t\|^2 : g(y) + \frac{\hat{\rho}}{2}\|y-x_t\|^2 \le 0\}$, and that the distance $\|x_t-\hat{x}_t\|$ is a valid measure of stationarity: when it is at most $\epsilon$, the proximal solution $\hat{x}_t$ is feasible and satisfies the KKT conditions of the original problem with $O(\epsilon)$ precision. The paper proves that, under Assumption 1, $T \ge 4(f(x_0)-f_{\mathrm{lb}})/(\epsilon^2(\hat{\rho}-\rho))$ iterations suffice for $\mathbb{E}_R[\|x_R-\hat{x}_R\|^2] \le \epsilon^2$ with probability at least $1-\delta$. Combined with a deterministic switching subgradient oracle, this yields total complexity $O(1/\epsilon^4)$; combined with a stochastic subgradient oracle, it yields $\tilde{O}(1/\epsilon^6)$.

Load-bearing premise

The paper's rates depend on a uniform Slater condition: every point that is already $\epsilon^2$-feasible must be separated from the constraint boundary by a fixed margin $\sigma_\epsilon$ after regularization, which is stronger than ordinary Slater's condition and is only verified in the paper on a small example.

Editorial extensions

If this is right

  • Deterministic weakly convex nonsmooth constrained problems now have a first-order subgradient method with an explicit $O(1/\epsilon^4)$ complexity guarantee.
  • Stochastic subgradient versions inherit the same framework at $\tilde{O}(1/\epsilon^6)$, covering learning problems where constraints are only available through samples.
  • Every intermediate iterate produced by the main algorithm is approximately feasible, so feasibility is maintained along the path, not only at the final output.
  • The same proximal treatment applies when the functions are smooth and strongly convex after regularization, where existing level-set or augmented Lagrangian oracles give total complexity $O(1/\epsilon^3)$ as noted in Remark 2.

Reading between the lines

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

  • Editorial inference: the uniform Slater condition is the natural place to look for a weaker sufficient condition; if the multiplier bound can be obtained from a data-dependent quantity, the method would extend to problems where the feasible region is thin or only known approximately.
  • Editorial inference: because the deterministic and stochastic rates differ by $\epsilon^{-2}$, a variance-reduced or mini-batch stochastic oracle could plausibly close the gap, giving a stochastic rate matching the deterministic one.
  • Editorial inference: the near-feasibility of every iterate suggests an online or safety-critical setting where an infeasible proposal is costly; one could test the method on such problems and monitor constraint violations at intermediate steps.
  • Editorial inference: a concrete numerical check of Assumption 1B on larger real datasets, computing $\min_{y\in X}\{g(y)+((\rho+\rho_\epsilon)/2)\|y-x\|^2\}$ for several $\epsilon^2$-feasible points, would show whether the assumption holds beyond the paper's small example.
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 / 6 minor

Summary. The paper studies constrained optimization of the form min_{x in X} f0(x) subject to fi(x) <= 0 for i=1,...,m, where all fi are weakly convex and possibly nonsmooth, and X is compact. The authors propose an inexact proximally constrained (IPC) method (Algorithm 1) that, at each outer iteration, approximately solves a strongly convex subproblem obtained by adding a quadratic proximal term to both the objective and each constraint function. The oracle subproblem is instantiated by a deterministic switching subgradient method (Algorithm 2) and by a stochastic online subgradient method (Algorithm 3) imported from Yu, Neely, and Wei. Under Assumption 1, which includes a uniform Slater-type condition, Theorem 1 gives O(1/epsilon^2) outer iterations to reach a point whose distance to the proximal solution is at most epsilon. Theorems 2 and 3 claim total complexity O(1/epsilon^4) for the deterministic oracle and O-tilde(1/epsilon^6) for the stochastic oracle. The paper also presents experiments on fairness-constrained classification with a truncated logistic loss, comparing IPC with an exact penalty method and with the method of Yu et al.

Significance. If the complexity claims hold, the paper would provide the first polynomial subgradient-method rates for weakly convex nonsmooth objective and constraint functions, a setting where previous proximal-point analyses were restricted to unconstrained or simply constrained problems. The potential-based proof of Theorem 1 and the adaptation of the switching subgradient method are useful contributions, and the paper is honest about its relationship to the concurrent work of Boob, Deng, and Lan. The main value is therefore conditional: the rates depend on the quantitative behavior of the uniform Slater parameters sigma_epsilon and rho_epsilon, and the paper does not currently establish that these constants are bounded away from zero uniformly in epsilon. The experiments are illustrative but do not verify the key assumption on the real datasets. With a clarified and strengthened Slater assumption, the paper could be a solid contribution; as written, the headline polynomial rates are not fully established.

major comments (3)
  1. [Assumption 1B; Lemma 1; Theorems 1-3; Appendix A.3-A.4] The uniform Slater constants sigma_epsilon and rho_epsilon in Assumption 1B are allowed to depend on epsilon, but every complexity bound in the paper depends on them. Lemma 1 bounds lambda_t by (M+rho_hat D)/sqrt(2 sigma_epsilon (rho_hat-rho)); Theorem 1 defines epsilon_hat using sigma_epsilon; Theorem 2's complexity in A.3, and Theorem 3's Lambda in A.4, have sigma_epsilon and rho_epsilon in denominators. If sigma_epsilon or rho_epsilon tends to zero as epsilon tends to zero, the claimed O(1/epsilon^4), O-tilde(1/epsilon^6), and even polynomial-in-epsilon rates are not established. In addition, Lemma 1 requires rho_hat <= rho + rho_epsilon, whereas Algorithm 1 and Theorem 1 state only that rho_hat > rho; when rho_epsilon is epsilon-dependent this is a missing condition. The authors should either state explicitly that sigma_epsilon and rho_epsilon are bounded below by positive constants independent of epsilon, or provide the explicit epsilon-dependence and revise the complexity claims accordingly. The numerical section does not fill this gap, because Remark 3 only establishes Assumption 1B when c and ||a|| are small enough, while the real datasets use c between 0.08 and 0.4 with unnormalized features.
  2. [Appendix A.1, proof of Lemma 1] The proof of Lemma 1 divides by lambda_t twice: it uses zeta_hat_t / lambda_t in the strong-convexity inequality and then forms a ratio of norms to conclude the bound on lambda_t. The KKT conditions (7) permit lambda_t = 0 by complementary slackness, in which case these divisions are invalid. The desired bound is trivially true when lambda_t = 0, so the proof can be repaired by treating that case separately, but as written the argument is incomplete and this lemma is load-bearing for Theorem 1.
  3. [Appendix A.3, Eq. (16) and Algorithm 2] The proof of Theorem 2 uses M^2 + rho_hat D^2 as an upper bound on ||F'(z_k)||^2, and Algorithm 2 sets K = ceil(4(M^2 + rho_hat D^2)/((rho_hat-rho) epsilon_hat^2)). Under Assumption 1F, the valid bound is ||F'(z_k)|| <= M + rho_hat D, so the squared norm is at most (M + rho_hat D)^2, which can be substantially larger. Consequently, the specified number of iterations K may be too small, and the deterministic oracle guarantee in Theorem 2 is not proven as stated. The proof and the input of Algorithm 2 should be corrected to use (M + rho_hat D)^2 or another valid upper bound; the O(1/epsilon^4) rate would survive this correction, but the current statement is inaccurate.
minor comments (6)
  1. [Abstract and Section 1] The abstract contains a duplicated word: 'the constraint functions are are weakly convex'.
  2. [Theorem 3] In the statement of Theorem 3, the second displayed bound is written as B1(D, ... ) but should be B2(D, ... ), matching equations (22) and (27).
  3. [Algorithm 2] The output xt+1 is defined as a weighted average over the index set I, but the algorithm does not state what to return if I is empty; nonemptiness follows from the choice of K in the proof, but this should be stated explicitly.
  4. [Appendix A.2, proof of Theorem 1] The proof uses g(x_t) <= epsilon_hat^2 for every t, including t = 0, but Assumption 1E only guarantees g(x_0) <= epsilon^2 and epsilon_hat can be much smaller than epsilon; the t = 0 term needs a separate argument or an explicit absorbed constant.
  5. [Section 5] The experimental section says 'We assume rho_hat = 2 rho in our algorithm for all experiments' and then later says the best rho_hat was tuned to 10^{-2.5}; this is confusing because rho is unknown and the stated relationship is not used consistently.
  6. [Throughout] There are several typographical errors, including 'stochatsic', 'orcale', and 'anlaysis'; these should be corrected in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity rates follow from independent oracle analyses and stated assumptions, not from fitted parameters or load-bearing self-citations.

full rationale

I walked the derivation chain from Assumption 1 through Lemma 1 and Theorems 1-3. The stationarity measure in Definition 1 is the proximal residual ||x - x_hat||, a standard measure in weakly convex optimization; it is not defined in terms of the algorithm's own output and does not presuppose the theorem. Lemma 1's uniform multiplier bound is derived from Assumption 1B, and the bound is then used in Theorem 1's telescoping argument; there is no circular step in which a theorem's conclusion is assumed in its hypothesis. Algorithm 2's oracle guarantee is proved directly via a Polyak switching-subgradient argument adapted from the external analysis of [24], and Algorithm 3's guarantee is imported from the external published analysis of [53]; neither is a self-citation. The O(1/epsilon^4) and O~(1/epsilon^6) complexities are products of these independent oracle bounds. Self-citations [27], [28], and [36] appear only as motivation or related work and do not carry the central complexity claims. The uniform-Slater condition (Assumption 1B) is an input assumption, not an output fitted to data; possible epsilon-dependence of sigma_epsilon and rho_epsilon is a legitimate correctness and verifiability concern, but it is not circularity because the paper does not fit these constants and then rename the fit as a prediction. No step reduces by construction to its own inputs, so no circular step is identified.

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

No new physical or mathematical entities are introduced. The algorithm depends on strong but explicitly stated assumptions: weak convexity, uniform Slater, bounded subgradients, compactness, lower boundedness, and an initial feasible point. The only tuned constant is the proximal parameter hat_rho in experiments; the theory treats it as an input within a stated range.

free parameters (1)
  • hat_rho (proximal parameter) = 10^{-2.5} in experiments; any value in (rho, rho+rho_epsilon] allowed in theory
    Controls the strength of quadratic regularization in both objective and constraints. The theoretical rate depends on hat_rho - rho, and the experiments select hat_rho by grid search based on empirical performance (Appendix A.5).
assumptions (8)
  • domain assumption Assumption 1A: all f_i are closed and rho-weakly convex on X with nonempty subdifferentials.
    Defines the function class and underlies the strong convexity of the prox-regularized subproblems in (9).
  • domain assumption Assumption 1B: uniform Slater's condition with constants sigma_epsilon and rho_epsilon.
    Critical for the uniform bound on Lagrange multipliers in Lemma 1 and hence for the complexity result in Theorem 1. It is stronger than standard Slater and hard to verify in general.
  • domain assumption Assumption 1C: X is compact with diameter at most D.
    Used to bound norms of regularized subgradients and to control distance terms in the proofs.
  • domain assumption Assumption 1D: f is lower bounded by f_lb on X.
    Needed for the telescoping potential argument in Theorem 1.
  • domain assumption Assumption 1E: an initial epsilon^2-feasible solution x_feas is available.
    The algorithm starts from a feasible point; Remark 1 discusses a partial mitigation without a known feasible point.
  • domain assumption Assumption 1F: subgradients of all f_i are bounded by M on X.
    Provides the Lipschitz-type bounds used in Lemma 1 and in the oracle error analyses.
  • domain assumption Assumption 2 in Section 4.2: unbiased stochastic subgradients with almost-sure bounded norms.
    Required for the stochastic oracle analysis in Theorem 3 and for applying the algorithm of [53].
  • domain assumption Theorem 4 of Yu, Neely, and Wei [53] for online convex optimization with stochastic constraints.
    The stochastic oracle guarantee in Theorem 3 imports convergence rates from [53] rather than re-deriving them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints." pith.science (2026). https://pith.science/paper/SQP2BOHG

@misc{pith2026190801871,
  author       = {Pith},
  title        = {Pith review of: Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SQP2BOHG}},
  note         = {Machine review of arXiv:1908.01871}
}
read the original abstract

Optimization models with non-convex constraints arise in many tasks in machine learning, e.g., learning with fairness constraints or Neyman-Pearson classification with non-convex loss. Although many efficient methods have been developed with theoretical convergence guarantees for non-convex unconstrained problems, it remains a challenge to design provably efficient algorithms for problems with non-convex functional constraints. This paper proposes a class of subgradient methods for constrained optimization where the objective function and the constraint functions are weakly convex and nonsmooth. Our methods solve a sequence of strongly convex subproblems, where a quadratic regularization term is added to both the objective function and each constraint function. Each subproblem can be solved by various algorithms for strongly convex optimization. Under a uniform Slater's condition, we establish the computation complexities of our methods for finding a nearly stationary point.

Figures

Figures reproduced from arXiv: 1908.01871 by the authors.

Figure 1
Figure 1. Numerical Results for Problems with Fairness Cons [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Experiments Results for Problems with Fairness Co [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization

    math.OC 2019-08 conditional novelty 7.0 of 10

    An inexact proximal-point penalty algorithm finds ε-stationary points of non-convex constrained problems in O~(ε^{-5/2}) steps with convex constraints and O~(ε^{-3}) to O~(ε^{-4}) steps with non-convex constraints.

  2. Optimization under Persistent State-Dependent Bias: Gradient-based Method and Complexity Analysis

    math.OC 2026-07 reject novelty 6.0 of 10

    Residual Learning, a proposed bilevel gradient method, claims exact convergence under state-dependent analog-hardware bias with rate O~(kappa1*kappa2^4*sigma^2/(mu*K)).

  3. Stochastic optimization over expectation-formulated generalized Stiefel manifold

    math.OC 2024-12 conditional novelty 6.0 of 10

    A new sixth-order penalty function makes stochastic optimization over expectation-formulated generalized Stiefel manifolds equivalent to unconstrained optimization, enabling stochastic gradient methods with O(epsilon^...

Reference graph

Works this paper leans on

58 extracted references · 38 canonical work pages · cited by 3 Pith papers

  1. [1]

    Allen-Zhu

    Z. Allen-Zhu. Natasha: Faster non-convex stochastic op timization via strongly non-convex parameter. In Proceedings of the 34th International Conference on Machin e Learning (ICML), pages 89–97, 2017

    work page 2017

  2. [2]

    Allen-Zhu and E

    Z. Allen-Zhu and E. Hazan. V ariance reduction for faster non-convex optimization. In Pro- ceedings of the 33nd International Conference on Machine Le arning (ICML), pages 699–707, 2016. 6https://archive.ics.uci.edu/ml/datasets/Bank+Marketing 7https://www.lendingclub.com/info/download-data.action 8https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/bi...

    work page 2016

  3. [3]

    Bayandina, P

    A. Bayandina, P . Dvurechensky, A. Gasnikov, F. Stonyaki n, and A. Titov. Mirror descent and convex optimization problems with non-smooth inequality c onstraints. In Large-Scale and Distributed Optimization, pages 181–213. Springer, 2018

    work page 2018

  4. [4]

    D. P . Bertsekas. Nonlinear programming. Athena scientific Belmont, 1999

    work page 1999

  5. [5]

    D. P . Bertsekas. Constrained optimization and Lagrange multiplier methods . Academic press, 2014

    work page 2014

  6. [6]

    D. Boob, Q. Deng, and G. Lan. Optimization with convex and nonconvex functional con- straints. arXiv preprint arXiv:1908.02734 , 2019

    arXiv 1908

  7. [7]

    Cartis, N

    C. Cartis, N. I. Gould, and P . L. Toint. On the evaluation c omplexity of composite function minimization with applications to nonconvex nonlinear pro gramming. SIAM Journal on Opti- mization, 21(4):1721–1739, 2011

    work page 2011

  8. [8]

    Cartis, N

    C. Cartis, N. I. Gould, and P . L. Toint. On the complexity o f finding first-order critical points in constrained nonlinear optimization. Mathematical Programming, 144(1-2):93–106, 2014

    work page 2014

Show all 58 references
  1. [9]

    J. Chen, T. Y ang, Q. Lin, L. Zhang, and Y . Chang. Optimal stochastic strongly convex optimiza- tion with a logarithmic number of projections. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence , pages 122–131. AUAI Press, 2016

    2016

  2. [10]

    Z. Chen, T. Y ang, J. Yi, B. Zhou, and E. Chen. Universal st agewise learning for non-convex problems with convergence on averaged solutions. CoRR, /abs/1808.06296, 2018

    2018 arXiv

  3. [11]

    Cotter, H

    A. Cotter, H. Jiang, and K. Sridharan. Two-player games for efficient non-convex constrained optimization. arXiv preprint arXiv:1804.06500 , 2018

    2018 arXiv

  4. [12]

    Crammer and Y

    K. Crammer and Y . Singer. On the learnability and design of output codes for multiclass problems. Machine learning, 47(2-3):201–233, 2002

    2002

  5. [13]

    Davis and D

    D. Davis and D. Drusvyatskiy. Complexity of finding near -stationary points of convex func- tions stochastically. arXiv preprint arXiv:1802.08556 , 2018

    2018 arXiv

  6. [14]

    Davis and D

    D. Davis and D. Drusvyatskiy. Stochastic model-based m inimization of weakly convex func- tions. arXiv preprint arXiv:1803.06523 , 2018

    2018 arXiv

  7. [15]

    Davis and D

    D. Davis and D. Drusvyatskiy. Stochastic subgradient m ethod converges at the rate o(k−1/4) on weakly convex functions. arXiv preprint arXiv:1802.02988 , 2018

    2018 arXiv

  8. [16]

    Davis and B

    D. Davis and B. Grimmer. Proximally guided stochastic s ubgradient method for nonsmooth, nonconvex problems. arXiv preprint arXiv:1707.03505 , 2017

    2017 arXiv

  9. [17]

    Drusvyatskiy

    D. Drusvyatskiy. The proximal point method revisited. arXiv preprint arXiv:1712.06038 , 2017

    2017 arXiv

  10. [18]

    Drusvyatskiy and C

    D. Drusvyatskiy and C. Paquette. Efficiency of minimizi ng compositions of convex functions and smooth maps. Mathematical Programming, Jul 2018

    2018

  11. [19]

    Fercoq, A

    O. Fercoq, A. Alacaoglu, I. Necoara, and V . Cevher. Almo st surely constrained convex opti- mization. arXiv preprint arXiv:1902.00126 , 2019

    1902 arXiv

  12. [20]

    Ghadimi and G

    S. Ghadimi and G. Lan. Stochastic first- and zeroth-orde r methods for nonconvex stochastic programming. SIAM Journal on Optimization , 23(4):2341–2368, 2013

    2013

  13. [21]

    Ghadimi and G

    S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program., 156(1-2):59–99, 2016

    2016

  14. [22]

    G. Goh, A. Cotter, M. Gupta, and M. P . Friedlander. Satis fying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems , pages 2415–2423, 2016

    2016

  15. [23]

    Lacoste-Julien

    S. Lacoste-Julien. Convergence rate of frank-wolfe fo r non-convex objectives. arXiv preprint arXiv:1607.00345, 2016. 10

    2016 arXiv

  16. [24]

    Lacoste-Julien, M

    S. Lacoste-Julien, M. Schmidt, and F. Bach. A simpler ap proach to obtaining an o (1/t) conver- gence rate for the projected stochastic subgradient method . arXiv preprint arXiv:1212.2002 , 2012

    2002 arXiv

  17. [25]

    Lan and Y

    G. Lan and Y . Y ang. Accelerated stochastic algorithms f or nonconvex finite-sum and multi- block optimization. CoRR, abs/1805.05411, 2018

    2018 arXiv

  18. [26]

    Lan and Z

    G. Lan and Z. Zhou. Algorithms for stochastic optimizat ion with expectation constraints. arXiv preprint arXiv:1604.03887, 2016

    2016 arXiv

  19. [27]

    Q. Lin, M. Liu, H. Rafique, and T. Y ang. Solving weakly-co nvex-weakly-concave saddle-point problems as weakly-monotone variational inequality. arXiv preprint arXiv:1810.10207 , 2018

    2018 arXiv

  20. [28]

    Q. Lin, R. Ma, and T. Y ang. Level-set methods for finite-s um constrained convex optimization. In International Conference on Machine Learning , pages 3118–3127, 2018

    2018

  21. [29]

    Q. Lin, S. Nadarajah, and N. Soheili. A level-set method for convex optimization with a feasible solution path. SIAM Journal on Optimization , 28(4):3290–3311, 2018

    2018

  22. [30]

    Loh et al

    P .-L. Loh et al. Statistical consistency and asymptoti c normality for high-dimensional robust m-estimators. The Annals of Statistics , 45(2):866–896, 2017

    2017

  23. [31]

    Mahdavi, T

    M. Mahdavi, T. Y ang, R. Jin, and S. Zhu. Stochastic gradi ent descent with only one projection. In Advances in Neural Information Processing Systems (NIPS) , pages 503–511, 2012

    2012

  24. [32]

    Nesterov

    Y . Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013

    2013

  25. [33]

    Nocedal and S

    J. Nocedal and S. Wright. Numerical optimization. Springer Science & Business Media, 2006

    2006

  26. [34]

    Paquette, H

    C. Paquette, H. Lin, D. Drusvyatskiy, J. Mairal, and Z. H archaoui. Catalyst for gradient-based nonconvex optimization. pages 1–10, 2018

    2018

  27. [35]

    B. Polyak. A general method of solving extremum problem s. Soviet Mathematics Doklady , 8(3):593–597, 1967

    1967

  28. [36]

    Rafique, M

    H. Rafique, M. Liu, Q. Lin, and T. Y ang. Non-convex min-ma x optimization: Provable algo- rithms and applications in machine learning. arXiv preprint arXiv:1810.02060 , 2018

    2018 arXiv

  29. [37]

    S. J. Reddi, A. Hefny, S. Sra, B. Póczós, and A. Smola. Sto chastic variance reduction for nonconvex optimization. In Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML) , pages 314–323. JMLR.org, 2016

    2016

  30. [38]

    S. J. Reddi, S. Sra, B. Póczos, and A. J. Smola. Fast incre mental method for smooth nonconvex optimization. In 55th IEEE Conference on Decision and Control (CDC) , pages 1971–1977, 2016

    1971

  31. [39]

    Rigollet and X

    P . Rigollet and X. Tong. Neyman-pearson classification , convexity and stochastic constraints. Journal of Machine Learning Research , 12(Oct):2831–2855, 2011

    2011

  32. [40]

    Rockafellar

    R. Rockafellar. Convex Analysis. Princeton mathematical series. Princeton University Pre ss, 1970

    1970

  33. [41]

    R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM J. on Control and Optimization, 14(5), 1976

    1976

  34. [42]

    A. P . Ruszczy ´nski. Nonlinear optimization, volume 13. Princeton university press, 2006

    2006

  35. [43]

    S. Sahni. Computationally related problems. SIAM Journal on Computing , 3(4):262–279, 1974

    1974

  36. [44]

    Wei and M

    X. Wei and M. J. Neely. Primal-dual frank-wolfe for cons trained stochastic programs with convex and non-convex objectives. arXiv preprint arXiv:1806.00709 , 2018. 11

    2018 arXiv

  37. [45]

    X. Wei, H. Y u, Q. Ling, and M. Neely. Solving non-smooth c onstrained programs with lower complexity than o(1/ε): A primal-dual homotopy smoothing approach. In Advances in Neural Information Processing Systems, pages 3995–4005, 2018

    2018

  38. [46]

    Weston and C

    J. Weston and C. Watkins. Multi-class support vector ma chines. Technical report, Citeseer, 1998

    1998

  39. [47]

    Y . Xu. First-order methods for constrained convex prog ramming based on linearized aug- mented lagrangian function. arXiv preprint arXiv:1711.08020 , 2017

    2017 arXiv

  40. [48]

    Y . Xu. Global convergence rates of augmented lagrangia n methods for constrained convex programming. arXiv preprint arXiv:1711.05812 , 2017

    2017 arXiv

  41. [49]

    Y . Xu. Primal-dual stochastic gradient method for conv ex programs with many functional constraints. arXiv preprint arXiv:1802.02724 , 2018

    2018 arXiv

  42. [50]

    Y . Xu, S. Zhu, S. Y ang, C. Zhang, R. Jin, and T. Y ang. Learn ing with non-convex truncated losses by sgd. arXiv preprint arXiv:1805.07880 , 2018

    2018 arXiv

  43. [51]

    Y ang, Q

    T. Y ang, Q. Lin, and Z. Li. Unified convergence analysis o f stochastic momentum methods for convex and non-convex optimization. volume abs/1604.0325 7, 2016

    2016

  44. [52]

    Y ang, Q

    T. Y ang, Q. Lin, and L. Zhang. A richer theory of convex co nstrained optimization with reduced projections and improved rates. In Proceedings of the 34th International Conference on Machine Learning-V olume 70, pages 3901–3910. JMLR. org, 2017

  45. [53]

    H. Y u, M. Neely, and X. Wei. Online convex optimization w ith stochastic constraints. In Advances in Neural Information Processing Systems , pages 1428–1438, 2017

    2017

  46. [54]

    Y u and M

    H. Y u and M. J. Neely. A simple parallel algorithm with an o(1/t) convergence rate for general convex programs. SIAM Journal on Optimization , 27(2):759–783, 2017

    2017

  47. [55]

    M. B. Zafar, I. V alera, M. Rodriguez, K. Gummadi, and A. W eller. From parity to preference- based notions of fairness in classification. In Advances in Neural Information Processing Systems, pages 229–239, 2017

    2017

  48. [56]

    M. B. Zafar, I. V alera, M. G. Rodriguez, and K. P . Gummadi. Fairness constraints: Mechanisms for fair classification. arXiv preprint arXiv:1507.05259 , 2015

    2015 arXiv

  49. [57]

    Zhang, T

    L. Zhang, T. Y ang, R. Jin, and X. He. O (logt) projections for stochastic optimization of smooth and strongly convex functions. arXiv preprint arXiv:1304.0740 , 2013

    2013 arXiv

  50. [58]

    Zhang and N

    S. Zhang and N. He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprint arXiv:1806.04781 , 2018. 12 A Appendix In this section, we provide the proofs for the theoretical re sults in the paper. A.1 Proof of Lemma 1 Proof. No...

    2018 arXiv

Pith tools

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