座標降下法 （ざひょうこうかほう、英 : Coordinate descent ）とは、関数 の極値を逐次座標方向に最小化して求める最適化アルゴリズム の一種。各反復において座標降下法は座標選択規則に従って座標 あるいは座標ブロックを決定し、選択されていない座標や座標ブロックを固定したままその座標超平面上で厳密あるいは近似的に最小化する。座標方向に直線探索 を行うことで現在の反復点における適切なステップサイズを求めることができる。座標降下法は微分可能・微分不可能な関数両者ともに適用できる解法である。
座標降下法は各反復において一つの（あるいは少数の）変数の最適化問題を解くように、変数の各方向に順番に最小化することで多変数関数
F
(
x
)
{\displaystyle F(\mathbf {x} )}
[ 1]
x
0
=
(
x
1
0
,
…
,
x
n
0
)
{\displaystyle \mathbf {x} ^{0}=(x_{1}^{0},\ldots ,x_{n}^{0})}
k
+
1
{\displaystyle k+1}
x
k
+
1
{\displaystyle \mathbf {x} ^{k+1}}
x
k
{\displaystyle \mathbf {x} ^{k}}
x
i
k
+
1
=
a
r
g
m
i
n
y
∈
R
f
(
x
1
k
+
1
,
…
,
x
i
−
1
k
+
1
,
y
,
x
i
+
1
k
,
…
,
x
n
k
)
{\displaystyle x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^{k},\dots ,x_{n}^{k})}
[ 2] ただし、変数
x
i
{\displaystyle x_{i}}
x
{\displaystyle \mathbf {x} }
n
{\displaystyle n}
i
{\displaystyle i}
すなわち、関数
F
{\displaystyle F}
x
0
{\displaystyle \mathbf {x} ^{0}}
x
0
,
x
1
,
x
2
,
…
{\displaystyle \mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\dots }
各反復において直線探索 を行うことで以下の性質が導かれる:
F
(
x
0
)
≥
F
(
x
1
)
≥
F
(
x
2
)
≥
…
.
{\displaystyle F(\mathbf {x} ^{0})\geq F(\mathbf {x} ^{1})\geq F(\mathbf {x} ^{2})\geq \dots .}
この点列は最急降下法と同様に極値への収束性を持つことが知られている。直線探索 による座標方向への探索が一通り巡回した後でも目的関数の改善がない場合は極値へ収束したとみなせる。
上記の手続きによる各反復は以下のように表される。
連続的微分可能 関数 F での座標降下法は以下の手続きを行う[ 1]
初期ベクトル x
収束あるいは反復の上限回数に達するまで以下を反復:
1 から n での添字 i を選択する。ステップサイズ α を選択する。
xi を xi − α ∂F / ∂xi x )
ステップサイズの選択方法はいくつか知られており、厳密に f (xi ) = F (x )xi を固定した上で F の最小化）、あるいは古典的な直線探索での選択基準に従った方法が挙げられる[ 1]
座標降下法は二つの問題を抱えている。一つ目は目的関数が滑らかな関数 でない場合である。下記の図では目的関数の等高線が滑らかでない場合について、座標降下法の各反復において停留点でない点が求まってしまう例を挙げている。最小化問題に対して座標降下法において現在の反復が点 (−2, −2) であるとすると、次の探索方向として赤い矢印の方向に進むことが考えられるが、どちらの方向に進むことを考えても、この場合目的関数は増大してしまう。この場合座標方向に進まず、二つの探索方向を併せた方向に方向に進むことで目的関数は改善される。下記の図では最適解に収束しない例を紹介したが、ある条件の下では収束性を示すことができる[ 3]
二つ目の問題点として座標降下法の並列化が困難であることが挙げられる。座標降下法では各座標方向に順番に探索し、目的関数を改善することから、大規模な並列化は難しいとされる。近年の研究で座標降下法は各座標方向への目的関数の変化を緩和することによって大規模な並列化を可能にする手法が提案されている[ 4] [ 5] [ 6]
座標降下法は単純な手続きで完結することから実用面においては人気のある解法となっているが、最適化理論に関する研究者の間ではより複雑な解法を注目することが多いことから、ほとんど研究されない解法となっている[ 1] [ 7] [ 8] [ 9] [ 10] 機械学習 における大規模最適化問題に対する応用においても注目されるようになり、特にサポートベクターマシン の訓練時や非負値行列因子分解 において座標降下法を適用した際に、他の解法以上の優位性が示されている[ 11] [ 12] [ 13]
^ a b c d Wright, Stephen J. (2015). “Coordinate descent algorithms”. Mathematical Programming 151 (1): 3–34. arXiv :1502.04759 . doi :10.1007/s10107-015-0892-3 .
^ “Coordinate descent ”. Optimization 10-725 / 36-725 . Carnegie Mellon University (2012年秋). 2025年3月10日閲覧。 ^ Spall, J. C. (2012). “Cyclic Seesaw Process for Optimization and Identification”. Journal of Optimization Theory and Applications 154 (1): 187–208. doi :10.1007/s10957-012-0001-1 . ^ Zheng, J.; Saquib, S. S.; Sauer, K.; Bouman, C. A. (2000-10-01). “Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence”. IEEE Transactions on Image Processing 9 (10): 1745–1759. Bibcode : 2000ITIP....9.1745Z . doi :10.1109/83.869186 . ISSN 1057-7149 . PMID 18262913 . ^ Fessler, J. A.; Ficaro, E. P.; Clinthorne, N. H.; Lange, K. (1997-04-01). “Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction”. IEEE Transactions on Medical Imaging 16 (2): 166–175. doi :10.1109/42.563662 . hdl :2027.42/86021 ISSN 0278-0062 . PMID 9101326 . ^ Wang, Xiao; Sabne, Amit; Kisner, Sherman; Raghunathan, Anand; Bouman, Charles; Midkiff, Samuel (2016-01-01). “High performance model based image reconstruction” . Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming . PPoPP '16. New York, NY, USA: ACM. pp. 2:1–2:12. doi :10.1145/2851141.2851163 . ISBN 9781450340922 . https://zenodo.org/record/895136 ^ Sauer, Ken; Bouman, Charles (1993-02). “A Local Update Strategy for Iterative Reconstruction from Projections” . IEEE Transactions on Signal Processing 41 (2): 534–548. Bibcode : 1993ITSP...41..534S . doi :10.1109/78.193196 . https://engineering.purdue.edu/~bouman/publications/orig-pdf/sp2.pdf . ^ Yu, Zhou; Thibault, Jean-Baptiste; Bouman, Charles; Sauer, Ken; Hsieh, Jiang (2011-01). “Fast Model-Based X-ray CT Reconstruction Using Spatially Non-Homogeneous ICD Optimization” . IEEE Transactions on Image Processing 20 (1): 161–175. Bibcode : 2011ITIP...20..161Y . doi :10.1109/TIP.2010.2058811 . PMID 20643609 . https://engineering.purdue.edu/~bouman/publications/orig-pdf/tip28.pdf . ^ Thibault, Jean-Baptiste; Sauer, Ken; Bouman, Charles; Hsieh, Jiang (2007-11). “A Three-Dimensional Statistical Approach to Improved Image Quality for Multi-Slice Helical CT” . Medical Physics 34 (11): 4526–4544. Bibcode : 2007MedPh..34.4526T . doi :10.1118/1.2789499 . PMID 18072519 . https://engineering.purdue.edu/~bouman/publications/orig-pdf/medphys1.pdf . ^ Canutescu, AA; Dunbrack, RL (2003). “Cyclic coordinate descent: A robotics algorithm for protein loop closure.” . Protein Science 12 (5): 963–72. doi :10.1110/ps.0242703 . PMC 2323867 . PMID 12717019 . https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2323867/ . ^ Hsieh, C. J.; Chang, K. W.; Lin, C. J.; Keerthi, S. S.; Sundararajan, S. (2008). “A dual coordinate descent method for large-scale linear SVM” . Proceedings of the 25th international conference on Machine learning - ICML '08 . pp. 408. doi :10.1145/1390156.1390208 . ISBN 9781605582054 . http://ntu.csie.org/~cjlin/papers/cddual.pdf ^ Hsieh, C. J.; Dhillon, I. S. (2011). Fast coordinate descent methods with variable selection for non-negative matrix factorization (PDF) . Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11. p. 1064. doi :10.1145/2020408.2020577 . ISBN 9781450308137 ^ Nesterov, Yurii (2012). “Efficiency of coordinate descent methods on huge-scale optimization problems” . SIAM J. Optim. 22 (2): 341–362. doi :10.1137/100802001 . http://www.ulouvain.be/cps/ucl/doc/core/documents/coredp2010_2web.pdf .
Bezdek, J. C.; Hathaway, R. J.; Howard, R. E.; Wilson, C. A.; Windham, M. P. (1987), “Local convergence analysis of a grouped variable version of coordinate descent”, Journal of Optimization Theory and Applications (Kluwer Academic/Plenum Publishers) 54 (3): pp. 471–477, doi :10.1007/BF00940196 Bertsekas, Dimitri P. (1999). Nonlinear Programming, Second Edition Athena Scientific, Belmont, Massachusetts. ISBN 1-886529-00-0 .
Luo, Zhiquan; Tseng, P. (1992), “On the convergence of the coordinate descent method for convex differentiable minimization”, Journal of Optimization Theory and Applications (Kluwer Academic/Plenum Publishers) 72 (1): pp. 7–35, doi :10.1007/BF00939948 , hdl :1721.1/3164 Wu, TongTong; Lange, Kenneth (2008), “Coordinate descent algorithms for Lasso penalized regression”, The Annals of Applied Statistics (Institute of Mathematical Statistics) 2 (1): pp. 224–244, arXiv :0803.3876 , doi :10.1214/07-AOAS147 Richtarik, Peter; Takac, Martin (2011-04), “Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function”, Mathematical Programming (Springer) 144 (1–2): pp. 1–38, arXiv :1107.2848 , doi :10.1007/s10107-012-0614-z Richtarik, Peter; Takac, Martin (2012-12), “Parallel coordinate descent methods for big data optimization”, ArXiv:1212.0873 , arXiv :1212.0873
