A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization

References

• [1] Ben-Tal A, Margalit T, Nemirovski A (2001) The ordered subsets mirror descent optimization method with applications to tomography. SIAM J. Optim. 12(1):79–108.Crossref, Google Scholar
• [2] Bernhard P, Rapaport A (1995) On a theorem of Danskin with an application to a theorem of Von neumann-sion. Nonlinear Anal. 24(8):1163–1181.Crossref, Google Scholar
• [3] Candés E, Strohmer T, Voroninski V (2013) Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Comm. Pure Appl. Math. 66(8):1241–1274.Crossref, Google Scholar
• [4] Chen Y, Chi Y, Goldsmith AJ (2015) Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Trans. Inform. Theory 61(7):4034–4059.Crossref, Google Scholar
• [5] Chen Y, Lan G, Ouyang Y (2017) Accelerated schemes for a class of variational inequalities. Math. Programming 165(1):113–149.Crossref, Google Scholar
• [6] Danskin JM (1967) The Theory of Max-Min and Its Application to Weapons Allocation Problems (Springer-Verlag, Berlin, Heidelberg).Crossref, Google Scholar
• [7] Davis D, Drusvyatskiy D (2019) Stochastic model-based minimization of weakly convex functions. SIAM J. Optim. 29(1):207–239.Crossref, Google Scholar
• [8] Davis D, Grimmer B (2019) Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM J. Optim. 29(3):1908–1930.Crossref, Google Scholar
• [9] Davis D, Drusvyatskiy D, MacPhee KJ (2018) Stochastic model-based minimization under high-order growth. http://www.optimization-online.org/DB_HTML/2018/07/6690.html.Google Scholar
• [10] Devolder O, Glineur F, Nesterov Y (2013) First-order methods with inexact oracle: The strongly convex case. CORE Discussion Paper (2013/16), Center for Operations Research and Econometrics, UCLouvain, Belgium.Google Scholar
• [11] Devolder O, Glineur F, Nesterov Y (2014) First-order methods of smooth convex optimization with inexact oracle. Math. Programming 146:37–75.Crossref, Google Scholar
• [12] Juditsky A, Nemirovski A (2012) First-Order Methods for Nonsmooth Convex Large-Scale Optimization, I: General Purpose Methods. Optimization for Machine Learning (MIT Press, Cambridge, MA), 121–148.Google Scholar
• [13] Kong W, Monteiro RDC (2019) An accelerated inexact proximal point method for solving nonconvex-concave min-max problems. Preprint, submitted May 31, https://arxiv.org/abs/1905.13433.Google Scholar
• [14] Kruger AY (2003) On Fréchet subdifferentials. J. Math. Sci. (N.Y.) 116(3):3325–3358.Crossref, Google Scholar
• [15] Lin T, Jin C, Jordan MI (2019) On gradient descent ascent for nonconvex-concave minimax problems. Preprint, submitted June 2, https://arxiv.org/abs/1906.00331.Google Scholar
• [16] Lu S, Tsaknakis I, Hong M, Chen Y (2019) Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications. Preprint, submitted February 21, https://arxiv.org/abs/1902.08294.Google Scholar
• [17] Nemirovski A (2005) Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.Crossref, Google Scholar
• [18] Nesterov Y (1983) A method of solving a convex programming problem with convergence rate o(1/k2). Soviet Mathematics Doklady. 27(2):372–376.Google Scholar
• [19] Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course (Springer, New York).Crossref, Google Scholar
• [20] Nesterov Y (2005) Smooth minimization of non-smooth functions. Math. Programming 103(1):127–152.Crossref, Google Scholar
• [21] Nesterov Y (2013) Gradient methods for minimizing composite functions. Math. Programming 140(1):125–161.Crossref, Google Scholar
• [22] Nouiehed M, Sanjabi M, Huang T, Lee JD, Razaviyayn M (2019) Solving a class of non-convex min-max games using iterative first order methods. Adv. Neural Inform. Process. Systems 32:14934–14942.Google Scholar
• [23] Ostrovskii DM, Lowy A, Razaviyayn M (2020) Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems. Preprint, submitted February 18, https://arxiv.org/abs/2002.07919.Google Scholar
• [24] Peypouquet J (2015) Convex Optimization in Normed Spaces: Theory, Methods and Examples (Springer, Cham, Switzerland).Crossref, Google Scholar
• [25] Rafique H, Liu M, Lin Q, Yang T (2018) Non-convex min-max optimization: Provable algorithms and applications in machine learning. Preprint, submitted October 4, https://arxiv.org/abs/1810.02060.Google Scholar
• [26] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [27] Schmidt M, Roux NL, Bach FR (2011) Convergence rates of inexact proximal-gradient methods for convex optimization. Proc. NIPS (Curran Associates, Inc., Red Hook, NY), 1458–1466.Google Scholar
• [28] Sinha A, Namkoong H, Duchi J (2017) Certifying some distributional robustness with principled adversarial training. Preprint, submitted October 29, https://arxiv.org/abs/1710.10571.Google Scholar
• [29] Sion M (1958) On general minimax theorems. Pacific J. Math. 8(1):171–176.Crossref, Google Scholar
• [30] Thekumparampil KK, Jain P, Netrapalli P, Oh S (2019) Efficient algorithms for smooth minimax optimization. Proc. NIPS (Curran Associates, Inc., Red Hook, NY), 12680–12691.Google Scholar
• [31] Tseng P (2008) On accelerated proximal gradient methods for convex-concave optimization. Technical report, University of Washington, Seattle.Google Scholar
• [32] Zhang T (2004) Solving large scale linear prediction problems using stochastic gradient descent algorithms. Proc. ICML (ACM, New York), 919–926.Google Scholar
• [33] Zhao R (2019) Optimal stochastic algorithms for convex-concave saddle-point problems. Preprint, submitted March 5, https://arxiv.org/abs/1903.01687.Google Scholar