NMNaoki Marumo

Naoki Marumo

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Naoki Marumo has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Complexity and convergence analysis of a single-loop SDCAM for Lipschitz composite optimization and beyond

    by Hao Zhang, Naoki Marumo, Ting Kei Pong, Akiko Takeda

    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

    by Naoki Marumo

    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.

  • Faster computation of nonstabilizerness

    by Hiroki Hamaguchi, Kou Hamada, Naoki Marumo, Nobuyuki Yoshioka


  • Open Access

    Accelerated-gradient-based generalized Levenberg–Marquardt method with oracle complexity bound and local quadratic convergence

    by Naoki Marumo, Takayuki Okuno, Akiko Takeda

    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.


  • Parameter-Free Accelerated Gradient Descent for Nonconvex Minimization

    by Naoki Marumo, Akiko Takeda

    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

    Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians

    by Naoki Marumo, Akiko Takeda

    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 }})$$ O ( H ν 1 2 + 2 ν ε - 4 + 3 ν 2 + 2 ν ) function and gradient evaluations, where $$\nu \in [0, 1]$$ ν ∈ [ 0 , 1 ] and $$H_{\nu }$$ H ν are the Hölder exponent and constant, respectively. This complexity result covers the classical bound of $$O(\varepsilon ^{-2})$$ O ( ε - 2 ) for $$\nu = 0$$ ν = 0 and the state-of-the-art bound of $$O(\varepsilon ^{-7/4})$$ O ( ε - 7 / 4 ) for $$\nu = 1$$ ν = 1 . Our algorithm is $$\nu $$ ν -independent and thus universal; it automatically achieves the above complexity bound with the optimal $$\nu \in [0, 1]$$ ν ∈ [ 0 , 1 ] without knowledge of $$H_{\nu }$$ H ν . 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

    by Naoki Marumo, Akiko Takeda

    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

    by Naoki Marumo, Takayuki Okuno, Akiko Takeda

    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

    Majorization-minimization-based Levenberg–Marquardt method for constrained nonlinear least squares

    by Naoki Marumo, Takayuki Okuno, Akiko Takeda

    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})$$ O ( ε - 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.