Naoki Marumo
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Naoki Marumo has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Akiko Takeda
Graduate School of Information Science and Technology, University of Tokyo, Tokyo, Japan
4 shared publications Akiko Takeda
Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan
3 shared publicationsTakayuki Okuno
2 shared publications- Hao Zhang
Department of Applied Mathematics The Hong Kong Polytechnic University Hong Kong China
1 shared publication - Hiroki Hamaguchi
The University of Tokyo
1 shared publication - Kou Hamada
University of Tokyo
1 shared publication
Latest Publications
- Open Access
Complexity and convergence analysis of a single-loop SDCAM for Lipschitz composite optimization and beyond
We develop and analyze a single-loop algorithm for minimizing the sum of a Lipschitz differentiable function $f$, a prox-friendly proper closed function $g$ (with a closed domain on which $g$ is continuous) and the composition of another prox-friendly proper closed function $h$ (whose domain is closed on which $h$ is continuous) with a continuously differentiable mapping $c$ (that is Lipschitz continuous and Lipschitz differentiable on the convex closure of the domain of $g$). Such models arise naturally in many contemporary applications, where $f$ is the loss function for data misfit, and $g$ and $h$ are nonsmooth functions for inducing desirable structures in $x$ and $c(x)$. Existing single-loop algorithms mainly focus either on the case where $h$ is Lipschitz continuous or the case where $h$ is an indicator function of a closed convex set. In this paper, we develop a single-loop algorithm for more general possibly non-Lipschitz $h$. Our algorithm is a single-loop variant of the successive difference-of-convex approximation method (SDCAM) proposed in [22]. We show that when $h$ is Lipschitz, our algorithm exhibits an iteration complexity that matches the best known complexity result for obtaining an $(ε_1,ε_2,0)$-stationary point. Moreover, we show that, by assuming additionally that dom $g$ is compact, our algorithm exhibits an iteration complexity of $\tilde{O}(ε^{-4})$ for obtaining an $(ε,ε,ε)$-stationary point when $h$ is merely continuous and real-valued. Furthermore, we consider a scenario where $h$ does not have full domain and establish vanishing bounds on successive changes of iterates. Finally, in all three cases mentioned above, we show that one can construct a subsequence such that any accumulation point $x^*$ satisfies $c(x^*)\in$ dom $h$, and if a standard constraint qualification holds at $x^*$, then $x^*$ is a stationary point.Open AccessComplexity and convergence analysis of a single-loop SDCAM for Lipschitz composite optimization and beyond
We develop and analyze a single-loop algorithm for minimizing the sum of a Lipschitz differentiable function $f$, a prox-friendly proper closed function $g$ (with a closed domain on which $g$ is continuous) and the composition of another prox-friendly proper closed function $h$ (whose domain is closed on which $h$ is continuous) with a continuously differentiable mapping $c$ (that is Lipschitz continuous and Lipschitz differentiable on the convex closure of the domain of $g$). Such models arise naturally in many contemporary applications, where $f$ is the loss function for data misfit, and $g$ and $h$ are nonsmooth functions for inducing desirable structures in $x$ and $c(x)$. Existing single-loop algorithms mainly focus either on the case where $h$ is Lipschitz continuous or the case where $h$ is an indicator function of a closed convex set. In this paper, we develop a single-loop algorithm for more general possibly non-Lipschitz $h$. Our algorithm is a single-loop variant of the successive difference-of-convex approximation method (SDCAM) proposed in [22]. We show that when $h$ is Lipschitz, our algorithm exhibits an iteration complexity that matches the best known complexity result for obtaining an $(ε_1,ε_2,0)$-stationary point. Moreover, we show that, by assuming additionally that dom $g$ is compact, our algorithm exhibits an iteration complexity of $\tilde{O}(ε^{-4})$ for obtaining an $(ε,ε,ε)$-stationary point when $h$ is merely continuous and real-valued. Furthermore, we consider a scenario where $h$ does not have full domain and establish vanishing bounds on successive changes of iterates. Finally, in all three cases mentioned above, we show that one can construct a subsequence such that any accumulation point $x^*$ satisfies $c(x^*)\in$ dom $h$, and if a standard constraint qualification holds at $x^*$, then $x^*$ is a stationary point. - Open Access
Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization
We propose a quasi-Newton-type method for nonconvex optimization with Lipschitz continuous gradients and Hessians. The algorithm finds an $\varepsilon$-stationary point within $\tilde{\mathrm{O}}(d^{1/4} \varepsilon^{-13/8})$ gradient evaluations, where $d$ is the problem dimension. Although this bound includes an additional logarithmic factor compared with the best known complexity, our method is parameter-free in the sense that it requires no prior knowledge of problem-dependent parameters such as Lipschitz constants or the optimal value. Moreover, it does not need the target accuracy $\varepsilon$ or the total number of iterations to be specified in advance. The result is achieved by combining several key ideas: momentum-based acceleration, quartic regularization for subproblems, and a scaled variant of the Powell-symmetric-Broyden (PSB) update.Open AccessParameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization
We propose a quasi-Newton-type method for nonconvex optimization with Lipschitz continuous gradients and Hessians. The algorithm finds an $\varepsilon$-stationary point within $\tilde{\mathrm{O}}(d^{1/4} \varepsilon^{-13/8})$ gradient evaluations, where $d$ is the problem dimension. Although this bound includes an additional logarithmic factor compared with the best known complexity, our method is parameter-free in the sense that it requires no prior knowledge of problem-dependent parameters such as Lipschitz constants or the optimal value. Moreover, it does not need the target accuracy $\varepsilon$ or the total number of iterations to be specified in advance. The result is achieved by combining several key ideas: momentum-based acceleration, quartic regularization for subproblems, and a scaled variant of the Powell-symmetric-Broyden (PSB) update. - 28 January 2025
- Published by American Physical Society (APS) in Physical Review Applied
- Vol. 23 (1)
Faster computation of nonstabilizerness
- 28 January 2025
- Published by American Physical Society (APS) in Physical Review Applied
- Vol. 23 (1)
Faster computation of nonstabilizerness
- Open Access
- 4 November 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 213 (1-2) , 771-822
Accelerated-gradient-based generalized Levenberg–Marquardt method with oracle complexity bound and local quadratic convergence
Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg–Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle complexity bound, and local convergence under a Hölderian growth condition. The local convergence results include local quadratic convergence under the quadratic growth condition; this is the first to extend the classical result for least-squares problems to a general smooth composite function. In addition, this is the first LM method with both an oracle complexity bound and local quadratic convergence under standard assumptions. These results are achieved by carefully controlling the damping parameter and solving the subproblems by the accelerated proximal gradient method equipped with a particular termination condition. Experimental results show that the proposed method performs well in practice for several instances, including classification with a neural network and nonnegative matrix factorization.
- 4 November 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 213 (1-2) , 771-822
Open AccessAccelerated-gradient-based generalized Levenberg–Marquardt method with oracle complexity bound and local quadratic convergence
Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg–Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle complexity bound, and local convergence under a Hölderian growth condition. The local convergence results include local quadratic convergence under the quadratic growth condition; this is the first to extend the classical result for least-squares problems to a general smooth composite function. In addition, this is the first LM method with both an oracle complexity bound and local quadratic convergence under standard assumptions. These results are achieved by carefully controlling the damping parameter and solving the subproblems by the accelerated proximal gradient method equipped with a particular termination condition. Experimental results show that the proposed method performs well in practice for several instances, including classification with a neural network and nonnegative matrix factorization.
- 17 June 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (2) , 2093-2120
Parameter-Free Accelerated Gradient Descent for Nonconvex Minimization
We propose a new first-order method for minimizing nonconvex functions with a Lipschitz continuous gradient and Hessian. The proposed method is an accelerated gradient descent with two restart mechanisms and finds a solution where the gradient norm is less than [Formula: see text] in [Formula: see text] function and gradient evaluations. Unlike existing first-order methods with similar complexity bounds, our algorithm is parameter-free because it requires no prior knowledge of problem-dependent parameters, e.g., the Lipschitz constants and the target accuracy [Formula: see text]. The main challenge in achieving this advantage is estimating the Lipschitz constant of the Hessian using only first-order information. To this end, we develop a new Hessian-free analysis based on two technical inequalities: a Jensen-type inequality for gradients and an error bound for the trapezoidal rule. Several numerical results illustrate that the proposed method performs comparably to existing algorithms with similar complexity bounds, even without parameter tuning.
- 17 June 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (2) , 2093-2120
Parameter-Free Accelerated Gradient Descent for Nonconvex Minimization
We propose a new first-order method for minimizing nonconvex functions with a Lipschitz continuous gradient and Hessian. The proposed method is an accelerated gradient descent with two restart mechanisms and finds a solution where the gradient norm is less than [Formula: see text] in [Formula: see text] function and gradient evaluations. Unlike existing first-order methods with similar complexity bounds, our algorithm is parameter-free because it requires no prior knowledge of problem-dependent parameters, e.g., the Lipschitz constants and the target accuracy [Formula: see text]. The main challenge in achieving this advantage is estimating the Lipschitz constant of the Hessian using only first-order information. To this end, we develop a new Hessian-free analysis based on two technical inequalities: a Jensen-type inequality for gradients and an error bound for the trapezoidal rule. Several numerical results illustrate that the proposed method performs comparably to existing algorithms with similar complexity bounds, even without parameter tuning.
- Open Access
- 4 June 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 212 (1-2) , 147-175
Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and Hölder continuous Hessians. The proposed algorithm is a heavy-ball method equipped with two particular restart mechanisms. It finds a solution where the gradient norm is less than $$\varepsilon $$ in $$O(H_{\nu }^{\frac{1}{2 + 2 \nu }} \varepsilon ^{- \frac{4 + 3 \nu }{2 + 2 \nu }})$$ function and gradient evaluations, where $$\nu \in [0, 1]$$ and $$H_{\nu }$$ are the Hölder exponent and constant, respectively. This complexity result covers the classical bound of $$O(\varepsilon ^{-2})$$ for $$\nu = 0$$ and the state-of-the-art bound of $$O(\varepsilon ^{-7/4})$$ for $$\nu = 1$$ . Our algorithm is $$\nu $$ -independent and thus universal; it automatically achieves the above complexity bound with the optimal $$\nu \in [0, 1]$$ without knowledge of $$H_{\nu }$$ . In addition, the algorithm does not require other problem-dependent parameters as input, including the gradient’s Lipschitz constant or the target accuracy $$\varepsilon $$ . Numerical results illustrate that the proposed method is promising.- 4 June 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 212 (1-2) , 147-175
Open AccessUniversal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and Hölder continuous Hessians. The proposed algorithm is a heavy-ball method equipped with two particular restart mechanisms. It finds a solution where the gradient norm is less than $$\varepsilon $$ in $$O(H_{\nu }^{\frac{1}{2 + 2 \nu }} \varepsilon ^{- \frac{4 + 3 \nu }{2 + 2 \nu }})$$ function and gradient evaluations, where $$\nu \in [0, 1]$$ and $$H_{\nu }$$ are the Hölder exponent and constant, respectively. This complexity result covers the classical bound of $$O(\varepsilon ^{-2})$$ for $$\nu = 0$$ and the state-of-the-art bound of $$O(\varepsilon ^{-7/4})$$ for $$\nu = 1$$ . Our algorithm is $$\nu $$ -independent and thus universal; it automatically achieves the above complexity bound with the optimal $$\nu \in [0, 1]$$ without knowledge of $$H_{\nu }$$ . In addition, the algorithm does not require other problem-dependent parameters as input, including the gradient’s Lipschitz constant or the target accuracy $$\varepsilon $$ . Numerical results illustrate that the proposed method is promising. - Open Access
Parameter-free accelerated gradient descent for nonconvex minimization
We propose a new first-order method for minimizing nonconvex functions with a Lipschitz continuous gradient and Hessian. The proposed method is an accelerated gradient descent with two restart mechanisms and finds a solution where the gradient norm is less than $\epsilon$ in $O(\epsilon^{-7/4})$ function and gradient evaluations. Unlike existing first-order methods with similar complexity bounds, our algorithm is parameter-free because it requires no prior knowledge of problem-dependent parameters, e.g., the Lipschitz constants and the target accuracy $\epsilon$. The main challenge in achieving this advantage is estimating the Lipschitz constant of the Hessian using only first-order information. To this end, we develop a new Hessian-free analysis based on two technical inequalities: a Jensen-type inequality for gradients and an error bound for the trapezoidal rule. Several numerical results illustrate that the proposed method performs comparably to existing algorithms with similar complexity bounds, even without parameter tuning.Open AccessParameter-free accelerated gradient descent for nonconvex minimization
We propose a new first-order method for minimizing nonconvex functions with a Lipschitz continuous gradient and Hessian. The proposed method is an accelerated gradient descent with two restart mechanisms and finds a solution where the gradient norm is less than $\epsilon$ in $O(\epsilon^{-7/4})$ function and gradient evaluations. Unlike existing first-order methods with similar complexity bounds, our algorithm is parameter-free because it requires no prior knowledge of problem-dependent parameters, e.g., the Lipschitz constants and the target accuracy $\epsilon$. The main challenge in achieving this advantage is estimating the Lipschitz constant of the Hessian using only first-order information. To this end, we develop a new Hessian-free analysis based on two technical inequalities: a Jensen-type inequality for gradients and an error bound for the trapezoidal rule. Several numerical results illustrate that the proposed method performs comparably to existing algorithms with similar complexity bounds, even without parameter tuning. - Open Access
Accelerated-gradient-based generalized Levenberg--Marquardt method with oracle complexity bound and local quadratic convergence
Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg--Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle complexity bound, and local convergence under a H\"olderian growth condition. The local convergence results include local quadratic convergence under the quadratic growth condition; this is the first to extend the classical result for least-squares problems to a general smooth composite function. In addition, this is the first LM method with both an oracle complexity bound and local quadratic convergence under standard assumptions. These results are achieved by carefully controlling the damping parameter and solving the subproblems by the accelerated proximal gradient method equipped with a particular termination condition. Experimental results show that the proposed method performs well in practice for several instances, including classification with a neural network and nonnegative matrix factorization.
Open AccessAccelerated-gradient-based generalized Levenberg--Marquardt method with oracle complexity bound and local quadratic convergence
Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg--Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle complexity bound, and local convergence under a H\"olderian growth condition. The local convergence results include local quadratic convergence under the quadratic growth condition; this is the first to extend the classical result for least-squares problems to a general smooth composite function. In addition, this is the first LM method with both an oracle complexity bound and local quadratic convergence under standard assumptions. These results are achieved by carefully controlling the damping parameter and solving the subproblems by the accelerated proximal gradient method equipped with a particular termination condition. Experimental results show that the proposed method performs well in practice for several instances, including classification with a neural network and nonnegative matrix factorization.
- Open Access
- 19 August 2023
- Published by Elsevier in Applied Mathematics Letters
- Vol. 147
Modelling the discretization error of initial value problems using the Wishart distribution
- 19 August 2023
- Published by Elsevier in Applied Mathematics Letters
- Vol. 147
Open AccessModelling the discretization error of initial value problems using the Wishart distribution
- Open Access
- 17 January 2023
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 84 (3) , 833-874
Majorization-minimization-based Levenberg–Marquardt method for constrained nonlinear least squares
A new Levenberg–Marquardt (LM) method for solving nonlinear least squares problems with convex constraints is described. Various versions of the LM method have been proposed, their main differences being in the choice of a damping parameter. In this paper, we propose a new rule for updating the parameter so as to achieve both global and local convergence even under the presence of a convex constraint set. The key to our results is a new perspective of the LM method from majorization-minimization methods. Specifically, we show that if the damping parameter is set in a specific way, the objective function of the standard subproblem in LM methods becomes an upper bound on the original objective function under certain standard assumptions. Our method solves a sequence of the subproblems approximately using an (accelerated) projected gradient method. It finds an $$\varepsilon$$ -stationary point after $$O(\varepsilon ^{-2})$$ computation and achieves local quadratic convergence for zero-residual problems under a local error bound condition. Numerical results on compressed sensing and matrix factorization show that our method converges faster in many cases than existing methods.- 17 January 2023
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 84 (3) , 833-874
Open AccessMajorization-minimization-based Levenberg–Marquardt method for constrained nonlinear least squares
A new Levenberg–Marquardt (LM) method for solving nonlinear least squares problems with convex constraints is described. Various versions of the LM method have been proposed, their main differences being in the choice of a damping parameter. In this paper, we propose a new rule for updating the parameter so as to achieve both global and local convergence even under the presence of a convex constraint set. The key to our results is a new perspective of the LM method from majorization-minimization methods. Specifically, we show that if the damping parameter is set in a specific way, the objective function of the standard subproblem in LM methods becomes an upper bound on the original objective function under certain standard assumptions. Our method solves a sequence of the subproblems approximately using an (accelerated) projected gradient method. It finds an $$\varepsilon$$ -stationary point after $$O(\varepsilon ^{-2})$$ computation and achieves local quadratic convergence for zero-residual problems under a local error bound condition. Numerical results on compressed sensing and matrix factorization show that our method converges faster in many cases than existing methods.