Adaptive coordinate descent (original) (raw)
Adaptive coordinate descent is an improvement of the coordinate descent algorithm to non-separable optimization by the use of . The adaptive coordinate descent approach gradually builds a transformation of the coordinate system such that the new coordinates are as decorrelated as possible with respect to the objective function. The adaptive coordinate descent was shown to be competitive to the state-of-the-art evolutionary algorithms and has the following invariance properties:
| Property | Value |
|---|---|
| dbo:abstract | Adaptive coordinate descent is an improvement of the coordinate descent algorithm to non-separable optimization by the use of . The adaptive coordinate descent approach gradually builds a transformation of the coordinate system such that the new coordinates are as decorrelated as possible with respect to the objective function. The adaptive coordinate descent was shown to be competitive to the state-of-the-art evolutionary algorithms and has the following invariance properties: 1. * Invariance with respect to monotonous transformations of the function (scaling) 2. * Invariance with respect to orthogonal transformations of the search space (rotation). CMA-like Adaptive Encoding Update (b) mostly based on principal component analysis (a) is used to extend the coordinate descent method (c) to the optimization of non-separable problems (d). The adaptation of an appropriate coordinate system allows adaptive coordinate descent to outperform coordinate descent on non-separable functions. The following figure illustrates the convergence of both algorithms on 2-dimensional Rosenbrock function up to a target function value , starting from the initial point . The adaptive coordinate descent method reaches the target value after only 325 function evaluations (about 70 times faster than coordinate descent), that is comparable to gradient-based methods. The algorithm has linear time complexity if update coordinate system every D iterations, it is also suitable for large-scale (D>>100) non-linear optimization. (en) Адаптивный координатный спуск — улучшенный вариант алгоритма координатного спуска для неразделимой оптимизации, использующий технику адаптивного кодирования. Адаптивный координатный спуск последовательно строит преобразования координатной системы так, что новые координаты максимально декоррелированы по отношению к целевой функции. Было показано, что адаптивный координатный спуск конкурентен с передовыми эволюционными алгоритмами и обладает следующими свойствами инвариантности: * инвариантность относительно монотонного изменения функции (масштабирование) * инвариантность относительно ортогональных преобразований пространства поиска (вращения). адаптивное кодирование (b), в основном базирующееся на методе главных компонент (a), используется для расширения метода координатного спуска (c) для решения неразделимых задач оптимизации (d). Адаптация приемлемой координатной системы позволяет методу адаптивного координатного спуска превзойти координатный спуск на неразделимых функциях. Следующий рисунок показывает сходимость обоих алгоритмов для двумерной функции Розенброка до целевого значения функции начиная с точки . Адаптивный координатный спуск достигает целевого значения всего за 325 вычислений функции (примерно в 70 раз быстрее координатного спуска), что сравнимо с методами, основанными на градиентах. Алгоритм имеет линейную сложность по времени, если обновлять систему координат каждые D итераций, и пригоден для нелинейных задач оптимизации большого размера (D>>100). (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Adaptive_Coordinate_Descent_illustration.png?width=300 |
| dbo:wikiPageExternalLink | http://www.loshchilov.com/acid.html |
| dbo:wikiPageID | 36844918 (xsd:integer) |
| dbo:wikiPageLength | 4289 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117727303 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Coordinate_descent dbr:Mathematical_optimization dbr:Gradient_descent dbc:Optimization_algorithms_and_methods dbr:Principal_component_analysis dbr:Rosenbrock_function dbr:CMA-ES dbr:Evolutionary_algorithms dbr:Rosenbrock_methods dbr:Orthogonal_transform dbr:Adaptive_encoding dbr:File:Adaptive_Coordinate_Descent_illustration.png dbr:File:Rosenbrock2D.png |
| dbp:wikiPageUsesTemplate | dbt:Reflist |
| dct:subject | dbc:Optimization_algorithms_and_methods |
| rdf:type | yago:WikicatOptimizationAlgorithmsAndMethods yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Adaptive coordinate descent is an improvement of the coordinate descent algorithm to non-separable optimization by the use of . The adaptive coordinate descent approach gradually builds a transformation of the coordinate system such that the new coordinates are as decorrelated as possible with respect to the objective function. The adaptive coordinate descent was shown to be competitive to the state-of-the-art evolutionary algorithms and has the following invariance properties: (en) Адаптивный координатный спуск — улучшенный вариант алгоритма координатного спуска для неразделимой оптимизации, использующий технику адаптивного кодирования. Адаптивный координатный спуск последовательно строит преобразования координатной системы так, что новые координаты максимально декоррелированы по отношению к целевой функции. Было показано, что адаптивный координатный спуск конкурентен с передовыми эволюционными алгоритмами и обладает следующими свойствами инвариантности: (ru) |
| rdfs:label | Adaptive coordinate descent (en) Адаптивный координатный спуск (ru) |
| owl:sameAs | freebase:Adaptive coordinate descent yago-res:Adaptive coordinate descent wikidata:Adaptive coordinate descent dbpedia-ru:Adaptive coordinate descent https://global.dbpedia.org/id/4LZLY |
| prov:wasDerivedFrom | wikipedia-en:Adaptive_coordinate_descent?oldid=1117727303&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Adaptive_Coordinate_Descent_illustration.png wiki-commons:Special:FilePath/Rosenbrock2D.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Adaptive_coordinate_descent |
| is dbo:wikiPageWikiLink of | dbr:Derivative-free_optimization dbr:List_of_numerical_analysis_topics dbr:Coordinate_descent dbr:Adaptive_algorithm dbr:Rosenbrock_function dbr:Rosenbrock_methods |
| is foaf:primaryTopic of | wikipedia-en:Adaptive_coordinate_descent |
