Asymptotic Dynamics of Alternating Minimization for Non-Convex
Optimization
- URL: http://arxiv.org/abs/2402.04751v1
- Date: Wed, 7 Feb 2024 11:09:10 GMT
- Title: Asymptotic Dynamics of Alternating Minimization for Non-Convex
Optimization
- Authors: Koki Okajima and Takashi Takahashi
- Abstract summary: This study investigates the dynamics of alternating non-linear function with normally distributed cos.
We employ the replica dependency from statistical physics in a multistep approach to precisely trace the dependencys evolution.
- Score: 3.5353632767823506
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This study investigates the asymptotic dynamics of alternating minimization
applied to optimize a bilinear non-convex function with normally distributed
covariates. We employ the replica method from statistical physics in a
multi-step approach to precisely trace the algorithm's evolution. Our findings
indicate that the dynamics can be described effectively by a two--dimensional
discrete stochastic process, where each step depends on all previous time
steps, revealing a memory dependency in the procedure. The theoretical
framework developed in this work is broadly applicable for the analysis of
various iterative algorithms, extending beyond the scope of alternating
minimization.
Related papers
- Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms [4.389938747401259]
This paper addresses second-order optimization for estimating the minimizer of a convex function written as an expectation.
A direct recursive estimation technique for the inverse Hessian matrix using a Robbins-Monro procedure is introduced.
Above all, it allows to develop universal Newton methods and investigate the efficiency of the proposed approach.
arXiv Detail & Related papers (2024-01-15T13:58:30Z) - Stochastic Nonlinear Control via Finite-dimensional Spectral Dynamic
Embedding [22.946517604055735]
This paper presents an approach, Spectral Dynamics Embedding Control (SDEC), to optimal control for nonlinear systems.
We use an infinite-dimensional feature to linearly represent the state-action value function and exploits finite-dimensional truncation approximation for practical implementation.
arXiv Detail & Related papers (2023-04-08T04:23:46Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets.
We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
arXiv Detail & Related papers (2023-02-24T18:41:48Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings.
We exploit a warm-start strategy to amortize the estimation of the exact gradient.
By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
arXiv Detail & Related papers (2021-11-29T15:10:09Z) - A theoretical and empirical study of new adaptive algorithms with
additional momentum steps and shifted updates for stochastic non-convex
optimization [0.0]
It is thought that adaptive optimization algorithms represent the key pillar behind the of the Learning field.
In this paper we introduce adaptive momentum techniques for different non-smooth objective problems.
arXiv Detail & Related papers (2021-10-16T09:47:57Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure.
We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
arXiv Detail & Related papers (2021-06-09T08:05:36Z) - A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
We introduce variational which allow us to derive different methods for optimization.
We derive two families of optimization methods in one-to-one correspondence.
The preservation of symplecticity of autonomous systems occurs here solely on the fibers.
arXiv Detail & Related papers (2021-06-04T20:21:53Z) - A Dynamical Systems Approach for Convergence of the Bayesian EM
Algorithm [59.99439951055238]
We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based.
The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM)
We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
arXiv Detail & Related papers (2020-06-23T01:34:18Z) - Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
empirical optimization is central to modern machine learning, but its role in its success is still unclear.
We show that it commonly arises in parameters of discrete multiplicative noise due to variance.
A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
arXiv Detail & Related papers (2020-06-11T09:58:01Z) - Generalized Kernel-Based Dynamic Mode Decomposition [0.0]
We devise an algorithm based on low rank constraint optimization and kernel-based computation that generalizes a recent approach called " Kernel-based dynamic mode decomposition"
This new algorithm is characterized by a gain in approximation accuracy, as evidenced by numerical simulations, and in computational complexity.
arXiv Detail & Related papers (2020-02-11T13:50:00Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.