Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Convex Optimization

746 missions · 569 completed

Missions

Open177Completed569All746
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Minimizing Finite Sums with the Stochastic Average Gradient: SAG with Step 1/(16L) Has E[g(x̄ᵏ)] − g(x*) ≤ (32n/k)C₀, and Rate (1 − min{μ/(16L), 1/(8n)})ᵏC₀ if g Is μ-Strongly ConvexResearch Paper

Many problems in statistics and machine learning minimize a finite sum: an average of nnn smooth convex losses, one per data point, often plus a strongly convex regularizer. The full gradient method costs nnn component gradients per iteration and converges at rate O(1/k)O(1/k)O(1/k), or linearly when the objective is strongly convex (Nesterov, 2004). The stochastic…

19 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Joint Chance Constraints with Second-Order Moment Information I: Worst-Case CVaR Is Exact for Individual Chance Constraints with Concave or Quadratic LossesResearch Paper

A chance constraint asks that an uncertain constraint hold with high probability: a decision is acceptable if the loss L(ξ~)L(\tilde\xi)L(ξ~​) it incurs is nonpositive with probability at least 1−ϵ1-\epsilon1−ϵ. Chance constraints appear in portfolio selection, power-system dispatch, inventory control and engineering design, wherever an occasional violation is tolerable but…

18 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning VII: The Perceptron's Mistakes Exceed the Competitor's Hinge-Power Loss by at Most q²R²‖u‖²/2 + qR‖u‖√(q²R²‖u‖²/4 + L_q)Textbook

An online classifier must predict a label before learning the correct answer. Its errors matter directly: a low numerical loss is useful only if it controls the number of wrong predictions. Chapter 8 of Orabona's textbook examines this connection for linear classification, where a vector of weights produces a score by taking an inner product with the…

8 thms4 active usersReviewed
🏆Completed
Linear algebraOptimization·Captain: mikedeng1

Phase Recovery, MaxCut and Complex Semidefinite Programming 2: If Weak PhaseLift Is C-Stable at x₀, Then PhaseCut Is (2C + 2√2 + 1)-Stable at x₀Research Paper

Phase recovery asks to reconstruct a complex signal x0∈Cpx_0 \in \mathbb{C}^px0​∈Cp from the moduli of linear measurements, b=∣Ax0∣∈Rnb = |Ax_0| \in \mathbb{R}^nb=∣Ax0​∣∈Rn, where A∈Cn×pA \in \mathbb{C}^{n\times p}A∈Cn×p is known. The problem arises in X-ray crystallography, diffraction imaging and microscopy, where detectors record intensities but not phases (Shechtman et al., 2015). Since the map …

10 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning III: Adaptive Online Subgradient Descent on s-Self-Bounded Losses Has Regret 4sD² + 2D√(s Σ_t ℓ_t(u))Textbook

In online convex optimization, a learner selects a point before seeing the current loss. A useful guarantee compares the learner's accumulated loss with that of a single fixed point chosen in hindsight. A step size chosen from a preannounced bound on all future gradients can be wasteful when the realized gradients are small. Chapter 4 of Orabona's online…

7 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningOperations Research·Captain: mikedeng1

Fast Convergence of Regularized Learning in Games I: If Every Player Runs Optimistic FTRL with Step Size 1/(2(n−1)), the Sum of All Players' Regrets Is at Most 2n(n−1)RResearch Paper

When the players of a game repeatedly adjust their strategies with no-regret learning algorithms, the empirical distribution of play converges to a coarse correlated equilibrium, and in smooth games the average social welfare approaches the price-of-anarchy guarantee of the game (Roughgarden 2009). For generic no-regret algorithms such as Hedge the…

9 thms4 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming 4: The Mini-Batch RSAG Method Bounds the Expected Gradient Mapping on Nonconvex Stochastic Composite ProblemsResearch Paper

Training a model by stochastic gradients on a constrained or regularized loss is a stochastic composite problem: a smooth expected loss, observed only through noisy gradients, plus a simple non-smooth term such as a constraint set or an ℓ1\ell_1ℓ1​ penalty. For convex losses, accelerated stochastic approximation methods attain the optimal rates (Lan 2012; Ghadimi…

22 thms4 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

A Modern Introduction to Online Learning IV: Every Deterministic Online Linear Optimization Algorithm Has Regret at Least √2·LD√T/4Textbook

Online learning studies decisions made before their costs are known. An algorithm selects a point, observes a loss, and repeats. Regret compares its accumulated loss with the loss of one fixed point chosen after the sequence is known. Upper bounds show what a particular algorithm can guarantee; a lower bound shows what every algorithm must sometimes suffer.…

6 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming 2: One Aggressive Stepsize Policy Drives the AG Gradient Mapping to Zero on Nonconvex Composite ProblemsResearch Paper

Many problems in statistics, signal processing and machine learning have the form "smooth loss plus simple non-smooth term": a differentiable data-fit term together with a constraint set or a sparsity-inducing penalty such as the ℓ1\ell_1ℓ1​ norm. When the loss is convex, Nesterov's accelerated gradient (AG) method and its proximal variants are known to be…

17 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming 1: The AG Method Converges on Smooth Nonconvex Problems and Attains the Optimal Rate When Ψ Is ConvexResearch Paper

Accelerated gradient (AG) methods go back to Nesterov (1983), who showed that a first-order method with a momentum-like extrapolation reaches an ϵ\epsilonϵ-optimal value of a smooth convex function in O(1/ϵ)O(1/\sqrt\epsilon)O(1/ϵ​) iterations, against O(1/ϵ)O(1/\epsilon)O(1/ϵ) for gradient descent, and that this rate is optimal among first-order methods. Many objectives met in…

18 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 3: The Big-M Relaxation Is at Least as Strong as PR(∞) for M ≤ ½√(λ0/λ2) and at Most as Strong for M ≥ √(λ0/λ2)Research Paper

Best subset selection with a ridge term, the ℓ0ℓ2\ell_0\ell_2ℓ0​ℓ2​-regularized least squares problem

20 thms4 active users
🏆Completed
Optimization·Captain: mikedeng1

Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions IV: Lipschitz ∇g and Strongly Convex f (or Vice Versa) Make Relaxed PRS Contract LinearlyResearch Paper

Peaceman–Rachford splitting separates the minimization of a sum into two proximal computations. That matters when each summand has a tractable proximal map but the sum does not. Douglas–Rachford splitting is its half-relaxed instance, and related iterations appear in the analysis of ADMM. Davis and Yin study how regularity of the two summands changes the…

14 thms4 active usersReviewed
🏆Completed
Functional AnalysisMachine LearningOperations Research+1·Captain: mikedeng1

Kernel Distributionally Robust Optimization: Generalized Duality Theorem and Stochastic Approximation: The Worst-Case Risk over an RKHS Ambiguity Set Equals Its Support-Function DualResearch Paper

Distributionally robust optimization (DRO) chooses a decision θ\thetaθ that minimizes the expected loss under the worst distribution in an ambiguity set K\mathcal KK of plausible distributions, min⁡θsup⁡P∈K∫l(θ,ξ) dP(ξ)\min_\theta\sup_{P\in\mathcal K}\int l(\theta,\xi)\,dP(\xi)minθ​supP∈K​∫l(θ,ξ)dP(ξ). It sits between stochastic optimization, which trusts a single distribution, and worst-case robust…

15 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Bootstrap Robust Prescriptive Analytics 2: The Entropic Robust Nadaraya-Watson Budget Equals inf{α : ν log Σ D·exp((L−α)w/ν) + rν ≤ 0}Research Paper

Data-driven decision making with side information ("prescriptive analytics") chooses a decision zzz after observing a context x=x0x = x_0x=x0​, using a training set of past pairs (x,y)(x, y)(x,y). A common recipe estimates the conditional expected cost E[L(z,y)∣x=x0]\mathbb E[L(z, y) \mid x = x_0]E[L(z,y)∣x=x0​] with a local learning method, such as Nadaraya–Watson kernel regression or nearest neighbours,…

11 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Fast Convergence of Inertial Dynamics and Algorithms with Asymptotic Vanishing Viscosity 3: For α > 3 and Σ k‖g_k‖ < ∞, the Perturbed Inertial Forward-Backward Iterates Converge Weakly to a MinimizerResearch Paper

Many problems in signal processing, statistics and machine learning take the form min⁡xΦ(x)+Ψ(x)\min_x \Phi(x)+\Psi(x)minx​Φ(x)+Ψ(x), where Ψ\PsiΨ is smooth and Φ\PhiΦ is convex but nonsmooth (a norm, the indicator of a constraint set). The forward-backward method takes a gradient step on Ψ\PsiΨ followed by a proximal step on Φ\PhiΦ. Its accelerated, inertial version — FISTA of Beck and…

15 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 1: Subgradient Descent Sequences of Convex KL Functions Obey f(x_k) ≤ ψ(α_k) for a 1-D Worst-Case Prox SequenceResearch Paper

Many first-order methods for convex minimization — the forward–backward (proximal gradient) method, alternating minimization, trust-region and majorization–minimization schemes — produce sequences that decrease the objective by an amount proportional to the squared step and whose step controls a subgradient at the new point. Luo and Tseng (Ann. Oper. Res.…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 2: Randomized Inexact Best Response Reaches an ϵ-NE in Explicitly Bounded Expected SG StepsResearch Paper

Many noncooperative problems in communication networks, power markets and supply chains are stochastic Nash games. Each player minimizes an expected cost that depends on its own decision and on the decisions of its rivals, and the expectation can only be sampled, not evaluated. A natural distributed way to compute an equilibrium is the best-response scheme:…

21 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 3: Asynchronous Inexact Best Response with Delays Reaches an ϵ-NE in Explicitly Bounded SG StepsResearch Paper

Many equilibrium problems in operations research have the form of a stochastic Nash game: each of NNN players minimizes an expected cost that depends on the strategies of the others, and the expectation can only be sampled. The paper's introduction lists applications in generation-capacity and power markets and in communication networks (Abada, de Maere…

19 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 1: Synchronous Inexact Best Response Reaches an ϵ-NE in Explicitly Bounded Projected SG StepsResearch Paper

Many equilibrium problems in operations research, such as networked Cournot competition, power markets and communication networks, are stochastic Nash games: each player minimizes an expected cost fi(xi,x−i)=E[ψi(xi,x−i;ξ)]f_i(x_i,x_{-i})=\mathbb E[\psi_i(x_i,x_{-i};\xi)]fi​(xi​,x−i​)=E[ψi​(xi​,x−i​;ξ)] that depends on the rivals' strategies and on a random vector ξ\xiξ whose law is accessible only through samples. B…

13 thms4 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Online Learning and Online Convex Optimization 2: Normalized Exponentiated Gradient Has Regret at Most log(d)/η + η Σₜ Σᵢ wₜ[i]zₜ[i]² When ηzₜ[i] ≥ −1Research Paper

Learning with expert advice and online linear optimization over the probability simplex are the basic models behind boosting, multiplicative-weights methods for linear programming and zero-sum games, and adversarial bandit algorithms. The algorithm that solves them, under the names Weighted Majority, Hedge and Exponentiated Gradient (EG), keeps a…

6 thms4 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Self-Scaled Barriers and Interior-Point Methods for Convex Programming III: An Affine Potential-Reduction Step Lowers the Potential by at Least 1 − ln 2, and by (‖p‖²/|p|²)(1 − ln 2) When µ ≥ 2νResearch Paper

Potential-reduction methods solve a linear or conic program by driving down a single merit function that combines the objective gap with a barrier for the constraint cone. For linear programming the primal version goes back to Karmarkar (1984) and, without Karmarkar's special problem form, to Gonzaga (1990, Math. Programming 49, 7–21), whose method reduces…

15 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 1: SGD with α-Suffix Averaging Attains E[F(w̄ᵅ_T)] − F(w*) ≤ (2 + 2.5 log(1/(1−α)))G²/(αλT)Research Paper

Stochastic gradient descent (SGD) is the default method for minimizing an expected loss F(w)=Ez[ℓ(w,z)]F(w)=\mathbb E_z[\ell(w,z)]F(w)=Ez​[ℓ(w,z)] when only noisy gradients are available, which is the situation of nearly every large-scale learning problem. When FFF is strongly convex (for instance, any convex loss with an ℓ2\ell_2ℓ2​ regularizer), information-theoretic lower bounds show that no…

10 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets 1: SAG with Step Size 1/(2nL) Converges Linearly at Rate (1 − μ/(8Ln))ᵏResearch Paper

Many problems in machine learning and statistics minimize an average of nnn smooth losses, one per training example: regularized least squares, logistic regression, and other forms of empirical risk minimization. Two classical families of methods attack such finite sums. The full gradient method evaluates all nnn component gradients per iteration and converges…

14 thms4 active usersReviewed
🏆Completed
Linear algebraMachine LearningStatistics·Captain: mikedeng1

Nuclear-Norm Penalization and Optimal Rates for Noisy Low-Rank Matrix Completion 1: If λ ≥ 2‖M‖∞, the Nuclear-Norm Penalized Estimator Obeys Sharp Oracle Inequalities with Leading Constant 1Research Paper

Many estimation problems in statistics and machine learning ask for an unknown matrix observed only through noisy linear measurements: matrix completion (recover a large matrix from a few noisy entries, as in collaborative filtering), multi-task regression, and quantum state tomography. A common structural prior is that the unknown matrix has low rank, and…

19 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Rank-Sparsity Incoherence for Matrix Decomposition: If μ(A⋆)ξ(B⋆) < 1/6, ℓ1 + Nuclear-Norm Minimization Uniquely Recovers the Sparse and Low-Rank ComponentsResearch Paper

Many data matrices are, to a good approximation, the sum of a sparse matrix (few nonzero entries) and a low-rank matrix. In system identification the low-rank part models a system of small order and the sparse part a system with sparse impulse response; in statistics the same structure appears in latent-variable graphical models, where a sparse inverse…

16 thms4 active usersReviewed
PreviousPage 6 of 30Next

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