PDE & Relaxed Greedy Algorithmus (RGA)

Worum geht es?

Ziel des Projekts ist die numerische Lösung eindimensionaler Poisson-Probleme mittels Relaxed Greedy Algorithmus (RGA). Die Lösung wird als spärliche Linearkombination aus einem Wörterbuch $ \mathbb{D} $ (z. B. Quadrate von ReLU-Einheiten) aufgebaut. In jedem Schritt wird ein Atom $ g\in\mathbb{D} $ über ein (approximatives) Arg-max der Richtungsableitung gewählt und mit Relaxation upgedatet.

Neben einer Referenz-Implementierung gibt es Debug-Varianten mit ausführlicher Protokollierung (Verläufe von $|\langle g,\nabla\mathcal{R}(u)\rangle|$, $k_1(u_k)$, $L^2$-Fehler sowie Arg-max-Spuren von $w$ und $b$). Zusätzlich wird eine Greedy Line-Search untersucht, die die Schrittweite pro Iteration optimal (eindimensional) bestimmt.

Kurz-Setup (Energie & Wörterbuch)

Energie (Poisson mit Randstrafe): $$\mathcal{R}_\delta(u)=\tfrac12\!\int_0^\pi |u'(x)|^2\,dx-\!\int_0^\pi f(x)\,u(x)\,dx +\tfrac{1}{2\delta}\big(u(0)^2+u(\pi)^2\big).$$
Wörterbuch $ \mathbb{D}=\{\, g_{w,b}(x)=\sigma(w x+b)^2\ :\ w\in W,\ b\in[-\pi,\pi] \,\} $, mit $ \sigma(z)=\max\{z,0\} $. Optional: Normierung in der $H_\delta$-Norm.
Variation-Norm (Budget): $\|v\|_{\mathcal{K}_1(\mathbb{D})}$ misst die „Misch-Sparsity“ relativ zu $ \mathbb{D} $.

RGA – Algorithmus

Greedy-Auswahl (approx. Arg-max): $$g_k\in\arg\max_{g\in\mathbb{D}} \big|\langle g,\nabla\mathcal{R}_\delta(u_{k-1})\rangle\big|.$$
Relaxiertes Update (Budget $M_k$, Schrittweite $\alpha_k$): $$u_k=(1-\alpha_k)u_{k-1}-\alpha_k\,M_k\,g_k.$$
Typische Schedules: $ \alpha_k=\min(1,2/k) $ oder $2/\sqrt{k}$; konstantes oder wachsendes $M_k$.

Code & Dateien

Die Python-Module enthalten Klassen (jeweils mit einer kleinen Dummy-main); die Notebooks führen die Experimente aus und erzeugen die 3×2-Debugplots.

RGA_debug.py: Referenz-RGA mit Arg-max über $w,b$, Logging und 3×2-Plots.
RGA_1d_exact_argmax.py: Variante mit exakter Arg-max-Suche im ReLU$^2$-Dictionary.
RGA_linesearch.py: Greedy Line-Search (direkter Schritt $u\leftarrow u-\lambda_k g_k$ mit $\lambda_k$ aus 1D-Minimum); gleiche Plots.
Notebooks: RGA_exact_debug.ipynb, RGA_linesearch_debug.ipynb, pde_rga_2d_debug.ipynb – Serien S0–S5 (RGA) und S6 (Line-Search).

Installation: virtuelle Umgebung mit requirements.txt anlegen und Notebooks starten.

python -m venv .venv
source .venv/bin/activate    # Windows: .venv\Scripts\activate
pip install -r requirements.txt
jupyter lab                  # oder: jupyter notebook

Numerische Experimente – Kurzüberblick

S0–S5 (klassischer RGA): Variation von Atom-Normierung, Budget $M_k$, Dictionary-Größe und Schrittweiten.

Ohne Normierung kann $k_1(u_k)$ sehr klein bleiben; die effektiven Schritte sind schwach → langsamer oder stagnierender Abfall von $|\langle g,\nabla\mathcal{R}\rangle|$ und $L^2$.
Mit Normierung und ausreichend großem/wachsenden $M_k$ wird die Auswahl stabiler; die beobachtbare Rate wird in der Praxis durch die Quadratur $N$ begrenzt: bei zu kleinem $N$ flacht die $L^2$-Kurve sichtbar ab.
Größeres Wörterbuch (mehr $w$, dichteres $b$) verändert frühe Arg-max-Treffer (sichtbar in den $w,b$-Spuren) und hilft, sofern Budget und Quadratur mithalten.

S6 (Greedy Line-Search): Ersetzt die relaxierte Mischung durch eine direkte Projektion entlang des gefundenen Atoms: $$u_k=u_{k-1}-\lambda_k g_k,\qquad \lambda_k=\arg\min_{\lambda\in\mathbb{R}} \mathcal{R}_\delta(u_{k-1}-\lambda g_k) \ \ (\text{optional }|\lambda_k|\le M_{\mathrm{cap}}).$$ In den Plots: deutlich monotones Sinken von $|\langle g,\nabla\mathcal{R}\rangle|$ und – nach Anlaufphase – klarer $L^2$-Abfall bis nahe an die Quadraturgrenze.

Theorie (Raten & Annahmen)

Unter Konvexität und $K$-Glattheit von $\mathcal{R}$ sowie normbeschränktem, symmetrischem Wörterbuch $ \mathbb{D} $ erreicht der klassische RGA (mit $\alpha_k=\min(1,2/k)$ und Budget $M$) die bekannte $\mathcal{O}(1/n)$-Rate:

$$ \mathcal{R}(u_n)-\inf_{\|v\|_{\mathcal{K}_1(\mathbb{D})}\le M}\mathcal{R}(v) \ \le\ \frac{32\,K\,(C M)^2}{n}. $$

In der diskretisierten Praxis addiert sich der Quadraturfehler (typisch $\mathcal{O}(N^{-1})$ bis $\mathcal{O}(N^{-2})$, je nach Regel) zum Optimierungsfehler. Um eine $\mathcal{O}(1/n)$-Kurve im $L^2$ sichtbar zu halten, sollte $N$ mit $n$ wachsen (heuristisch $N\sim n^2$ für stabile Sichtbarkeit der Rate).

Warum Line-Search hilft

Die Line-Search-Variante bestimmt den besten Schritt entlang $g_k$. Für quadratische PDE-Energien ist das 1D-Minimum explizit: $$ \lambda_k^\star=\frac{\langle g_k,\nabla\mathcal{R}_\delta(u_{k-1})\rangle}{\|g_k\|_{H_\delta}^2}. $$ Damit wird die Energie in jedem Schritt maximal abgesenkt (unter der Richtungswahl), wodurch Stagnation vermieden wird, die bei zu kleinem effektivem Budget und nicht normierten Atomen auftreten kann. Die Greedy-Natur bleibt erhalten; empirisch fällt der Fehler bis zur Diskretisierungsgrenze schneller.

Praxis – was einstellen?

Atom-Normierung: $\|g\|_{H_\delta}=1$ macht Skalen konsistent; ohne Normierung muss $M_k$ groß genug sein.
Budget $M_k$: konstant für Vergleiche; ansteigend, wenn frühe Schritte zu klein sind. Bei Line-Search optional Cap $|\lambda_k|\le M_{\mathrm{cap}}$.
Quadratur: Wähle $N$ so, dass die Optimierungsrate nicht im Rauschen versinkt. Faustregel: $N$ mit $n$ mitwachsen lassen (z. B. $N\sim n^2$).
Dictionary: dichtes $b$-Gitter und mehrere $w$ verbessern die Richtungswahl, solange Budget und Quadratur mithalten.

Grenzen & Ausblick

Die Garantien gelten für konvexe, glatte Ziele (PDE-Energien sind hier günstig). Nichtkonvexe Trainingsziele sind nicht abgedeckt.
Exakter Arg-max ist in 1D für ReLU$^2$ machbar; in höherer Dimension wird die Suche teuer (Heuristiken/Nettoeffekt vs. Kosten abwägen).
Die sichtbare Rate ist quadraturlimitiert; Skalierung $N$ vs. $n$ ist entscheidend.
Ausblick: 2D/3D-Varianten, adaptives Wörterbuch, beschleunigte Arg-max-Suche, und adaptive Quadratur.

Repository

Projekt-Repository: git.numexp.org/ferdinandkruppa/pde-relaxed-greedy

Clone

git clone https://git.numexp.org/ferdinandkruppa/pde-relaxed-greedy.git

Quellen

Siegel, J. W.; Hong, Q.; Jin, X.; Hao, W.; Xu, J.: Greedy Training Algorithms for Neural Networks and Applications to PDEs, arXiv:2107.04466 (rev. 2023). DOI