1 座標降下法の概要
1.1 定義と基本アイデア
1.1.1 変数を固定して一部を最適化する考え方
座標降下法は、最適化問題に含まれる多数の変数のうち、ある座標（あるいは少数の座標）だけを動かし、残りの変数は固定したうえで、その部分に関する最適化を反復的に行う手法である。全変数を同時に更新せず、部分問題を解くことで全体の目的関数を下げていく点に特徴がある。
この構成により、各反復で必要になる計算が単純化される場合がある。たとえば、目的関数が「特定の変数を固定すると、残りの変数の効果が解析的に整理できる」形になっていると、更新が高速に実装できる。
1.1.2 逐次更新と同時更新
更新方式には、(1)逐次更新と(2)同時更新がある。(1)逐次更新では、ある座標を更新した直後に、その新しい値を用いて次の座標の更新を計算する。結果として、反復の中で情報が順次反映されやすく、実務で収束が速くなることがある。
(2)同時更新では、反復開始時点の変数値を基準に各座標の更新量を計算し、まとめて反映する。理論解析や実装の見通しがよい場合がある一方、逐次更新より進みが鈍くなる局面もある。
1.2 数学的定式化
1.2.1 目的関数と変数ベクトルの設定
最適化対象を、ベクトル \(x\in\mathbb{R}^n\) に対する目的関数 \(f(x)\) とする。座標降下法では、反復 \(k\) における現在の推定値 \(x^{(k)}\) から出発し、次の反復の値 \(x^{(k+1)}\) を、座標成分に関する部分最小化で決める。
典型的には、目的関数は滑らかである場合も、非滑らか成分を含む場合もある。非滑らか性は、絶対値に基づく正則化などで現れ、そこで座標ごとの最小化が重要になる。
1.2.2 座標ごとの更新ルール
座標 \(i\) に関して、他の成分 \(x_{-i}\) を固定したときの1変数目的関数 \(g_i(t)=f(x_1,\dots,x_{i-1},t,x_{i+1},\dots,x_n)\) を考える。座標降下法の基本更新は \[ x_i^{(k+1)} \in \arg\min_{t} g_i(t) \] として、座標 \(i\) の値を最小化する \(t\) に置き換えることに相当する。
解析解が得られる場合、更新は閉形式になる。得られない場合は、数値的に部分最小化を行う。逐次更新では、この更新で得られた新しい \(x_i^{(k+1)}\) を次の座標計算に直ちに反映する。
1.3 座標降下法が扱う代表的問題
1.3.1 制約なし最適化
制約なしの枠組みでは、目的関数のみを考え、通常は \(x\in\mathbb{R}^n\) 上で最小化する。最も単純な例は、二次形式の損失に正則化を加えた形であり、座標ごとの部分最小化が容易になることがある。
さらに、非滑らかな正則化を含む場合でも、座標ごとの最適化が形を保てると、座標降下法は計算上の利点を持つ。特にスパース性を促す正則化が組み合わさると、座標ごとの更新が“スクリーニング”として作用しやすい。
1.3.2 制約付き最適化（簡約された形の扱い）
制約付きでは、制約集合 \(C\) を満たす \(x\) を探す必要がある。代表的な扱い方として、(1)制約により問題を同値変形して、実質的に自由変数が少ない形に落とす、(2)座標更新の後に射影を行う、(3)制約を正則化やペナルティとして吸収する、などがある。
「簡約された形」での扱いとは、制約に応じた変数変換や、独立に更新できる座標構造へ整理したうえで、座標ごとの部分問題を解ける状態にすることを指す。こうした整形が可能なとき、座標降下法は制約付きでも比較的実装しやすい。
2 アルゴリズム設計の要点
2.1 更新戦略
2.1.1 更新順序の選択
座標降下法の性能は、更新順序の設計に影響される。代表例として、(1)固定順・巡回順・ランダム順が挙げられる。
固定順では、座標番号の小さい順など一定の順序で更新する。巡回順は、反復のたびに順序を回すなどして偏りを減らす考え方である。ランダム順では、毎回の反復で更新対象の座標を確率的に選ぶ。一般に、ランダム化は局所的な停滞を抑える効果が期待される一方、結果のばらつき管理が必要になる。
2.1.2 ブロック座標降下法
座標単位ではなく、複数の座標を一つの“ブロック”としてまとめて更新するのがブロック座標降下法である。これにより、相互に強く結び付いた変数を同時に扱えるため、部分最小化がより適切な方向へ進む場合がある。
ブロックの設計は問題依存であり、たとえば共通の特徴量群や、モデル構造に沿った変数分割が自然な選択になる。各ブロックで解く部分問題が過度に重くならない範囲で、更新の質と計算量のバランスをとることが重要である。
2.1.3 部分最適化の方法（解析解・数値解）
座標ごとの最小化は、解析解があるならそれを採用するのが望ましい。解析解がある状況では、更新が高速であり、数値誤差も抑えやすい。
一方、解析解が難しい場合は、数値的に部分問題を解く。たとえば一変数の最小化に落とせる場合は、二分法やニュートン法などが利用できる。近似更新を採用する場合は、目的関数の低下が保証される設計（ラインサーチや停止判定）を同時に考える必要がある。
2.2 初期値と停止条件
2.2.1 初期値の影響
座標降下法は反復型であるため、初期値が結果に影響を与える。目的関数が凸であれば、最適解への収束性が理論的に扱いやすくなり、初期値の役割は比較的小さくなることがある。非凸の場合は、初期値に応じて到達する定常点が異なる可能性があり、初期化戦略が重要になる。
実務では、別手法で得た粗い推定値を初期にする、あるいはデータ正規化に合わせて初期スケールを調整するなどの工夫が行われる。
2.2.2 停止基準（目的関数低下・勾配・変化量）
停止条件は、反復をどこまで進めるかを決める要素である。代表的には、(1)目的関数の低下が十分小さい、(2)勾配のノルムが閾値以下、(3)変数ベクトルの変化量が閾値以下、などがある。
座標降下法では、全成分の更新を毎回完全に行わない構成もあり得る。その場合、停止判定に使う指標が“更新された部分”に偏らないよう、実装上の定義を明確にすることが必要になる。
2.2.3 計算量と反復回数の見積もり
計算量は、反復あたりの計算コストと、必要反復回数の積として捉える。反復あたりコストは、部分最小化の手間、目的関数値や勾配情報の再計算有無、前計算の有無に依存する。
反復回数の見積もりは理論上の収束率に基づく場合もあるが、現実には目的関数の形状やスケーリングの影響が大きい。実務上は、少数のテスト実行から経験的に閾値を調整する運用が多い。
2.3 ステップサイズと正則化
2.3.1 逐次最小化とステップサイズの関係
座標降下法の基本形では、各座標で“その座標に関する最小化”を行うため、勾配法のような固定ステップサイズは必須ではないことが多い。つまり更新は、座標方向への移動量が部分最小化によって決まる。
ただし、解析解を使わず数値的に近似最小化を行う場合、または正則化や制約により厳密最小化が難しい場合には、実質的なステップ制御が必要になることがある。ラインサーチや減衰率を組み込む設計が、その役割を担う。
2.3.2 適切な正則化（例：L1・L2）の役割
正則化は過学習の抑制や、推定の安定化に寄与する。L2正則化は滑らかな抑制として働き、解の安定性や数値条件の改善に関連することが多い。L1正則化はスパース性を促す性質があり、座標更新の形を特定の“閾値処理”へ結び付けられる場合がある。
正則化係数の選択は、解の品質とスパース性のトレードオフを決める。座標降下法では、この係数が部分最小化の難易度や更新の性質に直接影響するため、検証データでの調整やパス探索（係数を連続的に変える）と組み合わせることが多い。
3 収束性と理論的性質
3.1 凸問題における収束
3.1.1 強凸性と一意解
目的関数が強凸である場合、最適解は一意になり、最小化の進行に関する理論が整いやすい。座標降下法では、座標ごとの部分最小化を行うことで目的値が下がり、誤差が縮小する方向へ進むことが期待される。
強凸性は、誤差と目的関数差の関係を与えるため、収束の議論に適した枠組みになる。結果として、停止条件に基づく実務的な終了も設計しやすい。
3.1.2 リプシッツ連続性等の条件
凸最適化の収束解析では、勾配や関数の変化が“飛びにくい”性質を仮定することがある。代表例として、勾配がリプシッツ連続であるといった条件が挙げられる。これは、目的関数の曲率や座標方向の振る舞いを制御し、更新による下限評価や減少量の見積もりを可能にする。
座標ごとの更新では、各座標に対する“滑らかさ”の違いが現れるため、しばしば座標ごとの定数を用いた解析が行われる。これにより、更新順序やブロック構造が性能に影響する理由が理論化される。
3.2 非凸問題への拡張
3.2.1 定常点への収束の考え方
非凸では、一般に大域的最小値へ到達する保証を得にくい。その代わりに、反復が極小や鞍点を含む“定常点”へ近づくという見方が中心になる。座標降下法では、各座標に対する局所最小化が行われるため、全体としての停滞条件が満たされる方向へ進むと考えられる。
ただし、非凸の定義域や非滑らか性の扱いによって、定常点の意味は変わり得る。サブグラディエントや一般化された勾配の概念を使う場合もある。
3.2.2 実務での挙動と理論のギャップ
理論はしばしば仮定が強く、実務の目的関数はそれを満たさないことがある。にもかかわらず、座標降下法が良い解を与えるケースは多い。ギャップの要因として、近似更新、有限精度計算、目的関数の実データ特有の性質などが挙げられる。
実務では、理論に頼り切らず、目的関数の低下傾向や推定の安定性をモニタリングしながら運用することが一般的である。
3.3 収束速度の指標
3.3.1 反復ごとの進み方（単調性・加速の有無）
収束速度は、反復回数と目的関数差（または変数誤差）の関係で議論されることが多い。凸であれば目的値が単調に下がる設計を取れる場合があり、その単調性が性能指標に直結する。
一方、加速の要素は状況により異なる。座標降下法の基本形は単純だが、更新順序の設計や、近似を含む場合の再評価などによって、実際の減少は理論曲線より速く見えることも遅く見えることもある。
3.3.2 実装依存要因（近似更新・近傍問題）
収束速度は、部分最小化をどれだけ厳密に行ったかに依存する。近似更新では、座標ごとの最適化が完全に達成されないため、理論上の減少保証が弱まることがある。
また、部分問題を近傍領域に限定して解く設計（信頼領域的な考え方や、制約に合わせた簡約化）では、更新が適切に機能すれば進みが安定し、逆に領域選定が不適切だと停滞しやすい。これらは実装上の選択が収束挙動に直結する例である。
4 実装と応用
4.1 実装上の工夫
4.1.1 値の再利用（前計算と更新効率）
座標降下法では、各反復で目的関数の計算や中間量の更新が必要になる。そこで、行列積や集計量などの中間値を保持し、座標更新の影響分だけを更新することで計算効率を高める方法が使われる。
この“差分更新”は、疎性や構造がある場合に特に効果的である。再計算を避けることで反復あたりのコストが下がり、全体の実行時間が短縮される。
4.1.2 スパースデータの扱い
データが疎である場合、更新対象の座標に関連する要素だけを用いて計算する設計が有利になる。たとえば回帰の設計行列が疎なら、座標ごとの更新に必要な積を疎行列演算で行える。
加えて、更新順序を設計行列の疎パターンに合わせると、アクセス効率が向上する。結果として、同じ収束回数でも計算時間が大きく変わり得る。
4.1.3 数値安定性（スケーリング、条件数）
数値安定性は最適化の実装品質に直結する。特徴量のスケーリングは重要で、スケールが極端に異なると座標方向の曲率が偏り、部分最小化の誤差や収束の遅れが起こりやすくなる。
また、条件数が大きい問題では誤差の蓄積が目立つことがある。適切な正則化、倍精度の使用、停止判定の設計などが、実際の安定性に寄与する。
4.2 代表的な応用分野
4.2.1 回帰・推定（正則化付き回帰）
正則化付き回帰では、目的関数に損失と正則化が組み合わさる。座標降下法は、L1やL2の正則化を含む設計と相性がよく、座標ごとの更新が実装上の手続きとして組み立てやすい。
そのため、特徴量選択を促す推定や、ノイズに対する頑健性の確保といった目的に応用される。モデルの解釈性と計算効率の両立が求められる場面で利用される。
4.2.2 行列分解・分解学習
行列分解や分解に基づく学習では、変数が行列として現れるが、しばしば要素やブロックに分けて更新できる構造がある。座標降下法を拡張して、行列の成分あるいは低次元表現の一部を固定し、残りを最小化する形に落とすことで反復最適化が可能になる。
ブロックとして更新する設計は、行列内の相関を取り込みやすく、局所的な改善が全体の誤差低減につながることがある。
4.2.3 機械学習での最適化サブ問題
機械学習モデルの学習では、全体の最適化問題を一括で解くより、内部でサブ問題として座標更新を繰り返す構成が多い。たとえば、交互最適化の一段として座標降下法を使うことがある。
このとき重要なのは、サブ問題の目的関数がその更新に適した形を持つか、非凸性や非滑らか性の扱いが破綻しないかである。適切な正則化や簡約化がある場合、実装は比較的単純になる。
4.3 他手法との比較
4.3.1 勾配法・準ニュートン法との違い
勾配法や準ニュートン法は、全変数を同時に動かす方向性に基づいて更新することが多い。座標降下法は、変数の一部に限定して最小化するため、部分問題の構造を活かしやすい。
また、勾配法ではステップサイズや学習率の調整が性能に影響しやすいのに対し、座標降下法の基本形は部分最小化で更新量が決まりやすい。ただし、数値近似や制約処理を含む場合は、結局どこかで制御パラメータが必要になることがある。
4.3.2 ADMMや近接勾配法との関係
ADMM（交方向の分解）や近接勾配法は、正則化や制約を扱うための代表的な枠組みである。座標降下法と近接の考え方が似る場面として、非滑らか正則化の取り扱いが挙げられる。
ただし、座標降下法は“座標方向での部分最小化”が中心であり、ADMMのように複数の変数分割と双対更新を明示的に行うとは限らない。結果として、実装の部品構成や理論の適用範囲は異なる。
4.3.3 使い分けの判断基準
使い分けの判断は、目的関数の構造、スケール、更新の容易さに依存する。座標ごとの部分最小化が解析的に簡単、あるいは疎な計算が活きる場合は、座標降下法が有利になりやすい。
一方で、座標ごとの部分最小化が重い、あるいは強い相関によりブロック設計なしでは効きが弱い場合は、準ニュートン法や近接勾配法のほうが適することがある。経験的には、同じデータと評価指標で短い比較実験を行うことが実務的である。