Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.
Causal Projected Gradient Descent: Online Convex Optimization under DAG-Induced Partial Order Constraints.
2026-08-23
We study the constrained optimization problem where the parameter space Theta subset of R^p is equipped with a partial order induced by a directed acyclic graph (DAG). At each step, a convex loss function is revealed, and the parameter update is restricted to a convex cone of directions compatible with the graph structure. We propose Causal Projected Gradient Descent (CPGD) and prove a regret bound of O(sqrt(omega T)), where omega = omega(G) is the width of the partial order, which can be significantly smaller than the ambient dimension p. Additionally, we analyze the problem of estimating the graph G from a sequence of paired observations using a recursive partial correlation test and establish consistency at rate O(1 / sqrt(n)). A connection is established between the use of historical observations in the estimation procedure and Tikhonov-type regularization in the parameter space, providing a theoretical justification for experience replay in continual learning.
Ссылка для цитирования:
Тишков В. В. 2026. Causal Projected Gradient Descent: Online Convex Optimization under DAG-Induced Partial Order Constraints. PREPRINTS.RU. https://doi.org/10.24108/preprints-3116224
Список литературы
1. R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161-166, 1950.
2. M. Kalisch and P. Bühlmann. Estimating high-dimensional directed acyclic graphs with the PC-algorithm. Journal of Machine Learning Research, 8:613-636, 2007.
3. J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwińska, D. Hassabis, C. Clopath, D. Kumaran, and R. Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114(13):3521-3526, 2017.
4. J. Pearl. Causality: Models, Reasoning, and Inference, 2nd edition. Cambridge University Press, Cambridge, 2009.
5. P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search, 2nd edition. MIT Press, Cambridge, MA, 2000.
6. A. N. Tikhonov and V. Y. Arsenin. Solutions of Ill-Posed Problems. Winston & Sons, Washington, DC, 1977.
7. B. P. Welford. Note on a method for calculating corrected sums of squares and products. Technometrics, 4(3):419-420, 1962.
8. M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928-936, 2003
