Source-linked AI summary
Non-Parametric Optimization for Scalable Learning in Stochastic Decision Problems
Mohsen Amidzadeh, Lauri Viitasaari, Mario Di Francesco
TL;DR
Non-parametric optimality conditions for stochastic decisions in time-varying stochastic optimization have received less attention than their deterministic counterparts. The paper develops a Malliavin-based variational framework and SPF, reporting improved performance and scalability against state-of-the-art methods on distribution-drift problems.
Problem
Non-parametric optimality conditions for stochastic decisions in time-varying stochastic optimization have received less attention than deterministic counterparts, despite applications involving distribution drift.
Source: §1 · p. 1Method
The paper uses Malliavin calculus to derive non-parametric optimality conditions and develops the Stochastic Path Follower (SPF), a deep-learning algorithm designed to be insensitive to parameterization dimension.
Source: §1 · pp. 1–2Results
SPF outperforms state-of-the-art methods in performance and computational complexity on least-squares recovery and logistic regression.
Source: §1 · p. 2Takeaways & Limitations
The results highlight SPF's performance and scalability for stochastic optimization problems subject to distributional drift.
Source: §9 · p. 9The work derives necessary conditions; establishing sufficient conditions is left for future research.
Source: §9 · p. 9
Abstract
from arXiv · showhide
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.
1. Introduction
Non-parametric optimality conditions for stochastic decisions in time-varying stochastic optimization have received less attention than their deterministic counterparts. The paper develops a Malliavin-based framework and the Stochastic Path Follower (SPF), reporting better performance and computational complexity than state-of-the-art methods.
1. Introduction
- The work addresses a gap in optimality conditions for stochastic decisions, following extensive research on deterministic decisions and neural-network parameterizations for stochastic ones.The paper situates TV-SO among applications including adaptive control and machine learning under distribution drift.Source: §1 · p. 1
- Malliavin calculus yields non-parametric necessary optimality conditions for stochastic optimization problems with stochastic decisions.The framework focuses on time-varying stochastic optimization, where expected objectives and/or constraints vary over time.Source: §1 · p. 1
- SPF approximates optimal stochastic solutions with a deep-learning procedure designed to be largely insensitive to neural-network parameterization dimension.Table 1 contrasts SPF, whose required SDEs and learning loss do not depend on ϕ, with PDM, for which they do.Source: §1 · p. 2, Table 1 · p. 2
- The experiments report that SPF outperforms state-of-the-art methods in performance and computational complexity on least-squares recovery and logistic regression.The comparison covers two use cases.Source: §1 · p. 2
2. Related Work
The paper places its contribution alongside time-varying deterministic optimization, gradient-based methods for distribution drift, and neural approaches to SDE-driven functions. It treats stochastic decisions over a time horizon as a distinct setting for non-parametric optimality conditions.
2. Related Work
- Time-varying optimization studies parametric problems whose objectives or constraints vary continuously over time, with optimal trajectories represented by a path-differential ODE.The paper presents its stochastic path conditions as a stochastic generalization of these conditions.Source: §2 · p. 2
- The paper frames TV-SO with stochastic decisions as a novel setting and develops conditions characterizing how optimal stochastic paths evolve over time.A diffusion process is used to solve the conditions, yielding a stochastic path-differential equation.Source: §2 · p. 2
- Unlike proximal stochastic gradient, which tracks solutions under distribution drift using iterate averaging, this framework directly targets optimality conditions and derives a structured search direction.The comparison is with PSG for convex optimization problems under distribution drift.Source: §2 · p. 2
- Prior neural SDE approaches optimize finite network weights and do not address joint optimization of a sequence of objectives over an entire time horizon.The paper contrasts these parametric methods with its non-parametric, horizon-wide approach.Source: §2 · p. 2
3. Background
The background introduces path-following for time-varying deterministic optimization and Malliavin calculus tools for analyzing Wiener-driven processes. These tools provide the mathematical context for the paper's stochastic framework.
3.1. Time-Varying Optimization
- Time-varying optimization tracks the sequence of solutions over a horizon by requiring stationarity at every time and solving the resulting path-following ODE.Minimizing an aggregated objective does not generally recover the desired time-indexed solutions because the minimizer can change sign across time.Source: §3.1 · pp. 2–3
3.2. Malliavin Calculus
- Malliavin calculus analyzes sensitivity of stochastic processes to Wiener-process variations, including through a derivative chain rule for smooth functionals.For an adapted, Malliavin-differentiable stochastic integral, the derivative includes its integrand and an integral of the integrand's Malliavin derivative.Source: §3.2 · p. 3
- For Wiener-driven SDEs with measurable coefficients having bounded partial derivatives, the Malliavin derivative is expressed using the stochastic flow and variational SDEs.The flow matrix and its dynamics provide the derivative representation used in the background.Source: §3.2 · p. 3
4. Time-Varying Stochastic Optimization
The paper formulates TV-SO as joint optimization of stochastic decisions over time and derives necessary conditions using Malliavin-based stochastic variational analysis. Enforcing these conditions along stochastic trajectories gives a path-following framework.
4. Time-Varying Stochastic Optimization
- TV-SO jointly optimizes a Malliavin-differentiable stochastic decision process across the horizon for a time-varying performance measure and known stochastic input.The problem's expected objective minimizer may change sign over time, so minimizing an aggregated objective does not generally yield the desired solution.Source: §4 · pp. 3–4
- A simple example shows that allowing a stochastic decision can lower the objective relative to a deterministic decision, while an expected-gradient condition may admit infinitely many solutions.The example's linear stochastic decision has objective value −1.216 versus 0 for the deterministic decision.Source: §4 · p. 4
- For stochastic decisions, the objective is a Wiener functional, so ordinary gradients of the expected objective do not necessarily characterize an optimum.The paper motivates stochastic variational analysis and Malliavin-based perturbations along Wiener-driven paths to obtain non-parametric conditions.Source: §4 · pp. 3–4
- The necessary optimality conditions include an additional Malliavin-based condition for optimality of stochastic paths, analogous to deterministic stationarity with the time derivative replaced by the Malliavin derivative.The conditions apply under the stated adaptedness, Malliavin-differentiability, and square-integrability assumptions.Source: §4 · p. 4
- Enforcing the stochastic optimality conditions at every time yields stochastic path following, the stochastic counterpart of deterministic path following.The framework uses an energy-functional criterion to jointly optimize the decision process across the full horizon.Source: §4 · pp. 4–5
5. Diffusion Process as a Candidate Decision
The section represents the stochastic decision as a diffusion process and reduces finding the optimal probability law to choosing its drift and diffusion functions. It then uses Malliavin derivatives, computed through a stochastic flow, to evaluate the optimality conditions.
5. Diffusion Process as a Candidate Decision
- Finding the optimal probability law is equivalent to finding a diffusion process with optimal drift and diffusion functions.The process is initialized at a given x0 and is subject to bounded-derivative conditions that guarantee a unique solution.Source: §5 · p. 5
- The Malliavin derivative of the chosen diffusion process is the main quantity needed to evaluate the stated optimality conditions.The section motivates a method to compute Dsxt from this dependency.Source: §5 · p. 5
5.1. Computation of Malliavin Derivatives
- The Malliavin derivative Drxt is expressed using the r-to-t stochastic flow Γr,t, which satisfies a linear SDE adapted to the filtration at r.The flow has initial condition Γr,r = I.Source: §5.1 · p. 5
- The stochastic flow and Malliavin derivatives can be simulated recursively with an SDE simulator using the Euler–Maruyama scheme.The algorithm initializes the flow at Γr,r = I and advances it to compute the derivatives.Source: §5.1 · p. 5
6. The Stochastic Path Follower Algorithm
The Stochastic Path Follower (SPF) uses the paper's variational framework to learn diffusion processes whose paths follow stochastic optimal paths. It parameterizes drift and diffusion with neural networks and trains them using Malliavin derivatives and an expected-loss objective.
6. The Stochastic Path Follower Algorithm
- SPF learns neural drift and diffusion functions for a diffusion process, using the variational framework to follow stochastic optimal paths.The framework is independent of parameterization technique, while this algorithm adopts neural networks for the drift and diffusion functions.Source: §6 · p. 5
- SPF's three phases simulate the neural SDE, compute Malliavin derivatives through the stochastic flow, and evaluate the expected loss.The parameter update then uses an Adam-type optimizer on the drift and diffusion parameters.Source: §6 · pp. 5–6
- To obtain an ϵ-stationary point, SPF sets batch size p = 1/(ϵ ϕ), where ϕ is the neural-network parameterization dimension.The convergence guarantee follows the cited results and setup of Theorem 17 in Chen et al. (2022).Source: §6 · p. 6
7. Performance Evaluation
The evaluation benchmarks SPF on stochastic extrapolation and compares it with learning-based PDM and gradient-based PSG on least-squares recovery and logistic regression. SPF performs competitively with PDM in the extrapolation examples and outperforms or matches the baselines on the application problems, with computational efficiency also reported.
7. Performance Evaluation
- The evaluation uses PDM as a learning-based baseline and PSG as a gradient-based baseline for comparisons with SPF.PDM supports joint optimization over the time horizon; PSG tracks optimal decisions under distribution drift using iterate averaging.Source: §7 · p. 6
7.1. Benchmark: Stochastic Extrapolation
- For stochastic extrapolation, the experiments start from a known optimum at t = 0 and use SPF to follow optimal stochastic paths at later times.The benchmark considers expected time-varying objectives and applies the optimality condition to extrapolate into unknown paths.Source: §7.1 · p. 6
- In Exp1 and Exp2, SPF is competitive with or consistent with PDM at lower computational complexity; omitting the Malliavin-based term prevents optimal-solution recovery.The figure reports learning and ablation results for Exp1 and optimal values and stochastic trajectories for Exp2.Source: Figure 1 · p. 7, §7.1 · p. 7
7.2. Least-Squares Recovery
- SPF outperforms PDM and PSG overall on least-squares recovery, with the lowest objective suboptimality among the learning-based and gradient-based approaches.PDM achieves an optimality distance close to SPF, while SPF has the lowest error on objective suboptimality.Source: Figure 2 · p. 8, §7.2 · p. 8
7.3. Logistic Regression
- On logistic regression, SPF achieves better optimality distance than PDM and improves on PSG in objective suboptimality while performing comparably to PDM.The authors attribute SPF’s effectiveness to directly enforcing the optimality condition in its formulation.Source: §7.2 · p. 8, §7.3 · p. 8
8. Scalability
The scalability analysis finds that SPF's runtime is largely insensitive to neural-network parameterization dimension, unlike PDM's. In a high-dimensional least-squares task, SPF also outperforms the gradient-based baseline PSG.
8. Scalability
- SPF's average runtime remains largely unaffected by parameterization dimension ϕ, whereas PDM's runtime depends strongly on ϕ.SPF simulates SDEs of total dimension n + n^2; PDM simulates dimensions n + nϕ.Source: §8 · p. 8, Figure 3 · p. 9
- SPF clearly outperforms PSG on high-dimensional least-squares recovery, while PDM is omitted because of its computational inefficiency.The task uses n = 100 and d = 50.Source: §8 · p. 9, Figure 3 · p. 9
- The scalability analysis concludes that SPF combines computational efficiency with strong overall performance on high-dimensional problems.Source: §8 · p. 9
9. Conclusion
The paper derives non-parametric optimality conditions for time-varying stochastic optimization using Malliavin calculus and proposes a parameterization-insensitive deep-learning algorithm. It identifies sufficient conditions and time-series forecasting as directions for future work.
9. Conclusion
- The work derives non-parametric optimality conditions for time-varying stochastic optimization and proposes a deep-learning algorithm insensitive to parameterization dimension.It compares the method with learning-based and gradient-based state-of-the-art approaches; results indicate performance and scalability advantages under distributional drift.Source: §9 · p. 9
- Future work could establish non-parametric sufficient conditions and extend the framework to applications such as time-series forecasting.Source: §9 · p. 9
A. Preliminaries
- The preliminaries extend Malliavin-calculus integration by parts to the multivariate setting, with the stated interchange justified by square-integrability and Malliavin differentiability.The proof invokes Stein's lemma for zero-mean Gaussian random variables.Source: A. Preliminaries · p. 11
B. Proof of Theorem 4.1
The proof tests optimality by varying the stochastic process along admissible directions that depend on the underlying paths. Requiring the objective's variation to vanish for every such direction yields the necessary conditions.
B. Proof of Theorem 4.1
- The proof chooses variations that depend on the paths of the driving process because the candidate optimal process is adapted to those paths.Source: B. Proof of Theorem 4.1 · p. 11
- Admissible variations combine a deterministic direction k_t with a stochastic variation g_s drawn from the Hilbert space V_t.The stochastic variation is square-integrable over [0, t].Source: B. Proof of Theorem 4.1 · p. 11
- Optimality requires the objective variation to vanish for every admissible direction, jointly yielding the stated expectation conditions through the fundamental lemma of calculus of variations.The derivation uses Theorem A.1 and an identity from Stein's lemma.Source: B. Proof of Theorem 4.1 · p. 12
C. Proof of Proposition 5.1
The appendix verifies the stochastic-flow result, details the parameterized PDM baseline and its setup, and states assumptions and optimality conditions for functional stochastic optimization.
C. Proof of Proposition 5.1
- The Malliavin derivative process is a diffusion adapted to the relevant filtration, and the stochastic flow Γ_{r,t} is adapted to that same filtration.Source: C. Proof of Proposition 5.1 · p. 12
D. Details of the PDM Algorithm
- PDM parameterizes the SDE trajectory and jointly simulates the parametric SDE and its variational SDE to evaluate a parameter-dependent loss.Its loss is the stochastic analogue of the deterministic loss and explicitly depends on the SDE parameters.Source: D. Details of the PDM Algorithm · pp. 12–13
E. Algorithm Setup for Baselines
- The baseline setup uses three hidden layers of 32 neurons, normalization and activation layers, Adam with learning rate [8 × 10^-3, 10^-2], and 400 batches.Source: E. Algorithm Setup for Baselines · p. 13
F. Functional Stochastic Optimization
- Functional stochastic optimization assumes Malliavin-differentiable adapted processes and a twice-continuously-differentiable, square-integrable objective symmetric in its paired arguments.The theorem supplies non-parametric optimality conditions; the proof uses a variational Hilbert space and independent process copies.Source: F. Functional Stochastic Optimization · p. 13
F.1. Probability Law Following
The section formulates probability-law following as a stochastic optimization problem that minimizes average kernelized Stein discrepancy between induced and target laws. SPF outperforms FDM and TruncSig for most tested target laws, with comparable performance for P4.
F.1. Probability Law Following
- The task seeks a diffusion process whose marginal law matches a specified non-stationary target distribution over time.The experiments include time-varying mixture and Gaussian target laws.Source: §F.1 · p. 14
- The objective is average kernelized Stein discrepancy, which measures similarity between the induced law Q and target law P.The objective is minimized over the diffusion process.Source: §F.1 · p. 14
- FDM and TruncSig are learning-based baselines using neural SDEs and scoring rules to learn probability laws of diffusion processes.FDM uses a rule tailored to Markov processes, while TruncSig uses truncated signature kernels.Source: §F.1 · pp. 14–15
- SPF outperforms FDM and TruncSig on most target laws and achieves comparable performance for P4, measured by average KSD (mean ± std).The comparison is reported across five target laws.Source: §F.1 · p. 15, Table 4 · p. 15