×

Smoothness parameter of power of Euclidean norm. (English) Zbl 1453.46041

Summary: In this paper, we study derivatives of powers of Euclidean norm. We prove their Hölder continuity and establish explicit expressions for the corresponding constants. We show that these constants are optimal for odd derivatives and at most two times suboptimal for the even ones. In the particular case of integer powers, when the Hölder continuity transforms into the Lipschitz continuity, we improve this result and obtain the optimal constants.

MSC:

46G05 Derivatives of functions in infinite-dimensional spaces
26A16 Lipschitz (Hölder) classes

Software:

NESUN
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Nesterov, Y.; Polyak, BT, Cubic regularization of Newton method and its global performance, Math. Program., 108, 1, 177-205 (2006) · Zbl 1142.90500 · doi:10.1007/s10107-006-0706-8
[2] Nesterov, Y., Accelerating the cubic regularization of Newton’s method on convex problems, Math. Program., 112, 1, 159-181 (2008) · Zbl 1167.90013 · doi:10.1007/s10107-006-0089-x
[3] Cartis, C.; Gould, NI; Toint, PL, Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Program., 127, 2, 245-295 (2011) · Zbl 1229.90192 · doi:10.1007/s10107-009-0286-5
[4] Cartis, C.; Gould, NI; Toint, PL, Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity, Math. Program., 130, 2, 295-319 (2011) · Zbl 1229.90193 · doi:10.1007/s10107-009-0337-y
[5] Carmon, Y., Duchi, J.C.: Gradient descent efficiently finds the cubic-regularized non-convex Newton step. arXiv preprint arXiv:1612.00547 (2016) · Zbl 1461.65135
[6] Kohler, J.M., Lucchi, A.: Sub-sampled cubic regularization for non-convex optimization. In: Proceedings of the 34th International Conference on Machine Learning, vol. 70, pp. 1895-1904. JMLR (2017)
[7] Cartis, C.; Scheinberg, K., Global convergence rate analysis of unconstrained optimization methods based on probabilistic models, Math. Program., 169, 2, 337-375 (2018) · Zbl 1407.90307 · doi:10.1007/s10107-017-1137-4
[8] Doikov, N., Richtarik, P., et al.: Randomized block cubic Newton method. In: International Conference on Machine Learning, pp. 1289-1297 (2018)
[9] Schnabel, RB; Chow, TT, Tensor methods for unconstrained optimization using second derivatives, SIAM J. Optim., 1, 3, 293-315 (1991) · Zbl 0758.65047 · doi:10.1137/0801020
[10] Baes, M.: Estimate sequence methods: extensions and approximations. Optimization Online (2009)
[11] Cartis, C., Gould, N.I., Toint, P.L.: Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. arXiv preprint arXiv:1708.04044 (2017) · Zbl 1439.90056
[12] Gasnikov, A., Dvurechensky, P., Gorbunov, E., Vorontsova, E., Selikhanovych, D., Uribe, C.A., Jiang, B., Wang, H., Zhang, S., Bubeck, S., et al.: Near optimal methods for minimizing convex functions with Lipschitz \(p\)-th derivatives. In: Conference on Learning Theory, pp. 1392-1393 (2019)
[13] Nesterov, Y.: Implementable tensor methods in unconstrained convex optimization. Technical report, CORE discussion paper, Université Catholique de Louvain, Belgium (2015) · Zbl 1459.90157
[14] Grapiglia, GN; Nesterov, Y., Regularized Newton methods for minimizing functions with Hölder continuous Hessians, SIAM J. Optim., 27, 1, 478-506 (2017) · Zbl 1406.49029 · doi:10.1137/16M1087801
[15] Grapiglia, G.N., Nesterov, Y.: Tensor methods for minimizing functions with Hölder continuous higher-order derivatives. arXiv preprint arXiv:1904.12559 (2019) · Zbl 1406.49030
[16] Vladimirov, A.; Nesterov, YE; Chekanov, YN, On uniformly convex functionals, Vestnik Moskov. Univ. Ser. XV Vychisl. Mat. Kibernet, 3, 12-23 (1978) · Zbl 0442.47046
[17] Doikov, N., Nesterov, Y.: Minimizing uniformly convex functions by cubic regularization of Newton method. arXiv preprint arXiv:1905.02671 (2019) · Zbl 1470.90075
[18] Nesterov, Y., Universal gradient methods for convex optimization problems, Math. Program., 152, 1-2, 381-404 (2015) · Zbl 1327.90216 · doi:10.1007/s10107-014-0790-0
[19] Nesterov, Y.; Nemirovskii, A., Interior-Point Polynomial Algorithms in Convex Programming (1994), Philadelphia: SIAM, Philadelphia · Zbl 0824.90112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.