Advanced Computational Techniques in Science and Engineering

Latest papers

• Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View

  Tong Mao, Jinchao Xu · 4 August 2026

  Traditional approximation theory measures convergence rates in terms of the number of parameters or degrees of freedom. However, practical computation operates under finite precision: parameters must be encoded using a finite number of bits. Therefore, approximation efficiency should be evaluated in…

• Improved generalization bounds for binary linear classification via isoperimetry

  Shogo Nakakita · 7 July 2026

  We examine the concentration of uniform generalization errors around their expectation in binary linear classification problems via an isoperimetric argument. In particular, we establish Poincar\'{e} and log-Sobolev inequalities for the joint distribution of the output labels and the label-weighted …

• Lean Formalization of Generalization Error Bound by Rademacher Complexity and Dudley's Entropy Integral

  Sho Sonoda, Kazumi Kasaura, Yuma Mizuno, Kei Tsukamoto, Naoto Onda · 26 May 2026

  Understanding and certifying the generalization performance of machine learning algorithms -- i.e. obtaining theoretical estimates of the test error from the training error -- is a central theme of statistical learning theory. Among the many complexity measures used to derive such guarantees, Radema…

• Super-fast Rates of Convergence for Neural Network Classifiers under the Hard Margin Condition

  Nathanael Tepakbong, Xiang Zhou, Ding-Xuan Zhou · 6 May 2026

  We study the classical binary classification problem for hypothesis spaces of Deep Neural Networks (DNNs) under Tsybakov's low-noise condition with exponent $q>0$, as well as its limit case $q=\infty$, which we refer to as the \emph{hard margin condition}. We demonstrate that, for a wide range of co…

• Higher Order Approximation Rates for ReLU CNNs in Korobov Spaces

  Yuwen Li, Guozhi Zhang · 24 April 2026

  This paper investigates the $L_p$ approximation error for higher order Korobov functions using deep convolutional neural networks (CNNs) with ReLU activation. For target functions having a mixed derivative of order m+1 in each direction, we improve classical approximation rate of second order to (m+…

• Two-Dimensional Deep ReLU CNN Approximation for Korobov Functions: A Constructive Approach

  Qin Fang, Lei Shi, Min Xu, Ding-Xuan Zhou · 20 April 2026

  This paper investigates approximation capabilities of two-dimensional (2D) deep convolutional neural networks (CNNs), with Korobov functions serving as a benchmark. We focus on 2D CNNs, comprising multi-channel convolutional layers with zero-padding and ReLU activations, followed by a fully connecte…

• Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexity

  Davide Maran, Marcello Restelli · 10 March 2026

  We address the problem of learning an unknown smooth function and its derivatives from noisy pointwise evaluations under the supremum norm. While classical nonparametric regression provides a strong theoretical foundation, traditional kernel-based estimators often incur high computational costs and …

• Lean Formalization of Generalization Error Bound by Rademacher Complexity and Dudley's Entropy Integral

  Sho Sonoda, Kazumi Kasaura, Yuma Mizuno, Kei Tsukamoto, Naoto Onda · 23 February 2026

  Understanding and certifying the generalization performance of machine learning algorithms -- i.e. obtaining theoretical estimates of the test error from a finite training sample -- is a central theme of statistical learning theory. Among the many complexity measures used to derive such guarantees, …

• RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees

  Cristobal Heredia, Pedro Chumpitaz-Flores, Kaixun Hua · 29 October 2025

  Mixed-integer programming (MIP) has emerged as a powerful framework for learning optimal decision trees. Yet, existing MIP approaches for regression tasks are either limited to purely binary features or become computationally intractable when continuous, large-scale data are involved. Naively binari…

• Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations

  Xi He · 28 October 2025

  In the first paper (part I) of this series of two, we introduce four novel definitions of the ODT problems: three for size-constrained trees and one for depth-constrained trees. These definitions are stated unambiguously through executable recursive programs, satisfying all criteria we propose for a…

• Optimal kernel regression bounds under energy-bounded noise

  Amon Lahr, Johannes K\"ohler, Anna Scampicchio, Melanie N. Zeilinger · 27 October 2025