Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Optimization

2,311 missions · 1,728 completed

Missions

Open583Completed1728All2311
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Residuals-based distributionally robust optimization with covariate information 2: Sample Robust and Same-Support ER-DRO Converge at the Rate O_p(n^(−r/2))Research Paper

In many operational problems the decision zzz is taken after observing covariates xxx (weather, calendar, prices) that carry information about an uncertain quantity YYY (demand, yield, return). The target is the conditional stochastic program: minimize E[c(z,Y)∣X=x]\mathbb E[c(z,Y)\mid X=x]E[c(z,Y)∣X=x] over a feasible set Z\mathcal ZZ. Kannan, Bayraksan and Luedtke (Math. Program. 2023)…

9 thms2 active usersReviewed
Complexity TheoryConvex OptimizationMachine Learning·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives II: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(m√(γB²/ε)) Queries on Sums of m Convex γ-Smooth FunctionsResearch Paper

Many problems in machine learning and statistics minimize an average of mmm convex losses, one per data point or per block of data. Incremental methods such as SAG, SVRG, SAGA, SDCA, Finito and Katyusha exploit this finite-sum structure: each step touches one component fif_ifi​ instead of the whole average, and for smooth components the best of them reach accuracy …

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportProbability·Captain: mikedeng1

A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization III: Under a Tight Nominal Measure, f(x) − λd(x̂, x)^p Satisfies the Interchangeability PrincipleResearch Paper

Wasserstein distributionally robust optimization (DRO) replaces the expected loss under a nominal distribution P^\widehat{\mathbb P}P (typically an empirical distribution) by the worst expected loss over all distributions within a given optimal-transport distance of P^\widehat{\mathbb P}P. Its tractability rests on a strong duality theorem that turns a supremum…

7 thms2 active usersReviewed
Algebraic GeometryAnalysis·Captain: mikedeng1

Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 1: A G-Linear Functional Is Integration Against a G-Invariant Measure on K iff Its Symmetrized Localizing Forms Are PSDResearch Paper

Polynomial optimization asks for the minimum f∗f^*f∗ of a polynomial fff over a set K⊆RnK\subseteq\mathbb R^nK⊆Rn cut out by polynomial inequalities. Lasserre's moment relaxation (Lasserre 2001) replaces the minimization over points by a minimization over probability measures on KKK, and then over linear functionals on polynomials that satisfy semidefinite constraints. The…

7 thms2 active usersReviewed
Machine LearningProbability·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 2: Perturbed GD (Variant) Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f/ε²) IterationsResearch Paper

Training a model in machine learning usually means minimizing a nonconvex function f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R with first-order methods. Finding a global minimum of a general nonconvex function is NP-hard, so the classical guarantee for gradient descent (GD), xt+1=xt−η∇f(xt)x_{t+1}=x_t-\eta\nabla f(x_t)xt+1​=xt​−η∇f(xt​), is weaker: with step size η=1/ℓ\eta=1/\ellη=1/ℓ it reaches a point with …

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: mikedeng1

Distributionally Robust Convex Optimization I: Under the Nesting Condition, a Worst-Case Expectation Constraint over a Standardized Ambiguity Set Is Equivalent to a Finite Conic SystemResearch Paper

A constraint E[v(x,z~)]≤w\mathbb E[v(x,\tilde z)] \le wE[v(x,z~)]≤w on a decision xxx requires the distribution of the random vector z~\tilde zz~. In practice that distribution is known only partially: its support, a few moments, or the probability mass of some regions estimated from data. Distributionally robust optimization asks that the constraint hold for every distribution…

7 thms2 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Distributed Algorithms for Aggregative Games on Graphs III: Equal-Stepsize Gossip under Strong Monotonicity, limsup E‖x^k − x*‖² ≤ (α/μ)(2C²N + BC√(2nN)/(1 − √λ))Research Paper

In an aggregative game, each player's decision affects a common quantity, such as total production or total demand. An agent may be able to calculate its own preferred response while lacking direct access to that aggregate. Koshal, Nedić, and Shanbhag study how agents can estimate it by exchanging information only with neighbours on a communication graph.…

13 thms2 active usersReviewed
Algebraic GeometryOperations Research·Captain: mikedeng1

Optimality Conditions and Finite Convergence of Lasserre's Hierarchy II: Off a Proper Zariski-Closed Set of Input Data, the Classical Optimality Conditions Hold at Every Local MinimizerResearch Paper

Lasserre's hierarchy is a sequence of semidefinite relaxations for minimizing a polynomial over a set defined by polynomial equations and inequalities (Lasserre 2001). Under the archimedean condition its optimal values converge to the true minimum, but only asymptotically in general; in practice the hierarchy is often exact at a small relaxation order. J.…

15 thms2 active usersReviewed
Machine LearningProbability·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 1: Perturbed SGD Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f·𝔑/ε²) IterationsResearch Paper

Most training objectives in machine learning are smooth and nonconvex, and they are minimized by stochastic gradient descent (SGD) and its variants. For nonconvex fff the classical guarantee is convergence to an ϵ\epsilonϵ-first-order stationary point, ∥∇f(x)∥≤ϵ\|\nabla f(x)\|\le\epsilon∥∇f(x)∥≤ϵ: Ghadimi and Lan (arXiv:1309.5549) showed that SGD reaches one in …

17 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Robustness May Be at Odds with Accuracy 2: The Unit-Norm Soft-Margin SVM Is >99% Accurate but <1% Robust at ε ≥ 2η, While Adversarial Training Gives Accuracy pResearch Paper

Adversarial training asks a classifier to work even after an input has been changed within a prescribed perturbation budget. Tsipras, Santurkar, Engstrom, Turner, and Mądry studied why the classifier that performs best on ordinary inputs can behave very differently under these changes. Their explicit model separates one reliably predictive feature from many…

10 thms2 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Distributed Algorithms for Aggregative Games on Graphs II: The Gossip Algorithm with Stepsizes 1/Γ_k(i) Converges Almost Surely to the Unique EquilibriumResearch Paper

In an aggregative game, each player's cost depends on its own decision and on the sum of all players' decisions. That form appears in resource sharing, production, and network games: a player may know its own choice while lacking a central feed of the aggregate. A distributed algorithm therefore has to estimate the aggregate through local communication as…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Distributionally Robust Convex Optimization IV: An Absolute Mean Spread Bound Describes Exactly the z̃-Marginals of a Lifted Ambiguity SetResearch Paper

Distributionally robust optimization handles an uncertain parameter z~∈RP\tilde z\in\mathbb R^Pz~∈RP whose distribution is only partly known. A decision must satisfy an expectation constraint for every distribution in an ambiguity set, the set of distributions consistent with the available information. Wiesemann, Kuhn and Sim (Optimization Online preprint 3757, 2013; …

12 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Robust Markov Decision Processes 1: Over s-Rectangular Ambiguity Sets, Robust Policy Improvement Is Solved by a Stationary Randomized Policy and the Fixed Point of the Robust Bellman MapResearch Paper

A Markov decision process (MDP) is evaluated with a transition kernel that, in practice, is estimated from data. The expected total reward of a policy can be very sensitive to small errors in that estimate (Mannor, Simester, Sun and Tsitsiklis, 2007). Robust MDPs address this by letting the kernel range over an ambiguity set and optimizing the worst-case…

14 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

A Modern Introduction to Online Learning XII: Coordinate-Wise Krichevsky–Trofimov Betting Has Parameter-Free Regret ‖u‖₁L∞√(2T ln(1 + e‖u‖∞T/ε)) + dεL∞Textbook

In online convex optimization, a learner makes a prediction before seeing the next loss. A standard regret guarantee often depends on a learning rate chosen using the size of the comparator that will be assessed later. That comparator is unknown during play. Chapter 13 of Orabona's textbook uses coin betting to obtain a bound that adapts to every comparator…

7 thms2 active usersReviewed
Machine LearningProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 2: The Proximal Stochastic Subgradient Method Drives E‖∇φ_{1/ρ̄}(x_{t*})‖² to Zero at Rate O(1/√T)Research Paper

The proximal stochastic subgradient method is the workhorse of large-scale learning: to minimize a regularized population risk φ(x)=f(x)+r(x)\varphi(x) = f(x) + r(x)φ(x)=f(x)+r(x) with f(x)=Eξ∼P[f(x,ξ)]f(x) = \mathbb E_{\xi \sim P}[f(x,\xi)]f(x)=Eξ∼P​[f(x,ξ)], it samples a data point, takes a step against a sampled subgradient of fff, and applies the proximal map of the regularizer rrr. Its sample complexity is classical…

12 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 5: Under μ-Strong Convexity, Model-Based Minimization with β_t = μ(t+1)/2 Reaches Expected Function Gap O(1/(μT))Research Paper

Many problems in statistical learning and signal processing minimize an expectation f(x)=Eξ[F(x,ξ)]f(x)=\mathbb E_\xi[F(x,\xi)]f(x)=Eξ​[F(x,ξ)] plus a regularizer or constraint r(x)r(x)r(x), with access to fff only through samples ξ∼P\xi\sim Pξ∼P. The standard tool is the stochastic (proximal) subgradient method, which replaces fff at the current point by a random linear function. Two other methods use…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Closing the Gap for Makespan Scheduling via Sparsification Techniques: A Feasible Configuration IP Has a Thin Solution, Support at Most 4(d+1)log(4(d+1)T), Complex Configurations Used at Most OnceResearch Paper

Makespan minimization on identical parallel machines, P∥Cmax⁡P\|C_{\max}P∥Cmax​, asks to assign nnn jobs with processing times to mmm machines so that the largest machine load is as small as possible. It is strongly NP-hard, and the question has long been how fast a (1+ε)(1+\varepsilon)(1+ε)-approximate schedule can be found. After rounding and scaling, a guess TTT of the optimal…

7 thms2 active usersReviewed
Convex OptimizationMachine Learning·Captain: mikedeng1

A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic: Explicit Error Bounds for TTSA with a Strongly Convex Outer ObjectiveResearch Paper

Bilevel optimization asks for an outer decision while an inner optimization problem responds to that decision. In hyperparameter selection, for example, the outer objective evaluates a model whose parameters are chosen by a training problem. A two-timescale algorithm updates both levels in one stochastic loop, so its outer step uses an inner solution that…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Information Sharing in Competing Supply Chains with Production Cost Reduction: Under Cournot Competition Both Chains Share Below k_N, Both or Neither Between k_N and k_S, and Neither Above k_SResearch Paper

Retailers observe demand signals (point-of-sale data, local forecasts) that their suppliers do not. Whether a retailer should pass such a signal upstream is a central question of the supply chain information-sharing literature. In a single chain, sharing helps the manufacturer plan, but the retailer may lose from it. Competition between chains adds a second…

12 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear Optimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness III: Adaptive Restarts Take at Most ⌈2C(q+2)/(αβ)⌉ Inner Steps and Converge Linearly on Sharp ProblemsResearch Paper

First order primal–dual algorithms are used when a linear program is too large for a direct factorization or when matrix operations are cheaper than solving a sequence of linear systems. Their basic guarantees often bound an averaged duality gap by a quantity proportional to 1/t1/t1/t after ttt steps. A restart discards the current inner iteration history and…

8 thms2 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Certifying Some Distributional Robustness with Principled Adversarial Training 3: The Softmax Loss of a Smooth Deep Network Has a (√2·β_L(θ)+α_L(θ)²)-Lipschitz Input GradientResearch Paper

Sinha, Namkoong, Volpi and Duchi (arXiv:1710.10571, ICLR 2018) train classifiers against adversarial perturbations by solving a Lagrangian relaxation of a Wasserstein distributionally robust problem. The inner problem, sup⁡z{ℓ(θ;z)−γ c(z,z0)}\sup_z \{\ell(\theta;z)-\gamma\, c(z,z_0)\}supz​{ℓ(θ;z)−γc(z,z0​)}, is strongly concave, and hence solvable by gradient ascent with the paper's certificates,…

9 thms2 active usersReviewed
Probability·Captain: visuddhi

VC Theory for Inventory Policies: Xie–Ma–Xin BoundsResearch Paper

An inventory policy chooses how much stock to order before demand is observed. Its quality is assessed by the holding and backlogging costs it incurs on future demand. A policy chosen to perform well on historical demand can overfit those observations. A useful statistical guarantee therefore controls the difference between historical and future costs…

6 thms2 active usersReviewed
Convex OptimizationInformation TheoryQuantum Information·Captain: mikedeng1

Semidefinite Programming Hierarchies for Constrained Bilinear Optimization I: The Linearly Constrained de Finetti SDP Hierarchy Satisfies Q ≤ SDPₙ ≤ Q + ‖G‖∞·d_B²(d_B+1)·√((2 ln 2) log d_A / n)Research Paper

Many problems in quantum information theory ask for the maximum of a linear functional over pairs of quantum states, one on each of two systems, subject to linear constraints on each state. The best success probability of an approximate quantum error-correcting code of given size is of this form: the encoder and the decoder are quantum channels, their Choi…

17 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear Optimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness II: Fixed-Frequency Restarts Shrink the Distance to the Solution Set by β per Restart on Sharp ProblemsResearch Paper

Linear programs at very large scale are increasingly solved by first-order primal-dual methods, which use only matrix-vector products instead of matrix factorizations. Such methods parallelize well and have a small memory footprint, but on their own they are slow to reach moderate or high accuracy. Applegate, Hinder, Lu and Lubin (arXiv:2105.12715, Math.…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear Optimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness I: The LP Saddle-Point Problem Is 1/(H(K)√(1+4R²))-Sharp on Every Ball W_R(0)Research Paper

First-order primal-dual methods (PDHG, extragradient, ADMM) are the engine of a new generation of large-scale linear programming solvers, such as PDLP, because they need only matrix–vector products with the constraint matrix. Their textbook guarantees for convex–concave saddle-point problems are sublinear, O(1/t)O(1/t)O(1/t) for the averaged iterate, while in practice…

7 thms2 active usersReviewed
PreviousPage 71 of 93Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me