We investigate stochastic simple bilevel optimization with smooth and possibly nonconvex upper- and lower-level objectives. Existing stochastic extensions of dynamic barrier gradient descent (DBGD) either obtain fast convergence under an unverifiable trajectory-dependent ``rare-visit''assumption, or remove this assumption at a substantially higher oracle cost. We show that a simple denominator-only regularization of the DBGD multiplier eliminates the need for such an assumption while preserving fast convergence rates. Specifically, our method achieves $(\varepsilon, \varepsilon)$-stationarity in $O(\varepsilon^{-2})$ iterations using $O(\varepsilon^{-4})$ upper-level and $O(\varepsilon^{-7})$ lower-level stochastic gradients, which improves upon the best assumption-free complexities. We additionally derive anytime parameter schedules.
Daniel Cortild, Mathias Staudigl, J. Peypouquet et al.· 0 citations
We propose an adaptive accelerated gradient method for solving smooth convex optimization problems. The method incorporates a scheme to determine the step size adaptively, by means of a local estimation of the smoothness constant, which is assumed unknown, without resorting to line search procedures. The sequence generated by this method converges weakly to a minimizer of the objective function, and the function values converge at a fast rate of O1k2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}\left( \frac{1}{k^2} \right) $$\end{document}. Moreover, if the objective function is strongly convex, the function values converge at a linear rate O1k2(1-ρ)k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}\left( \frac{1}{k^2}(1-\rho )^k \right) $$\end{document}, with ρ=OμL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho =\mathcal {O}\left( \frac{\mu }{L} \right) $$\end{document}, without knowledge of the strong convexity parameter.
Zepeng Wang, J. Peypouquet· Journal of Optimization Theo...· 1 citation
Featuring Hessian-driven damping, two inertial primal dual dynamical systems are proposed for solving smooth saddle point problems with bilinear coupling. For convex-concave functions, we establish a convergence rate $\mathcal{O}\left( \frac{1}{t^2} \right)$ for the primal dual gap; for strongly convex-strongly concave functions, we obtain an asymptotic rate $\mathcal{O}\left( \frac{1}{t^{\alpha-1}} \right)$ ($\alpha\ge 3$ is the damping parameter) without knowledge of the strong convexity parameters, and an accelerated linear convergence rate when the strong convexity parameters are known. As an application of the proposed inertial systems, we also consider the affinely constrained convex optimization problem, and develop an inertial system with Hessian-driven damping, which complements existing results.
Zepeng Wang, J. Peypouquet· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
