Stochastic nonconvex optimization is central to training deep networks and LLMs in modern machine learning. We give a black-box reduction from stochastic nonconvex optimization to ordinary static regret minimization in online convex optimization (OCO), addressing the open problem posed by Chen and Hazan (2024). Our reduction maintains a predictable gradient tracker, while a black-box online learner $\mathcal A$ selects a preconditioner that transforms this tracker into the update direction. Given a $β$-smooth function with initial gap at most $M$ and an unbiased gradient oracle with variance bounded by $σ^2$, we bound the expected average squared gradient norm by $O(σ\sqrt{Mβ/T}+\sqrt{Mβ}\mathrm{Reg}_T(\mathcal A)/T+\frac{Mβ}{T})$, where $\mathrm{Reg}_T(\mathcal A)$ is the static regret of $\mathcal A$ against the identity preconditioner. Thus, any OCO oracle with $O(\sqrt T)$ regret recovers the classical $O(T^{-1/2})$ convergence rate. We also prove that the additive variance term cannot be removed: every conversion making a constant number of stochastic-oracle queries per round, whose guarantee is stated through static regret against a comparator that the online learner can play, must contain an additive term of order $σ\sqrt{Mβ/T}$ for sufficiently large $T$. Moreover, for every online learner, our conversion bound is tight up to universal constants. We also extend the framework to nonsmooth nonconvex optimization, still relying only on ordinary static regret, and attain the optimal convergence rate for Goldstein-type stationarity. Finally, we conduct numerical experiments on nonconvex objectives to illustrate how the reduction exploits online-selected preconditioners while using the same stochastic-oracle budget as stochastic gradient descent.
Nan Lu, Ethan Lee, Ruicheng Ao, David Simchi-Levi, Junwei Lu
We study offline inference for the optimal value in reinforcement learning under finite state and action spaces. Two new nuisances are derived as fixed points of a self-induced Bellman equation, in which we approximate the maximum Bellman operator by its softmax correspondence. We propose a debiased estimator through the Neyman orthogonality and establish its asymptotic normality under diverging horizons even when the behavior policy changes with time, as long as the nuisances have the statistical rates that can be achieved by many machine learning methods. We provide a concrete estimating procedure for these nuisances and show they can lead to valid inference. Synthetic experiments validate the numerical performance of our inference method, and we implement it in real-life decision-making problems, including bike repositioning and AI agentic tool use.
LLM-based multi-agent planning delegates operational decisions to specialists that communicate through finite reports. In this research, we study its reliability limits when a coordinator can revisit source records before completing a resource-constrained plan. A useful report can support an immediate decision or direct later reading, so its value depends on how these stages communicate. We derive exact communication and access tradeoffs and prove that two report forms suffice for a broad class of allocation requirements, one favoring immediate resource identification and the other distinguishing absence from unnamed availability. For shared capacity, this reduction permits joint optimization of reporting roles and adaptive reads for a fixed number of source types with unequal workloads and reading costs. Identical specialists can optimally report different facts, and maximizing immediate completion can impose an unbounded recovery cost penalty even with full-record access. We also conduct numerical experiments to quantify the benefits of the proposed joint optimization and show how source access improves language-agent decisions that already use their reports optimally. In particular, an exhaustive evaluation of 207,632 report designs on small allocation instances recovers the predicted joint optima. Our analysis suggests that reliable agent communication should be evaluated by the complete decisions it supports and the cost of finishing its unresolved cases, instead of solely by report length, local prediction accuracy, or immediate task completion, as is often the case in current practice.
Large language model (LLM) distillation can propagate teacher bias under covariate shift when target reward feedback is unavailable. We propose Iterative Calibration and Learning (IterCaL), which alternates source-reward teacher calibration through token-level branching with student learning on target prompts. We prove polynomial convergence in expected average KL to the oracle student, the reference-regularized target-reward maximizer within a potentially misspecified student class; a quantified source-to-target calibration discrepancy gives an explicit additive true-return term. Our separation shows that regularized direct teacher matching retains positive oracle-KL error at its population optimum for every shared reference penalty, even when the teacher is stronger than every student. On the same instance, IterCaL converges to the oracle using source rewards alone.
Yifu Ding, Zixi Chen, Ruicheng Ao, David Simchi-Levi, Thomas Magnanti
The rapid growth of large-scale AI workloads in data centers has placed increasing pressure on power grids in recent years. Since power systems must continuously balance supply and demand, there is growing interest in leveraging data-center workload flexibility as a grid service. We propose a contextual restless multi-armed bandit (CRMAB) framework in which a grid operator requests load reductions without observing internal job-scheduling decisions. Under an index-ability guarantee, each data center or physical machine is modeled as a Markov decision process (MDP) over a cyclic virtual-machine (VM) job queue, with unknown rewards and transition dynamics that are learned online using Thompson sampling and Whittle-index policies. To improve learning under sparse and noisy observations, the framework augments an adaptive Thompson--Whittle (TW) policy with domain-informed transition priors and gated prior mixing. In baseline experiments, the best refined adaptive variant achieves 91.4\% of the oracle reward after 100 rounds and 96.8\% after 1,000 rounds. Across a 16-setting stress test spanning different state-space sizes and levels of contextual feature noise, the best refined variant consistently outperforms the original TW policy with high confidence while remaining competitive with EXP4. A graph-based prior further incorporates data-center hardware constraints, including operating frequency and computing-resource limits. Overall, our results demonstrate the economic potential of data-center flexibility as a grid service and highlight the importance of high-quality, open-source AI workload traces for developing and evaluating such services.