Artificial Intelligence

Smaller Feasible Sets Proven to Accelerate Nonsmooth Convex Optimization, Settling 2015

Researchers prove p<q geometry accelerates nonsmooth convex optimization to tilde O(1/T) over the l1 ball, settling the COLT 2015 open problem.

StartupHub.ai Staff

By StartupHub.ai Staff, reviewed by Daniel Singer, Editor

3 min read

Smaller Feasible Sets Proven to Accelerate Nonsmooth Convex Optimization, Settling 2015

A decade old question in learning theory has been settled. In The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings, researchers prove that the geometry of the feasible set can accelerate nonsmooth convex optimization when the constraint is smaller than the Lipschitz geometry. For G-Lipschitz convex functions measured in lq norm optimized over an lp ball with p less than q, they show convergence rates that improve strictly over classical bounds and match prior lower bounds up to logarithmic factors. The headline case is striking: convex Euclidean-Lipschitz optimization over the l1 ball now achieves tilde O(1/T) after T first-order queries, answering the nonsmooth version of the COLT open question posed by Guz15b in the affirmative.

The result overturns the long standing intuition that only smoothness or strong convexity could break the slow rates of nonsmooth optimization. By exploiting nondual pairings where the feasible set is more constrained than the objective regularity, the analysis shows that structure alone buys speed, even without smoothing.

From optimal rates to efficient algorithms

The complexity result is existential, but a companion paper makes it constructive. Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates presents efficient algorithms that realize the same tilde O(GR/T^{1/p - (1/q - 1/2)_+}) error for p less than q, closing the gap between what is information theoretically possible and what can be run. Together the two papers resolve the nonsmooth end of the COLT 2015 problem both in theory and in practice.

A third advance points to how this momentum extends beyond pure minimization. Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex-Strongly Concave Minimax Optimization introduces a pure single-loop damped extragradient with fixed parameters and two gradient evaluations per iteration that attains last-iterate linear convergence without inner solves or restarts. For practitioners who train, evaluate and ship models via minimax formulations, from robust training to game theoretic alignment, the message is consistent: careful geometry and stable dynamics can deliver optimal rates with simpler, deployable loops.

Why it matters for model training

For teams training large models under norm constraints, sparsity inducing l1 balls or other small feasible sets are not just regularization choices but potential accelerators. The new rates suggest that choosing constraint geometry deliberately can reduce oracle complexity, while the accompanying efficient methods and single-loop minimax results show how to capture those gains without complex schedules. It is a rare case where theory changes the default for how to set up and solve the optimization that underpins modern machine learning.

Get the free daily brief every morning

Every morning the day's AI news, new AI startups and new funding rounds. Free and takes a few minutes to read, unsubscribe at any time.

Join 64,000 other subscribers.

StartupHub.ai StaffDaniel SingerWritten by StartupHub.ai Staff, Editorial teamReviewed by Daniel Singer, EditorAbout

StartupHub.ai Staff, Editorial team

The staff writers of StartupHub.ai, ranging from investment analysts to avid AI tool users, early adopters and critical enthusiasts. Backgrounds span engineering, business and the arts. We hold every piece to rigorous standards of research and review.

Daniel Singer, Editor

Daniel Singer is an AI expert who has been writing about, covering and building AI technology since 2018.

More from Daniel Singer

Test your Agent Readiness now

Paste your website. How well ChatGPT, Claude and the other agents can read and use a site, in about a minute.

Watch

The videos behind the news, one flip at a time

The feed mixes the videos from our articles with startup demos and you flip through them like TV channels for free with no signup.