Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Programming and Computer Software
Erschienen in: Programming and Computer Software 6/2023

01.12.2023

Gradient-Free Algorithms for Solving Stochastic Saddle Optimization Problems with the Polyak–Łojasiewicz Condition

verfasst von: S. I. Sadykov, A. V. Lobanov, A. M. Raigorodskii

Erschienen in: Programming and Computer Software | Ausgabe 6/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper focuses on solving a subclass of stochastic nonconvex-nonconcave black box optimization problems with a saddle point that satisfy the Polyak–Łojasiewicz (PL) condition. To solve this problem, we provide the first (to our best knowledge) gradient-free algorithm. The proposed approach is based on applying a gradient approximation (kernel approximation) to an oracle-biased stochastic gradient descent algorithm. We present theoretical estimates that guarantee its global linear rate of convergence to the desired accuracy. The theoretical results are checked on a model example by comparison with an algorithm using Gaussian approximation.
Vorheriger Artikel Robust Algebraic Connectivity

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Goodfellow, I., Bengio, Y., and Courville, A., Deep Learning, MIT Press, 2016.MATH
2.
Dai, B., et al., SBEED: Convergent reinforcement learning with nonlinear function approximation, Proc. Int. Conf. Machine Learning, 2018, pp. 1125–1134.
3.
Namkoong, H. and Duchi, J.C., Variance-based regularization with convex objectives, Adv. Neural Inf. Process. Syst., 2017, vol. 30.
4.
Xu, L., et al., Maximum margin clustering, Adv. Neural Inf. Process. Syst., 2004, vol. 17.
5.
Sinha, A., et al., Certifying some distributional robustness with principled adversarial training, 2017.
6.
Audet, C. and Hare, W., Derivative-free and blackbox optimization, 2017.
7.
Rosenbrock, H.H., An automatic method for finding the greatest or least value of a function, Comput. J., 1960, vol. 3, no. 3, pp. 175–184.MathSciNetCrossRef
8.
Gasnikov, A., et al., Randomized gradient-free methods in convex optimization, 2022.
9.
Lobanov, A., et al., Gradient-free federated learning methods with l 1 and l 2-randomization for non-smooth convex stochastic optimization problems, 2022.
10.
Gasnikov, A., et al., The power of first-order smooth optimization for black-box non-smooth problems, Proc. Int. Conf. Machine Learning, 2022, pp. 7241–7265.
11.
Bach, F. and Perchet, V., Highly-smooth zero-th order online optimization, Proc. Conf. Learning Theory, 2016, pp. 257–283.
12.
Beznosikov, A., Novitskii, V., and Gasnikov, A., One-point gradient-free methods for smooth and non-smooth saddle-point problems, Proc. 20th Int. Conf. Mathematical Optimization Theory and Operations Research (MOTOR), Irkutsk, Russia, 2021, pp. 144–158.
13.
Akhavan, A., Pontil, M., and Tsybakov, A., Exploiting higher order smoothness in derivative-free optimization and continuous bandits, Adv. Neural Inf. Process. Syst., 2020, vol. 33, pp. 9017–9027.
14.
Polyak, B.T., Gradient methods for the minimisation of functionals, USSR Comput. Math. Math. Phys., 1963, vol. 3, no. 4, pp. 864–878.CrossRefMATH
15.
Łojasiewicz, S., Une propriété topologique des sous-ensembles analytiques réels, Les Equations aux Dérivées Partielles, 1963, vol. 117, pp. 87–89.
16.
Ajalloeian, A. and Stich, S.U., On the convergence of SGD with biased gradients, 2020.
17.
Lobanov, A., Gasnikov, A., and Stonyakin, F., Highly smoothness zero-order methods for solving optimization problems under PL condition, 2023.
18.
Yue, P., Fang, C., and Lin, Z., On the lower bound of minimizing Polyak–Łojasiewicz functions, 2022.
19.
Yang, J., Kiyavash, N., and He, N., Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems, 2020.
20.
Akhavan, A., et al., Gradient-free optimization of highly smooth functions: Improved analysis and a new algorithm, 2023.
21.
Nouiehed, M., et al., Solving a class of non-convex min-max games using iterative first order methods, Adv. Neural Inf. Process. Syst., 2019, vol. 32.
22.
23.
Beckner, W., A generalized Poincaré inequality for Gaussian measures, Proc. Am. Math. Soc., 1989, vol. 105, no. 2, pp. 397–400.MathSciNetMATH
24.
Karimi, H., Nutini, J., and Schmidt, M., Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition, Proc. Eur. Conf. Machine Learning and Knowledge Discovery in Databases (ECML PKDD), Riva del Garda, Italy, 2016, pp. 795–811.
25.
Metadaten
Titel
Gradient-Free Algorithms for Solving Stochastic Saddle Optimization Problems with the Polyak–Łojasiewicz Condition
verfasst von
S. I. Sadykov
A. V. Lobanov
A. M. Raigorodskii
Publikationsdatum
01.12.2023
Verlag
Pleiades Publishing
Erschienen in
Programming and Computer Software / Ausgabe 6/2023
Print ISSN: 0361-7688
Elektronische ISSN: 1608-3261
DOI
https://doi.org/10.1134/S0361768823060063

Weitere Artikel der Ausgabe 6/2023

Programming and Computer Software 6/2023 Zur Ausgabe

OriginalPaper

Robust Algebraic Connectivity

OriginalPaper

On Accelerated Coordinate Descent Methods for Searching Equilibria in Two-Stage Transportation Equilibrium Traffic Flow Distribution Model

OriginalPaper

Adaptive Variant of the Frank–Wolfe Algorithm for Convex Optimization Problems

OriginalPaper

Adaptive Methods for Variational Inequalities with Relatively Smooth and Reletively Strongly Monotone Operators

OriginalPaper

Decentralized Conditional Gradient Method on Time-Varying Graphs

Premium Partner

    Bildnachweise