In this work, we obtained quality rates of convergence for accelerated first-order methods for minimizing a broad class of functions that generalize the convex case—specifically, quasar convex functions with convex non-smooth inequality constraints. We enhance the Mirror Descent framework by integrating adaptive step sizes from the AdaGrad and Polyak switching subgradient scheme, achieving fast convergence and robustness. Moreover, a generalization to the Online Convex Optimization framework was proposed, obtaining optimality of the methods. Numerical results confirm the practical effectiveness of the proposed methods, especially in problems with high-dimensional or structured geometry. AdaGrad adapts the learning rate for each parameter in proportion to the inverse of the gradient’s variance, leading to key advantages: parameters associated with low-frequency features receive larger learning rates, while those with high-frequency features receive smaller ones. By incorporating Mirror Descent, we leverage a function d that better models the problem’s geometry, avoiding restrictions to the Euclidean norm. This broadens the applicability and effectiveness of the method.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Convergence of First-Order Methods for Quasar Convex Functions

  • O. Santiago Valdivia Viscarra,
  • Fedor Stonyakin

摘要

In this work, we obtained quality rates of convergence for accelerated first-order methods for minimizing a broad class of functions that generalize the convex case—specifically, quasar convex functions with convex non-smooth inequality constraints. We enhance the Mirror Descent framework by integrating adaptive step sizes from the AdaGrad and Polyak switching subgradient scheme, achieving fast convergence and robustness. Moreover, a generalization to the Online Convex Optimization framework was proposed, obtaining optimality of the methods. Numerical results confirm the practical effectiveness of the proposed methods, especially in problems with high-dimensional or structured geometry. AdaGrad adapts the learning rate for each parameter in proportion to the inverse of the gradient’s variance, leading to key advantages: parameters associated with low-frequency features receive larger learning rates, while those with high-frequency features receive smaller ones. By incorporating Mirror Descent, we leverage a function d that better models the problem’s geometry, avoiding restrictions to the Euclidean norm. This broadens the applicability and effectiveness of the method.