اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNon-Asymptotic Convergence Analysis of the Multiplicative Gradient Algorithm for the Log-Optimal Investment Problems
125
0
0.0
(
0
)
تأليف
Renbo Zhao
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We analyze the non-asymptotic convergence rate of the multiplicative gradient (MG) algorithm for the log-optimal investment problems, and show that it exhibits $O(1/t)$ convergence rates, in both ergodic and non-ergodic senses.
قيم البحث
اقرأ أيضاً
For optimal power flow problems with chance constraints, a particularly effective method is based on a fixed point iteration applied to a sequence of deterministic power flow problems. However, a priori, the convergence of such an approach is not nec
essarily guaranteed. This article analyses the convergence conditions for this fixed point approach, and reports numerical experiments including for large IEEE networks.
We prove an asymptotic crystallization result in two dimensions for a class of nonlocal particle systems. To be precise, we consider the best approximation with respect to the 2-Wasserstein metric of a given absolutely continuous probability measure
$f mathrm{d}x$ by a discrete probability measure $sum_i m_i delta_{z_i}$, subject to a constraint on the particle sizes $m_i$. The locations $z_i$ of the particles, their sizes $m_i$, and the number of particles are all unknowns of the problem. We study a one-parameter family of constraints. This is an example of an optimal location problem (or an optimal sampling or quantization problem) and it has applications in economics, signal compression, and numerical integration. We establish the asymptotic minimum value of the (rescaled) approximation error as the number of particles goes to infinity. In particular, we show that for the constrained best approximation of the Lebesgue measure by a discrete measure, the discrete measure whose support is a triangular lattice is asymptotically optimal. In addition, we prove an analogous result for a problem where the constraint is replaced by a penalization. These results can also be viewed as the asymptotic optimality of the hexagonal tiling for an optimal partitioning problem. They generalise the crystallization result of Bourne, Peletier and Theil (Communications in Mathematical Physics, 2014) from a single particle system to a class of particle systems, and prove a case of a conjecture by Bouchitt{e}, Jimenez and Mahadevan (Journal de Mathematiques Pures et Appliquees, 2011). Finally, we prove a crystallization result which states that optimal configurations with energy close to that of a triangular lattice are geometrically close to a triangular lattice.
We propose and analyze the convergence of a novel stochastic algorithm for solving monotone inclusions that are the sum of a maximal monotone operator and a monotone, Lipschitzian operator. The propose algorithm requires only unbiased estimations of
the Lipschitzian operator. We obtain the rate $mathcal{O}(log(n)/n)$ in expectation for the strongly monotone case, as well as almost sure convergence for the general case. Furthermore, in the context of application to convex-concave saddle point problems, we derive the rate of the primal-dual gap. In particular, we also obtain $mathcal{O}(1/n)$ rate convergence of the primal-dual gap in the deterministic setting.
In this work, we analyze the global convergence property of coordinate gradient descent with random choice of coordinates and stepsizes for non-convex optimization problems. Under generic assumptions, we prove that the algorithm iterate will almost s
urely escape strict saddle points of the objective function. As a result, the algorithm is guaranteed to converge to local minima if all saddle points are strict. Our proof is based on viewing coordinate descent algorithm as a nonlinear random dynamical system and a quantitative finite block analysis of its linearization around saddle points.
In this paper, we provide a unified convergence analysis for a class of shuffling-type gradient methods for solving a well-known finite-sum minimization problem commonly used in machine learning. This algorithm covers various variants such as randomi
zed reshuffling, single shuffling, and cyclic/incremental gradient schemes. We consider two different settings: strongly convex and non-convex problems. Our main contribution consists of new non-asymptotic and asymptotic convergence rates for a general class of shuffling-type gradient methods to solve both non-convex and strongly convex problems. While our rate in the non-convex problem is new (i.e. not known yet under standard assumptions), the rate on the strongly convex case matches (up to a constant) the best-known results. However, unlike existing works in this direction, we only use standard assumptions such as smoothness and strong convexity. Finally, we empirically illustrate the effect of learning rates via a non-convex logistic regression and neural network examples.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
