Non-Parametric Optimization for Scalable Learning in Stochastic Decision Problems

Mohsen Amidzadeh; Lauri Viitasaari; Mario Di Francesco

cs.LGOct 16, 2026

Non-Parametric Optimization for Scalable Learning in Stochastic Decision Problems

Authors: Mohsen Amidzadeh, Lauri Viitasaari, Mario Di Francesco

Organizations: Department of Computer Science, Aalto University, Finland · Department of Information and Service Management, Aalto University, Finland

Abstract

Stochastic optimization (SO) plays a central role in decision-making under uncertainty. Among SO problems, time-varying stochastic optimization (TV-SO) is particularly important due to its applications in adaptive control and machine learning. Non-parametric approaches have been proposed for time-varying deterministic optimization; however, they have not been developed for their stochastic counterparts. This work addresses that gap by developing a stochastic variational framework based on Malliavin calculus. This framework yields non-parametric optimality conditions for SO problems with stochastic decisions and supports the design of a scalable deep-learning algorithm that is insensitive to the parameterization dimension. This algorithm, called the Stochastic Path Follower (SPF), is applied to two important problems under distribution drift, namely least-squares recovery and logistic regression. Experimental results show that the proposed approach outperforms state-of-the-art learning-based and gradient-based methods in both performance and scalability.

Figures & tables

Algorithm	Dimension of	SDEs and learning loss
Algorithm	required SDEs	explicitly depend on $\phi$
SPF (ours)	$n+n^{2}$	No
PDM	$n+n$ $\phi$	Yes

Table 1: Comparison of the SPF and PDM algorithms, where

n

denotes the dimension of the decision variable and

\phi

is the parameterization dimension. For SPF, both the required SDEs and the learning loss do not depend on

\phi

, while they do for PDM.

Problem	Condition
TV-O	$\nabla_{\textbf{x}}^{2}f\>{\color[rgb]{0,0,0.8}\frac{d\textbf{x}_{t}}{dt}}\hskip 7.0pt+{\color[rgb]{0,0.39,0}\frac{\partial}{\partial t}}\hskip 3.0pt\nabla_{\textbf{x}}f\hskip 23.0pt=\textbf{0}$
TV-SO	$\mathbb{E}\left\{\nabla_{\textbf{x}}^{2}f\>{\color[rgb]{0,0,0.8}D_{s}\textbf{x}_{t}}+{\color[rgb]{0,0.39,0}\nabla_{\bm{\xi}}}\nabla_{\textbf{x}}f\>{\color[rgb]{0.55,0,0}D_{s}\bm{\xi}}\right\}=\textbf{0}$

Table 2: Comparison of optimality conditions of TV-O ( 1 ) and TV-SO ( 4 ) problems.

Panel of Figure 1 — Figure 1: 1(a) Learning performance and ablation results for problem Exp1 at $t=1$ for the SPF and PDM methods; the ablation curves are obtained by omitting the Malliavin-based term in Eq. 11 . 1(b) Optimal values for each $t\in[0,1]$ in problems Exp1 and Exp2. Non-degenerate optimal stochastic trajectories obtained by SPF in problem Exp2 for all $t\in[0,1]$ for 1(c) $x_{t,1}$ and 1(d) $x_{t,2}$ .

Problem	SPF (ours)	PDM
Scalar TV-SO (Exp1)	$<1$	9
Constrained TV-SO (Exp2)	$<1$	41

Table 3: Average runtime per update step (in seconds).

Panel of Figure 2 — Figure 2: 2(a) The optimality distance $\mathbb{E}\|\textbf{x}_{t}-\textbf{x}_{t}^{*}\|^{2}$ and 2(b) the objective suboptimality $\mathbb{E}|f(\textbf{x}_{t})-f(\textbf{x}_{t}^{*})|$ for the considered approaches on the least-squares recovery problem in Section 7.2 . 2(c) The optimality distance $\mathbb{E}\|\textbf{x}_{t}-\textbf{x}_{t}^{*}\|^{2}$ and 2(d) the objective suboptimality $\mathbb{E}|f(\textbf{x}_{t})-f(\textbf{x}_{t}^{*})|$ for the considered approaches on the logistic regression problem in Section 7.3 .

Panel of Figure 3 — Figure 3: 3(a) Average runtime on the least-squares recovery problem for SPF and PDM. 3(b) - 3(c) Performance of SPF on a high-dimensional least-squares recovery task compared with the gradient-based baseline method, PSG.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Model	$\mathbb{P}_{1}$	$\mathbb{P}_{2}$	$\mathbb{P}_{3}$	$\mathbb{P}_{4}$	$\mathbb{P}_{5}$
SPF ( ours )	0.04 $\pm$ 0.01	0.037 $\pm$ 0.004	0.02 $\pm$ 0.005	0.018 $\pm$ 0.005	0.011 $\pm$ 0.003
FDM	0.08 $\pm$ 0.015	0.051 $\pm$ 0.008	0.028 $\pm$ 0.015	0.016 $\pm$ 0.003	0.015 $\pm$ 0.005
TruncSig	0.08 $\pm$ 0.01	0.16 $\pm$ 0.022	0.07 $\pm$ 0.015	0.22 $\pm$ 0.05	0.12 $\pm$ 0.02

Appendix

Table 4: Average KSD (mean

\pm

std) for the law-following problems with

\mathbb{P}_{i}

defined in Section Section F.1 . Comparison of our SPF algorithm against SOTA methods (FDM and TruncSig). SPF outperforms SOTA for most of the considered laws

\mathbb{P}_{i}

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 210 papers

Clipping the Price of Adaptivity at the Tail
Jun 21, 2026Itai Kreisler, Yair Carmon, Oliver HinderStochastic Optimization Stochastic Optimization Convergence
Tel Aviv University · University of Pittsburgh
Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization
Mar 13, 2026Noel Smith, Andrzej RuszczynskiStochastic Optimization Stochastic Approximation
Department of Management Science and Information Systems, Rutgers University
Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
May 9, 2026Zhirayr Tovmasyan, Artavazd Maranjyan, Peter RichtárikStochastic Optimization Distributed Optimization
KAUST

Jun 21, 2026J/K move · Enter open · S save

Clipping the Price of Adaptivity at the Tail

Itai Kreisler, Yair Carmon, Oliver Hinder

Tel Aviv University · University of Pittsburgh

Stochastic Optimization Stochastic Optimization Convergence

Open paper AskPDF arXiv

Adaptive stochastic convex optimization (SCO) methods face a fundamental ``price of adaptivity'' barrier: under the standard set of assumptions, they cannot efficiently adapt to large uncertainty in both the initial distance to optimality and the Lipschitz constant. We circumvent this barrier by requiring a small amount of additional structure common to many learning problems. Specifically, we assume that the objective decomposes into a model and a loss function, enabling us to intervene by modifying the model's output before it passes to the loss function. Under this assumption, we design a method that clips the learned model output in tail events where it deviates too much from the output of a fixed reference model. Our method matches the optimal bounds for known-parameter SCO up to logarithmic factors in the uncertainty in the distance and Lipschitz parameters, thus efficiently adapting to large uncertainty in both.

Abstract

Stochastic Optimization

Explore similar work

Clipping the Price of Adaptivity at the Tail

Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction