Asymptotic Dynamics of Alternating Minimization for Bilinear Regression

• URL: http://arxiv.org/abs/2402.04751v2
• Date: Mon, 26 Aug 2024 17:12:01 GMT
• Title: Asymptotic Dynamics of Alternating Minimization for Bilinear Regression
• Authors: Koki Okajima, Takashi Takahashi,
• Abstract summary: We show that the dynamics of alternating minimization can be described effectively by a two-dimensional dependence in memory of evolution. The theoretical framework developed in this work can be applied to analysis of various iterative algorithms, extending beyond the scope of alternating minimization.
• Score: 2.992602379681373
• 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. This is achieved by employing the replica method to a multi-temperature glassy system which unfolds the algorithm's time evolution. Our results show that the dynamics can be described effectively by a two-dimensional discrete stochastic process, where each step depends on all previous time steps, revealing the structure of the memory dependence in the evolution of alternating minimization. The theoretical framework developed in this work can be applied to the analysis of various iterative algorithms, extending beyond the scope of alternating minimization.

Related papers

• Multi-body dynamic evolution sequence-assisted PSO for interval analysis [0.0]
  This paper proposes a novel interval analysis method, i.e., multi-body dynamic evolution sequence-assisted PSO. By introducing the dynamical evolutionary sequence instead of the random sequence, the proposed method addresses the difficulty HCLPSO faces in covering the search space. The results of the case studies demonstrate that DES-PSO can significantly improve the computational speed of interval analysis.
  arXiv  Detail & Related papers  (2024-09-21T10:17:27Z)
• 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 Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  We show that when emphdone right -- by which we mean using specific insights from optimisation and kernel communities -- gradient descent is highly effective. We introduce a emphstochastic dual descent algorithm, explain its design in an intuitive manner and illustrate the design choices. Our method places Gaussian process regression on par with state-of-the-art graph neural networks for molecular binding affinity prediction.
  arXiv  Detail & Related papers  (2023-10-31T16:15:13Z)
• 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)
• Robust empirical risk minimization via Newton's method [9.797319790710711]
  A new variant of Newton's method for empirical risk minimization is studied. The gradient and Hessian of the objective function are replaced by robust estimators. An algorithm for obtaining robust Newton directions based on the conjugate gradient method is also proposed.
  arXiv  Detail & Related papers  (2023-01-30T18:54:54Z)
• 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)
• 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)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)
• 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.