First-Order Algorithms Without Lipschitz Gradient: A Sequential Local Optimization Approach

References

• Armijo L (1966) Minimization of functions having Lipschitz continuous first partial derivatives. Pacific J. Math. 16(1):1–3.Google Scholar
• Bauschke HH, Bolte J, Teboulle M (2017) A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications. Math. Oper. Res. 42(2):330–348.Link, Google Scholar
• Bertsekas DP (1999) Nonlinear Programming, 2nd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bolte J, Sabach S, Teboulle M, Vaisbourd Y (2018) First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM J. Optim. 28(3):2131–2151.Google Scholar
• Bompaire M, Bacry E, Gaïffas S (2018) Dual optimization for convex constrained objectives without the gradient-Lipschitz assumption. Preprint, submitted July 10, https://arxiv.org/abs/1807.03545.Google Scholar
• Carderera A, Besançon M, Pokutta S (2021) Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 5390–5401.Google Scholar
• Carmon Y, Duchi JC, Hinder O, Sidford A (2017) Convex until proven guilty: Dimension-free acceleration of gradient descent on non-convex functions. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learning, vol. 70 (PMLR, New York), 654–663.Google Scholar
• Comon P, Golub G, Lim L-H, Mourrain B (2008) Symmetric tensors and symmetric tensor rank. SIAM J. Matrix Anal. Appl. 30(3):1254–1279.Google Scholar
• Dragomir R-A, Taylor A, d’Aspremont A, Bolte J (2019) Optimal complexity and certification of Bregman first-order methods. Preprint, submitted November 19, https://arxiv.org/abs/1911.08510.Google Scholar
• Drusvyatskiy D, Davis D, MacPhee KJ (2018) Stochastic model-based minimization under high-order growth. Preprint, submitted July 1, https://arxiv.org/abs/1807.00255.Google Scholar
• Dvurechensky P, Safin K, Shtern S, Staudigl M (2023) Generalized self-concordant analysis of Frank–Wolfe algorithms. Math. Program. 198:255–323.Google Scholar
• Gao T, Lu S, Liu J, Chu C (2019) Leveraging two reference functions in block Bregman proximal gradient descent for non-convex and non-Lipschitz problems. Preprint, submitted December 16, https://arxiv.org/abs/1912.07527.Google Scholar
• Grimmer B (2018) Radial subgradient method. SIAM J. Optim. 28(1):459–469.Google Scholar
• Grimmer B (2019) Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity. SIAM J. Optim. 29(2):1350–1365.Google Scholar
• Grimmer B (2023) Radial duality part II: Applications and algorithms. Math. Program., ePub ahead of print May 26, https://doi.org/10.1007/s10107-023-01974-0.Google Scholar
• Hanzely F, Richtarik P, Xiao L (2018) Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. Preprint, submitted August 9, https://arxiv.org/abs/1808.03045.Google Scholar
• Hien LTK, Gillis N, Patrinos P (2019) Inertial block mirror descent method for non-convex non-smooth optimization. Preprint, submitted March 5, https://arxiv.org/abs/1903.01818.Google Scholar
• Hinton GE, Salakhutdinov RR (2006) Reducing the dimensionality of data with neural networks. Science 313(5786):504–507.Google Scholar
• Kolda TG, Bader BW (2009) Tensor decompositions and applications. SIAM Rev. 51(3):455–500.Google Scholar
• Li Q, Zhu Z, Tang G, Wakin MB (2019) Provable Bregman-divergence based methods for nonconvex and non-Lipschitz problems. Preprint, submitted April 22, https://arxiv.org/abs/1904.09712.Google Scholar
• Lu H, Freund RM, Nesterov Y (2018) Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28(1):333–354.Google Scholar
• Mukkamala MC, Westerkamp F, Laude E, Cremers D, Ochs P (2019) Bregman proximal framework for deep linear neural networks. Preprint, submitted October 8, https://arxiv.org/abs/1910.03638.Google Scholar
• Nocedal J, Wright S (2006) Numerical Optimization (Springer Science & Business Media, New York).Google Scholar
• Reem D, Reich S, De Pierro A (2019) A telescopic Bregmanian proximal gradient method without the global Lipschitz continuity assumption. J. Optim. Theory Appl. 182:851–884.Google Scholar
• Teboulle M (2018) A simplified view of first order methods for optimization. Math. Program. 170:67–96.Google Scholar
• Zhang J, He T, Sra S, Jadbabaie A (2019) Why gradient clipping accelerates training: A theoretical justification for adaptivity. Preprint, submitted May 28, https://arxiv.org/abs/1905.11881.Google Scholar
• Zhao R, Freund RM (2020) Analysis of the Frank-Wolfe method for logarithmically-homogeneous barriers, with an extension. Preprint, submitted October 18, https://arxiv.org/abs/2010.08999.Google Scholar